Ph.D Thesis

Ph.D StudentCarmeli Yaniv
SubjectOn Bugs and Ciphers: New Techniques in Cryptanalysis
DepartmentDepartment of Computer Science
Supervisor PROF. Eli Biham
Full Thesis textFull thesis text - English Version


This research thesis presents three independent contributions to cryptanalysis.

The first contribution is Bug Attacks, a new type of side-channel attack that takes advantages of bugs in hardware or software. The best known example of a bug in hardware 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, elliptic curve cryptography, 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. Bugs may also be planted by tampering with otherwise bug-free hardware. Recent documents leaked by Edward Sonwden show that this is a method which is used by the US against intelligence targets.

The second contribution is an efficient algorithm for the retrieval of the RC4 secret key, given an internal state. The algorithm we present is several orders of magnitude faster than previously published algorithms. In the case of a 40-bit key, it takes only about 0.02 seconds to retrieve the key, with success probability of 86.4%. Even in cases where our algorithm cannot retrieve the entire key, it can retrieve partial information about the key. The key can also be retrieved if some of the bytes of the initial permutation are incorrect or missing.

The third contribution is an improvement to the linear cryptanalysis of ciphers that use addition operations, which we demonstrate on the block cipher FEAL-8X. Since its introduction 27 years ago FEAL played a key role in the development of many cryptanalytic techniques, including differential and linear cryptanalysis. For its 25th anniversary Mitsuru Matsui announced a challenge for an improved known plaintext attack on FEAL-8X. We describe our attack as part of this challenge and introduce improvements to linear cryptanalysis that allow us to recover the key given 214 known plaintexts in about~14 hours of computation, and led us to win the challenge. An especially interesting improvement considers the approximation of addition-based S-boxes by partitioning into several sets in a way that amplifies the bias, and therefore allows for a reduction in the number of required known plaintexts as well as saving computation time.