Ph.D Thesis

Ph.D StudentBarkan Elad Pinhas
SubjectCryptanalysis of Ciphers and Protocols
DepartmentDepartment of Computer Science
Supervisor PROF. Eli Biham


Cryptography is a major enabler of the modern way of life. It provides secure electronic commerce, digital signatures, secure protocols, secure satellite set-top boxes, secure phone calls, electronic voting, and much more. Cryptanalysis verifies the promises of the cryptography, e.g., verifies that cryptographic algorithms and protocols are indeed secure.

This thesis contains four independent contributions in the field of cryptanalysis. In the first contribution, we consider the cipher Rijndael, which was recently chosen for the Advanced Encryption Standard (AES). We present the concept of dual ciphers, and show several applications for them, including insight for cryptanalysis, protection against side-channel attacks, and finding faster implementations of existing ciphers. As a result of our work, researchers used our dual ciphers to construct a very efficient implementation of Rijndael in hardware.

In the second contribution, we consider the most deployed cellular system - GSM. We present a very practical and quick  ciphertext-only attack on GSM 's "weaker" cipher A5/2, as well as a slower attack on the stronger cipher A5/1. We also describe fast active attacks that exploit flaws in the GSM protocol to attack strong GSM ciphers using weaker ciphers. A similar attack is applicable to GPRS (mobile internet on GSM). We provided early warnings of these attacks to the GSM authorities and they are working to correct the flaws.

Our third contribution is a new attack that we present on stream ciphers that use irregularly-clocked Linear Feedback Shift Registers (LFSRs). The attack uses a new method called conditional estimators to overcome some of the cryptanalytic difficulties caused by the irregular clocking. We apply the attack to GSM's A5/1, and achieve the best known-plaintext attack on A5/1 so far.

Our fourth contribution relates to generic attacks on ciphers, in particular, we prove bounds on cryptanalytic time/memory tradeoffs for the inversion of a random function f. In our work, we set a general model, which includes all the existing cryptanalytic time/memory tradeoffs schemes as special cases. Through a rigorous combinatorial analysis, we prove an upper bound on the number of images y=f(x) for which f can be inverted using a tradeoff scheme. With some additional natural assumptions on the algorithm that inverts f, we prove a tight lower bound on its worst-case time complexity. We also describe new variants of existing schemes, including a method that can improve the time complexity of the inversion algorithm by a small factor.