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.
Improve this question
6
  • 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 Retrocomputing Meta, or in Retrocomputing Chat. Comments continuing discussion may be removed.
    – Chenmunka ♦
    Nov 18 at 22:08
  • 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 at 2:45
  • 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 at 1:00
  • @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 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 at 10:04

3 Answers 3

Reset to default
49

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).

Improve this answer
12
  • 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 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 at 22:54
  • 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 at 21:01
  • 2
    @zomega: for RSA, the key length (more specifically, the size of the modulus) is the signature length
    – poncho
    Nov 18 at 21:40
  • 3
    The exact curve is listed in 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 at 1:12
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.

Improve this answer
11
  • 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 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 at 14:14
  • 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 at 17:02
  • 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 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 at 22:19
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.

Improve this answer
1
  • 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 at 11:19

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .