Impossible differential cryptanalysis of Mini-AES

Cryptologia, Oct 2003 by Phan, Raphael Chung-Wei

ABSTRACT: Impossible differential cryptanalysis is one of the cryptanalysis methods that are applicable to the new Advanced Encryption Standard (AES). In this paper, we present an introduction to the method by applying it on Mini-AES, the mini version of the AES published in Cryptologia recently.

KEYWORDS: Advanced Encryption Standard, Rijndael, Mini-AES, Impossible Differential Cryptanalysis.

1 INTRODUCTION

The Advanced Encryption Standard (AES) is the standard algorithm adopted by the National Institute of Standards and Technology (NIST) to replace the aging Data Encryption Standard (DES) for encryption and protection of secure and non-classified information [1, 2]. The AES is expected to not only gain popular usage among the U.S but also among the international community, and will be implemented in various situations such as for the securing of online transactions, smart cards and dedicated hardware.

Foreseeing the importance of the AES, a mini version of the AES, Mini-AES was recently presented [3]. Mini-AES is proposed as a purely educational encryption algorithm to aid cryptography and cryptanalysis students to better understand the concepts behind the real AES. It is also intended that the Mini-AES be a testbed for cryptanalysis students to start their cryptanalytic efforts on. As an illustration, the Square attack was mounted on Mini-AES. This work is of great importance since there is an absence of suitable texts or reference books for the field of cryptanalysis. Amateurs and aspirants new to the field have a hard time understanding the basic concepts from journal and conference papers which are the sole sources of cryptanalytic information.

In this paper, we extend on the effort by showing how another cryptanalysis method, the impossible differential cryptanalysis works. The impossible differential cryptanalysis is also applicable to the AES, and we show the details step by step by mounting it on Mini-AES.

In Section 2, we briefly describe Mini-AES. We introduce the notion of impossible differentials and apply it to an attack on Mini-AES in Section 3. We conclude in Section 4.

2 MINI-AES

In this section, we briefly describe Mini-AES. For further details, the reader should refer to [3]. Mini-AES is a 16-bit block cipher with a 16-bit secret key. It consists of 2 rounds, where each round is composed of 4 basic operations, namely NibbleSub, ShiftRow, MixColumn, and KeyAddition. For ease of explanation of these operations, the 16-bit plaintext block, P is expressed as a matrix of 2 rows and 2 columns of nibbles (a nibble is 4 bits). Each nibble is denoted as a^sub ij^ where i, j [is an element of] {0, 1} are the row and column indices respectively. This is shown in Figure 1.

The 16-bit block can sometimes also be expressed as a series of 4 nibbles, in which case, it is written as a^sub 00^, a^sub 10^, a^sub 01^, a^sub 11^. Note that in relating this to the matrix representation as in Figure 1, then the nibbles are read from the matrix column by column. When expressed as a series of 4 nibbles, then the leftmost nibble is referred to as the first nibble.

NibbleSub, [gamma] substitutes each input nibble with an output nibble based on Table 1 of [3]. For convenience, this table is also reproduced in the Appendix. ShiftRow, [pi] merely swaps the two nibbles in the second row, while the first row is left unchanged. MixColumn, [theta] takes each input column and multiplies it with a constant 2 x 2 matrix given in Figure 5 of [3] to obtain a new output column. This matrix is also available in the Appendix. Hence, each nibble in the output column depends on all the nibbles of the input column. KeyAddition, [sigma]^sub K^^sub i^ causes the 16-bit input block to be exclusive-ORed (XORed) with a 16-bit round key, K^sub i^ which is generated from the secret key.

In order to ensure that the same structure can be used for both encryption and decryption, an extra Key Addition (called the 0th round) is added prior to the first round, while MixColumn is removed from the last round.

3 IMPOSSIBLE DIFFERENTIAL CRYPTANALYSIS

The impossible differential cryptanalysis relies on finding an impossible event through a reduced part in the middle of a block cipher. Then, all possible round keys in the outer rounds are guessed, and those that suggest this impossible event are eliminated since the correct round key value would never cause such an event to occur. Currently, the most effective way of constructing an impossible event is by using the miss-in-the-middle technique, introduced by Biham et al. [4]. The miss-in-the-middle technique considers two events that always happen. By concatenating these events such that they cause a contradiction in the middle, an impossible event results.

3.1 A 4-round Impossible Differential of Mini-AES

Mini-AES has only 2 rounds [3], which makes it too trivial for an impossible differential attack, so we will consider more rounds of Mini-AES. In constructing an impossible event, we would like to have it cover as many rounds as possible. Nevertheless, similar to the case of the original AES [1, 2], 4 rounds is the maximum that an impossible event on Mini-AES can cover. In this section, we will describe how such a 4-round impossible event is constructed.