What block cipher mode of operation encrypts plaintext and computes a message

9.2.7 Scan Interface Encryption

A countermeasure against scan-based side channel attacks could be done through the encryption of the scan chain content [36]. These attacks use an efficient and secure block cipher placed at each scan port to decrypt/encrypt scan patterns/responses at each scan input/output, respectively.

As illustrated in Fig. 9.12, two block ciphers are inserted into the circuit. Whereas the input scan cipher decrypts test patterns provided by ATE, the output scan cipher encrypts test response before sending back to ATE. Based on this scheme, the test flow is as follows [36]:

Generate test patterns for CUT and calculate expected test responses;

Off-chip encryption of the test patterns based on pre-selected (e.g., AES) encryption algorithm and secret key;

On-the-fly decryption of the test patterns with input block cipher, then scan in patterns for CUT;

On-the-fly encryption of the test responses with output block cipher before response extraction;

Off-chip decryption of test responses to get the original responses and compare them with the expected ones.

2.1.4 Stream Ciphering with Block Ciphers

There are several kinds of modes of using block ciphers. The most studied four are the Electronic Codebook (ECB) mode, the Cipher Block Chaining (CBC) mode, the Cipher Feedback Chaining (CFB) mode, and the Output Feedback Chaining (OFB) mode [216].

In the ECB mode, a block cipher is applied block by block independently. Let M = M1M2 · · · Mt be the plaintext, then the encryption is carried out as

Ci = Eki(mi)  for i=1,2, ⋅ ⋅ ⋅ ,t.

Thus, the corresponding ciphertext is C = C1C2 · · · Ct. The decryption is then described by

Mi = Dk(ci)  for i=1,2, ⋅ ⋅ ⋅ ,t.

where Dk(x) is the inverse transformation of Ek(x). This is a rather straightforward way to use block ciphers.

In the CBC mode the blocks are chained together with an initial value IV. In this mode we assume that the plaintext and ciphertext block space are identical, and that this block space is an Abelian group with an operation +. The first ciphertext block is defined as

C1=Ek(M1+IV),

where IV is an initial value from the block space. The other ciphertext blocks are then computed as follows:

Ci=Ek(Mi+Ci−1)  for i=2,3, ⋅ ⋅ ⋅ ,t.

To decrypt, the first plaintext block is obtained as

M1 = Dk(C1) − IV,

where “−” is the inverse operation of “+”. The other plaintext blocks are then calculated as

Mi = Dk(Ci) − Ci−1 for i=2,3, ⋅ ⋅ ⋅ ,t.

Clearly, the CBC mode makes a block cipher into a stream cipher which has internal memory.

The CFB mode also uses a block cipher for stream ciphering. Assume that we have a block cipher with both plaintext and ciphertext block space An, where the alphabet (A, +) is an Abelian group. Let Ek(x) be the encryption transformation, rchopu denote the function that drops the u rightmost characters of its argument, and lchopu denote the function that drops the u leftmost characters of its argument. A simple variant of the CFB mode is described as follows. Choose m to be any integer between 1 and n. The stream cipher based on the block cipher has then the alphabet (Am, +), where the operation “+” of Am is a natural extension of the operation of A, i.e.,

(x1, ⋅ ⋅ ⋅ ,xm)+(y1, ⋅ ⋅ ⋅ ,ym)=(x1+y1,⋅ ⋅ ⋅ ,xm+ym),

where (x1, · · ·, xm) ∈ Am and (y1, · · ·, ym) ∈ Am. Under the choice of an initial value X1, the encryption of the ith plaintext character Mi ∈ Am is carried out as

Ci=Mi+rchopn−m(Ek(Xi)),   Xi+1 = lchopm(Xi)││Ci,

where || denotes the concatenation. The decryption is as follows:

Mi=Ci−rchopn−m(Ek(Xi)),   Xi+1 = lchopm(Xi)││Ci.

An internal register is needed to update Xi.

The OFB mode uses also a block cipher for stream ciphering. As in the CFB mode, we have first a block cipher with both plaintext and ciphertext block space An, where the alphabet (A, +) is an Abelian group. The stream cipher based on the block cipher is described as follows. The plaintext andciphertext alphabet of the stream cipher are Am, where m can be arbitrarily chosen between 1 and n. The stream cipher has an internal register for updating the values Xi ∈ An. Let X1 be the initial value of the register. The encryption of the ith plaintext character Mi ∈ Am is carried out as

Ci=Mi+ rchopn−m(Ek(Xi)),   Xi+1 = Ek(Xi).

The decryption is defined by

Mi=Ci−rchopn−m(Ek(Xi)),   Xi+1 = Ek(Xi).

Note that the only difference between the CFB and OFB is the updating of the internal register.

Among the above four modes of operations for block ciphers three of them result in stream ciphers. Naturally, there are many other ways to use block ciphers for stream ciphering. A nonadditive synchronous stream cipher based on block ciphers was described in the previous section. Another approach to the construction of stream ciphers based on block ciphers will be described in the following section.

10.1 Cryptographic Criteria

Boolean functions that are used in cryptographic applications (e.g., in block or stream ciphers) should satisfy special conditions as far as it is necessary for guaranteeing the security of a cipher against different kinds of cryptanalysis. The cryptographic properties of Boolean functions consist of the following: high degree, balancedness, correlation immunity and r-resilience, high nonlinearity, algebraic immunity, etc.

In general, “cryptographic properties of Boolean functions” is a great (huge!) separate theme. In this book, we do not discuss when and why distinct cryptographic criteria have appeared: we deal with them in relation to bent functions only.

Cryptographic Boolean functions and their applications have been studied in the excellent and detailed books by Cusick and Stănică [96] (2009) and Logachev et al. [247] (2004, 2012). Very informative and helpful on this topic are the chapters by Carlet [46, 47] written for the monograph Boolean Models and Methods in Mathematics, Computer Science, and Engineering (2010). In Russian, there are also monographs by Tarannikov [351] (2011) and Pankratova [295] (2014). We highly recommend them to the interested reader.

5.8 Hands-on Experiment: Hardware Trojan Attacks

4.1 Cryptography: Linear Cryptanalysis and Boolean Functions

Originally, bent functions were introduced in connection with cryptographic applications. Recall that a bent function is a Boolean function in an even number of variables that can be approximated by affine functions in an extremely bad manner. This base property of bent functions is used for protecting ciphers against linear cryptanalysis. Let us say several words about this method.

The linear cryptanalysis method for the fast data encipherment algorithm (FEAL) block cipher was proposed in 1992 by Matsui and Yamagishi [259], and for the Data Encryption Standard (DES) cipher was proposed in 1993 by Matsui [257]. Nowadays, this method (along with the differential cryptanalysis of Biham and Shamir [21]) is reputed to be one of the most efficient statistical methods. The idea of the method is as follows. First, for a known ciphering algorithm, a linear relation L on bits of a plaintext, ciphertext, and key is found that holds with probability p = 1/2 + ε far enough from 1/2 (the value ε is called here a bias). Then, for a fixed unknown key K, a cryptanalyst collects statistics of N pairs {plaintext—the corresponding ciphertext} and on the basis of the statistics, taking into account the sign of ε, distinguishes between two simple statistical hypotheses: whether or not the relation L holds for this unknown key K. As a result, a new probabilistic relation for bits of K is found. For this method to work reliably, N should be proportional to |ε|−2.

There are many papers devoted to various generalizations and applications of the linear cryptanalysis method. We describe some of them. A detailed analysis of the linear cryptanalysis method (in particular, for DES) is given by K. Nyberg; see also papers of other authors [29, 98, 151, 258]. To improve the efficiency of the linear cryptanalysis method, Kaliski and Robshaw [191] proposed considering several linear approximations for one combination of key bits; this subject was further developed by Biryukov et al. [22]. In 1997, Sakurai and Furuya [320] presented a way to improve the linear cryptanalysis method (in particular, for the LOKI91 cipher) by considering probabilistic behavior of some bits in approximation instead of their fixed values. See also [14, 203, 283, 324].

A series of papers are devoted to problems of resistance of various ciphering algorithms to linear cryptanalysis. Problems in the construction of Feistel-type ciphering schemes resistant to methods of linear and differential cryptanalysis were considered by Knudsen [202]; for SP networks such problems were studied by Heys and Tavares [164]. In 2001, it was proven by Shorin et al. [326] that the Russian GOST 28147-89 algorithm (with at least five rounds of ciphering for linear cryptanalysis, and seven rounds for differential cryptanalysis) is resistant to these methods. Resistance of the ciphers RC5, RC6, International Data Encryption Algorithm (IDEA), Serpent, Advanced Encryption Standard (AES), Blowfish, and Khufu to the linear cryptanalysis method was analyzed in [20, 23, 152, 253, 282].

In the next section, we illustrate how resistance of a cipher depends on the nonlinearities of the Boolean functions used in its construction.

16.2 Stability and Instability

Stability problems are everywhere and all around us. Every one has to stabilize his/her relations with most of the people around him/her. We have the problem of stabilizing the world. Every country has its own stability problems, which include the stability of the general welfare by taxing, the stability of political rights and social order by law, and stability amongindividuals and among different social classes. Similarly, every family has also its own stability problems. Generally, we may say that every system has its stability problems, so do cipher systems.

16.2.1 Stability and Diffusion

Many systems can be described with Figure 16.1, where whenever an input is given, a corresponding output is produced by the system, using functions which are controlled by the system parameters. One important stability problem of such systems is the study of changes in the output when the input is changed. Suppose that each input is taken from a metric space (I, + |.|1), and each output is from a metric space (O, +, |.|2), where (I, +) and (O, +) are Abelian groups with norms |.|1 and |.|2 respectively. Furthermore, suppose that the system has only one system mapping F(k1, ···, kr, i), where k = (k1, ···, kr) denotes the system parameter, which is supposed to be taken from another metric space (K, +, |.|3). Then there are two basic stability problems about the system. One is the study of the ratio

Figure 16.1. A description of cryptographic systems.

(16.2)ΔF(i1,i2)=  |F(k,i1)−F(k,i2)|2|i1−i2|1,

where k is a fixed element of K. This is a measure of the extent of change in the output relative to the change in the input, which is a stability problem for many such systems. Another stability problem is how sensitive the system is to parameter changes, which can be measured by

(16.3)ΔF(k,k′)=  |F(k,i)−F(k′,i)|2|k−k′|3,

where i is fixed. For many such continuous systems, calculus can be used to treat the two stability problems. Derivatives are measures of such stabilities. For discrete systems some mathematical tools which are analogous to calculus are needed to treat these two stability problems. The stability of the solution of some linear systems is one example of such problems.

Every cipher system may be described by the system of Figure 16.1, where the inputs are plaintexts, the outputs are ciphertexts and the system parameters are keys and/or the initial values of the internal memory state. The system functions are those which give the encryption transformation. For block ciphers, inputs and outputs are blocks of digits, say p = (p0, p1, ···, pm−1) is a plaintext block and c = (c0, c1, ···, cn−1) is the corresponding ciphertext block. Let E be the block encryption algorithm and E(k,.) the encryption transformation specified by a key k; then we have the relation

(16.4)c=E(k,p)⋅

For the sake of simplicity, we assume that both plaintext blocks and ciphertext blocks are taken from (GF(2)n, +, |.|), where |.| denotes the Hamming weight.

To guide the design of practical ciphers, Shannon suggested two general principles, which he called diffusion and confusion [397]. By diffusion, he meant the spreading out of the influence of a single plaintext digit over many ciphertext digits so as to hide the statistical structure of the plaintext. An extension of this idea is to spread the influence of a single key digit over many digits of ciphertext so as to frustrate a piecemeal attack on the key.

Thus, the concept of diffusion suggested by Shannon and its extension are in fact two kinds of instabilities which can be measured by (16.2) and (16.3) respectively, where F is the encryption algorithm. This means that Shannon's diffusion and its extension suggest designing ciphers which are not too stable with respect to both plaintext and keys. However, if we use (16.2) and (16.3) to measure the plaintext diffusion and key diffusion, it may be mathematically proven that there is a tradeoff between the extent of plaintext (key) diffusion and the nonlinearity of the encryption function E(k, p) with respect to the additions of (P, +) ((K, +)) and (C, +), where (P, +), (K, +) and (C, +) are respectively the plaintext block space, key space and ciphertext block space. This tradeoff can be seen from the discussion of Section 16.3. It follows that we have to make a compromise between diffusion and nonlinearity of the encryption transformations when designing ciphers.

By confusion, Shannon meant the use of enciphering transformations that complicate the determination of how the statistics of the ciphertext depend on the statistics of the plaintext. Thus, the nonlinearity of the enciphering transformations may be used as a partial measure of confusion. If it is rational to do so, this means there is a tradeoff between diffusion and confusion within a block cipher.

Another cryptographic stability function is the linear complexity stability of sequences which is described inSection 2.3.4.

4.3 Differential cryptanalysis

Consider the problem of encrypting short fixed length strings. In other words, let the set of possible messages be {0,1}nfor some integer n. Here n is called the block length. Typically, the value of n would be at most 256. Further, let the set of possible keys also be {0,1}kwhere k is the length of the key. In practice, the key length is at least as long as the block length and there are recommendations where the key length is longer than the block length. But, such details will not be important for explaining the basic idea.

A block cipher consists of two functions E,D:{0,1}k×{0,1}n→{0,1}nsatisfying the following two conditions:

For any K∈{0,1}k, the functions EK(·)≜E(K,·)and DK(·)≜D(K,·)are permutations of {0,1}n.

For any K∈{0,1}kand X∈{0,1}n, DK(EK(X))=X, i.e., DK is the inverse of EK.

This can be used to construct a basic encryption scheme as follows. Given an n-bit message X, and a secret key K, the ciphertext is Y=EK(X); given a ciphertext Y and a secret key K, the message is obtained as X=DK(Y). The invertibility condition ensures that the decryption can be properly done. Security depends on the actual design of the functions E and D. There is a fairly large literature on design and cryptanalysis of block ciphers and their related theory.

An exhaustive search ciphertext only attack on a block cipher can be carried out as follows. Given a ciphertext Y, attempt decryption by all possible keys and check whether the resulting message is meaningful. Given the sparseness of natural languages, there will be only one key (or at most a few keys) for which the decryption will be meaningful. With a known plaintext attack, the correct key can be uniquely found. Such an attack requires 2ntrial decryptions.

A cryptanalytic goal is to discover an attack whose work factor is lower, i.e., the time required will be less than the time required for 2ntrial decryptions. There are two basic approaches for mounting such an attack—the linear and the differential cryptanalysis. Differential cryptanalysis was introduced by Biham and Shamir (1991) while linear cryptanalysis of block ciphers was given by Matsui (1993). Both the attacks have statistical components. The attack given in Section 4.2 is also a linear cryptanalysis, though not of a block cipher. Nevertheless, it provides some idea of how a linear cryptanalysis can be carried out. Below we briefly outline how a differential cryptanalysis may be carried out on a block cipher.

The goal of differential cryptanalysis is to try and recover a subset of the key bits in time T which is substantially smaller than 2ndecryptions. Suppose t such bits can be recovered. Then the other n−tbits can certainly be recovered using exhaustive search requiring 2n−tdecryptions. This would give the overall complexity of the attack to be T+2n−t⪡2ndecryptions. Note that there can be better methods to obtain the other n−tbits. But, the point here is that if tbits can be recovered ‘easily’, then that constitutes a valid attack on the cipher. Though we mention this as the goal of differential cryptanalysis, such a top-level strategy is the goal of other cryptanalytic methods as well.

Given two messages X and X′, let ΔX=X+X′mod2, where the addition is done bit-wise. In the following, we will assume that all additions are done bit-wise and modulo 2 without explicitly mentioning this. The method of differential cryptanalysis involves finding the following two things:

Find a condition C such that Pr[C|ΔX=γ]=ε. Here the probability is over the uniform random choice of X; and X′is set to be X+γ.

There is an algorithm Awhich given a pair of inputs (X,X′)with input difference γ, the corresponding pair of outputs (Y,Y′)and a proper subset S of bits of the secret key, can efficiently determine whether the condition C holds or not. In other words, A(X,X′,Y,Y′,S)outputs 1 if C holds and outputs 0 if C does not hold.

The condition C is usually of the form ΔZ=δ, where Z (resp. Z′) is an intermediate quantity obtained during the encryption of X (resp. X′) and ΔZ=Z+Z′. The algorithm Awill then perform a partial decryption of Y and Y′using only the bits in the set S to obtain Z and Z′and check whether the difference in the two Z-values is indeed equal to δor not. The pair (γ,δ)is called a differential pair and is said to hold with probability ε. For a successful attack, it is required that ε⪢1/2n. The task of obtaining a suitable differential pair is specific to the actual design of the block cipher. It is a highly non-trivial task and involves working through the specific details of all the components. There has been substantial work in developing a theory whereby it can be shown that any differential pair for the block cipher will have sufficiently small probability.

Suppose that a proper differential pair (and the condition C) as mentioned above can be constructed. Then the scheme of a chosen plaintext attack is the following:

What is block cipher mode of operation?

What block cipher mode of operation uses the most basic approach?

Which block cipher operation mode has the property that each possible block of plaintext has a defined matching ciphertext value and vice versa?

What is an encryption/decryption scheme in which a block of plaintext is treated as a whole and used to produce a ciphertext block of equal length?