Forum discussion about cracking the TI-83+ key | Hacker News Reader

Forum discussion about cracking the TI-83+ key

unitedti.org

23 pointsedw5198 comments

I hope we see articles on Hacker News when the operating systems and homebrew apps start coming out.

Being able to do more complex stuff on a TI-83 would certainly allow beginning calculus students to cheat on tests, since most classes allow nothing higher than a TI-83 under the assumption that 83's won't do, for example, step-by-step integration.

Some previous discussion on cracking the TI:

http://news.ycombinator.com/item?id=767419

Can anyone briefly explain how factoring a large number is used to crack the TI? I know they needed to figure out what key to sign a new OS with, but is it symmetric or asymmetric? Also, what are the inputs to the problem and how do you know when it's solved/cracked? Thanks.

I'd guess that it's an asymmetric algorithm that uses some kind of public-key signing of the code:

http://en.wikipedia.org/wiki/Public-key_cryptography

The 'input' (the public key) of the problem can probably be found in the firmware of the device (it's probably too large to have been bruteforced). To be able to sign code so that the device will run it, you need the private key, which is one of the factors of the public key. So the guy used a program to factor the public key to get the private key so that he could sign the code (whatever code he wants) with it and get the calculator to run it.

The two prime numbers are multiplied to generate a larger number for use in the RSA algorithm. It is a hard problem to factor a large number and that is why it is used in the RSA algorithm. http://en.wikipedia.org/wiki/RSA . The inputs to the problem are the primes and you know when it is solved when you have the two numbers multiply to give you the larger number.

The calculator has an RSA public key in it (exponent e, modulus n). TI keeps secret an RSA private key (exponent d, same modulus n). The private key is used to sign the OS and the calculator verifies the signature before running the OS.

The modulus is composed of two primes, p and q. Factoring n into p and q is sufficient to regenerate the private exponent d. Thus, the hackers can now sign their own OS and have it loaded on stock calculators.

I suspect the 512-bit RSA key was used in order for the Z80 to verify a signature in a short period of time. It's possible they even use a small public exponent (e=3), which could enable simpler/quicker attacks than factoring.

TI could have solved this in a number of ways. Partitioning the key space so there isn't one global key (like broadcast encryption) is one solution. Another would be to use ECDSA with a fast curve.

From the forum discussion, someone mentioned that a Core2Quad extreme would need about 2 months (running 24/7) to factor the key. I don't know if there's anyone out there that's written a CUDA version, but a GTX295 should be able to run at at least 10x the speed of the CPU, if not something like 20-30x; that means if there are any other keys that need cracking (like for the TI-86 firmware), it could be done in a much shorter amount of time (probably less than a day for someone with a multi-GPU rig).

FTA article: it took "1745 hours, or a bit less than 73 days" on a 1900 MHz Athlon 64.

Also:

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

Reply on news.ycombinator.com