Technical Report PHD-2006-04

Title: Cryptanalysis of Ciphers and Protocols
Authors: Elad Pinhas Barkan
Supervisors: Eli Biham
Abstract: 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. For example, we are interested in verifying that encryption algorithms are indeed secure, as well as the protocols in which they are embedded. In many cases, it is better having a system without any security claims than having a poorly designed cipher in a badly designed system, as the user of a system with no security is aware of the fact that it is insecure, while users of a compromised communications system might believe that the system is secure, and trust it with their secrets.

This thesis contains four independent contributions in the field of cryptanalysis. In the first contribution we consider the cipher Rijndael, which was recently chosen as the United-States' Advanced Encryption Standard (AES). Like many other ciphers, Rijndael has constant values that are used during the encryption process. We ask what happens when we replace all the constant in the cipher. We show that such replacements can create many dual ciphers which are isomorphic to the original one. Dual ciphers have several possible applications, including insight for cryptanalysis, protection against side-channel attacks (such as measuring the power used during the encryption process to recover the encryption key), 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 --- the Global System for Mobile communications (GSM). We present a very practical ciphertext-only attack (an attack that can recover the encryption key given just some encrypted information) on encrypted GSM communications that works whenever the "weaker" cipher A5/2 is used. The attack takes less than a second to complete on a personal computer. Then, we adapt the attack to a more complicated and slower passive attack on the stronger cipher A5/1. We also describe a fast attack on networks using A5/1. This attack is an active attack, i.e., the attacker is required to transmit. We stress that the attack is on the protocol of GSM, and it works whenever the mobile phone supports the weaker cipher A5/2. This attack can also be used to attack the newest and strongest GSM cipher A5/3, by breaking A5/1 or A5/2, and can be used to attack GPRS (an internet-like service on GSM) in a similar way. We have provided early warnings to the GSM authorities about these attacks, and the authorities are working to correct the flaws.

Our third contribution is a new attack that we present on stream ciphers that use Linear Feedback Shift Registers (LFSRs) in a certain way that is called irregular clocking. The attack uses a new method called conditional estimators that can overcome some of the cryptanalytic difficulties induced 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. With 1500--2000 frames of known keystream, i.e., about 6.9--9.2 seconds of communication, the attack can find the encryption key within a couple of tens of seconds to a couple of minutes of computation on a personal computer.

Our fourth contribution relates to generic attacks on ciphers, in particular, we prove bounds on cryptanalytic time/memory tradeoffs. In generic attacks, the cipher is treated as a black-box function $f: \{0,1,\ldots,N\} \mapsto \{0,1,\ldots,N\}$, and the goal of the attack is to invert $f$ on a value $y$, i.e., to find an $x$ such that $f(x)=y$. Two extreme generic attacks are the exhaustive search attack which goes over all the values $x$ in search for a pre-image of $y$, and the table lookup attack which uses a huge table that stores for each image $y$ a preimage $x$. In 1980, Hellman presented the best known cryptanalytic time/memory tradeoff, which can be seen as a compromise between exhaustive search and table lookup. In a time/memory tradeoff, the attacker uses several tables which together consume significantly less memory compared to the table needed for table lookup, but the attack also works in a significantly shorter time than exhaustive search. Since Hellman's discovery, many improvements to time/memory tradeoff followed, including a new scheme from 2003, called the Rainbow scheme, which claims to save a factor two in the worst-case time complexity. In our work, we set a general model for cryptanalytic time/memory tradeoffs, which includes all the existing schemes as special cases. The model is based on a new notion of stateful random graphs, in which the evolution of paths depends on a hidden state. 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, and derive from it a lower bound on the number of hidden states. These bounds hold with an overwhelming probability over the random choice of the function $f$. With some additional natural assumptions on the behavior of the online phase of the algorithm, we prove a tight lower bound on its worst-case time complexity $T=\Omega(N^2/(M^2 \ln N))$, where $M$ is the memory complexity. We describe new variants of existing schemes, including a method that can improve the time complexity of the online phase (by a small factor) by performing deeper analysis during the preprocessing phase.

CopyrightThe above paper is copyright by the Technion, Author(s), or others. Please contact the author(s) for more information

Remark: Any link to this technical report should be to this page (, rather than to the URL of the PDF files directly. The latter URLs may change without notice.

To the list of the PHD technical reports of 2006
To the main CS technical reports page

Computer science department, Technion