In the last segment, we looked at a padding Oracle attack that completely breaks an authenticated encryption system. I hope this attack convinces you that you shouldn't implement authenticated encryption on your own cause you might end up exposing yourself to a padding oracle attack or a timing attack or any other such attack. Instead you should be using standards like GCM or any other of the standardized authenticated encryption modes as implemented in many crypto libraries. In this segment, I'm gonna show you another very clever attack on an authenticated encryption system. And I hope after you see this attack, you'll be completely convinced not to invent and implement your own authenticated encryption systems. But instead, always use one of the standard schemes, like GCM or others. So this particular attack that I want to show you is an attack on the SSH binary packet protocol. So SSH is a standard secure remote shell application that uses a protocol between a client and the sever. It has a key exchange mechanism and once two sides exchange keys, SSH uses what's called the binary packet protocol to send messages back and forth between the client and the server. Now here is how SSH works, so recall that SSH uses what we called encrypt-and-MAC. Okay so technically what happens is every SSH packet begins with a sequence number, and then the packet contains the packet length, the length of the CBC pad, the actual payload follows, then the CBC pad follows. Now this whole red block here is CBC encrypted also with a chained IV, so this is also vulnerable to the CPA attacks that we discussed before. But nevertheless, this whole red packet is encrypted using CBC encryption. And then the entire clear text packet is MAC-ed. And the MAC is sent in the clear, along with the packet. So I want you to remember that the MAC is computed over plain text packets, and then the MAC is sent in the clear. This is what we call encrypt-and-MAC. And we said that this is not a good way to do things, because MACs have no confidentiality requirements. And by sending the MAC of the clear text in the clear, you might be exposing information about the clear text. But this is not the mistake that I want to show you here. I want to show you a much more clever attack. So first, let's look at how decryption works in SSH. So what happens is, first of all, the server decrypts the encrypted packet length field only. So it only decrypts these particular first few bytes. Then it will go ahead and read from the network, as many bytes as specified in the packet length field. It's gonna decrypt the remaining cipher text blocks using CBC decryption. Then, once it's recovered the entire SSH packet, it will go ahead and check the MAC of the plain text, and report an error if the MAC happens to be invalid. Now the problem here is that the packet length field is decrypted and then used directly to determine the length of the packet before any authentication has taken place. In fact, it's not possible to verify the MAC of the packet length field because we haven't recovered the entire packet yet and as a result we cannot check the MAC. But nevertheless the protocol uses the packet length before verifying that the MAC is valid. So it turns out this introduces a very, very cute attack. And I'm only gonna describe a very simplified version of this attack, just to get the idea across. So here's the idea. Suppose the attacker intercepted a particular cipher text block, namely the direct AES encryption of the message block M. And now he wants to recover this M. And I emphasize that this intercepted cipher text is only one block length. It's one AES block. So here's what the attacker is gonna do. Well, he's gonna send a packet to the server that starts off as normal. It's basically, starts off with a sequence number and then he's going to inject his captured cipher text as the first cipher text block that's sent to the server. Now, what is the server going to do? The server is gonna decrypt the first few bytes of this first AES block and he's going to interpret the first few bytes as the length fields of the packet. The next thing that's gonna happen is, the server is gonna expect this many bytes, before it checks that the MAC is valid. And so what the attacker is gonna do, is, he's gonna feed the server one byte at a time. So the server will read one byte, and then another byte, and then another byte. Eventually, the server will read as many bytes as the length field specifies, at which point, it will check that the MAC is valid. And of course, the attacker was just feeding the server junk bytes. And as a result, the MAC is not gonna verify, and the server will send a MAC error. But you realize that what happened here, the attacker was counting how many bytes it sent to the server. And so it knows exactly how many bytes were sent at the time that it receives the MAC error from the server. So that tells it that the decryption of the first 32 bits of its cypher text C are exactly equal to the number of bytes that were sent before it saw the MAC error. So this is a very clever attack. So let me say it one more time to make sure this is clear. So again, the attacker has a one block cipher text C that it wants to decrypt and let's pretend that when C is decrypted the 32 most significant bits of the plain text happen to be the number five. In this case, what the attacker will see, is the following behavior. The server is gonna decrypt the challenge block c and he's gonna obtain the number five as the length field. So, now, the attacker is gonna feed the server one byte at a time and after the attacker feeds the server five bytes the server says, hey, I've just recovered the entire packet, let me check the MAC. The MAC is likely to be false and, then, it will send, bad MAC error. So after five bytes are read off the network the attacker is gonna see a bad MAC error and then the attacker learns that the most significant 32 bits of the decrypted block is equal to the number five. So there. So, you just learned the 32 most significant bits of C. So this is a very significant attack, because the attacker just learned 32 bits of the decrypted cipher text block. And since he can apply this attack to any cipher text block he wants, he can basically learn the first 32 bits of every cipher text block in a very long message. So what just happened here? Well, there are actually two things that were wrong in this design. The first one is the decryption operation is non-atomic. In other words, the decryption algorithm doesn't take a whole packet as input, and respond with a whole plain text as output, or with the word reject. Instead, the decryption algorithm partially decrypts the cipher text, namely to obtain the length field, and then it waits to recover as many bytes as needed and then it completes the decryption process. So these nonatomic decryption operations are fairly dangerous, and generally, they should be avoided. In this example, this nonatomic decryption happens to break authenticated encryption. The other problem that happened is that the length field was used before it was properly authenticated. And this is another issue that should never be done. So the encryption field should never be used before the field is actually authenticated. So let me ask you, if you had the option of redesigning SSH what is the minimum change that you would do to make SSH resist this attack? And let me tell you that multiple answers might be correct. One option is to send a length field in the clear, just as in the case of TLS. In this case, there's no opportunity for an attacker to submit chosen cipher text attack, because, well, the length field is never decrypted. And so there's no decryption taking place that the attacker can abuse. Replacing encrypt-and-MAC by encrypt-then-MAC doesn't have any impact because this attack would apply either way. The problem is that the length field is used before it's authenticated and that would have to happen either way. So a better mode of encryption doesn't actually help. Another option is to MAC the length field separately so that now the server can read the length field, check that the MAC for just the length field is valid, and then it would know how many subsequent bytes to read before checking MAC field on the entire packet. The last option is actually one that works, but is terribly inefficient, and it would expose the server to a denial of service attack, so I'm not going to mark it as a valid answer. So the main lesson to remember is, don't implement or design your own authenticated encryption system. Just use the standards like GCM. But if for some reason, you can't use the standards, and you have to implement your own authenticated encryption system, then use encrypt-then-MAC. And make sure not to repeat the mistakes of the last two segments, namely don't use a length field before the length field is authenticated. And more generally, don't use any decrypted field before that field is authenticated. Okay so this is the end of our discussion of authenticated encryption. I wanted to point out a couple of papers on authenticated encryption that you could use as further reading. The first one is a very cute one on the order of encryption and authentication that talks about whether one should do encrypt-then-MAC or MAC-then-encrypt and it shows that one is correct and one is incorrect. It's a good read and there's a lot of information in that paper. The second discusses OCB mode, which is a very efficient way of building authenticated encryption. In particular, it looks at a variant of OCB with associated data as we discussed when we described OCB. The last three papers are attack papers. The first one describes the padding oracle attack that we discussed in the last segment. This one here describes the length attack that we just described in this segment. And the last one describes a number of attacks on encryptions that just use CPA security without adding integrity. So this last paper actually provides a number of good examples for why CPA security by itself should never, ever, ever be used for encryption. Remember the only thing you're allowed to use is authenticated encryption for confidentiality. Or if all you need is integrity with no confidentiality then you just use a MAC.
