From my undergraduate writings in November, 2000 (quoted word for word). I’ll post my impressions in a later post.
Weak Yet Strong:
Rijndael’s security in today’s environment
The Rijndael algorithm was chosen as the final candidate for the Advanced Encryption Standard by the Advanced Encryption Standard group (AES). Rijndael was one of the five finalists that were chosen. The other finalists include RC6, Serpent, Twofish and MARS. There are many disadvantages and advantages for the Rijndael algorithm. Rijndael is likely the best choice for todays security needs.
The Rijndael algorithm is an algorithm that uses multiple rounds that deal with arrays of input bytes. There are four layers to most of the rounds except for the last round which does not contain any mixing. The first layer is a simple S-box transformation. The second and third layers are mixing layers that the rows of the array are shifted and the columns mixed. In the fourth layer bytes from the key are XORed into each byte in the array.
Possible weaknesses
“The best way to hide something is in plain sight.” – unattributed
The AES spent a large amount of time analysing and talking about the five finalist algorithms. there were several vulnerabilities in reduced versions of Rijndael as well as some merely possible minor weaknesses in the complete algorithm. There was quite a bit of data that went into the AES conferences and security of the chosen algorithm was not the only goal. The speed of the algorithms may have lured the AES into choosing a less secure algorithm.
Many possible weaknesses in Rijndael may lead to real weaknesses and there were several analysis done to suggest were weaknesses may be found. It is important to note that any weakness in one part of the algorithm does not mean that the whole algorithm is weak, but nevertheless any weakness can provide a starting point for cryptanalysists. Many parts of the algorithm provide for the possibility that the cipher text will not be adequately enciphered.
The number of rounds can be as low as 10 [1] leaving the possibility of too few permutations of the inputted bits. Serpent uses 32 rounds [2] to be more thorough. Of the five AES finalists only Twofish uses anywhere near as few rounds. Twofish uses only 16 rounds [2. At the most Rijndael uses 14 rounds [2].
The fact that Rijndael derives a larger key from the key that is given [1] is suspicious. Little additional security is gained from making the key larger unless it can be shown that the new key is adequately unique. There could possibly be patterns in the larger keys that could make cryptanalysis easier by making it easier to eliminate possible messages. The larger key may make some of the rounds in effect worthless if it is known what the rounds are doing without knowning the key. If the probabilities, without knowning the key, of what the rounds are doing are not adequately even and unique then a heuristic can be built to attack a message faster than through an exhaustive search. The column mixing algorithm [1] may do the same mixing given different keys. Doing the same thing given different keys is known as collisions. the possibility of collisions ideally would be zero for every part of the algorithm.
It was suggested that attacks on the Rijndael algorithm could be built from the Square attack [2]. The biggest reason for the dismissal of attacks built from the Square attack was that 7 and 8 round variants require almost the entire codebook [2]. It was said that even 9 rounds could be vulnerable to a related key attacks [2].
With several old attacks being partially effective on reduced versions of Rijndael, the possibility of collisions in the mixing algorithm, possible collisions in the rounds due to an enlarged key and few rounds there coudl be the possibility of a huge time savings for a cryptanalysists to attack messages encrypted with the Rijndael algorithm. The AES itself said that Rijndael provides an adequate security while saying that three of the other five finalist algorithms provide high security [2]. The tests done with Rijndael were not equal in all ways to the tests done on the other four candidates, perhaps due to the fact that it is a unqiue algorithm or perhaps results were simply not available at the time.
Possible strengths
The Rijndael algorithm went through many tests and many analysis, the difficulty of finding a heuristic to beat the time for an exhaustive search is very high. Many different things are done in the Rijndael algorithm to try and make it far less vulnerable to known heuristics. Analysis were done using many known heuristics and showed that the Rijndael algorithm is very security with today’s knowledge and computing power.
“Rijndael does not have Feistel structure” ([1] section 3 page 8). Many algorithms including several of the AES finalist algorithms use the Feistel structure. The Feistel structure has been around for a while and has been widely analysed and thus it is felt that the structure may be easier to attack than other structures. Rijndael has a uniform structure, but the intermediate states are not simply transposed unchanged [1]. the changing of the states make Rijndael more resistant against linear and differential cryptanalysis [1].
the fact that the number of rounds is not constant [1] may give the Rijndael algorithm an advantage over other algorithms. If the block and key sizes are not known then there are many more different decryptions that would be necessary to do an exhaustive search.
Variable shift offsets [1] in the rows add quite a few more possible transformations when combined with column mixing. With simply a mixing of the columns there is still the possibility of leaving cryptanalysists with the ability to do statistical analysis on the columns. When row shifting is combined with column mixing the cryptannalists must first figure out the row shift. If the row shifts were constant it would be much easier to cryptanalyse.
there were many tests done on many architectures with many configurations and Rijndael was shown to have far longer time necessary to decrypt messages than encrypt them [1]. Having a longer decryption time is very advantageous as it makes any search using the algorithm take linearly more time. With a longer decryption time exhaustive searches start to become unreasonable a great deal faster.
It was worried that there may be trap doors built into the chosen AES algorithm [2]. It was said that Rijndael can easily use a different S-box thus relieving some possible fears that there may be back doors in it’s S-box.
Being a bit level algorithm that dealt at the byte level for many of its operations Rijndael was shown to be quite quick. Fewer rounds also speed up the algorithm. It is not all that useful to have a high security algorithm when it “eats up” too many resources.
Rijndael has many advantages that make it a good choice to be the Advanced Encryption Standard. It is fast and has been shown to be very reasonably secure. It was anticipated that a new standard would need to be chosen for the distant future so many of the possible holes in Rijndael were not perceived to be a threat to security. It is anticipated that Rijndael will go through its entire life as an algorithm that is secure against all attacks. Rijndael will give security in many different applications, most importantly it is efficient on much of the hardware and software of today.
References:
[1] AES Proposal: Rijndael, 1999, Daemen and Rijmen 45 pages (Rijndael.pdf)
[2] Report on the Development of the Advanced Encryption Standard, 1999 Nechvatal et al, 116 pages (r2report.pdf)
The above wouldn’t be what I’d write today, but gives a good reference that I wanted to write out word for word. It includes typographical errors to avoid inadvertently changing the meaning from correcting them.
My resume is at http://www.boxheap.net/ddaniels/resume.html