Hi folks, Ed Amaroso here, and today, in this video, I want to take you through a really interesting protocol called S/Key. It was written by a very famous computer scientist named Leslie Lamport. I want to tell you a story, back in the 1980s, I was a graduate student, and one of my friends said, hey listen, you really like security, which I did, and you really like this guy, Leslie Lamport, which I did. And he said, he wrote a paper, real simple, three page paper, why don't you read it? So I remember, I went and I got the paper, I sat down, I was all excited, short paper, my favorite author, favorite topic. I sat to read it, and guess what, I couldn't understand it at all. And I thought, maybe I'm having a bad day, so I put it aside, took it back out, tried to read it again, went through it, got lost halfway through page one. I think I iterated four, five times on that, and the dirty trick here is that it's one of the required readings for you. But it's the topic of today's video, so I'm going to explain it to you, and a subsequent video will do some cryptoanalysis on it. Now here's the idea, Alice is trying to authenticate to Bob. So Bob is essentially saying to Alice, hey, prove who you are. Here's how it works, it's this crazy but really interesting scheme. The idea is that Alice and Bob both have the ability to encrypt a seed, a number. And what happens is Bob, the server, saves not the seed, but rather saves the encryption function, and then the result of having encrypted the seed n times. So imagine when we're doing the setup and I'm setting the server up, I take some number, remember, a lot of times, we refer to a random number as a nonce. I take a nonce and the server will encrypt it, let's say n is 10,000. So I go [SOUND] I keep encrypting 10,000 times, and when I'm done, I store that value alongside the actual encryption function. You got that, so think of storing f and f to the n of lambda, you got that? Now, at the client, what the client does is, the client has the seed value, knows the number n, and has the encryption function. So I've got stored here f to the n of lambda, here's what happens. The server interrogates the client, says, prove who you are. And the client encrypts the lambda seed value n minus 1 times, isn't that crazy, but here's the idea. I encrypt it n minus 1 times, and I send it to the server. Now when it receives that f to the n minus 1 of lambda, what can it do? It's got the encryption function, so it can encrypt it one more time. And then it's got f of f to the n minus 1 lambda, which is f to the n of lambda, which is what it has stored, isn't that amazing? So it's got f to the n, I send you f to the n minus 1, you encrypt one more time, you compare, if they're right, I say, hello, Alice. And then I throw away f to the n of lambda as my stored value, and I now store f to the n minus 1. Now, the next time I come along as Alice and I want to authenticate to the server, it says, hey, prove. Now I have f to the n minus 1 stored, so Alice keeps track of the fact that n now has been decremented. Now Alice sends f to the n minus 2 in a separate session, the second time around, and Bob then can encrypt one more time to get f to the n minus 1. Compares, says hello Alice, throws out f to the n minus 1, and now stores f to the n minus 2 as the seed value, or as the multiply times encrypted, seed. Isn't that kind of a cool concept, you can see how reading a paper on this would be a little bit confusing. And I remember thinking to myself, what happens if you run out? Like let's say it's 10,000 and you keep decrementing each time somebody wants to authenticate, what do you do? Well I thought about it, I thought, what if it is 10000, there are 365 days in a year. So if you did it every day for 10 years, that's still less than 4000. If you did it twice a day for ten years, and I thought, nobody's going to do it twice a day for ten years. And even if you did, you could replenish, you just have to go back to the drawing board and reset things up. It's an extremely interesting protocol, but the irony is, hardly anybody used it. The place I first learned about it was in some free firewall toolkit code that I downloaded in the 90s. And there was a guy named Phil Karn, who was working for a company called Belcorp at the time, who'd actually read the paper. I guess he understood it where I didn't, and in the liner notes to the code, he explained what I just described to you. And I remember reading it, going, I see, I understand how it works. I couldn't read the paper, but I read the liner notes to some source code, go figure. Now listen, in a subsequent video, what we will do is, we will cryptoanalyze this, but just sort of as an additional consideration, something to think about. I do want you to think about protocols that have finite numbers of log in or use or rounds, and whether that makes sense. Do you think it's reasonable to have sort of an end, and limit the number of times that you can do it? Just for your further consideration as you ponder the Lamport S/Key protocol, and think more and more about how authentication can be used in a practical setting. So we'll see you in the next video, where we'll do some cryptoanalytic, sort of investigation of this protocol, and see which type of cryptoanalysis would need to be done to break it, I'll see you in the next one.
