AES: Other attacks

21 April 2014
Published in Research

It is clear that so far, none of the attacks carried out against full-AES has been successful, these attacks usually focus on reducing rounds. Many authors claim that none of the following types of attacks have been more effective than an exhaustive-key search:

  • Linear cryptanalysis
  • Differential Cryptanalysis
  • Truncated diferencials
  • Interpolation attacks
  • Square attack

However, the ordered structure and the deep mathematical basis that AES uses, make it an object of study for new attacks proposals such as algebraic attacks. These attacks consist on propose an equation system, and with the unknowns of the system, it can deduce the key; one of the advantages of this type of attack, is the small number of known texts needed.

As we mentioned in a previous article, rounds that make up the AES algorithm can be divided into three different categories: initial rounds, standard round and final round. When encryption, the information is subjected to a different number of rounds (10, 12 and 14 respectively) in each case depending on the length of the key (128, 192 and 256 respectively). Each such round is made up of combinations of transformations, the possible transformations include: ByteSub, ShiftRow, MixColumns and AddRoundKey. Figure # 1 shows the relationship of the transformation and corresponding rounds.

 

Figure # 1: Distribution of the transformations in each round.

Some time ago, I read an interesting article of a "successful attack" against AES, the famous symmetric-key algorithm. Raphael C.-W. Phan [1] presented a seven rounds "impossible differential attack" for AES-192 and AES-256. Someone may ask: what kind of attack is this?, well, it is a crypt-analysis that takes advantage of the differences that are impossible to be, in a data block through encryption, in order to discover the key?. Without going into many details of the method used, below I comment some of the most important results of this study.

The attack involves taking pairs of identical texts in all bytes except one and encrypt these texts, then, analyze the data produced at the outputs of each rounds in order to observe the evolution of the information during the encryption process. With this information, a impossible key's probability (or probability 0) can be assigned.

The attack is based on the algorithm outlined in [1], which is used to break AES-192 and AES-256, it consists in 9 steps and focuses on the key expansion system. The algorithm permits to perform certain calculations and assigns probabilities when some sub-keys have been determined. In summary, the author hopes to determine the key in the seventh round with the mathematical model presented in this study, by observing the movements made by the various transformations.

Summarizing the results obtained in [1], for the case of AES-192, 292 plain texts, 2153 memory words and 2186 encryptions were required, in the case of AES-256, 292.5 plain texts, the same memory space 2153 and 2250.5 encryptions were requiered. The Table # 1 shows a comparison between the results presented by [1] and two earlier attacks with fewer rounds.

 

Table # 1: Comparison of results to attacks on AES [1].

 

Aside from the process itself, and analyzing the results of this attack, we can see that to break the algorithm, the test has needed 2186 and 2250.5 encryptions for AES-192 and AES-256 respectively. Taking into account that an exhaustive search would have taken 2192 and 2256 for each algorithm respectively, we could say that the attack presented by [1] has been successful.

Now, it is important to clarify that this is an attack on reduced-rounds (7 rounds) and AES may have a key length of 128, 192 or 256 bits for an amount of standard rounds: 10, 12 and 14 respectively. This means that despite the successful attack presented, AES maintains a large margin of safety with respect to this study, because there are 5 rounds of difference (for AES-192), and thus, the decoding complexity of an information packet is increased by applying the number of rounds which is defined by the standard.

 

Reference

  1. Raphael CP. Impossible differential cryptanalysis of 7-round Advanced Encryption Standard (AES). Information Processing Letters (2004) 91: pp. 33-38.

 

 

 

In Part I of the Overview of AES (Advanced Encryption Standard) the most relevant aspects of AES and S-Box was described. Now, we discuss some details of the so-called transformations (ByteSub, ShiftRow, MixColumns and AddRoundKey) and the subkey generation process. To see more details in a more dynamic way the Rijndael Animation application is recommended.

 

ByteSub

This transformation performs a byte-by-byte substitution in each of the state matrix elements, ie, the state matrix [aij] is replaced by the matrix [Sij], Figure # 1 shows this process. Using Rijndael Animation [1] application, it can be seen as the first byte of the state matrix ([a00]) is divided into two groups of four bits each one and they are used as pointers to the S-Box rows and columns, respectively, for replacement, in Figure # 1 is shown how the value 19 will be replaced by d4.

 

Figure # 1: S-Box use [1].

Page 1 of 2