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: . 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.

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 of n characters. This scheme is a particular case of affine encryption. Given a bijective map between and , and denoting the set of invertible elements in , one is able to write the affine encryption function for a message from a key :

1. Express and .

2. Still considering and using the key (justify the use of such key), give the ciphertexts for .

3. Express the affine decryption function .

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

Alice sends a text to Bob. Tacitely, characters not belonging to 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

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 ), which is used in the Vernam code. This principle is illustrated in Figure 3.4

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 that, with a 64-bits initial value, generates 512-bits of internal state (-bits ) and 512-bits of internal counters (-bits ) with:

If we set , some 32-bits constants (), and , then the internal state evolution ( and are computed modulo ) and the random bits are given in Table 3.3.

Table 3.3 Rabbit Stream Internal State Evolution and Bit Extraction

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 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.

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 bits² 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 . Thus, one has: where contains the first 32 (most significant) bits of and 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 according to the rule:

3. 3.2

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 at the round) and the other one has 48 bits (). The round keys 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 on in order to get a ciphertext block (Notice that and 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 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. is computed and split into eight consecutive substrings of 6 bits each: . Each substring is then passed through a substitution box (the famous SBox), which outputs a block of four bits.

3. The 32-bit string is then reorganized using a determined permutation P. The result defines .

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 extracted from the initial key K. This paragraph details the algorithm that is used to generate the 16 subkeys .

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-1, where contains the 28 most significant bits of PC-1 and contains the 28 least significant bits.

2. , and () are computed recursively in the following way:

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.

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, UEPS, Universal 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, ; see Section 1.2.5) satisfies .

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 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

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

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 possible keys, that is, less than . Let us consider 1000 cores running at . Thus, it takes s (30 h) to perform 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 and . 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 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 possible encryptions of a given message M.

2. Sort the with a fast sort in steps. There are approximately operations.

3. Compute all possible decryptions of C with a single key j: ; in the same time, compare the with the (as the latter are sorted, the research requires at most steps for each by dichotomy).

4. When one finds , the target keys are and .

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 (this is called ); 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 (), which provides a security of 112 bits and is compliant with simple DES encryption taking .

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

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

For AES, , and (one easily checks that is actually an irreducible polynomial on , see Algorithm 1.8). Hence, the byte is represented by the polynomial . By extension, the polynomial 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 ), which corresponds to the eXclusive OR (XOR ) on the bytes.

· The multiplication is a multiplication of polynomials modulo .

Exercise 3.4 (Operations in )

1. One considers the bytes and (in hexadecimal notation; one can also write and if there is no ambiguity) seen as elements in .

a. Compute

b. Compute

2. 2. Now, let us use the polynomial notation. Let .

a. Give an algorithm for computing the element in corresponding to .

b. Deduce an algorithm for computing the element in .

3. Let be a generator of . In this case, any nonzero element in can be represented uniquely by . Deduce an efficient way of performing the multiplication of two elements in . Remark: For AES, 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 the number of columns of the matrix representing a block and the number of columns of the matrix representing a key.

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 columns. In the same way:

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

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

· for a key of 256 bits, the matrix has 4 lines and 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 (), 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 the number of rounds that are to be performed. This number depends on the values of and . The different configurations are given in Table 3.7.

Table 3.7 Configurations for AES

We have seen previously that AES operates on blocks that are represented with matrices of elements in . AES encryption consists of a preliminary addition with a key (AddRoundKey), followed by 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.

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 into the element .

Figure 3.10 SubBytes operation in AES

Remark: The SBox table is derived from the inverse function over . 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

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

Finally, the affine function f is defined as follows:

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 (hexadecimal notation) with the same representation convention used in AES. Compute .

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 elements, such that the element in position j in the line i is moved to the position . The values of the depend on the value of and are given in detail in Table 3.8.

Table 3.8 Value of the Shift According to the Value of in ShiftRows

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 .

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

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 of degree 3 with coefficients in . It consists in performing on each column a multiplication with , or simply , modulo the polynomial (the coefficients of the polynomials are elements in represented with hexadecimal numbers; for instance with represents represents X, and represents simply 1). Thus, in MixColumns, one performs the following operation: . From a matricial point of view, this operation (illustrated in Figure 3.12) is written as follows:

Figure 3.12 MixColumns operation in AES

Besides, as and are coprime, is actually invertible modulo and the MixColumn transformation is invertible too, which enables the decryption.

Exercise 3.8 (Flash Back to and InvMixColumns)

Let us look again at the representation of the elements in which are used in AES. The elements are written in the form of two hexadecimal digits in square brackets. Forinstance, is written in binary, or simply in hexadecimal.

1. Compute .

2. What is the result of the Euclidean division of by in ?

3. Find the inverse of in .

4. Give the algorithm for the multiplication by X in the binary form over . Deduce the binary values of , and . Give the details of the multiplication with ?

5. What is the value of modulo 2? Deduce the expression of modulo 2.

6. From the two previous questions, deduce the value of .

7. In AES, the MixColumns stage is performed by multiplying the column with the polynomial modulo the polynomial . Compute the polynomial Q such that with .

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

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

One may use the following multiplications: .

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 , it is actually a bitwise eXclusive OR 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 ( bytes) and to obtain an expanded key W of bytes. Hence, one gets round keys (each key has bytes—see Figure 3.13).

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 column of W (respectively of K).

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 or . In all cases, the first columns of K are copied without modifications to the 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 as input and performs a cyclic permutation and outputs the word .

· The table of round constants Rcon[i] is independent of and is defined recursively by

Algorithm 3.2 summarizes the key schedule in AES.

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 and ?

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 , nor any opposite fixed point , nor any inverse fixed point . 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, . The successive values of the state are denoted by capital letters and coordinate indices: the starting state is , then after the first AddRoundKey, then after the first SubBytes, and ends by afterthe fifth AddRoundKey. Using the saturation we will denote by the value of the state if the first byte of the initial state was m (i.e., ).

1. Suppose that is a permutation of .

a. Show that .

b. Show that and are also permutations of .

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 is a permutation of for any .

4. Deduce that , for all and , for all .

5. In general, the latter does not imply that is a permutation of and , for all .

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

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.