0:05

Hi folks, I want to talk to you about a really interesting contribution to

communication and to computer science made by computer security folks.

Particularly a group at IBM in the 70s led by Horst Feistel and a number of

others who were just absolutely wonderful pioneers of cryptography,

and the result of their work is something we call Triple-DES.

Now here's the idea, when I encrypt something using DES,

which we went through in a previous video,

I'm effectively doing the work of 2 to the 56 bit size domain.

So if I wanted to do brute force on single DES I could technically search

a 2 to the 56 bit, or 2 to the 56 number of choices for

keys, since that's actually a pretty small number for computers.

In the old days we used to say astronomical was a big number, now I think

we should say sort of computational is a big number because 2 to the 56 is actually

very small cryptography, so the question was how can we make it bigger?

And this IBM team took some time, looked into this, and actually came

up with an answer that now we would say is sort of duh, yeah, it seems so obvious.

They said let's just encrypt it multiple times, because if you do the thought

process in your mind you realize that if I encrypt something with say a 56 bit key

and then I have to do it again, I'm doing twice the work, I'm actually increasing

the computational complexity, or rather the size of the domain.

So here's what the IBM team said, they said all right, instead of doing one DES,

single DES, with key K, let's invent key K1 and

K2, different, and I'll encrypt it with K1,

and then encrypt it again with K2, and I'll have 56 + 56, or 112,

bit cryptography, everybody went yeah.

And if you don't get why it's additive go off and do a few little examples on paper

with small numbers and you'll convince yourself that it is additive, the work.

So here's the problem,

if you do that then a bank off in some place that wants to communicate with

you using single-DES equipment now looks at you with your double-DES or

2-DES equipment with the two keys, and it'll go how do I communicate with you,

how do I arrange the keys in such a manner that we can communicate?

And you can see that it doesn't really work,

it's hard to do that, you could come up with weird sort of arrangements but

you'll never be able to duplicate single-DES with keys on double-DES.

So they came up with the idea of something called Triple-DES, and you can see on

the screen there the progression from single-DES, double-DES, Triple-DES.

The way Triple-DES works is first it takes advantage of an artifact in

DES that is essentially that you can either encrypt and

then decrypt, or you can decrypt and then encrypt and it's the same thing.

Remember I said encryption might be like walking that way so

I'll go boom, boom and then the key is sort of to now I'm over there,

now decryption is walking this way, boom, boom and I'm back.

Well I could decrypt first, walk that way to, and then encrypt walk this way,

it's the same thing, that's how DES works, you can do either one.

So they said let's set this up with three keys, K1, K2, K3, and I'm

going to do it in an arrangement I call EDE mode, or encrypt decrypt encrypt mode.

Here's how that works, I start with a message M and I encrypt it with key K1, or

if you want to put it in the middle you can call it K3 or whatever you like,

we'll call it K1, then I'm going to decrypt that with key K2, and

then I'm going to encrypt that with key K3.

Three keys, encrypt, decrypt, encrypt, okay.

4:05

Now the fun part of that is take the first two operations,

I encrypted something with key K1, I decrypted something with key K2,

think about it, if I set K1 to K2 then they cancel out, don't they?

[LAUGH] I'm encrypting with a key, I decrypt with the key,

I get the message back, and then I encrypt with K key K3,

I've got single-DES, how freaking cool is that?

By just setting K1 and K2 to be the same thing I can have

Triple-DES become single-DES and I can encrypt for the bank.

But if you don't like that and you go no, no I really want to do it more,

I want it to be stronger, let's say you want 112 bit cryptography, no problem.

Set K1 and K3, 1 and 3 to be the same, K2 to be different.

So now what happens is I encrypt with key K1,

I decrypt with a different key which is like encrypting again, and

then I encrypt again with key K3, the whole thing is 112 bit cryptography

with two keys because we said K1 and K3 were the same, so that's a choice.

Let's say you want even stronger cryptography, you want 3 times 56 or

whatever that comes to, 168, then K1, K2 and K3 are all different.

So do you see, this is how modern ciphers provide you choices in how strong

you want the cryptography to be based on how you set up the keys.

It's genius, [LAUGH], the guys that came up with this are geniuses,

it's beautiful mathematics.

The team at IBM, give them a lot of credit in their ability to do this,

Walt and Horst Feistel, and these wonderful mathematicians,

they deserve so much credit for having created these beautiful ciphers,

particularly Triple-DES which I think to this day is a marvelous achievement.

So I hope you enjoy that,

I mean that fixes the one problem we said in DES, the 56 part.

But there's another problem and that's sort of the scaling and

other kinds of issues that you have in Triple-DES, and we'll start looking at

some additional problems and limitations in a subsequent video.

So I hope you enjoyed it, we'll see you in the next one.