0:00

In this segment we're gonna look at another method to achieve chosen plain

Â text security that's actually superior to CBC. And this method is called randomized

Â counter mode. Unlike CBC. Randomized counter mode uses a secure PRF. It doesn't

Â need a block cypher. It's enough for counter mode to just use a PRF because

Â we're never going to be inverting this function F. So we're going to let F be the

Â secure PRF and it acts on N byte blocks. Again if we use AES, N will be 128. And

Â the way the encryption algorithm works in counter mode is it starts off by choosing

Â a random IV, that's 128 bytes random IV in the case of AES, and the essentially we

Â start counting. From this random IV, so you notice the first encryption is of IV

Â then IV+1 up to IV+L. So we generate this random pad. We XOR the result with the

Â message, and that gives us the cipher text. And, as usual, you notice that the

Â IV here is included along with the cipher text. So that, in fact, the cipher text is

Â a little longer than the original plain text. And the point, of course, is that,

Â encryption algorithm chooses a new IV for every message. And so even if I encrypt

Â the same message twice, I'm gonna get different resulting cipher texts. One

Â thing to notice that this mode is completely paralyzable, unlike CBC. CBC

Â was sequential. In other words, you couldn't encrypt block #5 until you've

Â encrypted blocks ##1 to 4, so hardware companies who might have multiple

Â AES engines working in parallel cannot actually use those AES engines when using

Â CBC because CBCs inherently sequential. So even though you might have two or three of

Â four AES engines, you could only use one of them when doing CBC encryption. With

Â counter mode, everything is completely paralyzable. If you have three AES engines

Â encryption basically will work three times as fast. So that's the beauty of counter

Â mode. And counter mode also has a corresponding nonce based counter mode.

Â Where the IV is not truly random, but rather, is just a nonce which could

Â be a counter. And the way you would implement nonce based counter mode, is you

Â would take the 128 bits block that used in AES. And then you would split it in two.

Â You would use the left 64 bits as the nonce, so the counter say would count from

Â zero to 2 to the 64. And then, that will be the nonce part of it. And then once you

Â specify the nonce, the lower order, 64 bits, would be doing the counting inside

Â of the counter modes encryption. Okay, so nonce goes on the left, and the

Â counter mode encryption counter goes on the right. And it's perfectly fine if this

Â nonce is unpredictable. The only restriction is that you encrypt at most

Â 2 to the 64 blocks using one particular nonce. The danger is that you don't

Â want this counter to reset to zero so that, then, you will have two blocks. Say,

Â this guy, this guy, and this guy that are encrypted using the same one time pad.

Â Namely this one and this one. So lets quickly state the security theorem for a

Â randomized counter mode . By now you should be used to these kind of theorems.

Â Basically we are given a secure PRF. What we end up with is an encryption scheme.

Â We'll call it E sub CTR, E sub counter mode, which is semantically secure under a

Â chosen plain text attack. It encrypts messages that are L blocks long, and

Â produces cipher text that are L+1 blocks long because the IV has to be included in

Â the cipher text. This is for randomized counter mode. And the error bounds

Â are stated over here. It's basically the same bounds as in the case of CBC

Â encryption. As usual, we argue that this term is negligible because the PRF F is

Â secure and we would like to deduce from that, that this term is negligible so that

Â E<u>CTR is secure. Unfortunately we have this error term here and so we have to make</u>

Â sure this error term is negligible. And for that we have to make sure Q squared L

Â is less than the size of a block. And remember, Q is the number of messages

Â encrypted under a particular key. And L is the maximum length of those messages. Now

Â interestingly in the case of CBC we have Q squared L squared. Has to be less than x.

Â Which is actually worse than we have for counter modes. In other words, counter

Â modes can actually be used for more. Blocks than CBC could. Lets see a quick

Â example of that. So here is, again, the error term for counter-node, and remember

Â Q is again the number of messages encrypted with a key, and L is the length

Â of those messages. And as before, just as in the case of CBC, suppose we want the

Â adversary's advantage to be at most, one over 2 to the 32. That basically requires

Â that this Q-squared, L over X be less than 1 over 2 to the 32. So for AES what

Â happens is, if you plug in the values X is 2 to 128, 128 bit blocks. So Q times

Â square root of L should be less than 2 to the 48. This is basically the bound you

Â get from plugging in 2 to the 128 into this bound here. And as a result, you can

Â see if you're encrypting messages that are each, 2 to the 32 blocks. Then after 2

Â to the 32 such messages you have to replace your secret key otherwise

Â randomized counter mode is no longer CPA secure. So this means we could encrypt a

Â total of 2 to the 64 AES blocks using a single secret key. Remember, for CBC the

Â corresponding value was 2 to the 48 blocks so in fact because counter mode has

Â a better security parameterization in fact we can use the same key to encrypt more

Â blocks with counter mode than we could with CBC. So I wanted to do a quick

Â comparison of counter mode and CBC. And argue that in every single aspect, counter

Â mode is superior to CBC. And that's actually why most modern encryption

Â schemes actually are starting to migrate to counter mode, and abandoned CBC. Even

Â though CBC is still quite widely used. So let's look at the comparison. First of

Â all, recall that CBC actually had to use a block cypher because if you look at the

Â decryption circuit, the decryption circuit actually ran the block cypher in reverse.

Â It was actually using the decryption capabilities of the block cypher. Whereas

Â in counter mode, we only use a PRF. We never ever, ever use the decryption

Â capabilities of the block cypher. We only use it in the forward direction, only

Â encrypt with it. Because of this, counter mode is actually more general and you can

Â use primitives like Salsa, for example, Salsa20, if you remember, as a PRF.

Â But is not a PRP. So counter mode can Salsa but CBC cannot. And in essence,

Â counter mode is more general than CBC. Counter mode, as we said, is actually

Â parallel, whereas CBC is a very sequential process. We said that counter mode is more

Â secure. The security bounds, the error terms are better for counter mode than

Â they are for CBC. And as a result, you can use a key to encrypt more blocks in

Â counter mode than you could with CBC. The other issue is, remember in CBC we talked

Â about the dummy padding block. If you had a message that's a multiple of the block

Â length. In CBC we said that we had to add a dummy block whereas in counter mode this

Â wasn't necessary. Although, I did want to mention that there is a variation of

Â CBC called CBC with cipher text tiling, that actually avoids the dummy block issue. So

Â for standardized CBC, we actually need a dummy block. But in fact there is a

Â modification to CBC that doesn't need a dummy block. Just like counter mode.

Â Finally, suppose you're encrypting just a stream of one byte messages, and using

Â nonce encryption with an implicit nonce. So, the nonce is not

Â included in the cipher text. In this case. Every single one byte message would have

Â to be expanded into a sixteen byte block and then encrypted, and the result would

Â be a sixteen byte block. So if you have, like, a stream of 100 one byte messages,

Â each one separately would have to become a sixteen byte block. And you'll end up.

Â With a stream of 116 byte cipher texts. So you get a 16x expansion on the length of

Â the cipher text, compared to the length of the plain text. In counter mode, of

Â course, this is not a problem. You would just encrypt each one byte message by

Â XORing with the first bytes of the stream that's generated in the counter mode. So

Â every cipher text would just be one byte, just like the corresponding plain text.

Â And so no expansion at all, using counter mode. So you see that essentially, every

Â single aspect counter mode dominates CBC. And that's why it's actually the

Â recommended mode to be using today. Okay, so this concludes our discussion of chosen

Â plaintext security. I wanted to just quickly summarize and remind you that

Â we're going to be using these PRP and PRF abstractions of block ciphers.

Â This is actually the correct way of thinking of block ciphers and so we'll

Â always think of them as either pseudorandom permutations or pseudorandom

Â functions. And then I wanted to remind you again that, so far, we saw two notions of

Â security. Both only provide security against eavesdropping. They don't provide

Â security against tampering with the cipher text. One was used when the key is only

Â used to encrypt a single message. The other one was used when the key was used

Â to encrypt multiple messages. And as we said, because neither one is designed to

Â defend against tampering, neither one provides data integrity. And we're going

Â to see this as a real problem. And as a result, in fact, I'm going to say in the

Â next segment that these modes actually should never, ever be used. You should

Â only be using these modes in addition to an integrity mechanism, which is our next

Â topic. Okay, so, so far we've seen basically for using a, the key once, you

Â can use stream ciphers or you can use deterministic counter mode. If you're

Â gonna use the key many times you could use randomize CBC or randomize counter mode

Â and we're gonna talk about how to provide integrity and confidentiality. Once we

Â cover the topic of integrity, which is our next module.

Â