Ph.D Thesis | |

Ph.D Student | Carmeli Yaniv |
---|---|

Subject | On Bugs and Ciphers: New Techniques in Cryptanalysis |

Department | Department of Computer Science |

Supervisor | PROF. Eli Biham |

Full Thesis text |

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 2^{14} 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.