The Taub Faculty of Computer Science Events and Talks

In this talk I will present a cryptanalytic attack, which we call Bug Attacks. This attack utilizes bugs in the hardware implementation of computer instructions. The best known example of such a bug is the Intel division bug, which resulted in slightly inaccurate results for extremely rare inputs. Whereas in most applications such bugs can be viewed as a minor nuisance, we show that in the case of RSA (even when protected by OAEP), Pohlig-Hellman and several other schemes such bugs can be a security disaster: Decrypting ciphertexts on any computer which multiplies even one pair of numbers incorrectly can lead to full leakage of the secret key, sometimes with a single well-chosen ciphertext. With the increasing word size and the sophisticated optimizations of multiplication units in modern microprocessors it becomes increasingly likely that they contain undetected bugs. This was demonstrated by the accidental discovery of the Pentium division bug in the mid 1990's, by the discovery of a bug in the Intel Core 2 memory management unit (which allows memory corruptions outside the permitted range of writing for a process), and many more. Bug attacks are not restricted only to bugs that are discovered by chance - our techniques can be used also by an attacker (e.g., some intelligence organization) that secretly plants even one pair of single-word integers A and B whose product is computed incorrectly. Alternatively, the attacker can inject the multiplication error through a third-party software packages for cryptographic or mathematical computations. In the talk I will describe bug attacks against several implementations of RSA and Pohlig-Hellman, and discuss possible countermeasures that can be taken to protect from them. Joint work with Eli Biham and Adi Shamir.