[Script Info]
Title: 
[Events]
Format: Layer, Start, End, Style, Name, MarginL, MarginR, MarginV, Effect, Text
Dialogue: 0,0:00:00.00,0:00:03.84,Default,,0000,0000,0000,,In this segment, we're gonna construct\Nauthenticated encryption systems. Since we
Dialogue: 0,0:00:03.84,0:00:08.25,Default,,0000,0000,0000,,already have CPA secured encryption, and\Nwe have secure MACs, the natural question
Dialogue: 0,0:00:08.25,0:00:12.82,Default,,0000,0000,0000,,is whether we can combine the two somehow,\Nin order to get authenticated encryption.
Dialogue: 0,0:00:12.82,0:00:15.72,Default,,0000,0000,0000,,And if, that's exactly what we're gonna do\Nin this segment. Authenticated encryption
Dialogue: 0,0:00:15.72,0:00:20.45,Default,,0000,0000,0000,,was introduced in the year 2000, in two\Nindependent papers that I point to at the
Dialogue: 0,0:00:20.45,0:00:25.92,Default,,0000,0000,0000,,end of this module. But before then, many\Ncrytpolibraries provided an API that
Dialogue: 0,0:00:25.92,0:00:31.22,Default,,0000,0000,0000,,separately supported CPA secure\Nencryption, and MAC-ing. So there was one
Dialogue: 0,0:00:31.22,0:00:36.18,Default,,0000,0000,0000,,function for implementing CPA secure\Nencryption. For example, CBC with a random
Dialogue: 0,0:00:36.18,0:00:41.14,Default,,0000,0000,0000,,IV. And another function for implementing\Na MAC. And then every developer that
Dialogue: 0,0:00:41.14,0:00:45.65,Default,,0000,0000,0000,,wanted to implement encryption, had to,\Nhimself, call separately the CPA secure
Dialogue: 0,0:00:45.65,0:00:50.55,Default,,0000,0000,0000,,encryption scheme and the MAC scheme. In\Nparticular, every developer had to invent
Dialogue: 0,0:00:50.55,0:00:55.70,Default,,0000,0000,0000,,his own way of combining encryption and\NMAC-ing to provide some sort of
Dialogue: 0,0:00:55.70,0:00:59.38,Default,,0000,0000,0000,,authenticated encryption. But since the\Ngoals of combining encryption and MAC-ing
Dialogue: 0,0:00:59.38,0:01:03.69,Default,,0000,0000,0000,,wasn't well understood since authenticated\Nencryption hasn't yet been defined, it
Dialogue: 0,0:01:03.69,0:01:08.50,Default,,0000,0000,0000,,wasn't really clear which combinations of\Nencryption and MAC-ing are correct and
Dialogue: 0,0:01:08.50,0:01:13.24,Default,,0000,0000,0000,,which aren't. And so, every project as I\Nsaid had to invent its own combination.
Dialogue: 0,0:01:13.24,0:01:17.20,Default,,0000,0000,0000,,And in fact, not all combinations were\Ncorrect. And I can tell you that the most
Dialogue: 0,0:01:17.20,0:01:22.56,Default,,0000,0000,0000,,common mistake in software projects were\Nbasically incorrectly combining the
Dialogue: 0,0:01:22.56,0:01:27.02,Default,,0000,0000,0000,,encryption and integrity mechanisms. So\Nhopefully, by the end of this module, you
Dialogue: 0,0:01:27.02,0:01:31.26,Default,,0000,0000,0000,,will know how to combine them correctly,\Nand you won't be making these mistakes
Dialogue: 0,0:01:31.26,0:01:35.17,Default,,0000,0000,0000,,yourself. So let's look at some\Ncombinations of CPA secure encryption and
Dialogue: 0,0:01:35.17,0:01:39.30,Default,,0000,0000,0000,,MAC, that were introduced by different\Nprojects. So here are three examples. So,
Dialogue: 0,0:01:39.30,0:01:43.82,Default,,0000,0000,0000,,first of all, in all three examples,\Nthere's a separate key for encryption, and
Dialogue: 0,0:01:43.82,0:01:47.77,Default,,0000,0000,0000,,a separate key for MACing. These two\Nkeys are independent of one another, and
Dialogue: 0,0:01:47.77,0:01:52.22,Default,,0000,0000,0000,,both are generated at session setup time.\NAnd we're gonna see how to generate these
Dialogue: 0,0:01:52.22,0:01:57.07,Default,,0000,0000,0000,,two keys later on in the course. So the\Nfirst example is the SSL protocol. So the
Dialogue: 0,0:01:57.07,0:02:02.68,Default,,0000,0000,0000,,way SSL combines encryption and MAC in the\Nhope of achieving authenticated encryption
Dialogue: 0,0:02:02.68,0:02:07.66,Default,,0000,0000,0000,,is the following. Basically you take the\Nplain text, m, and then you compute a MAC
Dialogue: 0,0:02:07.66,0:02:13.42,Default,,0000,0000,0000,,on the plain text, m. So you use your MAC\Nkey, kI, to compute tag for this message
Dialogue: 0,0:02:13.42,0:02:17.79,Default,,0000,0000,0000,,m. And then you can concatenate the tag to\Nthe message and then you encrypt the
Dialogue: 0,0:02:17.79,0:02:22.58,Default,,0000,0000,0000,,concatenation of the message and the tag\Nand what comes out is the actual final cipher text.
Dialogue: 0,0:02:22.58,0:02:26.71,Default,,0000,0000,0000,,So that's option number one. The\Nsecond option is what IPsec does. So
Dialogue: 0,0:02:26.71,0:02:31.16,Default,,0000,0000,0000,,here, you take the message. The first\Nthing you do is you encrypt the message.
Dialogue: 0,0:02:31.16,0:02:35.69,Default,,0000,0000,0000,,And then, you compute a tag on the\Nresulting cipher text. So you notice the
Dialogue: 0,0:02:35.69,0:02:40.24,Default,,0000,0000,0000,,tag itself is computed on the resulting\Ncipher text. A third option is what the
Dialogue: 0,0:02:40.24,0:02:45.43,Default,,0000,0000,0000,,SSH protocol does. So here, the SSH takes\Nthe message, and encrypts it using a CPA
Dialogue: 0,0:02:45.43,0:02:50.94,Default,,0000,0000,0000,,secure encryption scheme. And then, to it,\Nit concatenates a tag of the message. The
Dialogue: 0,0:02:50.94,0:02:55.57,Default,,0000,0000,0000,,difference between IPsec and SSH, is that\Nin IPsec, the tag is computed over the
Dialogue: 0,0:02:55.57,0:02:59.99,Default,,0000,0000,0000,,cipher text, whereas, in SSH, the tag is\Ncomputed over the message. And so these
Dialogue: 0,0:02:59.99,0:03:04.54,Default,,0000,0000,0000,,are three completely different ways of\Ncombining encryption and MAC. And the
Dialogue: 0,0:03:04.54,0:03:09.09,Default,,0000,0000,0000,,question is, which one of these is secure?\NSo, I will let you think about this for a
Dialogue: 0,0:03:09.09,0:03:12.10,Default,,0000,0000,0000,,second, and then when we continue we'll do\Nthe analysis together.
Dialogue: 0,0:03:13.20,0:03:17.16,Default,,0000,0000,0000,,Okay. So let's start with the SSH method. So \Nin the SSH method you notice that the tag
Dialogue: 0,0:03:17.16,0:03:21.63,Default,,0000,0000,0000,,is computed on the message and then \Nconcatenated in the clear to the cipher text.
Dialogue: 0,0:03:21.63,0:03:26.41,Default,,0000,0000,0000,,Now this is actually quite a problem \Nbecause MACs themselves are not designed
Dialogue: 0,0:03:26.41,0:03:30.78,Default,,0000,0000,0000,,to provide confidentiality. MACs are only \Ndesigned for integrity. And in fact, there's
Dialogue: 0,0:03:30.78,0:03:36.01,Default,,0000,0000,0000,,nothing wrong with a MAC that as part of\Nthe tag outputs a few bits of the plain
Dialogue: 0,0:03:36.01,0:03:41.46,Default,,0000,0000,0000,,text. Outputs a few bits of the message M.\NThat would be a perfectly fine tag. And yet if
Dialogue: 0,0:03:41.46,0:03:46.67,Default,,0000,0000,0000,,we did that, that would completely break\NCPA security here, because some bits of
Dialogue: 0,0:03:46.67,0:03:51.82,Default,,0000,0000,0000,,the message are leaked in the cipher text.\NAnd so the SSH approach, even though the
Dialogue: 0,0:03:51.82,0:03:56.60,Default,,0000,0000,0000,,specifics of SSH are fine and the\Nprotocol itself is not compromised by
Dialogue: 0,0:03:56.60,0:04:00.82,Default,,0000,0000,0000,,this specific combination, generally it's\Nadvisable not to use this approach. Simply
Dialogue: 0,0:04:00.82,0:04:05.93,Default,,0000,0000,0000,,because the output of the MAC signing algorithm might leak bits of the message. So
Dialogue: 0,0:04:05.93,0:04:11.48,Default,,0000,0000,0000,,now let's look at SSL and IPsec. As it\Nturns out, the recommended method actually
Dialogue: 0,0:04:11.48,0:04:16.56,Default,,0000,0000,0000,,is the IPsec method. Because it turns out\Nno matter what CPA secure system and MAC
Dialogue: 0,0:04:16.56,0:04:21.13,Default,,0000,0000,0000,,key you use the combination is always\Ngonna provide authenticated encryption.
Dialogue: 0,0:04:21.13,0:04:26.07,Default,,0000,0000,0000,,Now let me very, very briefly explain why.\NBasically what happens is once we encrypt
Dialogue: 0,0:04:26.07,0:04:31.00,Default,,0000,0000,0000,,the message well the message contents now\Nis hidden inside the cipher text and now
Dialogue: 0,0:04:31.00,0:04:35.76,Default,,0000,0000,0000,,when we compute a tag of the cipher text\Nbasically we're locking, this tag locks
Dialogue: 0,0:04:35.76,0:04:40.82,Default,,0000,0000,0000,,the cipher text and makes sure no one can\Nproduce a different cipher text that would
Dialogue: 0,0:04:40.82,0:04:45.31,Default,,0000,0000,0000,,look valid. And as a result this approach\Nensures that any modifications to the
Dialogue: 0,0:04:45.31,0:04:49.56,Default,,0000,0000,0000,,cipher text will be detected by the\Ndecrypter simply because the MAC isn't
Dialogue: 0,0:04:49.56,0:04:54.03,Default,,0000,0000,0000,,gonna verify. As it turns out, for the SSL\Napproach, there actually are kind of
Dialogue: 0,0:04:54.03,0:04:59.35,Default,,0000,0000,0000,,pathological examples, where you combine\NCPA secure encryption system with a secure
Dialogue: 0,0:04:59.35,0:05:03.54,Default,,0000,0000,0000,,MAC. And the result is vulnerable to a\Nchosen cipher text attack, so that it does
Dialogue: 0,0:05:03.54,0:05:07.98,Default,,0000,0000,0000,,not actually provide authenticated\Nencryption. And basically, the reason that
Dialogue: 0,0:05:07.98,0:05:12.82,Default,,0000,0000,0000,,could happen, is that there's some sort of\Na bad interaction between the encryption
Dialogue: 0,0:05:12.82,0:05:17.32,Default,,0000,0000,0000,,scheme and the MAC algorithm. Such that,\Nin fact, there will be a chosen cipher
Dialogue: 0,0:05:17.32,0:05:21.75,Default,,0000,0000,0000,,text attack. So if you're designing a new\Nproject the recommendation now is to
Dialogue: 0,0:05:21.75,0:05:26.16,Default,,0000,0000,0000,,always use encrypt then MAC because that\Nis secure no matter which CPA secure
Dialogue: 0,0:05:26.16,0:05:30.61,Default,,0000,0000,0000,,encryption and secure MAC algorithm you're\Ncombining. Now, just to set the
Dialogue: 0,0:05:30.61,0:05:37.100,Default,,0000,0000,0000,,terminology, the SSL method is sometimes\Ncalled MAC-then-encrypt. And the
Dialogue: 0,0:05:37.100,0:05:45.04,Default,,0000,0000,0000,,IPsec method is called encrypt-then-MAC.\NThe SSH method even though you're
Dialogue: 0,0:05:45.04,0:05:51.90,Default,,0000,0000,0000,,not supposed to use it, is called encrypt-and-MAC. Okay, so I'll often refer to
Dialogue: 0,0:05:51.90,0:05:57.00,Default,,0000,0000,0000,,encrypt-then-MAC, and MAC-then-encrypt to\Ndifferentiate SSL and IPsec. Okay, so
Dialogue: 0,0:05:57.00,0:06:02.11,Default,,0000,0000,0000,,just to repeat what I've just said. The IPsec\Nmethod encrypt-then-MAC always
Dialogue: 0,0:06:02.11,0:06:07.16,Default,,0000,0000,0000,,provides authenticated encryption. If you start \Nfrom a CPA secure cipher and a secure MAC
Dialogue: 0,0:06:07.16,0:06:11.11,Default,,0000,0000,0000,,you will always get authenticated\Nencryption. As I said, MAC-then-encrypt in
Dialogue: 0,0:06:11.11,0:06:15.74,Default,,0000,0000,0000,,fact, there are pathological cases where\Nthe result is vulnerable to CCA attacks and
Dialogue: 0,0:06:15.74,0:06:20.31,Default,,0000,0000,0000,,therefore does not provide authenticated\Nencryption. However, the story's a little
Dialogue: 0,0:06:20.31,0:06:24.65,Default,,0000,0000,0000,,bit more interesting than that, in that,\Nit turns out, if you're actually using
Dialogue: 0,0:06:24.65,0:06:29.22,Default,,0000,0000,0000,,randomized counter mode or randomized CBC,\Nthen it turns out, for those particular
Dialogue: 0,0:06:29.22,0:06:33.62,Default,,0000,0000,0000,,CPA secure encryption schemes, MAC-then-encrypt\Nactually does provide authenticated
Dialogue: 0,0:06:33.62,0:06:38.03,Default,,0000,0000,0000,,encryption and therefore it is secure. In\Nfact, there's even a more interesting
Dialogue: 0,0:06:38.03,0:06:42.33,Default,,0000,0000,0000,,twist here in that if you're using\Nrandomized counter mode. Then, it's enough
Dialogue: 0,0:06:42.33,0:06:46.80,Default,,0000,0000,0000,,that your MAC algorithm just be one time\Nsecure. It doesn't have to be a fully
Dialogue: 0,0:06:46.80,0:06:51.56,Default,,0000,0000,0000,,secure MAC. It just has to be secure when\Na key is used to encrypt a single message,
Dialogue: 0,0:06:51.56,0:06:56.09,Default,,0000,0000,0000,,okay? And when we talked about message\Nintegrity, we saw that there are actually
Dialogue: 0,0:06:56.09,0:07:00.58,Default,,0000,0000,0000,,much faster MACs that are one time secure\Nthan MACs that are fully secure. As a
Dialogue: 0,0:07:00.58,0:07:04.45,Default,,0000,0000,0000,,result, if you're using randomized counter\Nmode MAC-then-encrypt could actually
Dialogue: 0,0:07:04.45,0:07:08.19,Default,,0000,0000,0000,,result in a more efficient encryption\Nmechanism. However, I'm going to repeat
Dialogue: 0,0:07:08.19,0:07:12.21,Default,,0000,0000,0000,,this again. The recommendation is to use\Nencrypt-then-MAC and we're going to see a
Dialogue: 0,0:07:12.21,0:07:16.09,Default,,0000,0000,0000,,number of attacks on systems that didn't\Nuse encrypt-then-MAC. And so just to make
Dialogue: 0,0:07:16.09,0:07:20.12,Default,,0000,0000,0000,,sure things are secure without you having\Nto think too hard about this. Again, I am
Dialogue: 0,0:07:20.12,0:07:24.12,Default,,0000,0000,0000,,going to recommend that you always use\Nencrypt-then-MAC. Now, once the concept of
Dialogue: 0,0:07:24.12,0:07:27.76,Default,,0000,0000,0000,,authenticated encryption became more\Npopular, a number of standardized
Dialogue: 0,0:07:27.76,0:07:31.61,Default,,0000,0000,0000,,approaches for combining encryption and\NMAC turned up. And those were even
Dialogue: 0,0:07:31.61,0:07:35.98,Default,,0000,0000,0000,,standardized by the National Institute of\NStandards. So I'm just gonna mention three
Dialogue: 0,0:07:35.98,0:07:41.03,Default,,0000,0000,0000,,of these standards. Two of these were\Nstandardized by NIST. And these are
Dialogue: 0,0:07:41.03,0:07:46.14,Default,,0000,0000,0000,,called Galois counter mode and CBC counter\Nmode. And so let me explain what they do.
Dialogue: 0,0:07:46.14,0:07:51.24,Default,,0000,0000,0000,,Galois counter mode basically uses counter\Nmode encryption, so a randomized counter
Dialogue: 0,0:07:51.24,0:07:56.16,Default,,0000,0000,0000,,mode with a Carter-Wegman MAC, so a very\Nfact Carter-Wegman MAC. And the way the
Dialogue: 0,0:07:56.16,0:08:01.15,Default,,0000,0000,0000,,Carter-Wegman MAC works in GCM is it's\Nbasically a hash function of the message
Dialogue: 0,0:08:01.15,0:08:06.31,Default,,0000,0000,0000,,that's being MACed. And then the result is\Nencrypted using a PRF. Now this hash
Dialogue: 0,0:08:06.31,0:08:11.56,Default,,0000,0000,0000,,function in GCM is already quite fast to\Nthe point where the bulk of the running
Dialogue: 0,0:08:11.56,0:08:15.84,Default,,0000,0000,0000,,time of GCM is dominated by the counter\Nmode encryption and it's even made more so
Dialogue: 0,0:08:15.84,0:08:22.37,Default,,0000,0000,0000,,in that Intel introduces a special\Ninstruction PCLMULQDQ specifically
Dialogue: 0,0:08:22.37,0:08:27.43,Default,,0000,0000,0000,,designed for the purpose of making the\Nhash function in GCM run as fast as possible.
Dialogue: 0,0:08:27.43,0:08:32.95,Default,,0000,0000,0000,,Now CCM counter mode is another\NNIST standard. It uses a CBC MAC and
Dialogue: 0,0:08:32.95,0:08:37.28,Default,,0000,0000,0000,,then counter mode encryption. So this\Nmechanism, you know, this uses MAC, then
Dialogue: 0,0:08:37.28,0:08:40.91,Default,,0000,0000,0000,,encrypt, like SSL does. So this is\Nactually not the recommended way of doing
Dialogue: 0,0:08:40.91,0:08:44.02,Default,,0000,0000,0000,,things, but because counter mode\Nencryption is used. This is actually a
Dialogue: 0,0:08:44.02,0:08:47.94,Default,,0000,0000,0000,,perfectly fine encryption mechanism. One\Nthing that I'd like to point out about
Dialogue: 0,0:08:47.94,0:08:53.80,Default,,0000,0000,0000,,CCM, is that everything is based on AES.\NYou notice, it's using AES for the CBC
Dialogue: 0,0:08:53.80,0:08:58.78,Default,,0000,0000,0000,,MAC, and it's using AES for the counter\Nmode encryption. And as a result, CCM can
Dialogue: 0,0:08:58.78,0:09:03.08,Default,,0000,0000,0000,,be implemented with relatively little\Ncode. Cause all you need is an AES engine
Dialogue: 0,0:09:03.08,0:09:08.34,Default,,0000,0000,0000,,and nothing else. And because of this, CCM\Nactually was adopted by the Wi-Fi
Dialogue: 0,0:09:08.34,0:09:13.96,Default,,0000,0000,0000,,alliance, and in fact, you're probably\Nusing CCM on a daily basis if you're using
Dialogue: 0,0:09:13.96,0:09:19.09,Default,,0000,0000,0000,,encrypted Wi-Fi 802.11i then you're\Nbasically using CCM to encrypt traffic
Dialogue: 0,0:09:19.09,0:09:23.45,Default,,0000,0000,0000,,between your laptop and the access point.\NThere's another mode called a EAX that
Dialogue: 0,0:09:23.45,0:09:28.92,Default,,0000,0000,0000,,uses counter mode encryption, and then\NCMAC. So, again you notice encrypt-then-MAC
Dialogue: 0,0:09:28.92,0:09:31.91,Default,,0000,0000,0000,,and that's another fine mode to\Nuse. We'll do a comparison of all these
Dialogue: 0,0:09:31.91,0:09:36.81,Default,,0000,0000,0000,,modes in just a minute. Now I wanted to\Nmention that first of all, all these modes are
Dialogue: 0,0:09:36.81,0:09:41.19,Default,,0000,0000,0000,,nonce-based. In other words, they don't\Nuse any randomness but they do take as
Dialogue: 0,0:09:41.19,0:09:46.36,Default,,0000,0000,0000,,input a nonce and the nonce has to be\Nunique per key. In other words, as you
Dialogue: 0,0:09:46.36,0:09:50.60,Default,,0000,0000,0000,,remember, the pair (key, nonce)\Nshould never ever, ever repeat. But the
Dialogue: 0,0:09:50.60,0:09:53.85,Default,,0000,0000,0000,,nonce itself need not be random, so\Nit's perfectly fine to use a counter, for
Dialogue: 0,0:09:53.85,0:09:57.52,Default,,0000,0000,0000,,example, as a nonce. And the other\Nimportant point is that, in fact, all
Dialogue: 0,0:09:57.52,0:10:01.38,Default,,0000,0000,0000,,these modes are what's called\Nauthenticated encryption with associated
Dialogue: 0,0:10:01.38,0:10:04.94,Default,,0000,0000,0000,,data. This is an extension of\Nauthenticated encryption, that comes
Dialogue: 0,0:10:04.94,0:10:10.88,Default,,0000,0000,0000,,up very often in networking protocols. So\Nthe idea between AEAD is that, in fact,
Dialogue: 0,0:10:10.88,0:10:15.22,Default,,0000,0000,0000,,the message that's provided to the encryption\Nmode is not intended to be fully
Dialogue: 0,0:10:15.22,0:10:19.92,Default,,0000,0000,0000,,encrypted. Only part of the message is\Nintended to be encrypted, but all of the
Dialogue: 0,0:10:19.92,0:10:24.16,Default,,0000,0000,0000,,message is intended to be authenticated. A\Ngood example of this is a network packet.
Dialogue: 0,0:10:24.16,0:10:29.41,Default,,0000,0000,0000,,Think of like a IP packet where there's a\Nheader and then there's a payload. And
Dialogue: 0,0:10:29.41,0:10:33.16,Default,,0000,0000,0000,,typically the header is not gonna be\Nencrypted. For example, the header might
Dialogue: 0,0:10:33.16,0:10:36.90,Default,,0000,0000,0000,,contain the destination of the packet, but\Nthen the header had better not be
Dialogue: 0,0:10:36.90,0:10:40.95,Default,,0000,0000,0000,,encrypted otherwise routers along the way\Nwouldn't know where to route the packet.
Dialogue: 0,0:10:40.95,0:10:45.22,Default,,0000,0000,0000,,And so, typically the header is sent in\Nthe clear, but the payload, of course, is
Dialogue: 0,0:10:45.22,0:10:49.50,Default,,0000,0000,0000,,always encrypted, but what you'd like to\Ndo is have the header be authenticated.
Dialogue: 0,0:10:49.50,0:10:55.91,Default,,0000,0000,0000,,Not encrypted but authenticated. So this is\Nexactly what these AEAD modes do. They
Dialogue: 0,0:10:55.91,0:11:00.03,Default,,0000,0000,0000,,will authenticate the header and then\Nencrypt the payload. But the header and
Dialogue: 0,0:11:00.03,0:11:04.18,Default,,0000,0000,0000,,the payload are bound together in the\Nauthentication so they can't
Dialogue: 0,0:11:04.18,0:11:07.80,Default,,0000,0000,0000,,actually be separated. So this is not\Ndifficult to do. What happens is in these
Dialogue: 0,0:11:07.80,0:11:14.17,Default,,0000,0000,0000,,three modes GCM, CCM, and EAX, basically\Nthe MAC is applied to the entire data. But
Dialogue: 0,0:11:14.17,0:11:18.85,Default,,0000,0000,0000,,the encryption is only applied to the part\Nof the data that needs to be encrypted.
Dialogue: 0,0:11:18.85,0:11:22.98,Default,,0000,0000,0000,,So I wanted to show you what an API\Nto these authenticated encryption with
Dialogue: 0,0:11:22.98,0:11:28.72,Default,,0000,0000,0000,,associated data encryption schemes look\Nlike. So here's what it looks like in OpenSSL.
Dialogue: 0,0:11:28.72,0:11:33.61,Default,,0000,0000,0000,,For example, this is, an API\Nfor GCM. So what you do is you call the
Dialogue: 0,0:11:33.61,0:11:37.40,Default,,0000,0000,0000,,init function to initialize the encryption\Nmode, and you notice you give it a key and
Dialogue: 0,0:11:37.40,0:11:40.61,Default,,0000,0000,0000,,the nonce. The nonce again,\Ndoesn't have to be random, but it has to
Dialogue: 0,0:11:40.61,0:11:44.40,Default,,0000,0000,0000,,be unique. And after initialization, you\Nwould call this encrypt function, where
Dialogue: 0,0:11:44.40,0:11:48.17,Default,,0000,0000,0000,,you see that you give it the associated\Ndata that's gonna be authenticated, but
Dialogue: 0,0:11:48.17,0:11:51.79,Default,,0000,0000,0000,,not encrypted. You give it the data, and\Nit's gonna be both authenticated and
Dialogue: 0,0:11:51.79,0:11:55.75,Default,,0000,0000,0000,,encrypted. And it gives you back the full\Ncipher text, which is an encryption of the
Dialogue: 0,0:11:55.75,0:11:59.58,Default,,0000,0000,0000,,data, but of course does not include the\NAEAD, because the AEAD is gonna be sent in
Dialogue: 0,0:11:59.58,0:12:04.54,Default,,0000,0000,0000,,the clear. So now that we understand\Nthis mode of encrypt-then-MAC, we can go
Dialogue: 0,0:12:04.54,0:12:09.95,Default,,0000,0000,0000,,back to the definition of MAC security and\NI can explain to you something that might
Dialogue: 0,0:12:09.95,0:12:13.97,Default,,0000,0000,0000,,have been a little obscure when we looked\Nat that definition. So if you remember,
Dialogue: 0,0:12:13.97,0:12:18.57,Default,,0000,0000,0000,,one of the requirements that followed from\Nour definition of secure MACs meant that
Dialogue: 0,0:12:18.57,0:12:25.69,Default,,0000,0000,0000,,given a message-MAC pair on a message M,\Nthe attacker cannot produce another tag on
Dialogue: 0,0:12:25.69,0:12:30.39,Default,,0000,0000,0000,,the same message M. In other words, even\Nthough the attacker already has a tag for
Dialogue: 0,0:12:30.39,0:12:34.77,Default,,0000,0000,0000,,the message M, he shouldn't be able to\Nproduce a new tag for the same message M.
Dialogue: 0,0:12:34.77,0:12:39.38,Default,,0000,0000,0000,,And it's really not clear, why does that\Nmatter? Who cares, if the adversary already
Dialogue: 0,0:12:39.38,0:12:44.04,Default,,0000,0000,0000,,has a tag on the message M, who cares if\Nhe can produce another tag? Well, it turns
Dialogue: 0,0:12:44.04,0:12:48.83,Default,,0000,0000,0000,,out if the MAC didn't have this property. \NIn other words, given a message-MAC pair
Dialogue: 0,0:12:48.83,0:12:53.62,Default,,0000,0000,0000,,you can produce another MAC on\Nthe same message, then that MAC would
Dialogue: 0,0:12:53.62,0:12:58.69,Default,,0000,0000,0000,,result in an insecure encrypt-then-MAC mode.\NAnd so if we want our encrypt-then-MAC to
Dialogue: 0,0:12:58.69,0:13:03.96,Default,,0000,0000,0000,,have cipher text integrity, it's crucial\Nthat our MAC security would imply this strong
Dialogue: 0,0:13:03.96,0:13:08.91,Default,,0000,0000,0000,,notion of security, which, of course, it\Ndoes because we defined it correctly.
Dialogue: 0,0:13:08.91,0:13:13.61,Default,,0000,0000,0000,,So let's see what would go wrong, if, in\Nfact, it was easy to produce this type of
Dialogue: 0,0:13:13.61,0:13:18.08,Default,,0000,0000,0000,,forgery. So what I'll do is I'll show you\Na chosen cipher text attack on the
Dialogue: 0,0:13:18.08,0:13:22.78,Default,,0000,0000,0000,,resulting encrypt-then-MAC system. And\Nsince the system has a chosen cipher text
Dialogue: 0,0:13:22.78,0:13:27.19,Default,,0000,0000,0000,,attack on it, it necessarily means that it\Ndoesn't provide authenticated
Dialogue: 0,0:13:27.19,0:13:31.46,Default,,0000,0000,0000,,encryption. So let's see. So the\Nadversary's gonnna start by sending two
Dialogue: 0,0:13:31.46,0:13:35.86,Default,,0000,0000,0000,,messages, M0 and M1. And he's gonna\Nreceive, as usual, the encryption of one
Dialogue: 0,0:13:35.86,0:13:39.52,Default,,0000,0000,0000,,of them, either the encryption of M0 or\Nthe encryption of M1. And since we're
Dialogue: 0,0:13:39.52,0:13:44.91,Default,,0000,0000,0000,,using encrypt-then-MAC, the adversary\Nreceives the cipher text we'll call it C0
Dialogue: 0,0:13:44.91,0:13:49.88,Default,,0000,0000,0000,,and a MAC on the cipher text C0.\NWell now we said that given the MAC on
Dialogue: 0,0:13:49.88,0:13:53.83,Default,,0000,0000,0000,,a message the adversary can produce\Nanother MAC on the same message. So what
Dialogue: 0,0:13:53.83,0:13:57.99,Default,,0000,0000,0000,,he's gonna do is he's gonna produce\Nanother MAC on the message C0. Now he has
Dialogue: 0,0:13:57.99,0:14:03.53,Default,,0000,0000,0000,,a new cipher text (C0,T'), which is a\Nperfectly valid cipher text. T' is a
Dialogue: 0,0:14:03.53,0:14:09.56,Default,,0000,0000,0000,,valid MAC of C0. Therefore, the adversary\Nnow can submit a chosen cipher text query
Dialogue: 0,0:14:09.56,0:14:14.49,Default,,0000,0000,0000,,on C' and this is a valid chosen\Ncipher text query because it's different
Dialogue: 0,0:14:14.49,0:14:19.29,Default,,0000,0000,0000,,from C. It's a new cipher text. The poor\Nchallenger now is forced to decrypt this
Dialogue: 0,0:14:19.29,0:14:23.28,Default,,0000,0000,0000,,cipher text C' so he's going to send\Nback the decryption of C'. It's a
Dialogue: 0,0:14:23.28,0:14:29.09,Default,,0000,0000,0000,,valid cipher text therefore the decryption\Nof C prime is the message Mb but now the
Dialogue: 0,0:14:29.09,0:14:32.32,Default,,0000,0000,0000,,attacker just learned the value of B\Nbecause he can test whether Mb is equal to
Dialogue: 0,0:14:32.32,0:14:37.37,Default,,0000,0000,0000,,M0 or MB is equal to M1. As a result he\Ncan just output B and he gets advantage
Dialogue: 0,0:14:37.37,0:14:43.47,Default,,0000,0000,0000,,one in defeating the scheme. And so\Nagain if our MAC security did not imply
Dialogue: 0,0:14:43.47,0:14:48.47,Default,,0000,0000,0000,,this property here. Then, there would be a\Nchosen cipher text attack on encrypt-then-MAC.
Dialogue: 0,0:14:48.47,0:14:53.18,Default,,0000,0000,0000,,And therefore, it would not be secure. So the\Nfact that we define MAC security correctly
Dialogue: 0,0:14:53.18,0:14:57.24,Default,,0000,0000,0000,,means that encrypt-then-MAC really does\Nprovide authenticated encryption. And
Dialogue: 0,0:14:57.24,0:15:01.73,Default,,0000,0000,0000,,throughout all the MACs that we discussed\Nactually do satisfy this strong notion of
Dialogue: 0,0:15:01.73,0:15:06.15,Default,,0000,0000,0000,,unforgeability. So, interestingly, this is\Nnot the end of the story. So, as we said
Dialogue: 0,0:15:06.15,0:15:10.38,Default,,0000,0000,0000,,before the concept of authenticated\Nencryption was introduced everyone was
Dialogue: 0,0:15:10.38,0:15:15.30,Default,,0000,0000,0000,,just combining MACs and encryption in\Nvarious ways in the hope of achieving
Dialogue: 0,0:15:15.30,0:15:19.20,Default,,0000,0000,0000,,some authenticated encryption. After\Nthe notion of authenticated encryption
Dialogue: 0,0:15:19.20,0:15:23.55,Default,,0000,0000,0000,,became formalized and rigorous, people\Nkind of started scratching their heads and said,
Dialogue: 0,0:15:23.55,0:15:28.13,Default,,0000,0000,0000,,hey, wait a minute. Maybe we can achieve\Nauthenticated encryption more efficiently
Dialogue: 0,0:15:28.13,0:15:32.72,Default,,0000,0000,0000,,than by combining a MAC and an encryption\Nscheme. In fact, if you think about how
Dialogue: 0,0:15:32.72,0:15:37.37,Default,,0000,0000,0000,,this combination of MAC and encryption\Nworks, let's say we combine counter mode
Dialogue: 0,0:15:37.37,0:15:42.13,Default,,0000,0000,0000,,with CMAC, then for every block of\Nplaintext, you first of all have to use
Dialogue: 0,0:15:42.13,0:15:46.42,Default,,0000,0000,0000,,your block cipher for counter mode, and\Nthen you have to use to your block cipher
Dialogue: 0,0:15:46.42,0:15:51.36,Default,,0000,0000,0000,,again, for the CBC-MAC. This means that if\Nyou're combining CPA secure encryption with a
Dialogue: 0,0:15:51.36,0:15:55.94,Default,,0000,0000,0000,,MAC, for every block of plaintext, you\Nhave to evaluate your block cipher twice,
Dialogue: 0,0:15:55.94,0:16:00.54,Default,,0000,0000,0000,,once for the MAC and once for the\Nencryption scheme. So the natural question
Dialogue: 0,0:16:00.54,0:16:05.40,Default,,0000,0000,0000,,was, can we construct an authenticated\Nencryption scheme directly from a PRP,
Dialogue: 0,0:16:05.40,0:16:10.34,Default,,0000,0000,0000,,such that we would have to only evaluate\Nthe PRP once per block? And it turns out
Dialogue: 0,0:16:10.34,0:16:14.12,Default,,0000,0000,0000,,the answer is yes, and there's this\Nbeautiful construction called OCB, that
Dialogue: 0,0:16:14.12,0:16:18.34,Default,,0000,0000,0000,,pretty much does everything you want, and\Nis much faster than constructions that are
Dialogue: 0,0:16:18.34,0:16:22.47,Default,,0000,0000,0000,,separately built from an encryption and a\NMAC. So I wrote down, kind of a schematic
Dialogue: 0,0:16:22.47,0:16:26.29,Default,,0000,0000,0000,,of OCB. I don't want to explain it in\Ndetail. I'll just kind of explain it at a
Dialogue: 0,0:16:26.29,0:16:30.02,Default,,0000,0000,0000,,high level. So here we have our input\Nplain text, here at the top. And you
Dialogue: 0,0:16:30.02,0:16:34.54,Default,,0000,0000,0000,,notice that, first of all, OCB is\Nparallelizable, completely parallelizable.
Dialogue: 0,0:16:34.54,0:16:39.70,Default,,0000,0000,0000,,So every block can be encrypted separately of\Nevery other block. The other thing to
Dialogue: 0,0:16:39.70,0:16:44.34,Default,,0000,0000,0000,,notice is that as I promised, you only\Nevaluate your block cipher once per plain
Dialogue: 0,0:16:44.34,0:16:49.32,Default,,0000,0000,0000,,text block. And then you evaluate it one\Nmore time at the end to build your
Dialogue: 0,0:16:49.32,0:16:53.89,Default,,0000,0000,0000,,authentication tag and then the overhead\Nof OCB beyond just a block cipher is
Dialogue: 0,0:16:53.89,0:16:58.75,Default,,0000,0000,0000,,minimal. All you have to do is evaluate a\Ncertain very simple function P. The
Dialogue: 0,0:16:58.75,0:17:02.84,Default,,0000,0000,0000,,nonce goes into the P you notice, the\Nkey goes into this P and then there is a
Dialogue: 0,0:17:02.84,0:17:08.24,Default,,0000,0000,0000,,block counter that goes into this P. So\Nyou just evaluate this function P, twice
Dialogue: 0,0:17:08.24,0:17:12.75,Default,,0000,0000,0000,,for every block and you XOR the result\Nbefore and after encryption using the
Dialogue: 0,0:17:12.75,0:17:17.55,Default,,0000,0000,0000,,block cipher and that's it. That's all you\Nhave to do and then you get a very fast
Dialogue: 0,0:17:17.55,0:17:22.24,Default,,0000,0000,0000,,and efficient authenticated encryption\Nscheme built from a block cipher. So OCB
Dialogue: 0,0:17:22.24,0:17:26.06,Default,,0000,0000,0000,,actually has a nice security theorem\Nassociated with it and I am going to point
Dialogue: 0,0:17:26.06,0:17:29.57,Default,,0000,0000,0000,,to a paper on OCB when we get to end of\Nthis module where I list some further
Dialogue: 0,0:17:29.57,0:17:34.46,Default,,0000,0000,0000,,reading papers that you can take a look\Nat. So you might be wondering if OCB is so
Dialogue: 0,0:17:34.46,0:17:40.17,Default,,0000,0000,0000,,much better than everything you've seen so\Nfar, all these three standards CCM, GCM and
Dialogue: 0,0:17:40.17,0:17:46.04,Default,,0000,0000,0000,,EAX why isn't OCB being used or why isn't\NOCB the standard? And the answer is a
Dialogue: 0,0:17:46.04,0:17:50.73,Default,,0000,0000,0000,,little sad. The primary answer that\NOCB is not being used is actually because
Dialogue: 0,0:17:50.73,0:17:54.57,Default,,0000,0000,0000,,of various patents. And I'll just leave it\Nat that. So to conclude this section I
Dialogue: 0,0:17:54.57,0:17:58.22,Default,,0000,0000,0000,,wanted to show you some performance\Nnumbers. So here on the right I listed
Dialogue: 0,0:17:58.22,0:18:02.37,Default,,0000,0000,0000,,performance numbers for modes that you\Nshouldn't be using. So this is for
Dialogue: 0,0:18:02.37,0:18:07.88,Default,,0000,0000,0000,,randomized counter mode, and this is for\Nrandomized CBC. And you can see also the
Dialogue: 0,0:18:07.88,0:18:12.46,Default,,0000,0000,0000,,performance of CBC MAC is basically the\Nsame as the performance of CBC encryption.
Dialogue: 0,0:18:12.46,0:18:16.22,Default,,0000,0000,0000,,Okay. Now here are the authenticated\Nencryption modes, so these are the ones
Dialogue: 0,0:18:16.22,0:18:20.08,Default,,0000,0000,0000,,that you're supposed to using, these\Nyou're not supposed to be using on their
Dialogue: 0,0:18:20.08,0:18:23.80,Default,,0000,0000,0000,,own, right. These two, you should never\Never use these two because they only
Dialogue: 0,0:18:23.80,0:18:27.86,Default,,0000,0000,0000,,provide CPA security, they don't\Nactually provide security against active
Dialogue: 0,0:18:27.86,0:18:31.67,Default,,0000,0000,0000,,attacks. You're only supposed to use\Nauthenticated encryption for encryption.
Dialogue: 0,0:18:31.67,0:18:35.51,Default,,0000,0000,0000,,And so I listed performance numbers\Nfor the three standards. And let me remind
Dialogue: 0,0:18:35.51,0:18:40.11,Default,,0000,0000,0000,,you that GCM basically uses a very fast\Nhash. And then it uses counter mode for
Dialogue: 0,0:18:40.11,0:18:43.77,Default,,0000,0000,0000,,actual encryption. And you can see that\Nthe overhead of GCM over counter mode is
Dialogue: 0,0:18:43.77,0:18:49.55,Default,,0000,0000,0000,,relatively small. CCM and EAX both use a\Nblock cipher based encryption and a
Dialogue: 0,0:18:49.55,0:18:54.63,Default,,0000,0000,0000,,block cipher based MAC. And as a result\Nthey're about twice as slow as counter
Dialogue: 0,0:18:54.63,0:18:59.20,Default,,0000,0000,0000,,modes. You see that OCB is actually the\Nfastest of these, primarily because it
Dialogue: 0,0:18:59.20,0:19:03.82,Default,,0000,0000,0000,,only use the block cipher once per message\Nblock. So based on these performance
Dialogue: 0,0:19:03.82,0:19:08.33,Default,,0000,0000,0000,,numbers, you would think that GCM is\Nexactly the right mode to always use. But
Dialogue: 0,0:19:08.33,0:19:12.66,Default,,0000,0000,0000,,it turns out if you're on the space\Nconstrained hardware, GCM is not ideal.
Dialogue: 0,0:19:12.66,0:19:16.71,Default,,0000,0000,0000,,Primarily because its implementation\Nrequires larger code than the other two
Dialogue: 0,0:19:16.71,0:19:21.32,Default,,0000,0000,0000,,modes. However, as I said, Intel\Nspecifically added instructions to speed
Dialogue: 0,0:19:21.32,0:19:26.06,Default,,0000,0000,0000,,up GCM mode. And as a result, implementing\NGCM on an Intel architecture takes
Dialogue: 0,0:19:26.06,0:19:30.32,Default,,0000,0000,0000,,very little code. But on other hardware\Nplatforms, say in smart cards or other
Dialogue: 0,0:19:30.32,0:19:34.74,Default,,0000,0000,0000,,constrained environments, the code size\Nfor implementing GCM would be considerably
Dialogue: 0,0:19:34.74,0:19:39.39,Default,,0000,0000,0000,,larger than for the other two modes. But\Nif code size is not a constraint then GCM
Dialogue: 0,0:19:39.39,0:19:43.93,Default,,0000,0000,0000,,is the right mode to use. So to summarize\Nthis segment I want to say it one more
Dialogue: 0,0:19:43.93,0:19:48.27,Default,,0000,0000,0000,,time that when you want to encrypt\Nmessages you have to use an authenticated
Dialogue: 0,0:19:48.27,0:19:52.72,Default,,0000,0000,0000,,encryption mode and the recommended way to\Ndo it is to use one of the standards,
Dialogue: 0,0:19:52.72,0:19:57.04,Default,,0000,0000,0000,,namely one of these three modes for\Nproviding authenticated encryption.
Dialogue: 0,0:19:57.04,0:19:59.85,Default,,0000,0000,0000,,Don't implement the encryption scheme yourself.\NIn other words don't implement
Dialogue: 0,0:19:59.85,0:20:05.84,Default,,0000,0000,0000,,encrypt-then-MAC yourself. Just use one of these\Nthree standards. Many crypto libraries
Dialogue: 0,0:20:05.84,0:20:10.51,Default,,0000,0000,0000,,now provide standard API's for these three\Nmodes and these are the one's you should
Dialogue: 0,0:20:10.51,0:20:14.35,Default,,0000,0000,0000,,be using and nothing else. In the next\Nsegment we're going to see what else can
Dialogue: 0,0:20:14.35,0:20:17.50,Default,,0000,0000,0000,,go wrong when you try to implement\Nauthenticated encryption by yourself.