I find this extremely interesting - one of the threats that well known cryptographic keys face is "angry mob cryptanalysis" - a bunch of people get together on the Internet and crack your key. If there is enough widespread interest in cracking your key that the masses have enough computing power between them to crack it, the mob wins and your private key becomes a matter of public knowledge.

This is a risk for code signing keys because they make it hard for people to do what they want their their computers. While its interesting on paper I'm not aware that it ever happened in practice until today. All of the distributed computing efforts to crack keys that I'm aware of have focused on "public challenges" that are intended to be cracked, or were otherwise organized as security demonstrations rather than as real attacks. Maybe someone on MemeStreams will recall an older example of this that I'm forgetting.

(I'm talking about cases where cracking the cryptography was a means to an end and not the end itself. The hash collision attack from December was extremely cool but it doesn't qualify, because they were breaking the security of the system for the sole purpose of demonstrating that it could be done - rather than because they wanted to get at the thing that the security protects.**)

The ever-mysterious Benjamin Moody posted a cryptic message on the United-TI forum yesterday. In it, he listed the factorization of the 512-bit RSA modulus used by TI's OS signing key for the 83+ (the "0004 key").

With this achievement... Third party operating systems can thus be loaded on any 83+ calculators... Complete programming freedom has finally been achieved on the TI-83 Plus!.

In this case the key is old, and due to the nature of the platform in question a relatively small, 512 bit key was chosen. The guy was able to crack the key by himself without organizing a mob. He posted some details about his cracking effort:

- The factorization took, in total, about 1745 hours, or a bit less than 73 days, of computation. (I've actually been working on this since early March; I had a couple of false starts and haven't been able to run the software continously.)
- My CPU, for reference, is a dual-core Athlon64 at 1900 MHz.
- The sieving database was 4.9 gigabytes and contained just over 51 million relations.
- During the "filtering" phase, Msieve was using about 2.5 gigabytes of RAM.
- The final processing involved finding the null space of a 5.4 million x 5.4 million matrix.

However, it appears that a mob has formed to target some of the other keys on the TI:

A distributed computing project has been set up. Information about how to join the effort to crack the OS keys for the remaining TI models can be found here.

Lawsuits are certainly a tactic that could be used to counter the mob - to go after big keys you've got to organize the effort publicly and that involves setting up a coordinating center that could be sued out of existence. I have no idea whether Texas Instruments cares enough to do so in this case, but one way to counter that risk would be to organize the effort from behind Tor.

I wonder - do browsers currently trust any 512 bit certificate authority keys?

(** The MD5 cracking team also doesn't fit the definition of an "angry mob." While they went after a real, deployed cryptosystem, it was a small group of people who amassed a lot of computing resources privately. Private groups have been cracking real ciphers in the shadows for years. What makes the TI case really unique in my view is that its a real cipher and the call to crack it has been made to the general public - anyone can participate.)

TI-83 Plus OS Signing Key Cracked - ticalc.org