Constructions from ciphers and MACs (21 min)

In this segment, we're gonna construct
authenticated encryption systems. Since we

already have CPA secured encryption, and
we have secure MACs, the natural question

is whether we can combine the two somehow,
in order to get authenticated encryption.

And if, that's exactly what we're gonna do
in this segment. Authenticated encryption

was introduced in the year 2000, in two
independent papers that I point to at the

end of this module. But before then, many
crytpolibraries provided an API that

separately supported CPA secure
encryption, and MAC-ing. So there was one

function for implementing CPA secure
encryption. For example, CBC with a random

IV. And another function for implementing
a MAC. And then every developer that

wanted to implement encryption, had to,
himself, call separately the CPA secure

encryption scheme and the MAC scheme. In
particular, every developer had to invent

his own way of combining encryption and
MAC-ing to provide some sort of

authenticated encryption. But since the
goals of combining encryption and MAC-ing

wasn't well understood since authenticated
encryption hasn't yet been defined, it

wasn't really clear which combinations of
encryption and MAC-ing are correct and

which aren't. And so, every project as I
said had to invent its own combination.

And in fact, not all combinations were
correct. And I can tell you that the most

common mistake in software projects were
basically incorrectly combining the

encryption and integrity mechanisms. So
hopefully, by the end of this module, you

will know how to combine them correctly,
and you won't be making these mistakes

yourself. So let's look at some
combinations of CPA secure encryption and

MAC, that were introduced by different
projects. So here are three examples. So,

first of all, in all three examples,
there's a separate key for encryption, and

a separate key for MACing. These two
keys are independent of one another, and

both are generated at session setup time.
And we're gonna see how to generate these

two keys later on in the course. So the
first example is the SSL protocol. So the

way SSL combines encryption and MAC in the
hope of achieving authenticated encryption

is the following. Basically you take the
plain text, m, and then you compute a MAC

on the plain text, m. So you use your MAC
key, kI, to compute tag for this message

m. And then you can concatenate the tag to
the message and then you encrypt the

concatenation of the message and the tag
and what comes out is the actual final cipher text.

So that's option number one. The
second option is what IPsec does. So

here, you take the message. The first
thing you do is you encrypt the message.

And then, you compute a tag on the
resulting cipher text. So you notice the

tag itself is computed on the resulting
cipher text. A third option is what the

SSH protocol does. So here, the SSH takes
the message, and encrypts it using a CPA

secure encryption scheme. And then, to it,
it concatenates a tag of the message. The

difference between IPsec and SSH, is that
in IPsec, the tag is computed over the

cipher text, whereas, in SSH, the tag is
computed over the message. And so these

are three completely different ways of
combining encryption and MAC. And the

question is, which one of these is secure?
So, I will let you think about this for a

second, and then when we continue we'll do
the analysis together.

Okay. So let's start with the SSH method. So
in the SSH method you notice that the tag

is computed on the message and then
concatenated in the clear to the cipher text.

Now this is actually quite a problem
because MACs themselves are not designed

to provide confidentiality. MACs are only
designed for integrity. And in fact, there's

nothing wrong with a MAC that as part of
the tag outputs a few bits of the plain

text. Outputs a few bits of the message M.
That would be a perfectly fine tag. And yet if

we did that, that would completely break
CPA security here, because some bits of

the message are leaked in the cipher text.
And so the SSH approach, even though the

specifics of SSH are fine and the
protocol itself is not compromised by

this specific combination, generally it's
advisable not to use this approach. Simply

because the output of the MAC signing algorithm might leak bits of the message. So

now let's look at SSL and IPsec. As it
turns out, the recommended method actually

is the IPsec method. Because it turns out
no matter what CPA secure system and MAC

key you use the combination is always
gonna provide authenticated encryption.

Now let me very, very briefly explain why.
Basically what happens is once we encrypt

the message well the message contents now
is hidden inside the cipher text and now

when we compute a tag of the cipher text
basically we're locking, this tag locks

the cipher text and makes sure no one can
produce a different cipher text that would

look valid. And as a result this approach
ensures that any modifications to the

cipher text will be detected by the
decrypter simply because the MAC isn't

gonna verify. As it turns out, for the SSL
approach, there actually are kind of

pathological examples, where you combine
CPA secure encryption system with a secure

MAC. And the result is vulnerable to a
chosen cipher text attack, so that it does

not actually provide authenticated
encryption. And basically, the reason that

could happen, is that there's some sort of
a bad interaction between the encryption

scheme and the MAC algorithm. Such that,
in fact, there will be a chosen cipher

text attack. So if you're designing a new
project the recommendation now is to

always use encrypt then MAC because that
is secure no matter which CPA secure

encryption and secure MAC algorithm you're
combining. Now, just to set the

terminology, the SSL method is sometimes
called MAC-then-encrypt. And the

IPsec method is called encrypt-then-MAC.
The SSH method even though you're

not supposed to use it, is called encrypt-and-MAC. Okay, so I'll often refer to

encrypt-then-MAC, and MAC-then-encrypt to
differentiate SSL and IPsec. Okay, so

just to repeat what I've just said. The IPsec
method encrypt-then-MAC always

provides authenticated encryption. If you start
from a CPA secure cipher and a secure MAC

you will always get authenticated
encryption. As I said, MAC-then-encrypt in

fact, there are pathological cases where
the result is vulnerable to CCA attacks and

therefore does not provide authenticated
encryption. However, the story's a little

bit more interesting than that, in that,
it turns out, if you're actually using

randomized counter mode or randomized CBC,
then it turns out, for those particular

CPA secure encryption schemes, MAC-then-encrypt
actually does provide authenticated

encryption and therefore it is secure. In
fact, there's even a more interesting

twist here in that if you're using
randomized counter mode. Then, it's enough

that your MAC algorithm just be one time
secure. It doesn't have to be a fully

secure MAC. It just has to be secure when
a key is used to encrypt a single message,

okay? And when we talked about message
integrity, we saw that there are actually

much faster MACs that are one time secure
than MACs that are fully secure. As a

result, if you're using randomized counter
mode MAC-then-encrypt could actually

result in a more efficient encryption
mechanism. However, I'm going to repeat

this again. The recommendation is to use
encrypt-then-MAC and we're going to see a

number of attacks on systems that didn't
use encrypt-then-MAC. And so just to make

sure things are secure without you having
to think too hard about this. Again, I am

going to recommend that you always use
encrypt-then-MAC. Now, once the concept of

authenticated encryption became more
popular, a number of standardized

approaches for combining encryption and
MAC turned up. And those were even

standardized by the National Institute of
Standards. So I'm just gonna mention three

of these standards. Two of these were
standardized by NIST. And these are

called Galois counter mode and CBC counter
mode. And so let me explain what they do.

Galois counter mode basically uses counter
mode encryption, so a randomized counter

mode with a Carter-Wegman MAC, so a very
fact Carter-Wegman MAC. And the way the

Carter-Wegman MAC works in GCM is it's
basically a hash function of the message

that's being MACed. And then the result is
encrypted using a PRF. Now this hash

function in GCM is already quite fast to
the point where the bulk of the running

time of GCM is dominated by the counter
mode encryption and it's even made more so

in that Intel introduces a special
instruction PCLMULQDQ specifically

designed for the purpose of making the
hash function in GCM run as fast as possible.

Now CCM counter mode is another
NIST standard. It uses a CBC MAC and

then counter mode encryption. So this
mechanism, you know, this uses MAC, then

encrypt, like SSL does. So this is
actually not the recommended way of doing

things, but because counter mode
encryption is used. This is actually a

perfectly fine encryption mechanism. One
thing that I'd like to point out about

CCM, is that everything is based on AES.
You notice, it's using AES for the CBC

MAC, and it's using AES for the counter
mode encryption. And as a result, CCM can

be implemented with relatively little
code. Cause all you need is an AES engine

and nothing else. And because of this, CCM
actually was adopted by the Wi-Fi

alliance, and in fact, you're probably
using CCM on a daily basis if you're using

encrypted Wi-Fi 802.11i then you're
basically using CCM to encrypt traffic

between your laptop and the access point.
There's another mode called a EAX that

uses counter mode encryption, and then
CMAC. So, again you notice encrypt-then-MAC

and that's another fine mode to
use. We'll do a comparison of all these

modes in just a minute. Now I wanted to
mention that first of all, all these modes are

nonce-based. In other words, they don't
use any randomness but they do take as

input a nonce and the nonce has to be
unique per key. In other words, as you

remember, the pair (key, nonce)
should never ever, ever repeat. But the

nonce itself need not be random, so
it's perfectly fine to use a counter, for

example, as a nonce. And the other
important point is that, in fact, all

these modes are what's called
authenticated encryption with associated

data. This is an extension of
authenticated encryption, that comes

up very often in networking protocols. So
the idea between AEAD is that, in fact,

the message that's provided to the encryption
mode is not intended to be fully

encrypted. Only part of the message is
intended to be encrypted, but all of the

message is intended to be authenticated. A
good example of this is a network packet.

Think of like a IP packet where there's a
header and then there's a payload. And

typically the header is not gonna be
encrypted. For example, the header might

contain the destination of the packet, but
then the header had better not be

encrypted otherwise routers along the way
wouldn't know where to route the packet.

And so, typically the header is sent in
the clear, but the payload, of course, is

always encrypted, but what you'd like to
do is have the header be authenticated.

Not encrypted but authenticated. So this is
exactly what these AEAD modes do. They

will authenticate the header and then
encrypt the payload. But the header and

the payload are bound together in the
authentication so they can't

actually be separated. So this is not
difficult to do. What happens is in these

three modes GCM, CCM, and EAX, basically
the MAC is applied to the entire data. But

the encryption is only applied to the part
of the data that needs to be encrypted.

So I wanted to show you what an API
to these authenticated encryption with

associated data encryption schemes look
like. So here's what it looks like in OpenSSL.

For example, this is, an API
for GCM. So what you do is you call the

init function to initialize the encryption
mode, and you notice you give it a key and

the nonce. The nonce again,
doesn't have to be random, but it has to

be unique. And after initialization, you
would call this encrypt function, where

you see that you give it the associated
data that's gonna be authenticated, but

not encrypted. You give it the data, and
it's gonna be both authenticated and

encrypted. And it gives you back the full
cipher text, which is an encryption of the

data, but of course does not include the
AEAD, because the AEAD is gonna be sent in

the clear. So now that we understand
this mode of encrypt-then-MAC, we can go

back to the definition of MAC security and
I can explain to you something that might

have been a little obscure when we looked
at that definition. So if you remember,

one of the requirements that followed from
our definition of secure MACs meant that

given a message-MAC pair on a message M,
the attacker cannot produce another tag on

the same message M. In other words, even
though the attacker already has a tag for

the message M, he shouldn't be able to
produce a new tag for the same message M.

And it's really not clear, why does that
matter? Who cares, if the adversary already

has a tag on the message M, who cares if
he can produce another tag? Well, it turns

out if the MAC didn't have this property.
In other words, given a message-MAC pair

you can produce another MAC on
the same message, then that MAC would

result in an insecure encrypt-then-MAC mode.
And so if we want our encrypt-then-MAC to

have cipher text integrity, it's crucial
that our MAC security would imply this strong

notion of security, which, of course, it
does because we defined it correctly.

So let's see what would go wrong, if, in
fact, it was easy to produce this type of

forgery. So what I'll do is I'll show you
a chosen cipher text attack on the

resulting encrypt-then-MAC system. And
since the system has a chosen cipher text

attack on it, it necessarily means that it
doesn't provide authenticated

encryption. So let's see. So the
adversary's gonnna start by sending two

messages, M0 and M1. And he's gonna
receive, as usual, the encryption of one

of them, either the encryption of M0 or
the encryption of M1. And since we're

using encrypt-then-MAC, the adversary
receives the cipher text we'll call it C0

and a MAC on the cipher text C0.
Well now we said that given the MAC on

a message the adversary can produce
another MAC on the same message. So what

he's gonna do is he's gonna produce
another MAC on the message C0. Now he has

a new cipher text (C0,T'), which is a
perfectly valid cipher text. T' is a

valid MAC of C0. Therefore, the adversary
now can submit a chosen cipher text query

on C' and this is a valid chosen
cipher text query because it's different

from C. It's a new cipher text. The poor
challenger now is forced to decrypt this

cipher text C' so he's going to send
back the decryption of C'. It's a

valid cipher text therefore the decryption
of C prime is the message Mb but now the

attacker just learned the value of B
because he can test whether Mb is equal to

M0 or MB is equal to M1. As a result he
can just output B and he gets advantage

one in defeating the scheme. And so
again if our MAC security did not imply

this property here. Then, there would be a
chosen cipher text attack on encrypt-then-MAC.

And therefore, it would not be secure. So the
fact that we define MAC security correctly

means that encrypt-then-MAC really does
provide authenticated encryption. And

throughout all the MACs that we discussed
actually do satisfy this strong notion of

unforgeability. So, interestingly, this is
not the end of the story. So, as we said

before the concept of authenticated
encryption was introduced everyone was

just combining MACs and encryption in
various ways in the hope of achieving

some authenticated encryption. After
the notion of authenticated encryption

became formalized and rigorous, people
kind of started scratching their heads and said,

hey, wait a minute. Maybe we can achieve
authenticated encryption more efficiently

than by combining a MAC and an encryption
scheme. In fact, if you think about how

this combination of MAC and encryption
works, let's say we combine counter mode

with CMAC, then for every block of
plaintext, you first of all have to use

your block cipher for counter mode, and
then you have to use to your block cipher

again, for the CBC-MAC. This means that if
you're combining CPA secure encryption with a

MAC, for every block of plaintext, you
have to evaluate your block cipher twice,

once for the MAC and once for the
encryption scheme. So the natural question

was, can we construct an authenticated
encryption scheme directly from a PRP,

such that we would have to only evaluate
the PRP once per block? And it turns out

the answer is yes, and there's this
beautiful construction called OCB, that

pretty much does everything you want, and
is much faster than constructions that are

separately built from an encryption and a
MAC. So I wrote down, kind of a schematic

of OCB. I don't want to explain it in
detail. I'll just kind of explain it at a

high level. So here we have our input
plain text, here at the top. And you

notice that, first of all, OCB is
parallelizable, completely parallelizable.

So every block can be encrypted separately of
every other block. The other thing to

notice is that as I promised, you only
evaluate your block cipher once per plain

text block. And then you evaluate it one
more time at the end to build your

authentication tag and then the overhead
of OCB beyond just a block cipher is

minimal. All you have to do is evaluate a
certain very simple function P. The

nonce goes into the P you notice, the
key goes into this P and then there is a

block counter that goes into this P. So
you just evaluate this function P, twice

for every block and you XOR the result
before and after encryption using the

block cipher and that's it. That's all you
have to do and then you get a very fast

and efficient authenticated encryption
scheme built from a block cipher. So OCB

actually has a nice security theorem
associated with it and I am going to point

to a paper on OCB when we get to end of
this module where I list some further

reading papers that you can take a look
at. So you might be wondering if OCB is so

much better than everything you've seen so
far, all these three standards CCM, GCM and

EAX why isn't OCB being used or why isn't
OCB the standard? And the answer is a

little sad. The primary answer that
OCB is not being used is actually because

of various patents. And I'll just leave it
at that. So to conclude this section I

wanted to show you some performance
numbers. So here on the right I listed

performance numbers for modes that you
shouldn't be using. So this is for

randomized counter mode, and this is for
randomized CBC. And you can see also the

performance of CBC MAC is basically the
same as the performance of CBC encryption.

Okay. Now here are the authenticated
encryption modes, so these are the ones

that you're supposed to using, these
you're not supposed to be using on their

own, right. These two, you should never
ever use these two because they only

provide CPA security, they don't
actually provide security against active

attacks. You're only supposed to use
authenticated encryption for encryption.

And so I listed performance numbers
for the three standards. And let me remind

you that GCM basically uses a very fast
hash. And then it uses counter mode for

actual encryption. And you can see that
the overhead of GCM over counter mode is

relatively small. CCM and EAX both use a
block cipher based encryption and a

block cipher based MAC. And as a result
they're about twice as slow as counter

modes. You see that OCB is actually the
fastest of these, primarily because it

only use the block cipher once per message
block. So based on these performance

numbers, you would think that GCM is
exactly the right mode to always use. But

it turns out if you're on the space
constrained hardware, GCM is not ideal.

Primarily because its implementation
requires larger code than the other two

modes. However, as I said, Intel
specifically added instructions to speed

up GCM mode. And as a result, implementing
GCM on an Intel architecture takes

very little code. But on other hardware
platforms, say in smart cards or other

constrained environments, the code size
for implementing GCM would be considerably

larger than for the other two modes. But
if code size is not a constraint then GCM

is the right mode to use. So to summarize
this segment I want to say it one more

time that when you want to encrypt
messages you have to use an authenticated

encryption mode and the recommended way to
do it is to use one of the standards,

namely one of these three modes for
providing authenticated encryption.

Don't implement the encryption scheme yourself.
In other words don't implement

encrypt-then-MAC yourself. Just use one of these
three standards. Many crypto libraries

now provide standard API's for these three
modes and these are the one's you should

be using and nothing else. In the next
segment we're going to see what else can

go wrong when you try to implement
authenticated encryption by yourself.