Foundations of Coding: Compression, Encryption, Error Correction (2015)

Chapter 3. Cryptology

3.2 Secret Key Cryptography

3.2.1 Principle of Symmetric Cryptography

Let us take the notation of the Equation (3.1 ); symmetric encryption rests upon the following principle: c3-math-0015. In other words, Alice and Bob secretly agree upon a shared key K, which is used in both encryption and decryption. They also agree upon a cryptographic algorithm for encryption and decryption. The general principle of symmetric cryptography is illustrated in Figure 3.3. One often uses the analogy of a safe to qualify symmetriccryptosystems: only the key holders (a priori, Alice and Bob) may be able to open the safe. Oscar, who does not possess the key, will have to force the safe if he wishes to have access to its content. Obviously, if Oscar is able to get the key by any means, he will be able to decrypt all messages exchanged between Alice and Bob.

nfg003

Figure 3.3 Principle of symmetric cryptography

Let us notice that the expression “ symmetric encryption” is used to differentiate this scheme from asymmetric cryptography. The main advantage of such systems is that they are very efficient in terms of computation time for both encryption and decryption. On the other hand, the main weakness of this system comes from the necessity of having an absolute secrecy surrounding the key K. Historically, it was the first kind of encryption to be used. Several examples of this type (Caesar encryption and Vernam perfect encryption) were described in Chapter 1. Let us study other examples of this kind in the form of an exercise.

Exercise 3.1 (Affine Encryption)

On page 6, we studied the case of Caesar encryption defined over some alphabet c3-math-0016 of n characters. This scheme is a particular case of affine encryption. Given a bijective map between c3-math-0017 and c3-math-0018, and denoting c3-math-0019 the set of invertible elements in c3-math-0020, one is able to write the affine encryption function for a message c3-math-0021 from a key c3-math-0022 :

equation

1.  Express c3-math-0024 and c3-math-0025.

2.  Still considering c3-math-0026 and using the key c3-math-0027 (justify the use of such key), give the ciphertexts for c3-math-0028.

3.  Express the affine decryption function c3-math-0029.

4.  Although ciphertexts produced by affine encryption seem incomprehensible, this scheme does not modify the frequency of occurrence of the various letters composing the text. Statistical repartition of the letters in a text written in French, as well as the bijective map letter by letter which will used in the sequel, are provided in Table 3.1.

Table 3.1 Frequency of the Letters in French

c3-math-0030

8.11%

c3-math-0031

0.18%

c3-math-0032

8.87%

c3-math-0033

0.81%

c3-math-0034

0.02%

c3-math-0035

7.44%

c3-math-0036

3.38%

c3-math-0037

5.99%

c3-math-0038

5.23%

c3-math-0039

4.28%

c3-math-0040

2.29%

c3-math-0041

1.28%

c3-math-0042

17.69%

c3-math-0043

7.68%

c3-math-0044

0.06%

c3-math-0045

1.13%

c3-math-0046

5.20%

c3-math-0047

0.53%

c3-math-0048

1.19%

c3-math-0049

2.92%

c3-math-0050

0.26%

c3-math-0051

0.74%

c3-math-0052

0.83%

c3-math-0053

0.12%

c3-math-0054

7.24%

c3-math-0055

6.43%

   

Alice sends a text to Bob. Tacitely, characters not belonging to c3-math-0056 are not encrypted. One intercepts the following message:

     mcahbo isbfock, ekb kp cbfbo vobixo,

        hopcah op esp foi kp rbsmcuo.

      mcahbo bopcbl, vcb j'slokb cjjoixo

        jka haph c vok vboe io jcpucuo:

      "xo! fspdskb, mspeaokb lk isbfock,

yko nske ohoe dsja! yko nske mo eomfjoz fock!

        ecpe mophab, ea nshbo bcmcuo

        eo bcvvsbho a nshbo vjkmcuo,

 nske ohoe jo vxopat loe xshoe lo ioe fsae."

One counts the occurrences of each letter of the alphabet in the ciphertext. Hence, one gets Table 3.2.

Table 3.2 Frequency Analysis of the Ciphertext

In the Ciphertext

Reference (text in French)

c3-math-0057

18.11%

c3-math-0058

17.69%

c3-math-0059

9.05%

c3-math-0060

8.87%

c3-math-0061

7.82%

c3-math-0062

8.11%

c3-math-0063

7.41%

c3-math-0064

c3-math-0065

c3-math-0066

c3-math-0067

   

1.  a. From this result, deduce the key used by Alice.

2.  Deduce the decryption key and the plaintext.

Solution on page 303.

3.2.2 Classes of Symmetric Encryption Schemes

As we have seen in Chapter 1, Sections 1.2 and 1.3, one distinguishes two kinds of codes. Similarly, there are two kinds of encryption schemes.

3.2.2.1 Symmetric Stream Ciphers

In order to get close to Vernam's model (described in Section 1.2.1), such ciphers process the data on-the-fly. Their use is based on a Pseudo-Random Number Generators (PRNG) (1.3.7) and on a fast bitwise substitution mechanism such as “eXclusive OR” (XOR c3-math-0068), which is used in the Vernam code. This principle is illustrated in Figure 3.4

nfg004

Figure 3.4 Stream cipher

As a consequence of Kerckhoffs' principles, one immediatly notices that security of a stream cipher depends on the quality of the key generator.

Among the most famous examples (not necessarily the most secure ones), one may notice LFSR (see the mechanism of the generator on page 63), RC4 (which is used, for example, in the Secure Sockets Layer (SSL) protocol in order to protect Internet communications or in the WEP protocol in order to secure WiFi connections), Py, E0 (used in Bluetooth communications), and A5/3 (used in GSM communications).

As RC4-WEP and A5-GSM were broken, the estream project has identified a portfolio of seven promising new stream ciphers. Four of them are software oriented (HC-128, Rabbit, Salsa20/12, and Sosemanuk), whereas the three remaining ones are hardware oriented (Grain, Trivium, and Mickey).

A common property of stream ciphers is to generate an internal state from which pseudo-random bits are produced in a stream. The sender and the receiver must synchronize their internal state in order to be able to produce the same sequence of pseudo-random bits.

For instance, the Rabbit stream cipher uses a 128-bits key c3-math-0069 that, with a 64-bits initial value, generates 512-bits of internal state (c3-math-0070-bits c3-math-0071) and 512-bits of internal counters (c3-math-0072-bits c3-math-0073) with:

equation

If we set c3-math-0075, some 32-bits constants (c3-math-0076), and c3-math-0077, then the internal state evolution (c3-math-0078 and c3-math-0079 are computed modulo c3-math-0080) and the random bits c3-math-0081 are given in Table 3.3.

Table 3.3 Rabbit Stream Internal State Evolution and Bit Extraction

c3-math-0082

Overall, the major interest of such a stream cipher is its speed as it requires 3.7 cycles per produced bit on a single 1 GHz machine. Now, the generation is intrinsically sequential as the internal state is required to produce new bits. Block ciphers can overcome this latter issue by using the same key to encrypt different parts of a message.

3.2.2.2 Symmetric Block Ciphers

Such ciphers split a message M on n bits into s blocks on c3-math-0083 bits (one may initially add meaningless characters to the message so that its size is a multiple of r). A block cipher algorithm processes blocks on r bits and produces in general blocks on r bits to ensure that the code is bijective. The combination with an encryption mode (ECB, CBC, CFB, OFB, or CTR—see Section 1.3.1) fully describes the encryption of a message M, as illustrated in Figure 3.5.

nfg005

Figure 3.5 Block cipher

Common systems such as DES and AES, which use block ciphers, are presented in the sequel.

3.2.2.3 Unconditionally Secure Encryption

One recalls that an encryption scheme is said unconditionally secure or perfect if the knowledge of the ciphertext provides absolutely no information on the plaintext. Hence, the only possible attack is the exhaustive search for the secret key. Up to now, only Vernam encryption—which uses a secret key as long as the plaintext (Section 1.2.1)—has been proved unconditionally secure, assuming that the secret key is chosen randomly and used only once. In particular, all other systems are theoretically breakable.

Therefore, nowadays one considers almost secure encryption algorithms. For such systems, the ciphertext does not enable one to recover the plaintext nor the key in humanly reasonable time. This enables one to choose keys of smaller length with respect to Vernam coding. We will now present the two most important standards for block ciphers.

3.2.3 Data Encryption Standard (DES) System

3.2.3.1 Exhaustive Description of DES

This is the most well-known symmetric cryptosystem. It was first presented as an encryption standard by the NIST in 1977.

It processes plaintext blocks of 64 bits using a key K of 56 bits2 and outputs 64-bit ciphertext blocks. The algorithm is divided into three steps:

1.  Let x be a plaintext block of 64 bits. One applies some determined initial permutation IP in order to obtain a string c3-math-0084. Thus, one has: c3-math-0085 where c3-math-0086 contains the first 32 (most significant) bits of c3-math-0087 and c3-math-0088 the remaining (least significant) 32 bits.

2.  One performs 16 iterations (called rounds) with some function f using the key K as a parameter. The function f will be described in detail in the sequel. One computes c3-math-0089 according to the rule:

3.  3.2equation

nfg006

Figure 3.6 One round of DES

4.   Figure 3.6 describes one encryption round. The function f has two parameters: one has 32 bits (it corresponds to c3-math-0091 at the c3-math-0092 round) and the other one has 48 bits (c3-math-0093). The round keys c3-math-0094 are obtained from the so-called key derivation performed on the bits of the original key K: this process will be described later on.

5.  One applies the inverse permutation c3-math-0095 on c3-math-0096 in order to get a ciphertext block c3-math-0097 (Notice that c3-math-0098 and c3-math-0099 are inverted).

The same algorithm, with the same key, but performing the rounds in the inverse order, is used in order to decrypt the blocks.

The security of DES comes from the application of the function f at each round. This function has two parameters:

·     a string A of 32 bits (the right part of the block one wishes to encrypt);

·     a string J of 48 bits (the round key).

The computation of c3-math-0100 is divided into several steps, which are illustrated in Figure 3.7:

1.  A is expanded to get a string of 48 bits using an expansion function E.

2.  c3-math-0101 is computed and split into eight consecutive substrings of 6 bits each: c3-math-0102. Each substring c3-math-0103 is then passed through a substitution box c3-math-0104 (the famous SBox), which outputs a block c3-math-0105 of four bits.

3.  The 32-bit string c3-math-0106 is then reorganized using a determined permutation P. The result c3-math-0107 defines c3-math-0108.

nfg007

Figure 3.7 DES: Function f

Exercise 3.2 (DES Decryption)

Show that it is not necessary to invert f in order to invert a DES round. Deduce the decryption algorithm of the DES system.

Solution on page 304.

3.2.3.2 DES Key Derivation

We have seen that at round i the second parameter of the function f is a subkey c3-math-0109 extracted from the initial key K. This paragraph details the algorithm that is used to generate the 16 subkeys c3-math-0110.

1.  The key K of 64 bits is reorganized with an initial permutation PC-1 that removes the parity bits (those located at the positions 8,16,…,64). One denotes PC-1c3-math-0111, where c3-math-0112 contains the 28 most significant bits of PC-1c3-math-0113 and c3-math-0114 contains the 28 least significant bits.

2.  c3-math-0115, and c3-math-0116 (c3-math-0117) are computed recursively in the following way:

c3-math-0118

c3-math-0119 is a circular shift by one or two positions depending on the value of i and PC-2 is another bit permutation.

All these steps are illustrated in Figure 3.8.

3.2.3.3 Advantages and Practical Uses of DES

After 16 rounds the output of DES is statistically “ flat”, namely the general features of the source message (the frequencies of the characters, the number of spaces, etc.) are undetectable. Moreover, DES has a very important characteristic for avoiding differential analysis attacks: the least modification of the key or the plaintext induces important changes in the ciphertext.

nfg008

Figure 3.8 DES key derivation

The main advantage of DES is that—for both encryption and decryption—computation uses operations that are easy to implement at the hardware level. Therefore, it is possible to obtain very high encryption speeds (already of the order of 190 MB/s 10 years ago on certain machines).

The DES system has been used for securing credit card payments (for example, UEPSUniversal Electronic Payment System), network authentication protocols such as Kerberos, and e-mail clients such as PEM (Privacy-Enhanced Mail). From its cryptanalysis, see next section, we will however see that nowadays its successor, the AES, should in general be preferred. When the DES is nonetheless in use, it is in general at least used in its triple form, as discussed also in the following section.

Exercise 3.3 (Confidentiality of DES)

1.  Show that a perfect encryption scheme (the ciphertext does not give any information about the plaintext or in terms of entropy, c3-math-0120; see Section 1.2.5) satisfies c3-math-0121.

2.  Discuss the perfect confidentiality of DES for a block.

Solution on page 304.

3.2.3.4 Cryptanalysis of DES

After publication, many research efforts have been invested in the cryptanalysis of DES, first on versions with less rounds and then on the full version. Meaningful breakthroughs (including the techniques that were used) appeared at the beginning of the nineties. Nowadays, one distinguishes four cryptanalysis methods for DES:

·     Exhaustive research. Obviously, this method can be applied on any cryptosystem.

·     Exhaustive precomputation. The objective is to store the result of the encryption of a chosen plaintext using DES for all possible keys K. Hence, if one manages to obtain a ciphertext associated with this particular plaintext from a target cryptosystem, one is able to easily recover the secret key (the cost is constant). This implies that one is able to store c3-math-0122 blocks of 64 bits, which is possible using current hard disks.

·     Differential cryptanalysis. This attack aims to study the differences in the encryption of two similar texts in order to extract a subset of probable keys. It represented a significant breakthrough in the cryptanalysis of DES.

·     Linear cryptanalysis. This was another major breakthrough in the cryptanalysis of block ciphers in general. The objective is to find linear relations between some bits of the ciphertext and some bits of the plaintext in order to interpolate certain bits of the secret key.

Table 3.4 summarizes the complexities of the attacks on DES.

Table 3.4 Complexities of Cryptanalysis Methods on DES

Attack method

Known

Chosen

Memory

Computations

 

Plaintext

Plaintext

Space

 

Exhaustive research

1

   

c3-math-0123

Exhaustive precomputation

 

1

c3-math-0124

1 table

Linear cryptanalysis

c3-math-0125 then c3-math-0126

 

Texts

c3-math-0127 then c3-math-0128

Differential cryptanalysis

c3-math-0129

c3-math-0130

Texts

c3-math-0131

With the breakthroughs in the field of cryptanalysis and the growth of computational possibilities, a study was proposed in 1996 to estimate the efficiency of the attacks on DES for a given budget. The result of this study is given in Table 3.5.

Table 3.5 Cost and Efficiency of Attacks on DES in 1996

Attacker

Budget

Tool

Time to Find

     

a 56-bit Key

Hacker

300 €

Software

38 years

Small company

7500 €

Circuit

18 months

Big company

225 K €

ASIC Circuit

19 d. 3 h

International Co.

7.5 M €

ASIC

6 min

Government

225 M €

ASIC

12 s

Nowadays, DES is no longer considered to be almost secure because of its key of 56 bits. A small calculation is enough to explain the main idea of this statement: there are c3-math-0132 possible keys, that is, less than c3-math-0133. Let us consider 1000 cores running at c3-math-0134. Thus, it takes c3-math-0135 s (30 h) to perform c3-math-0136 operations; therefore, brute force attack is not impossible in reasonable time!

In order to improve the security of DES, a first solution was to combine two keys. One obtained the “double DES” system, for which c3-math-0137 and c3-math-0138. However, it quickly appeared that actually breaking this system is in this way only 100 times more difficult than breaking the simple DES (and not c3-math-0139 times more difficult as one might have expected using two keys). Indeed, the “meet-in-the-middle” attack uses a fast sort to break the double DES with almost no computation overhead with respect to breaking the simple DES:

1.  Compute all c3-math-0140 possible encryptions c3-math-0141 of a given message M.

2.  Sort the c3-math-0142 with a fast sort in c3-math-0143 steps. There are approximately c3-math-0144 operations.

3.  Compute all c3-math-0145 possible decryptions of C with a single key jc3-math-0146; in the same time, compare the c3-math-0147 with the c3-math-0148 (as the latter are sorted, the research requires at most c3-math-0149 steps for each c3-math-0150 by dichotomy).

4.  When one finds c3-math-0151, the target keys are c3-math-0152 and c3-math-0153.

Therefore, the security of the key of double DES is only around 64 bits.

Later, the use of “triple DES” was proposed with an effective key of 112 bits but with a computational time multiplied by three. This operation can be performed using three keys and the encryption c3-math-0154 (this is called c3-math-0155); in this case, the previous attack gives a security of the key rather of around 120 bits. That is why one often prefers to use only two keys and the encryption c3-math-0156 (c3-math-0157), which provides a security of 112 bits and is compliant with simple DES encryption taking c3-math-0158.

Finally, a new faster standard has taken its place since 2000: the AES, Advanced Encryption Standard.

3.2.4 Rijndael: Advanced Encryption Standard (AES)

Rijndael is a symmetric cipher chosen by the NIST (National Institute of Standards and Technology) to be the new American encryption standard (AES: Advanced Encryption Standard). This system was chosen after a contest organized by the NIST. Among the five finalists (Rijndael, Serpent, Twofish, RC6, and Mars), Rijndael appeared to be the most resistant and became the new American standard, replacing DES. It is a block cipher processing 128-bit blocks with a key of 128, 192, or 256 bits. It is important to notice that Rijndael was also among the proposals giving the fastest results, as we can see in Table 3.6 (which is taken from the report of the New European Schemes for Signatures, Integrity, and Encryption (NESSIE)-D21).

Table 3.6 Performance of Several Block Ciphers

   

Clock cycles/Byte

Algorithm

Key size

Encryption

Decryption

IDEA

128

56

56

Khazad

128

40

41

Misty1

128

47

47

Safer++

128

152

168

CS-Cipher

128

156

140

Hierocrypt-L1

128

34

34

Nush

128

48

42

DES

56

59

59

3-DES

168

154

155

kasumi

128

75

74

RC5

64

19

19

Skipjack

80

114

120

Camellia

256

47

47

RC6

256

18

17

Safer++

256

69

89

Anubis

256

48

48

Grand cru

128

1250

1518

Hierocrypt-3

260

69

86

Nush

256

23

20

Q

256

60

123

SC2000

256

43

46

Rijndael

256

34

35

Serpent

256

68

80

Mars

256

31

30

Twofish

256

29

25

All the operations of AES are operations performed on bytes that are considered as elements of the finite field of c3-math-0159 elements, c3-math-0160. One recalls that for p prime, c3-math-0161 is isomorphic to c3-math-0162, where c3-math-0163 is an irreducible polynomial on c3-math-0164 of degree m (see Section 1.3.4).

For AES, c3-math-0165, and c3-math-0166 (one easily checks that c3-math-0167 is actually an irreducible polynomial on c3-math-0168, see Algorithm 1.8). Hence, the byte c3-math-0169 is represented by the polynomial c3-math-0170. By extension, the polynomial c3-math-0171 is written 0x11B, namely the corresponding byte in hexadecimal notation.

·     The addition of two polynomials is the bitwise addition of their coefficients (the addition in c3-math-0172), which corresponds to the eXclusive OR (XOR c3-math-0173) on the bytes.

·     The multiplication is a multiplication of polynomials modulo c3-math-0174.

Exercise 3.4 (Operations in c3-math-0175)

1.  One considers the bytes c3-math-0176 and c3-math-0177 (in hexadecimal notation; one can also write c3-math-0178 and c3-math-0179 if there is no ambiguity) seen as elements in c3-math-0180.

a.  Compute c3-math-0181

b.  Compute c3-math-0182

2.  2. Now, let us use the polynomial notation. Let c3-math-0183.

a.  Give an algorithm for computing the element in c3-math-0184 corresponding to c3-math-0185.

b.  Deduce an algorithm for computing the element c3-math-0186 in c3-math-0187.

3.  Let c3-math-0188 be a generator of c3-math-0189. In this case, any nonzero element in c3-math-0190 can be represented uniquely by c3-math-0191. Deduce an efficient way of performing the multiplication of two elements in c3-math-0192Remark: For AES, c3-math-0193 0x03.

Solution on page 304.

Blocks of bytes are organized in a matricial form, according to the model illustrated in Figure 3.9. This matrix has necessarily four lines and a number of columns depending on the size of the block. One denotes c3-math-0194 the number of columns of the matrix representing a block and c3-math-0195 the number of columns of the matrix representing a key.

nfg009

Figure 3.9 Matricial representation of a 16-byte block

For instance, for input/output streams that correspond in the AES to 16-byte sequences, one obtains matrices of 4 lines and c3-math-0196 columns. In the same way:

·     the matrix associated to a key of 128 bits has 4 lines and c3-math-0197 columns;

·     for a key of 192 bits, the matrix has 4 lines and c3-math-0198 columns; and

·     for a key of 256 bits, the matrix has 4 lines and c3-math-0199 columns.

To be more precise, the AES algorithm is not stricto sensu exactly the Rijndael algorithm. The latter may have more block sizes than that of AES. AES considers only 128-bit data blocks (c3-math-0200), whereas the Rijndael algorithm considers data blocks of 128, 192, or 256 bits.

3.2.4.1 Principle of the Algorithm

Similar to DES, AES performs a sequence of rounds that are given in detail in the sequel. One denotes c3-math-0201 the number of rounds that are to be performed. This number depends on the values of c3-math-0202 and c3-math-0203. The different configurations are given in Table 3.7.

Table 3.7 Configurations for AES

 

c3-math-0204

c3-math-0205

c3-math-0206

AES-128

4

4

10

AES-192

6

4

12

AES-256

8

4

14

We have seen previously that AES operates on blocks that are represented with matrices of c3-math-0207 elements in c3-math-0208. AES encryption consists of a preliminary addition with a key (AddRoundKey), followed by c3-math-0209 rounds. Each round is divided into four stages:

1.  1. SubBytes is a nonlinear substitution: each byte is replaced by another byte chosen in a particular table (an SBox).

2.  ShiftRows is a transposition stage. Each element of the matrix is shifted for some number of position to the left.

3.  MixColumns performs a matrix multiplication operating on each column (seen as a vector) of the matrix.

4.  AddRoundKey performs a bytewise addition with a round key derived from the encryption key.

A FinalRound is applied (it corresponds to a round in which the MixColumns stage is removed). The round key for stage i is denoted RoundKeys[i], and RoundKeys[0] refers to the parameter of the preliminary key addition. The derivation of the encryption key K in the tableRoundKeys[] is denoted KeySchedule and explained in detail later on. Algorithm 3.1 describes the AES encryption.

ngr001

SubBytes (State) This stage corresponds to the only nonlinear transformation of the algorithm. In this stage, each element of the matrix State is permuted according to an invertible substitution table denoted SBox. For instance, Figure 3.10 illustrates the transformation of the element c3-math-0210 into the element c3-math-0211.

nfg010

Figure 3.10 SubBytes operation in AES

Remark: The SBox table is derived from the inverse function c3-math-0212 over c3-math-0213. This function is known for its good properties of nonlinearity (as 0 has no inverse, it is mapped onto 0 in this stage). In order to avoid attacks based on simple algebraic properties, the SSBoxBox is built combining this inverse function and an affine invertible transformation f. Therefore, one has

equation

Moreover, AES was designed to avoid any fixed point and opposite fixed point:

equation

Finally, the affine function f is defined as follows:

equation

Exercise 3.5 (InvSubBytes)

Give the details of the inverse operation of this stage.

Solution on page 306.

Exercise 3.6 (Operations on SubBytes)

One sets c3-math-0217 (hexadecimal notation) with the same representation convention used in AES. Compute c3-math-0218.

Solution on page 306.

ShiftRows (State) In this stage, one operates on the lines of the matrix State and one performs, for each element of a line, a cyclic shift of n positions to the left. The value of the shift depends on the line one considers. The line i is shifted by c3-math-0219 elements, such that the element in position j in the line i is moved to the position c3-math-0220. The values of the c3-math-0221 depend on the value of c3-math-0222 and are given in detail in Table 3.8.

Table 3.8 Value of the Shift According to the Value of c3-math-0223 in ShiftRows

c3-math-0224

c3-math-0225

c3-math-0226

c3-math-0227

c3-math-0228

4

0

1

2

3

5

0

1

2

3

6

0

1

2

3

7

0

1

2

4

8

0

1

3

4

This table is provided only to give an idea of the general Rijndael algorithm as the AES standard sets the size of the blocks to c3-math-0229.

The overall ShiftRows stage in AES is illustrated in Figure 3.11.

nfg011

Figure 3.11 ShiftRows stage in AES

Exercise 3.7 (InvShiftrows)

Give the details of the inverse operation of this stage.

Solution on page 306.

MixColumns (State) After rotating the rows, the MixColumns transformation operates on the column a of the matrix State considering each column as a polynomial c3-math-0230 of degree 3 with coefficients in c3-math-0231. It consists in performing on each column a multiplication with c3-math-0232, or simply c3-math-0233, modulo the polynomial c3-math-0234 (the coefficients of the polynomials are elements in c3-math-0235 represented with hexadecimal numbers; for instance with c3-math-0236 represents c3-math-0237represents X, and c3-math-0238 represents simply 1). Thus, in MixColumns, one performs the following operation: c3-math-0239. From a matricial point of view, this operation (illustrated in Figure 3.12) is written as follows:

equation

nfg012

Figure 3.12 MixColumns operation in AES

Besides, as c3-math-0241 and c3-math-0242 are coprime, c3-math-0243 is actually invertible modulo c3-math-0244 and the MixColumn transformation is invertible too, which enables the decryption.

Exercise 3.8 (Flash Back to c3-math-0245 and InvMixColumns)

Let us look again at the representation of the elements in c3-math-0246 which are used in AES. The elements are written in the form of two hexadecimal digits in square brackets. Forinstance, c3-math-0247 is written c3-math-0248 in binary, c3-math-0249 or simply c3-math-0250 in hexadecimal.

1.  Compute c3-math-0251.

2.  What is the result of the Euclidean division of c3-math-0252 by c3-math-0253 in c3-math-0254?

3.  Find the inverse of c3-math-0255 in c3-math-0256.

4.  Give the algorithm for the multiplication by X in the binary form over c3-math-0257. Deduce the binary values of c3-math-0258, and c3-math-0259. Give the details of the multiplication with c3-math-0260 ?

5.  What is the value of c3-math-0261 modulo 2? Deduce the expression of c3-math-0262 modulo 2.

6.  From the two previous questions, deduce the value of c3-math-0263.

7.  In AES, the MixColumns stage is performed by multiplying the column with the polynomial c3-math-0264 modulo the polynomial c3-math-0265. Compute the polynomial Q such that c3-math-0266 with c3-math-0267.

8.  Assuming that one knows the value of two polynomials U and V such that c3-math-0268, give the Bézout relation between c and M.

9.           Practical application: given c3-math-0269 and c3-math-0270, make the reciprocal function of twothe AES MixColumns explicit. This function is denoted InvMixColumns in the sequel.

One may use the following multiplicationsc3-math-0271.

Solution on page 307.

AddRoundKey(State,Ki) This operation is a simple addition of the two matrices State and Ki. As the addition operates on elements in c3-math-0272, it is actually a bitwise eXclusive OR c3-math-0273 performed on the bytes of the matrices.

Exercise 3.9 (InvAddRoundKey)

Give the detail of the inverse operation of this stage.

Solution on page 307.

3.2.4.2 Key Schedule in AES

This stage, denoted KeySchedule, enables one to expand the encryption key K (c3-math-0274 bytes) and to obtain an expanded key W of c3-math-0275 bytes. Hence, one gets c3-math-0276 round keys (each key has c3-math-0277 bytes—see Figure 3.13).

nfg013

Figure 3.13 KeySchedule operation in AES

K and W tables can be seen as a sequence of columns of 4 bytes, as illustrated in Figure 3.14. In the sequel, we will denote c[i] (respectively k[i]) the c3-math-0278 column of W (respectively of K).

nfg014

Figure 3.14 Representation of the expanded key W as a sequence of columns

The algorithm used for the key expansion slightly differs depending on whether c3-math-0279 or c3-math-0280. In all cases, the c3-math-0281 first columns of K are copied without modifications to the c3-math-0282 first columns of W. The next columns are recursively computed from the previous columns. KeySchedule notably uses the two functions and the constant table defined as follows:

·     SubWord is a function that takes a word of 4 bytes as input and applies an SBox to each byte.

·     RotWord is a function that takes a word of 4 bytes c3-math-0283 as input and performs a cyclic permutation and outputs the word c3-math-0284.

·     The table of round constants Rcon[i] is independent of c3-math-0285 and is defined recursively by equation

Algorithm 3.2 summarizes the key schedule in AES.

ngr002

Exercise 3.10 (AES Decryption)

Give the details of the decryption of the AES system.

Solution on page 307.

Exercise 3.11 (Block Sizes and Collisions)

One recalls that several encryption modes were introduced on Section 1.3.1.

1.  ECB mode: Describe a scenario that illustrates the weakness of this mode.

2.  CBC mode:

a.  Assuming that one encrypts 35 GB of data on a hard disk using the Triple-DES in CBC mode, what is the number of cipherblocks and what is the probability of having a collision between two cipherblocks c3-math-0287 and c3-math-0288 ?

b.  How could this flaw be exploited?

c.  What about AES ? Derive a conclusion concerning the importance of the size of the blocks.

Solution on page 308.

3.2.4.3 Security of the AES

The “ Sbox” was designed to resist cryptanalysis. In particular, it does not have any fixed point c3-math-0289, nor any opposite fixed point c3-math-0290, nor any inverse fixed point c3-math-0291. In addition, the operator ShiftRows creates a high diffusion of the data by separating the initially consecutive bytes. Finally, when combined with MixColumn, it allows, after several rounds, each output bit to depend on all input bits. Besides, MixColumn is a linear code of maximum distance (see Section 4.4.1).

So far, there does not exist any significant attack on AES. However, one must temper this statement insomuch as this standard is still quite recent and it has only been submitted to worldwide cryptanalysis for a little more than 10 years. Today, the only known attacks on AES, that is to say anything that gives some information with a complexity less than brute force search, are applicable only to a reduced number of rounds when compared to those of Table 3.7.

Exercise 3.12 (Square Attack on AES-128)

Take 256 messages differing only on their first byte (the first byte is called active, while the others are called passive). Using a selected number of active bytes or bits and trying all their possible values, leads to what is called saturation attacks. Such an attack was designed for the Square cipher of which the AES is an evolution and this attack is still applicable. Suppose we apply Algorithm 3.1 of AES-128 with only four rounds, that is, c3-math-0292. The successive values of the state are denoted by capital letters and coordinate indices: the starting state is c3-math-0293, then c3-math-0294 after the first AddRoundKey, then c3-math-0295 after the first SubBytes, c3-math-0296 and ends by c3-math-0297 afterthe fifth AddRoundKey. Using the saturation we will denote by c3-math-0298 the value of the state if the first byte of the initial state was m (i.e., c3-math-0299).

1.  Suppose that c3-math-0300 is a permutation of c3-math-0301.

a.  Show that c3-math-0302.

b.  Show that c3-math-0303 and c3-math-0304 are also permutations of c3-math-0305.

2.  Using the polynomial view, show that if two columns differ only on a single byte, then all the bytes of their MixColumns must differ.

3.  Deduce from the preceding two questions that right before the third and last MixColumns, we have that c3-math-0306 is a permutation of c3-math-0307 for any c3-math-0308.

4.  Deduce that c3-math-0309, for all c3-math-0310 and c3-math-0311, for all c3-math-0312.

5.  In general, the latter does not imply that c3-math-0313 is a permutation of c3-math-0314 and c3-math-0315, for all c3-math-0316.

a.  Show that if RoundKeys[4] is known, then c3-math-0317 can be deduced from the output ciphertext c3-math-0318.

b.  Deduce a way to test independently for each byte of RoundKeys[4].

6.  What is the complexity of this attack?

Solution on page 308.