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.

Modes of Operation: Many Time Key (CTR)

Cryptography I

与讲师见面