Foundations of CryptographyProf. Dr. Ashish Choudhury(Former) Infosys Foundation Career Development Chair ProfessorInternational Institute of Information Technology-BangaloreLecture-17Modes of Operations of Block Ciphers Part IIHello everyone, welcome to lecture 16. In this lecture we will continue our discussion regarding the modes of operations of block ciphers.(Refer Slide Time: 00:36)Specifically the roadmap for this lecture is as follows, we will discuss how to design efficient CPA secure ciphers using 2 of the modes of operations, namely the output feedback mode and counter mode of operation.(Refer Slide Time: 00:50)So, let us start with the output feedback mode or OFB mode in short. So, the idea here is basically sender and receiver generate a pseudo random stream of pad, which is actually independent of the plaintext, which sender wants to encrypt. And once the pseudo random stream of pad is generated and the message is available, the pseudo random stream of pad is used for XORing or masking the message. So let us see how the pseudo random stream of pad is generated. So, the sender randomly choose an IV, which we do not as y0.And the size of the IV has to be the same as the block length of your underlying function F. And then imagine we want to generate 3 blocks of pseudo random stream of pads here is how we go. So we invoke 3 underlying invocations of the function F, all instantiated with the same key k and we feed the IV as block input for the first invocation, obtain the output y1, and then we do the chaining.But now this chaining is different from the CBC mode of encryption that we had seen in the last lecture. Here the chaining is independent of the message block because as of now, there is no actual plaintext which is getting involved here. So, the output y1 is fed as the block input for the second invocation of the function to obtain the second block of pseudo random stream of pad which we could denote as y2 and then this is fed as the block input for the third invocation.And we can continue like this right. So, this is how the pseudo random stream of pad is generated. And now if the message is available for encryption, whatever pseudo random stream of pad that has been generated till now it can be used to master message depending upon the length of the message right. So, you can imagine that encryption here is now a 2 stage process and offline process and an online process where in the offline phase or a message independent phase a pseudo random stream of pad is generated.And during the online phase when the actual message is available, we do the encryption by using whatever pad that has been generated in the offline phase as the mask right. So, if the IV is also communicated to the receiver and the receiver also can generate a pseudo random stream of pad offline and once the message is encrypted from the sender side and communicated back to the receiver it can be decrypted properly.So, in this specific example, the encryption of the message will consist of the IV and the actual encryption namely c1 c2 c3, right. And to decrypt, we do the corresponding operation namely to recover back the ith plaintext block, what we do is receiver needs the ith block of pseudo random stream of pad and which can be computed by just doing this operation and once the ith block of pseudo random stream of pad is available it can be XORed from the ith ciphertext block to recover back the plaintext.That means, it is sufficient in this mode of operation, for the F being just a pseudo random function, we do not need the function f to be an invertible function. That is of, it suffice for F(k)to be just be PRF. And the advantage of this mode of operation is that that the stream can be pre computed and once precomputed the ciphertext computation is parallelizable. That means we cannot generate the stream of pads in parallel because the pad generation happens sequentially.But once the offline phase is over and the pad is available, whatever message block we want to encrypted encryption can happen in parallel right, moreover, the another advantage here is that a plaintext may not be a multiple of the block length of your underlying function F, that means here we do not require any sophisticated padding to make the length of the message to beto be a multiple of the block length of your underlying function before encrypting the message, right.So this is unlike your CBC mode of encryption. And it can be proved formally that if your underlying keyed function F(k) is a secure PRF, then this mode of operation namely the OFB mode is CPA secure, also we can prove that a stateful variant is also CPA secure that means, imagine a scenario where sender and receiver are synchronized and they have generated a pseudo random stream of pad y1 y2 y3 and which is used to encrypt a message m right.And now, there is a new message m’ for encryption which is available for the sender. So, if the sender now wants to encrypt a message m’ using the OFB mode, there is no need to pick a fresh IV the y3 which has been used which was the last block of the pseudo random pad for the previous message can be used as the IV for the message m’ and using y3 we can kick start the whole process.And generate a fresh pseudo random stream of pad which can be then used for masking the new message m’ and it can be proved that a the stateful variant of this OFB mode is also CPA secureright. So, more or less we actually get all the advantages that we want or we expect from the best possible mode of operation. Namely, now we have CPA security, we have the minimal assumption required from the underlying function namely PRF assumption. And if we assume that the pad has been generated in the offline phase and ciphertext computation is parallelizable and so on. But it turns out that we can do better, right.(Refer Slide Time: 06:26)And further better mode of operation is the counter mode of operation of the CTR mode. And the idea here is more or less the same. Namely, we divide the encryption process into 2 phases. The first phase is the message independent phase, where a pseudo random stream of pad is generated, and which is later used to do the actual masking of the message. But now, the way the pseudo random stream of pad will be generated, everything can be parallelized.That means the pad generation as well as the actual encryption can be made parallelized. So here is how does counter mode of operation is executed. So as in the OFB mode, we start with a random IV, which we call the counter, and the counter is selected randomly from the domain of the block length of your underlying function. So it is a uniformly random bit string of length L and which will be also a part of the cipher text.And then we generate the pseudo random stream of pad, but unlike the OFB mode, we do not do any chaining here, the way we generate the pseudo random stream of pad is as follows. So, the first invocation of your function F will be with the input counter plus one, the second invocation of the function will be with the input counter plus 2 and so on. That means all the invoke subsequent invocations of the function will be with an input which is one more than the previous value of the counter used in the previous or the previous invocation of the function.And once the functions Fs are evaluated on this input, we get the pseudo random stream of blocks of pads which can be led to used to actually mask your message for the encryption right. So that is the only difference here, the way we are generating the pseudo random stream of pad, remaining all the operations remain same as in the OFB mode here. So here again, the actual encryption of the message will consist of your counter value, which will be the c0 block, and actually encryptions blocks are the encrypted blocks will be c1 c2 c3 okay.(Refer Slide Time: 08:26)So, as in the OFB mode, we can actually formally prove that it suffice for the underlying keyed function to just be a PRF over to have the counter mode of operation to be CPA secure. Because for the decryption process we do not require any inversion to be computed. So that is why itsuffice for the underlying keyed function to be just a PRF. More importantly, the encryption as well as decryption can happen in parallel. This is because when we if you see closely the way we are generating the pseudo random stream of pad.If I want to generate y2 I do not need to depend on y1 which was the case in the OFB mode, in the OFB mode and until and unless you generate, y1 you cannot compute y2 and hence until and unless y2 is computed, you cannot generate y3 and so on. So that is why the pseudo random stream of pad generation that was not parallelizable. But the way we are generating the pseudo random stream of pad and the counter mode of operation, y2 can be generated independently of y1 and so on.In that sense, both the encryption and the decryption operation can be parallelized right. More importantly in the counter mode of operation, if I want to just decrypt a specific ciphertext block, and I am not interested in decrypting the other blocks that is possible, and that to by just invoking one invocation of the underlying keyed function, for instance, if I just want to decrypt c2, for decrypting c2 what I need is y2.And y2 just requires me to invoke the underlying function on the value counter plus 2. So if I have the initial counter value, which is there in c0, and if I want to decrypt c2 what I have to do is I have to create c0 as the counter value, compute counter plus 2 invoke my underline keyedfunction on the input counter plus 2 generate the pseudo random pad y2 and XOR it from c2which will give me back m2.So, depending upon my requirement, I can decrypt any specific ciphertext block by just invoking one invocation of the underlying key function, which was not possible in the OFB mode. And more importantly, we can prove formally that the stateful variant of the counter mode of operation is also CPA secure. That means, if I have a message m, and for that my resulting ciphertext is c0, c1 c2 c3, where y3 was the last stream of pseudo random pad.And now I have a new message m’, right, so, I do not need to pick a fresh counter value to generate a pseudo random stream of pad for the message m’, I can use y3 as the counter value for generating the next sequence of pseudo random pad for the message m’, and the same can be done at the receiver end, and it can be proved formerly that the stateful variant is also CPA secure. So we have now almost exactly all the features that we required from it, good mode of operation of the block cipher.And that is why this counter mode of operation is very popular, which is used in several instantiations of the real world protocols okay.(Refer Slide Time: 11:25)So now we want to do rigorous security analysis of the CPA security for this counter mode of operation right. So, I am going to use this example. So imagine a scenario where a sender has encrypted say a message consisting of 3 blocks right and this is how the counter mode of operation would have operated. And we want to prove that this counter mode of operation is CPA secure. So before going into the actual security proof of the counter mode of operation.Let us consider a variant of this counter mode of operation where everything remains as it is in the actual counter mode of operation except that all the invocations of the key PRF are replaced by invocations of a truly random function which is an unkeyed function. So, imagine both sender and receiver have agreed upon a truly random function which is an unkeyed function, mapping L bit strings to L bit strings.So, the variant of the counter mode of operation which I denote as Π ??? is almost the same as the actual counter mode of operation except that all the invocations of the keyed function Fk are replaced by the truly invocations of the truly random function f. Now, what we are going to prove next is that, if we consider this variant of the counter mode of operation based on truly random function. And if we consider any arbitrary poly time adversary participating in an instance of CPA indistinguishability game and makes total of q(n) number of encryption oracle queries then the probability with which that adversary can win the CPA game is upper bounded by ½ + (2 q(n)2/ 2L), right. So if L is actually if we assume that L is some polynomial function of the security parameter, and anyhow q(n) is a polynomial function of the security parameter.Then overall we end up showing that the probability of any poly time adversary winning the CPA game against this truly random function based counter mode of operation is half plus negligible, which satisfies the definition of CPA security. So let us first do that. Once we do this, later on we will actually show that actual counter mode of operation which we want to prove formally to be CPA secure, is not CPA secure, Then it means that there exist a distinguisher who can distinguish apart the behavior of the keyed pseudo random function from the behavior of a truly random function and which will be a contradiction to the assumption that keyed function is a pseudo random function. So that is the overall idea of the proof, we will first consider a variant of the counter mode of operation prove it to be CPA secure formally.And then we will come back and argue that since the only difference between the actual counter mode of operation and a variant of the counter mode of operation is the underlying invocations of the function. So, the actual counter mode of operation should also be CPA secure. Otherwise, there is a distinguisher who can distinguish apart from the keyed function from the outcome of a truly random function right.(Refer Slide Time: 14:37)So, let us first proceed to prove the CPA security of the truly random function based counter mode of operation. So, consider an arbitrary computationally bounded adversary who participates in an instance of a CPA game which will consist of 4 phases, we will have pre?challenge training phase and we will have a challenge phase, right. And to answer the queries of the pre-challenge training phase basically, the challenger will select a truly random function which would not be known to that adversary right.And all those queries will be encrypted by running the encryption algorithm of the truly random function based encryption process. And then once the pair of challenge plaintexts are submitted by the adversary, the challenger will pick one of those messages randomly for encryption. And it will encrypt it by picking a random counter value, which I denote as CTR* and then c* will be basically the value of the CTR* on the truly random function XORed with the message mb.And then there will be a post challenge training phase, again, where the adversary will adaptively submit encryption oracle queries and which will be encrypted as per this modified encryption process. And finally, the adversary will output whether this challenge ciphertext is an encryption of message m0 or message m1, right. So let us assume that the total number of queries which the adversary is asking throughout this instance of this experiment is q(n).The q(n) is some polynomial function of the security parameter l. Moreover, we also assume that each query also consist of at most q(n) number of blocks. So, actually we will assume the worst case scenario where there are total of q(n) number of queries and each query is exactly consisting of q(n) number of blocks right. So, I denote the ith query for which the adversary has asked the encryption oracle service to be Mi.And since Mi consist of q(n) number of blocks adverse to answer the encryption oracle service to answer to encrypt this message Mi, the challenger need to take q(n) number of counter values. So, I denote those counter values as counter i + 1, counter i + q(n) and so on. So, the firstobservation is that if adversary submits the message Mi for encryption and c is the encryption of that message as per this variant of the counter mode of operation, then by seeing the ciphertext adversary will learn the value of the unknown truly random function on this counter values, namely counter i + 1, counter i + 2 and so on.(Refer Slide Time: 17:20)Why, so let us consider the ith query Mi which basically consist of q(n) number of blocks, rightand for encrypting that message, the challenger will pick a random counter value, which I denote as CTRi right. And once the counter value is selected, since there are q(n) number of blocks in my message mi basically the challenger needs to evaluate the truly random function on CTRi + 1, CTRi + 2 and CTRi + q(n), which will generate the sequence of pad blocks which will be XORed with the actual message blocks that are present in the message mi to generate the ciphertext blocks.And the whole cipher text will be communicated back to the adversary as the response from the encryption oracle query, since the adversary will know the value of the counter i and counter i + 1 and so on. The adversary just can simply perform this operation namely, it can XORed the jthciphertext block and the jth message block present in the message mi and that will give him the value of the unknown truly random function on this counter value namely counter i + 2 right.(Refer Slide Time: 18:32)So, since I am assuming that my adversary is going to make q(n) number of queries those queries I am representing as message m1 m2 and mq(n) and I am assuming that each of those messages further consist of q(n) number of blocks. And I assume that the our challenger in this instance of the experiment uses this counter values for encrypting these message blocks namely the first message is encrypted using the counter values CTR1 + 1, CTR1 + 2, CTR1 + q(n) so on.So, these are the counter values which are used by the challenger. And as I have seen that based on the encryption of his message the adversary learns the corresponding output of the truly random function on the corresponding counter values. So that means adversary basically have access to the value of the unknown truly random function f and all the counter values which have been used by the challenger to respond to the encryption oracle queries.Now our goal is to analyze what is the success probability of this adversary in identifying whether this challenge ciphertext is an encryption of the message m0 or whether it is an encryption of m1 and we can split this overall probability into the summation of 2 probabilities. So consider the first case when the counter values which are used to prepare the challenge ciphertext c* are different from all the counter value which have been used to respond to the encryption oracle queries raised by the adversary.That is the first case. And the second event is when the counter values which are used to prepare the challenge ciphertext overlaps or gets repeated in at least one of the instances of the encryption oracle queries namely the counter values which are used to prepare the challenge ciphertext overlaps with the counter values which have been used to respond to the adversary’sencryption oracle queries. So these are the 2 separate cases.(Refer Slide Time: 20:33)And let us take the first case and try to analyze what is the probability that in that case, adversary is able to win the CPA game right. So we are in the case when the counter values namely CTR*+ 1, CTR* + 2 and so on, which are actually used for encrypting the challenge plaintext mb are different from all the counter values which has been used to respond to adversary’s encryption oracle queries right, so we are in this case.So this is the challenge plaintext mb encrypted by evaluating first the truly random function on this counter values which have not been used so far in any of the encryption oracle queries to generate the pads. That is what our next goal is. So this will follow more or less using the same argument that we had used to prove the CPA security of our first candidate, CPA secure scheme based on the pseudo random function, right. So remember, in that proof, we had first considered a hypothetical truly random function based construction, proved its CPA security.And then we gave a reduction based argument where we showed that the difference in the winning advantage of the adversary between the 2 instances of the CPA game is upper bounded by a negligible probability if my underlying function is a pseudo random function. So we can use the same or similar argument and end up showing that the difference in the adversary winning the CPA game against the actual counter mode of operation.And the adversary winning the CPA game against a truly random function based counter mode of operation can be upper bounded by a negligible quantity. And since we know that adversary winning the CPA game against counter mode of operation is 1/2 + (2 q(n)2 / 2L) by reshuffling the term we end up getting that the counter mode of operation using the pseudo random function is also CPA security right.(Refer Slide Time: 34:05)So that is what we end up showing, and which concludes that the counter mode of operation is actually CPA secure. So, that brings me to the end of this lecture. To summarize, in this lecture, we had seen 2 of the modes of operation, namely OFB mode and counter mode of operation. And we had also seen the security proof of the counter mode of operation, the counter mode of operation has several attractive features.Namely, the encryption and the decryption can happen in parallel. And we do not require any sophisticated assumption from the underlying keyed function, it is enough or suffice for the underlying keyed function to be just a pseudo random function. And the stateful variant is also CPA secure. And these attractive features make the counter mode of operation to be used rigorously in the real world protocol. Thank you.