Attacking non-atomic decryption (10 min)

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.