Financial Cryptography

How to crack RSA

Adi Shamir is currently circulating a research note that looks like, on the face of it, a stunning piece of research. In short: how a powerful enemy can routinely and trivially crack RSA, and other public key algorithms. If found valid, this will again shake up the dusty world of cryptography in a way generally only seen every 5-10 years. The NYT report

Research Announcement: Microprocessor Bugs Can Be Security Disasters

Adi Shamir
Computer Science Department
The Weizmann Institute of Science
Israel

With the increasing word size and sophisticated optimizations of multiplication units in modern microprocessors, it becomes increasingly likely that they contain some undetected bugs. This was demonstrated by the accidental discovery of the obscure Pentium division bug in the mid 1990's, and by the recent discovery of a multiplication bug in the Microsoft Excel program. In this note we show that if some intelligence organization discovers (or secretly plants) even one pair of integers a and b whose product is computed incorrectly (even in a single low order bit) by a popular microprocessor, then ANY key in ANY RSA-based security program running on ANY one of the millions of PC's that contain this microprocessor can be trivially broken with a single chosen message. A similar attack can be applied to any security scheme based on discrete logs modulo a prime, and to any security scheme based on elliptic curves (in which we can also exploit division bugs), and thus almost all the presently deployed public key schemes will become vulnerable to such an attack.

Let's work it through: if an agency can pervert a maths processor in your standard CPU chip, it can also craft a single message that when processed (encrypted, signed, etc) will result in revealing to the attacker the entire key.

Assumption 1: an agency can pervert the modern CPUs. Such commodity hardware is mostly all created in American design studios, and we know that the chip manufacturers work closely with US intelligence agencies for special instructions, special spaces inside the chip, and no doubt other things. Conclusion: they are all ready working at that level so the only reasons that they haven't done it is that they chose not to, or they didn't think of it first.

Assumption 2: a message is processed, and the results are returned. Now, this means providing something to decrypt or encrypt, and seeing the both plaintext and ciphertext, *OR* presenting something to sign, and looking at the signature. The latter looks much more likely, as there is a basis for seeing both before and after texts (although, normally the signer can fudge the issue by firstly adding some random junk, and secondly hashing the message). Conclusion: it's not entirely clear what the vector of attack is here.

Either way, this is pretty big. What to do about it? Nothing today, as one thing is to bear in mind the caveat: until the cryptography community can comment on this, it is difficult for us non-cryptographers to really understand the scope and breadth. Indeed, the man I would have asked to explain this result is Adi Shamir himself, as he has an almost unique ability in the cryptography world to separate the interesting from the theoretical.

Meanwhile I suppose we start thinking of software designs for RSA. This would be like using a Virtual Machine, as in Java, Perl, Python, etc, where the software insulates against a rogue CPU's attempt to follow and pervert the higher layer semantics. Alternatively, we may now have found a reason to encourage open design cryptographic hardware.

Posted by iang at November 19, 2007 01:45 PM | TrackBack