18

After 20 years the telephone activation algorithm of Windows XP has been cracked. Please understand the algorithm itself has been cracked and not the activation program.

Microsoft had designed its own algorithm which is based on a lot of math. When they did that they had to spend a lot of money on the development of this algorithm and they had the risk that it won't be safe.

Because it has been cracked, it's shown that the algorithm is not safe. I'm also quite sure the reason it's possible to crack it today is not because of computers being faster. Because already in 2004 there was an Intel Prescott 3,8GHz CPU for Desktop PCs.

My question is why didn't Microsoft simply use RSA or another proven algorithm?

For those who don't know I think the activation process works like this:

  1. The client generates an activation ID and sends it to the activation server (over a phone call).
  2. The server signs it using the private key.
  3. The client verifies the signature using the public key.
Glorfindel
  • 407
  • 1
  • 3
  • 16
zomega
  • 5,362
  • 4
  • 25
  • 52
  • Comments have been moved to chat; please do not continue the discussion here. Before posting a comment below this one, please review the purposes of comments. Comments that do not request clarification or suggest improvements usually belong as an answer, on [meta], or in [chat]. Comments continuing discussion may be removed. – Chenmunka Nov 18 '23 at 22:08
  • 4
    "Because already in 2004 there was an Intel Prescott 3,8GHz CPU for Desktop PCs." Careful, you can't compare CPU performance between CPU families like that. A 3.8 Ghz Pentium 4 is not equivalent to a modern 3.8 Ghz CPU; it's quite slow. For example, a quite low end AMD Ryzen 3 4100 is about 30x faster despite both having similar clock speeds and power usage. Even with 1 core the Ryzen is 4x faster. Computers are quite a bit faster today than 20 years ago. – Schwern Nov 20 '23 at 01:00
  • 1
    You should watch Dave's Garage's video on Windows Product Activation. He gives a lot of information about the limitations that the telephone activation process has to deal with and the decisions that were made when implementing it. – normanr Nov 19 '23 at 02:45
  • @Schwern: Can RSA signature checking be usefully multi-threaded? I think the 4x number is more reasonable, since for this application it's only latency for 1 signature that matters, not throughput. But maybe another factor of 2 to 4 to account for 64-bit code working in 64-bit chunks on BigInt, getting about 4x the amount of work done from a 64x64 => 128-bit multiply as from a 32x32 => 64-bit multiply. (Even on an x86-64 Nocona P4, Win XP would be in 32-bit legacy mode). Also that P4 had bad latency for adc and imul, like 6c latency and multiple uops for adc r,r, worse in Prescott. – Peter Cordes Nov 20 '23 at 10:00
  • 1
    So P4 specifically was especially slow at BigInt math, compared to AMD at the time as well as compared to modern Intel and AMD. But still, a 500 MHz PIII is totally fine at RSA for SSH logins, as I commented under an answer. P4 sucks, but the high clock speeds should make up the difference vs. a PIII. – Peter Cordes Nov 20 '23 at 10:04
  • From a link-only answer: https://youtu.be/FpKNFCFABp0 - video from Dave Plummer, who implemented the Windows product activation when he worked at MS. titled: "Blame Me: The INSIDER Secrets of Windows Product Activation!". Apparently has quite a bit of info about design considerations around the limitations of telephone activation. – Peter Cordes Nov 21 '23 at 23:10

3 Answers3

48

My question is why didn't Microsoft simply use RSA or another proven algorithm?

Because they thought it was important to minimize the signature. That is, in the use case:

For those who don't know I think the activation process works like this:

The client generates an activation ID and sends it to the activation server (over a phone call).

The server signs it using the private key.

The client verifies the signature using the public key.

If the client needs to manually enter the signature into the computer (encoded in, say, base64), it is important to minimize the number of symbols the human would need to type in. If we were to use, say, RSA-1024 (this was 20 years ago, when RSA-1024 would have been reasonable), then the signature would be circa 170 symbols long - far too many to expect the user to type in precisely. Even ECDSA based on a 128 bit curve would have been 43 symbols - arguably too many. Hence, Microsoft designed their own method.

It turned out to be not quite as strong as they originally expected, and that it would have been secure with a larger curve (but a larger curve would have given them larger signatures, and that was precisely what they were trying to avoid).

poncho
  • 581
  • 3
  • 3
  • 21
    Length of the generated key being manually entered is a good consideration when deciding on an encryption algorithm. You mention it not being as strong as they expected, but without any evidence of what their expectations were... it's likely it did meet expectations. Windows XP is 20+ years old. The blow to Microsoft of lost sales of Windows XP today, because the user decided to crack the activation is probably trivial. Spending more time and money to make the algorithm last more years would see little if any return. – David Jacobsen Nov 17 '23 at 21:59
  • 3
    @DavidJacobsen: "You mention it not being as strong as they expected, but without any evidence of what their expectations were" - some background. They are using a pairing friendly elliptic curve; you can break it by solving the discrete log either in the curve group or in the extension field. At the time, the extension field was expected to be about as strong as a same sized prime field. It has since been discovered that the extension field is somewhat easier to break (and I'm sure that's what the hackers took advantage of). So, we know it is weaker than was expected at the time – poncho Nov 17 '23 at 22:54
  • Isn't the signature size of RSA adjustable? – zomega Nov 18 '23 at 14:56
  • 3
    @zomega, yes, but it wouldn't help. In 1999, RSA-512 (86 characters, still much too long for manual entry) had been broken. RSA-192 (a reasonable 32 characters) is so weak it wasn't included in the original RSA factoring challenge – Mark Nov 18 '23 at 21:01
  • @Mark That's the key length not the signature length but I'm not sure. – zomega Nov 18 '23 at 21:30
  • 2
    @zomega: for RSA, the key length (more specifically, the size of the modulus) is the signature length – poncho Nov 18 '23 at 21:40
  • 3
    The exact curve is listed in https://github.com/Endermanch/XPKeygen/blob/main/README.md in the screenshot near the end. It is NOT a pairing-friendly curve. The scheme was broken purely with a Pollard rho solver. – djao Nov 19 '23 at 01:12
  • When Windows XP was developed, the main CPU in use was the Pentium III, which as you know was not very fast. Another thing this resulted in was that one of the ten things that it checks to see changed to trigger a reactivation is the unique Processor Serial Number of the CPU, which was a Pentium III-specific feature that was removed due to privacy concerns. – gparyani Nov 19 '23 at 19:17
  • 2
    @gparyani: I doubt CPU speed was a big limitation. Activation for most users is a once-ever thing, or at least pretty infrequent when changing hardware. A few seconds of computation is fine in that context, only adding a small amount of time to the whole process of phoning and manually entering numbers on phone number pad. Also, PIII is not bad at all. Clock speeds weren't high (like 300 to 500 MHz in early models), but its integer multiplier was about as good as modern CPUs, with 1/clock throughput and 4 cycle latency (https://agner.org/optimize/). But only 32x32 => 64-bits wide. – Peter Cordes Nov 19 '23 at 22:13
  • 2
    @gparyani: ssh logins from an old 500MHz Katmai PIII take under a second to verify RSA host keys with lengths like 2048 bit, and to authenticate itself to another computer using a 1024-bit RSA private key. (With OpenSSH from an ancient Debian version that's probably insecure by now). So unless you're worried about the server load of many users phoning in with RSA keys, RSA was zero problem for client-side CPU speed on PIII clients. Even P5 Pentium was probably fine, IIRC from using ssh back in the day on my 200MHZ Pentium-MMX. – Peter Cordes Nov 19 '23 at 22:27
  • @djao: Note the repository is for a product key generator, which is a string of letters and digits that’s found somewhere in the box Windows ships in, and entered when installing Windows. The question is about phone activation, which is a challenge-response thing (user calls a number and types in/tells digits generated by Windows and receives a set of digits that will make Windows happy and work beyond the 30 day trial). – Chris Warrick Nov 20 '23 at 21:33
  • @chris I am aware of the difference. Simply based on the timing, it's virtually impossible that the Windows XP phone activation functionality uses pairing based cryptography. Windows XP was released in October 2001 and BLS signatures were published in December 2001. – djao Nov 21 '23 at 00:15
17

Opinion:

RSA received a patent for the algorithm in 1977. Microsoft was unlikely to use someone else's patented algorithm.

Though the RSA patent became public-domain in September 2000, and Windows XP was not released to manufacturing until August 2001, it was probable that the activation algorithm had been decided on (and activation servers implemented) long before that date.

dave
  • 35,301
  • 3
  • 80
  • 160
  • Why shouldn't MS licence? They did so for many other items - not at least QDOS :)) – Raffzahn Nov 17 '23 at 12:59
  • 1
    I assume they wouldn't if they didn't have to. – dave Nov 17 '23 at 13:03
  • 2
    (Don't get me wrong, I'm not criticising your answer as it's clearly marked as opinion, just trying to understand its base) Sure, but then again, they are sill not an ideological caballe (even thru we love to call it that), but a business. Developing a new algorithm doesn't come for free, while at the same time MS does have a considerable power in negotiatons. – Raffzahn Nov 17 '23 at 13:09
  • 10
    They commissioned Arial et al to avoid paying a per-box licence for Helvetica, etc; possibly RSA terms weren’t acceptable even if licensing in general was okay? Again, random guesses, from thin air. – Tommy Nov 17 '23 at 13:17
  • 6
    @Tommy Then again that font part was right at a time when font factories still thought of large printers as their customers, not every PC on the planet. But yeah, very good point. Also showing why proving Why-nots is a murky area. – Raffzahn Nov 17 '23 at 14:14
  • 1
    Maybe there was some element of NIH involved in the activation decision. – dave Nov 17 '23 at 15:41
  • 5
    Also, the US used to have strict limitations on the export of cryptography. By the year 2000, the rules were relaxed to finally allow the export of DES or RSA without any "key recovery" backdoors, but maybe Microsoft had already implemented its algorithm by then. – dan04 Nov 17 '23 at 17:02
  • 1
    The counterexample to this answer is that since Windows NT 4 (1996), Windows ships with cryptographic libraries for things like SSL/TLS. They would already have licensed the algorithm. – user71659 Nov 17 '23 at 20:22
  • 12
    "RSA received a patent ... in 1977 ...became public-domain in September 2000" - Interesting to see how usage of RSA increased so much after the patent expired. You wonder what other good technologies barely see any usage due to patent encumbrance... – marcelm Nov 17 '23 at 20:40
  • 5
    @dan04: the ITAR restrictions explicitly did not limit strength of algorithms or implementations that only did signature or authentication, not encryption; that's why the contemporaneous SSL 'export' ciphersuites could use RSA(S)-1024 or more or DSA-1024 for auth but only RSA(E)-512 or DHE-512 for key-exchange (and DES-40 or RC4-40 for data encryption, but SHA1 with (then!) 80-bit generic strength for HMAC). – dave_thompson_085 Nov 17 '23 at 22:19
  • 1
    I'd be very surprised if MS wasn't already paying for a very broad license for RSA at the time Win XP was being designed and then shipped. RSA signatures are just too big. – President James K. Polk Nov 18 '23 at 22:51
14

After 20 years

You could argue that the encryption was plenty strong enough. Support for XP ended nearly 15 years ago, the encryption lasted 15 years longer than the OS.

All security systems have to balance security and usability. They could have made it more secure but that'd likely increase the size of the activation code, as this was designed to be passed over the phone a longer key would be impractical.

XP has very limited value to Microsoft now (if any) so the fact that the activation has been broken really doesn't mean much to them.

Alan Birtles
  • 241
  • 3
  • 7
    Actually, XP was widely used all the way to the end of the extended support period, which was in April 2014, which is significantly less than 15 years ago. But your point still stands. – TooTea Nov 20 '23 at 11:19