Technical Report PHD-2006-02

TR#:PHD-2006-02
Class:PHD
Title: Techniques for Cryptanalysis of Block Ciphers
Authors: Orr Dunkelman
Supervisors: Eli Biham
PDFNot Available
Abstract: Block ciphers play an important role in many cryptographic and security protocols. They are used to conceal confidential information, not only during its broadcast over a public channel, but also when it is stored (e.g., on the hard disk of a personal computer). The security of these protocols and storing procedures relies on the security of the underlying block ciphers against various attacks. The field of cryptanalysis of block ciphers focuses on assessing the security of block ciphers. The process of assessment of the security of a given block cipher is mostly concerned with applying various cryptanalytic techniques to the block cipher. Each of these techniques has a different attack model and aims at exploiting different design flaws.

Many cryptanalytic techniques were published in the last few decades. The first group of attacks consists of meet-in-the-middle attacks and its variants. These attacks rely on bad avalanche properties of the cipher.

Another approach for the cryptanalysis of block ciphers is the study of statistical properties. This approach aims at finding statistical properties that distinguish between a given cipher (or a reduced-round version of it) and a random permutation. Such properties include differentials (the propagation of differences through encryption) or linear approximations (finding that there is some correlation between the plaintexts and the ciphertexts).

Some attacks, like the SQUARE attack, use sets of plaintexts such that the corresponding ciphertext sets have specific and easy to identify properties. Such properties are typically that for a given ciphertext byte all possible values are found in the set of ciphertexts or that the XOR of some bit mask in all ciphertexts is known.

A recent new approach is the algebraic attack. In this attack the cipher is treated as an overdefined set of low degree equations. Then, the attacker tries to solve this set. Despite the fact that this approach succeeds if sufficiently many equations are present, the exact time complexity of such attacks is unknown, as the techniques used to handle the set of equations are heuristic in nature.

This thesis presents new cryptanalytic techniques that can be used to assess the security of block ciphers. The techniques are: the rectangle attack, the enhanced differential-linear attack, the differential-bilinear attack, the higher-order differential-linear attack, and the differential-bilinear boomerang attack (the differential-bilinear attack is actually four different attacks, whose most general version is the differential-bilinear attack). We also introduce the related-key boomerang and the related-key rectangle attacks.

We apply these newly developed techniques to various block ciphers. For example, our related-key rectangle attack on AES-192 is the first theoretical attack on 9-round AES-192 faster than exhaustive key search. We also present the first attack on the full 3GPP block cipher KASUMI. We apply our proposed techniques to other ciphers as well, such as DES, Serpent, IDEA, and COCONUT98.

In the appendix we also suggest a criterion that measures how far is a given cipher from a randomly chosen permutation. Our criterion is closely related to the difference distribution table of the cipher. This criterion can be used in distinguishing attacks and in key recovery attacks. We present several examples of block ciphers that cannot be attacked using other techniques but can be distinguished and attacked using our criterion. For example, a block cipher that is susceptible to a differential attack, when adding decorrelation module at the beginning and at the end of the cipher becomes secure against the differential attack. However, attacks that are based on our proposed criterion can still succeed in attacking the cipher.

Finally, we suggest an attack on the GSM stream cipher A5/1 in another appendix. Our attack is a variant of the divide-and-conquer approach. It finds the internal state of the cipher given few minutes of conversation (i.e., known key stream). Since its first publication in 2000, this attack was implemented and verified by an independent research.

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 (http://www.cs.technion.ac.il/users/wwwb/cgi-bin/tr-info.cgi/2006/PHD/PHD-2006-02), rather than to the URL of the PDF or PS 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