Year

2012

Degree Name

Doctor of Philosophy

Department

School of Computer Science and Software Engineering

Abstract

The Advanced Encryption Standard (AES) is a symmetric-key encryption standard adopted by the U.S. government in 2000. It is one of the most popular algorithms used in symmetric key cryptography nowadays. In this thesis, we study the internal structure of the AES algorithm and two AES-based cryptographic primitives: the ALPHA-MAC message authentication code and the LEX stream cipher. In the analysis of the AES internal structure, we focus on two areas: the internal algebraic properties and the key schedule of the AES algorithm. This thesis makes the following four contributions.

First, we ask the question what happens if we change the values of some bytes of some intermediate results during an AES encryption. We aim to investigate the impact of these changes on the output of the encryption, and study the feasibility of cancelling out the effects of such changes. By using the structural features of the AES round transformation, we propose a five-round algebraic property which shows that if one carries out four extra exclusive or operations on four fixed-position bytes in some round, five consecutive rounds of such operations will cancel out all changes made to the intermediate results and, consequently, the final output of the encryption will not be affected by these changes.

Second, we use the proposed five-round algebraic property of the AES cipher to study the construction of the ALPHA-MAC. We introduce two methods: the Backwards-aNd-Backwards search algorithm and the Backwards-aNd-Forwards search algorithm. By combining these two methods, one can find second preimages of the ALPHA-MAC, given an intermediate value. In addition, we demonstrate that the second-preimage search algorithm can also be used to generate internal collisions for the ALPHA-MAC if an intermediate value is known.

Third, we carry out further investigations on the key schedule of the AES cipher, and our research identifies some repeated differential properties in the AES-128 and AES-256 key schedules. In the case of AES-128, if the difference of two secret keys has a special pattern, which we call repeated differential pattern, the propagation of the difference via the key schedule will produce at least seven zero differences in each round, and the same pattern repeats every four rounds. In the case of AES-256, we show that two secret keys with a double-sized repeated differential pattern generate similar repeated features in the resultant subkeys.

Fourth, we describe a differential fault analysis of the LEX stream cipher. The attack exploits computational errors during keystream generation to recover secret keys of the cipher. In our analysis, the cipher is assumed to have random faults in its states and typically, there is one random faulty bit injected during each computation. In the proposed attack, the adversary can extract the secret key of LEX by analysing the output keystream generated by 40 faults.

Share

COinS