Foundations of CryptographyProf. Dr. Ashish Choudhury(Former) Infosys Foundation Career Development Chair ProfessorIndian Institute of Technology-BengaluruLecture-20Practical Constructions of Block ciphers Part IIHello everyone, welcome to lecture 19. In this lecture we will continue our discussion regarding the practical constructions of block ciphers. The road map of this lecture is as follows.(Refer Slide Time: 00:46)We will see that how using SPN and Feistel network, we can design a highly popular block cipherwhich we call us DES. We will also discuss some of the pitfalls of DES and how those pitfalls motivated the construction of another popular block cipher called AES and we will see a very high level overview of AES. Before I further continue, I would like to stress here that why during all this discussion, I am continuously using the term practical constructions of block ciphers. Because this is the way we instantiate our pseudo-random functions, pseudo-random permutations and strong pseudo-random permutations in reality. However, it turns out that we do not have any provable security guarantees for the DES, triple DES, AES. It is only that ever since their discovery, no practical flaw has been identified and no security breach has been identified.And that is why we believe that DES, triple DES, AES behave like pseudo-random permutation and strong pseudo-random permutations. Whereas the constructions of pseudo-random permutations and pseudo random-functions based on one way functions that we had seen in some of our earlier lectures, they are provably secure, because we have a mathematical security proof that indeed they satisfy the definitions of pseudo-random function, pseudo-random permutations.But the reason I call those constructions as theoretical constructions, is that even though they are efficient, there running time is polynomial in the underlying security parameters. The underlying polynomials are so huge that we cannot afford them to use in practice. Whereas, the practical constructions that we are going to discuss in this lecture based on SPN, Feistel network, they are highly efficient.But the downside is that you do not have any mathematical security guarantee, you just have heuristic security guarantee, namely ever since they are discovered, no security breaches have been identified. And that is why we can safely use them to instantiate any cryptography primitive where you want to instantiate pseudo-random functions, pseudo-random permutations and so on. So let us start our discussion here.(Refer Slide Time: 03:08)So we start the discussion with respect to Data Encryption Standard or DES. It was designed by the IBM, with the help of NSA in 1970, adopted as a standard by the United States in 1977. The original form of DES operates with a key of size 56 bits and that is why it is no longer considered to be secure. Because the original form of the DES is susceptible to a brute force attack, namely if an adversary is given an (?, ?) pair or several (?, ?) pairs, where ? is the value of DES with respect to an unknown 56 bit key and input ?, where the ? input is known to the adversary. Then just by doing computations of order 256, adversary can recover back the key. So that is why the security of the original proposal of the DES was strengthened and that is how we obtained the new construction, which we call as to 3-DES, which we will also discuss in this lecture and it has a larger key size.(Refer Slide Time: 04:13)DES has got great historical importance because it is one of the best studied cryptographicalgorithms. And even though the original form of DES is susceptible to brute force attack, it isvulnerable to the brute force attack, it does not mean that it has any serious design flaw. Namelyever since 1970, no security flaw has been reported in the architecture or the design of the DES.The only complaint is that it operates with a small size key, that is all.And in this lecture, we are going to discuss only the high level ideas of the algorithm. These are not the exact details and the discussion that we are going to have in this lecture is not good forimplementation purpose. If you are interested in implementing DES, you should consult some of the relevant sources which are given in the textbook by Katz-Lindell.(Refer Slide Time: 05:12)So the DES architecture is as follows. Basically it is a 16-round Feistel network, mapping 64 bit input to 64 bit output. And the key for the Feistel network is of 56 bits. And there will be a publicly known key scheduling algorithm based on which we will be determining 48 bit round key for each of the individual iterations. So each of these individual iterations is going to use a subset of 48 bits from the master key of size 56 bits. And scheduling of which 48-bit subset of the master key I amgoing to use for each iteration will be publicly known.(Refer Slide Time: 06:01)Now let us focus on the individual round functions. So remember, as per the description of the Feistel network, the round functions could be any arbitrary round function, it need not be invertible. So if I focus on the ??ℎround function, which takes the key of size 48 bits, and a right-half of the current ?-input of 32 bits. Why 32 bits? Because remember as per the architecture of the Feistelnetwork, each current ?-input or each intermediate output, will be parsed as a collection of left part and a right part, where the left part will be of 32 bits and the right part will be 32 bits.(Refer Slide Time: 06:40)So that is why my individual round function will be a keyed function, with a 48-bit key and a 32-bit input. And it turns out that the round function is nothing, but a 1-round is SPN. And that is why you can interpret DES to be a kind of keyed permutation obtained by composing both 1-round SPN and ?-round Feistel network, where ? = 16. So in some sense, we are actually trying to get best of the both primitives here. So for the DES round function, you have a key-mixing step, you have a substitution step and you have a mixing step.(Refer Slide Time: 07:23)So now let us go a little bit deeper into the description of the DES round function. So imagine, this is the ??ℎround function. It will take a sub-key ??, determined by a publicly known key-scheduling algorithm, of size 48 bits. And it will take a block input, namely the R-part with respect to the Feistel network, whose size is 32 bits. So in SPN, the first step is the key-mixing step and in the key-mixing step, we actually perform the XOR of the sub-key with the block input. But if you see,the block input is of size 32 bits and the key size is 48 bits. So we have an incompatibility to perform the XOR operation.(Refer Slide Time: 08:10)So that is why we perform an expansion function here, which will be publicly known. And what exactly the expansion function does is, it basically duplicates half of the bits of the block input.Namely, for the 32-bit R input, some of the 16 bits of the R-input, they are duplicated to obtain a 48-bit input, which is now used to do the key-mixing step here.(Refer Slide Time: 08:34)Now once we do the key-mixing, we parse the intermediate output as a collection of 8 pieces of 6 bits each. And each of these individual 6 bits go through an S box. Now the interesting aspect here is that unlike the SPN, where we require each of the S box to be a permutation or to be a 1-to-1 onto mapping, the S boxes here, they are not invertible. Because the inputs of the S boxes are 6bits whereas the outputs of the S boxes are 4 bits.But it suffice to have S boxes like this because remember, this 1 round SPN is going to serve as the round function for a Feistel network. And for the Feistel network, we do not require the round functions to be invertible. So even though these S boxes are not invertible, it is fine. So once we obtain the output of the key-mixing step, we parse it as 8 pieces of 6 bits each, make each of the individual pieces of 6 bits go through the respective S boxes.(Refer Slide Time: 09:50)And obtain a 32-bit output and then we apply the mixing-permutation, which will be publicly known to obtain the output of the ??ℎround function. So that is the internal description of your ??ℎround function of the DES. And the S boxes and the mixing permutations that are used in each of the round functions of the Feistel network inside DES, they have very special properties. And those special properties we are going to discuss very soon. What I want to stress here is that the S boxes and the mixing permutation that are used here, they are so carefully designed, that even a minor modification can lead to severe security vulnerabilities.(Refer Slide Time: 10:37)Now let us see how exactly these S boxes in the context of DES look like. So, for your reference I am taking the first S box and I am taking the description on this first S box from Wikipedia. So, each S box you can imagine here as a 4 × 16 lookup table and each entry in the table consist of a 4-bit string. Because remember the output of an S box is a 4-bit output and each row in the table is a permutation of the set 0 to 15. So you can see here, in each of the 4 rows, you have the value of 0 to 15, occurring exactly once, but arranged in some arbitrarily looking order. And since each of the strings 0 to 15, can be represented by 4 bits, that is why I am saying that each entry in this table basically consist of 4 bits. Now how exactly we are going to access this lookup table? So remember, the input for S box is a 6-bit input.(Refer Slide Time: 11:35)So the input 6 bits of the S box, determine the entry that we are going to look for in this lookup table and how exactly we parse the 6 input bits. So the first and the last bit of the inputs of the S box, they determine your row number. So that is why you can see along the rows, I am just focusing on the first bit and the last bit, the middle 4 bits, I am not focusing. The middle 4 bits, they are used to access a particular column number. So that is why along the columns, it is the middle 4 bits which are highlighted and that is why we have 16 possible columns. Now, the way the numbers 0 to 15 are arranged in this S box is to ensure that if you change the input of the S box by 1 bit then it should result in the change of at least 2 output bits of the S box.(Refer Slide Time: 12:34)So let us see whether it is ensured or not. So let us first try to see what exactly will be the value of the first S box on the input, say 011110. So since 0 and 0 are used for row number that means we want to have the first row and then we have to go for column number 1111. So namely, we come to the last column in the first row, which has the value 7, which in Binary is 0111. And now let ussee what will be the value of this first S box on an input, say 011111, which differs from the input 011110 in exactly one bit. So the first bit and the last bit are used for accessing the row that means we have to go to the second row. And then we have to go to the column number accessed by the middle 4 bits, which 1111. So that means this will go to the last entry in the second row, which is 8, which in the Binary is 1000. And this output is different from the previous output 0111 in at least 2 bit positions. So now it is easy to see that due to the above properties, each S box defines a 4-to-1 function. And why it defines a 4-to-1 function is because you have inputs of 6 bits and you have an output of 4 bits. So that means there will be 4 inputs mapping to the same output.(Refer Slide Time: 15:06)So, the DES expansion function and the mixing permutation, they also have some important properties here. So we already discuss the properties that we required from the S box, basically they ensure that if there is a change of 1 bit of input then the output differs in at least 2 bit positions.Now the expansion function and the mixing permutation they also have some important properties.So, the mixing permutation have the property that the output of each S box will affect the input of6 S boxes in the next iteration. That means if I consider the first S box here, you have 4 output bits coming from here. And if I do a mixing permutation, the mixing permutation is designed in such a way that the output of the mixing permutation followed by the expansion function which I amgoing to apply in the next iteration ensures that there will be 6 S boxes whose inputs will be differing here.So, the expansion function, namely which 16 bits of the input are replicated, and the mixing permutations which determine the shuffling operation, both of them ensure this important property,namely the output of each S box affect the input of 6 S boxes in the next iteration. And remember that why we are interested in these special properties from the mixing permutation and S boxes.(Refer Slide Time: 16:29)Basically our goal here is to obtain good avalanche effect and just to recall what exactly is avalanche effect. The avalanche effect ensures that if you have a keyed permutation ??, constructed using a Feistel network or SPN, then you require that ?? should have the property that ??(?) and ??(?′) should differ in significant number of bit positions, even if ? and ?′ differs only in less number of bits, say even in 1 bit. And we had seen in the last lecture that if you have some special properties from the mixing permutation and from the S boxes, we can achieve this avalanche effect.(Refer Slide Time: 17:16)And that is the principle we are following in the S boxes and a mixing permutation and expansion function that we are using in DES. It turns out that 16 rounds which we are using here in the Feistelnetwork is very important. Because if you do not use a 16 round Feistel network and use a less round Feistel network, then there are easy attacks on the reduced round DES. But if you operate it with full 16 rounds, then the only complaints that have been reported till now is the short key size complaint. Namely, 256 complexity brute force can be launched, given the current computing speed.(Refer Slide Time: 17:52)Another complaint with the DES is the short block length. So the block length here is 64 bits. And now you might be wondering that how a short block length can have a consequence on the security of the overall block cipher. So recall the counter mode of operation of the block cipher, or the pseudo-random permutation. And we had seen in the CPA-security analysis of the counter mode of operation that the CPA security of the counter mode of operation depends upon with how much probability the random ?? that we use in encrypting the challenge plaintext gets repeated in any of the encryption-oracle queries. And the value of the ?? and the probability of the ?? getting repeated, depends upon the actual block length of the underlying keyed permutation. So ? is the block size here and if my block size is small than the probability of the random ?? which is used for encrypting the challenge plaintext getting repeated, becomes significantly high. So these are the 2 complaints reported with respect to the original construction of the DES. Apart from that no severe vulnerabilities have been reported till now.(Refer Slide Time: 19:16)(Refer Slide Time: 19:17)So now let us see how we can go about increasing the size of the key. Our goal will be to increase the size of the original DES. And there are 2 approaches for designing a modified block cipher or modified DES where you can operate the modified construction with a larger sized key. The first approach will be to make internal modifications to the existing design to handle larger size key.Namely, you make modifications to the existing key scheduling algorithm, you make modifications to the S boxes, you make modification to the expansion function and mixing permutations and so on.Unfortunately, this approach is not at all recommended, because it has turned out that even a slight modification to the existing DES structure has severe security consequences. So, we cannot afford to make modifications to the internal structure of the DES to ensure that we have a modified DESoperating with a larger key size. The second approach which is recommended is to actually incorporate a larger key in a black box fashion without making any internal modifications.For example, let us see how exactly a double encryption will work and the discussion that we are going to have will be very generic, it is applicable with respect to any block cipher. But for simplicity, you can always consider DES in your mind. So, imagine we have a keyed permutation which is a secure and practical block cipher, whose key size is ? bits, block length is ℓ bits andoutput size is ℓ bits.And since it is a practically secure block cipher, the best possible attack is of order 2?. Now imagine I compose this existing construction to obtain what we call as a double encryption block cipher, which now operates with a key of size 2? bits. But a block length of ℓ bits and giving an output of ℓ bits. And the way I designed this double encryption block cipher is basically I parsethe key ? for the double encryption block cipher as 2 independent parts ?1 and ?2 each of ? bits.I operate first the existing block cipher with the ?1 part with the input ? and I obtain an output ?,which is of ℓ bits. And then treat that ? output, as the input for the second invocation for the existing block cipher with the ?2 part of my double encryption block cipher key. So that is the way I am doing a double encryption.(Refer Slide Time: 22:15)And as you can see here, I am not making any modification at all in the description or the design of the existing block cipher. The existing block cipher is operated as it is, for instance if your existing ? is DES, then what we are basically trying to do here is we are trying to design double DES, where the size of the key will be now 112 bits. The first part will be ?1, the second part will be ?2. And basically what I am doing here is I am just invoking DES twice, and that is what my double DES is considered. So now we have to analyze or argue is the new double encryption block cipher that we have design is practically secure or not?(Refer Slide Time: 23:00)That means, is the best possible attack of order 22?or not?(Refer Slide Time: 23:07)Interestingly, the answer is no, and there is a very interesting attack which we call as meet in the middle attack. Where we can show that by launching this meet in the middle attack, adversary can recover the unknown key of the double encryption block cipher with a complexity of order 2?,which is much much less than 22?. So imagine that adversary has got several (?, ?) pairs.For simplicity imagine it has got one (?, ?) pair, where ? is the outcome of the double encryption block cipher with a known input ?. But with an unknown key which is a concatenation of ?1followed by ?2. And what we are going to show is an attack namely meet in the middle attack where an adversary can recover the unknown key with computation of order ? × 2?.(Refer Slide Time: 24:05)The idea here is as follows, basically adversary has to do brute force in 2 opposite directions. In the first direction, what it does is, it performs a brute force over all candidate ?1, and there are 2?candidate ?1. For each candidate ?1, it operates the existing construction ? with respect to the known input ? and obtain the intermediate outputs, which it calls the ?. And it stores all those(?1, ?) pairs in a list called ?-list or left list, that is the first brute force it performs.(Refer Slide Time: 24:46)And what it performs is that it takes the ? output which is available with the adversary and it now performs the reverse brute force. Namely it performs the brute force with respect to all candidate ?2. But with respect to the inverse of the function ? on the output ?, namely it takes each candidate ?2 and compute the inverse of the output ? available to it under that candidate ?2 and obtain the corresponding ? and store these (?2, ?) pairs in a list called R-list. So that is the second brute force it is performing.(Refer Slide Time: 25:25)So, the first brute force it performs its complexity is of order 2?, the second brute force that it has performed parallelly its complexity is of order 2?. And now, what adversary has to do is, it sorts the left list and the right list right according to the ? values.(Refer Slide Time: 22:51)And once it has the sorted ?-list and ?-list according to the ? values, what adversary basically has to do is, it has to see whether it has a (?1, ?1) pair in the ?-list and a (?2, ?2) pair in the ?-list, such that ?1 = ?2 holds. If that is the case, then the candidate ?1 concatenated with the candidate ?2is the actual candidate ? used for the double encryption. Now, what is exactly is the idea of this attack? If you see the construction of the double encryption, to do the double encryption, from ?we go to ??1(?). And then from ??(?) we would have gone to ?, namely we would have obtained ??2(??1(?)). Another way to interpret the same construction is that from ?, I could have actually performed ??−21(?). And from here, the same thing I could have obtained if I would have computed ??1(?).So, that is basically adversary is trying to do, adversary brute forcing in the forward direction, it isbrute forcing in the reverse direction. And trying to see whether for some candidate ?1 and for candidate ?2, it reaches the same point or not. And definitely there will be one candidate ?1 and one candidate ?2 where the meeting will happen. That meeting point basically gives him the candidate ?.And to obtain the meeting point adversary basically have to perform a computation of order ?2?.It has to perform 2 brute forces and then it has to do the sorting, and then it has to find down the meeting point. So, as you can see, even though we have now constructed a double encryption block cipher, with a key of size 2? bits. And we expect that the best possible attack should be of order 22?.(Refer Slide Time: 27:55)It turns out that by doing a computation of only order ?2?, the adversary can recover the key. And hence increasing the key size by doing a double encryption is not sufficient.(Refer Slide Time: 28:03)So that leads us to what we call us triple encryption. So again, imagine you have an existing, practically secure block cipher. And now we are defining a new block cipher based on triple encryption. We have 2 possible variants possible. In the first variant, we actually operate the existing secure construction with 3 independent keys of size ? bits as follows:?new?1, ?2,?3 (?) ≝ ??3(?−1?2(??1(?)))We first apply the existing construction on ? with respect to the ?1 portion of the key, whatever output I obtain, I invert it with respect to the ?2 portion, whatever output I obtain, again I apply the existing construction with respect to the ?3 portion of the key. And that is what going to be the overall output of the triple encryption with respect to the key namely ?1||?2||?3, that is the first variant.(Refer Slide Time: 29:05)The second variant actually is going to operate on with respect to only 2 independent keys of size ? bits each as follows:?new?1, ?2 (?) ≝ ??1(?−1?2(??1(?))) It will invoke, 3 invocations of the ?, the first invocation will be ??1, the second invocation will be ??−21and again, the third invocation will be ??1.(Refer Slide Time: 29:2)Now you might be wondering that why the middle invocation in both the variants is ??−1, instead of ??. Well, security wise it is not a concern, because if the existing construction ?? is a practically secure strong pseudo random permutation or block cipher, then we can prove that so is ??−1. So it does not matter whether the middle invocation is ??2or ??−21, both are sufficient as far as security is concerned.(Refer Slide Time: 30:00)The only reason that the middle invocation is an inverse function and not a forward function is to ensure backward compatibility. Namely, if I ensure that the ?1 portion of the key and the ?2 portion of the key and the ?3 portion of the key for the triple encryption block cipher are all same, then basically the triple encryption based block cipher becomes equivalent to the existing construction.That means, if my existing construction ? was DES and my triple encryption based construction is triple DES. Then if I have a software implementation of triple DES and if I want to get an effect of original DES, then I do not have to do any modification in the software implementation of triple DES, what basically I have to do is I take a key of size 3? bits where I ensure that the first portion of the key and the second portion of the key and the third portion of the key are all same.If I use the special type of key and use the software implementation of triple DES, I basically end up getting the effect of original DES.  They satisfies the definition of indistinguishability based definition.The downside is that they cannot be used practically because the running time is enormouscompared to the practical instantiations like DES and AES. Thank you.