In this segment, I want to give a few examples of stream ciphers that are used in practice. I'm gonna start with two old examples that actually are not supposed to be used in new systems. But nevertheless, they're still fairly widely used, and so I just want to mention the names so that you're familiar with these concepts. The first stream cipher I want to talk about is called RC4, designed back in 1987. And I'm only gonna give you the high-level description of it, and then we'll talk about some weaknesses of RC4 and leave it at that. So RC4 takes a variable size seed, here I just gave as an example where it would take 128 bits as the seed size, which would then be used as the key for the stream cipher. The first thing it does, is it expands the 128-bit secret key into 2,048 bits, which are gonna be used as the internal state for the generator. And then, once it's done this expansion, it basically executes a very simple loop, where every iteration of this loop outputs one byte of output. So, essentially, you can run the generator for as long as you want, and generate one byte at a time. Now RC4 is actually, as I said, fairly popular. It's used in the HTTPS protocol quite commonly actually. These days, for example, Google uses RC4 in its HTTPS. It's also used in WEP as we discussed in the last segment, but of course in WEP, it's used incorrectly and it's completely insecure the way it's used inside of WEP. So over the years, some weaknesses have been found in RC4, and as a result, it's recommended that new projects actually not use RC4 but rather use a more modern pseudo-random generator as we'll discuss toward the end of the segment. So let me just mention two of the weaknesses. So the first one is, it's kind of bizarre basically, if you look at the second byte of the output of RC4. It turns out the second byte is slightly biased. If RC4 was completely random, the probability that the second byte happens to be equal to zero would be exactly one over 256. There are 256 possible bytes, the probability that it's zero should be one over 256. It so happens that for RC4 the probability is actually two over 256, which means that if you use the RC4 output to encrypt a message the second byte is likely to not be encrypted at all. In other words it'll be XOR-ed with zero with twice the probability that it's supposed to. So two over 256, instead of one over 256. And by the way I should say that there's nothing special about the second byte. It turns out the first and the third bytes are also biased. And in fact it's now recommended that if you're gonna use RC4, what you should do is ignore basically the first 256 bytes of the output and just start using the output of the generator starting from byte 257. The first couple of bytes turned out to be biased, so you just ignore them. The second attack that was discovered is that in fact if you look at a very long output of RC4 it so happens that you're more likely to get the sequence 00. In other words, you're more likely to get sixteen bits, two bytes of zero, zero, than you should. Again, if RC4 was completely random the probability of seeing zero, zero would be exactly 1/256 squared. It turns out RC4 is a little biased and the bias is 1/256 cubed. It turns out this bias actually starts after several gigabytes of data are produced by RC4. But nevertheless, this is something that can be used to predict the generator and definitely it can be used to distinguish the output of the generator from a truly random sequence. Basically the fact that zero, zero appears more often than it should is the distinguisher. And then in the last segment we talked about related-key attacks that were used to attack WEP, that basically say that if one uses keys that are closely related to one another then it's actually possible to recover the root key. So these are the weaknesses that are known of RC4 and, as a result, it's recommended that new systems actually not use RC4 and instead use a modern pseudo-random generator. Okay, second example I want to give you is a badly broken stream cipher that's used for encrypting DVD movies. When you buy a DVD in the store, the actual movie is encrypted using a stream cipher called the content scrambling system, CSS. CSS turns out to be a badly broken stream cipher, and we can very easily break it, and I want to show you how the attack algorithm works. We're doing it so you can see an example of an attack algorithm, but in fact, there are many systems out there that basically use this attack to decrypt encrypted DVDs. So the CSS stream cipher is based on something that hardware designers like. It's designed to be a hardware stream cipher that is supposed to be easy to implement in hardware, and is based on a mechanism called a linear feedback shift register. So a linear feedback shift register is basically a register that consists of cells where each cell contains one bit. Then basically what happens is there are these taps into certain cells, not all the cells, certain positions are called taps. And then these taps feed into an XOR and then at every clock cycle, the shift register shifts to the left. The last bit falls off and then the first bit becomes the result of this XOR. So you can see that this is a very simple mechanism to implement, and in hardware takes very few transistors. Just the shift right, the last bit falls off and the first bit just becomes the XOR of the previous bits. So the seed for this LFSR basically, is the initial state of the LFSR. And it is the basis of a number of stream ciphers. So here are some examples. So, as I said, DVD encryption uses two LFSRs. I'll show you how that works in just a second. GSM encryption, these are algorithms called A51 and A52. And that uses three LFSRs. Bluetooth encryption is an algorithm called, E zero. These are all stream ciphers, and that uses four LFSRs. Turns out all of these are badly broken, and actually really should not be trusted for encrypting traffic, but they're all implemented in hardware, so it's a little difficult now to change what the hardware does. But the simplest of these, CSS, actually has a cute attack on it, so let me show you how the attack works. So, let's describe how CSS actually works. So, the key for CSS is five bytes, namely 40 bits, five times eight is 40 bits. The reason they had to limit themselves to only 40 bits is that DVD encryption was designed at a time where U.S. Export regulations only allowed for export of crpyto algorithms where the key was only 40 bits. So the designers of CSS were already limited to very, very short keys. Just 40 bit keys. So, their design works as follows. Basically, CSS uses two LFSR's. One is a 17-bit LFSR. In other words, the register contains 17 bits. And the other one is a 25-bit LFSR, it's a little bit longer, 25-bit LFSR. And the way these LFSRs are seeded is as follows. So the key for the encryption, basically looks as follows. You start off with a one, and you concatenate to it the first two bytes of the key. And that's the initial state of the LFSR. And then the second LFSR basically is intitialized the same way. One concatenated the last three bytes of the key. And that's loaded into the initial state of the LFSR. You can see that the first two bytes are sixteen bits, plus leading one, that's seventeen bits overall, whereas the second LFSR is 24 bits plus one which is 25 bits. And you notice we used all five bits of the key. So then these LFSRs are basically run for eight cycles, so they generate eight bits of output. And then they go through this adder that does basically addition modulo 256. Yeah so this is an addition box, modulo 256. There's one more technical thing that happens. In fact let's actually—also added is the carry from the previous block. But that is not so important. That's a detail that's not so relevant. OK, so every block, you notice we're doing addition modulo 256 and we're ignoring the carry, but the carry is basically added as a zero or a one to the addition of the next block. Okay? And then basically this output one byte per round. Okay, and then this byte is then of course used, XOR-ed with the appropriate byte of the movie that's being encrypted. Okay, so it's a very simple stream cipher, it takes very little hardware to implement. It will run fast, even on very cheap hardware and it will encrypt movies. So it turns out this is easy to break in time roughly two to the seventeen. Now let me show you how. So suppose you intercept the movies, so here we have an encrypted movie that you want to decrypt. So let's say that this is all encrypted so you have no idea what's inside of here. However, it so happens that just because DVD encryption is using MPEG files, it so happens if you know of a prefix of the plaintext, let's just say maybe this is twenty bytes. Well, we know if you XOR these two things together, so in other words, you do the XOR here, what you'll get is the initial segment of the PRG. So, you'll get the first twenty bytes of the output of CSS, the output of this PRG. Okay, so now here's what we're going to do. So we have the first twenty bytes of the output. Now we do the following. We try all two to the seventeen possible values of the first LFSR. Okay? So two to the seventeen possible values. So for each value, so for each of these two to the seventeen initial values of the LFSR, we're gonna run the LFSR for twenty bytes, okay? So we'll generate twenty bytes of outputs from this first LFSR, assuming—for each one of the two to the seventeen possible settings. Now, remember we have the full output of the CSS system. So what we can do is we can take this output that we have. And subtract it from the twenty bites that we got from the first LFSR, and if in fact our guess for the initial state of the first LFSR is correct, what we should get is the first twenty-byte output of the second LFSR. Right? Because that's by definition what the output of the CSS system is. Now, it turns out that looking at a 20-byte sequence, it's very easy to tell whether this 20-byte sequence came from a 25-bit LFSR or not. If it didn't, then we know that our guess for the 17-bit LFSR was incorrect and then we move on to the next guess for the 17-bit LFSR and the next guess and so on and so forth. Until eventually we hit the right initial state for the 17-bit LFSR, and then we'll actually get, we'll see that the 20 bytes that we get as the candidate output for the 25-bit LFSR is in fact a possible output for a 25-bit LFSR. And then, not only will we have learned the correct initial state for the 17-bit LFSR, we will have also learned the correct initial state of the 25-bit LFSR. And then we can predict the remaining outputs of CSS, and of course, using that, we can then decrypt the rest of the movie. We can actually recover the remaining plaintext. Okay. This is things that we talked about before. So, I said this a little quick, but hopefully, it was clear. We're also going to be doing a homework exercise on this type of stream ciphers and you'll kind of get the point of how these attack algorithms work. And I should mention that there are many open-source systems now that actually use this method to decrypt CSS-encrypted data. Okay, so now that we've seen two weak examples, let's move on to better examples, and in particular the better pseudo-random generators come from what's called the eStream Project. This is a project that concluded in 2008, and they qualify basically five different stream ciphers, but here I want to present just one. So first of all the parameters for these stream ciphers are a little different than what we're used to. So these stream ciphers as normal they have a seed. But in addition they also have, what's called a nonce and we'll see what a nonce is used for in just a minute. So they take two inputs a seed and a nonce. We'll see what the nonce is used for in just a second. And the of course they produce a very large output, so n here is much, much, much bigger than s. Now, when I say nonce, what I mean is a value that's never going to repeat as long as the key is fixed. And I'll explain that in more detail in just a second. But for now, just think of it as a unique value that never repeats as long as the key is the same. And so of course once you have this PRG, you would encrypt, you get a stream cipher just as before, except now as you see, the PRG takes as input both the key and the nonce. And the property of the nonce is that the pair, k comma r, so the key comma the nonce, is never—never repeats. It's never used more than once. So the bottom line is that you can reuse the key, reuse the key, because the nonce makes the pair unique, because k and r are only used once. I'll say they're unique. Okay so this nonce is kind of a cute trick that saves us the trouble of moving to a new key every time. Okay, so the particular example from the eStream that I want to show you is called Salsa twenty. It's a stream cipher that's designed for both software implementations and hardware implementations. It's kind of interesting. You realize that some stream ciphers are designed for software, like RC4. Everything it does is designed to make software implementation run fast, whereas other stream ciphers are designed for hardware, like CSS, using an LFSR that's particularly designed to make hardware implementations very cheap. It's also, the nice thing about that is that it's designed so that it's both easy to implement it in hardware and its software implementation is also very fast. So let me explain how Salsa works. Well, Salsa takes either 128 or 256-bit keys. I'll only explain the 128-bit version of Salsa. So this is the seed. And then it also takes a nonce, just as before, which happens to be 64 bits. And then it'll generate a large output. Now, how does it actually work? Well, the function itself is defined as follows. Basically, given the key and the nonce, it will generate a very long, well, a long pseudorandom sequence, as long as necessary. And it'll do it by using this function that I'll denote by H. This function H takes three inputs. Basically the key. Well, the seed k, the nonce r, and then a counter that increments from step to step. So it goes from zero to one, two, three, four as long as we need it to be. Okay? So basically, by evaluating this H on this k r, but using this incrementing counter, we can get a sequence that's as long as we want. So all I have to do is describe how this function H works. Now, let me do that here for you. The way it works is as follows. Well, we start off by expanding the states into something quite large which is 64 bytes long, and we do that as follows. Basically we stick a constant at the beginning, so there's tao zero, these are four bytes, it's a four byte constant, so the spec for Salsa basically gives you the value for tao zero. Then we put k in which is sixteen bytes. Then we put another constant. Again, this is four bytes. And as I said, the spec basically specifies what this fixed constant is. Then we put the nonce, which is eight bytes. Then we put the index. This is the counter zero, one, two, three, four, which is another eight bytes. Then we put another constant tau two, which is another four bytes. Then we put the key again, this is another sixteen bytes. And then finally we put the third constant, tau three, which is another four bytes. Okay so as I said, if you sum these up, you see that you get 64 bytes. So basically we've expanded the key and the nonce and the counter into 64 bytes. Basically the key is repeated twice I guess. And then what we do is we apply a function, I'll call this functional little h. Okay, so we apply this function, little h. And this is a function that's one to one so it maps 64 bytes to 64 bytes. It's a completely invertible function, okay? So this function h is, as I say, it's an invertable function. So given the input you can get the output and given the output you can go back to the input. And it's designed specifically so it's a- easy to implement in hardware and b- on an x86, it's extremely easy to implement because x86 has this SSE2 instruction set which supports all the operations you need to do for this function. It's very, very fast. As a result, Salsa has a very fast stream cipher. And then it does this basically again and again. So it applies this function h again and it gets another 64 bytes. And so on and so forth, basically it does this ten times. Okay so the whole thing here, say repeats ten times, so basically apply h ten times. And then by itself, this is actually not quite random. It's not gonna look random because like we said, H is completely invertable. So given this final output, it's very easy to just invert h and then go back to the original inputs and then test that the input has the right structure. So you do one more thing, which is to basically XOR the inputs and the final outputs. Actually, sorry. It's not an XOR. It's actually an addition. So you do an addition word by word. So if there are 64 bytes, you do a word-by-word addition four bytes at a time, and finally you get the 64-byte output, and that's it. That's the whole pseudo-random generator. So that, that's the whole function, little h. And as I explained, this whole construction here is the function big H. And then you evaluate big H by incrementing the counter I from zero, one, two, three onwards. And that will give you a pseudo-random sequence that's as long as you need it to be. And basically, there are no signifigant attacks on this. This has security that's very close to two to the 128. We'll see what that means more precisely later on. It's a very fast stream cipher, both in hardware and in software. And, as far as we can tell, it seems to be unpredictable as required for a stream cipher. So I should say that the eStream project actually has five stream ciphers like this. I only chose Salsa 'cause I think it's the most elegant. But I can give you some performance numbers here. So you can see, these are performance numbers on a 2.2 gigahertz, you know, x86 type machine. And you can see that RC4 actually is the slowest. Because essentially, well it doesn't really take advantage of the hardware. It only does byte operations. And so there's a lot of wasted cycles that aren't being used. But the E-Stream candidates, both Salsa and other candidate called Sosemanuk. I should say these are eStream finalists. These are actually stream ciphers that are approved by the eStream project. You can see that they have achieved a significant rate. This is 643 megabytes per second on this architecture, more than enough for a movie and these are actually quite impressive rates. And so now you've seen examples of two old stream ciphers that shouldn't be used, including attacks on those stream ciphers. You've seen what the modern stream ciphers look like with this nonce. And you see the performance numbers for these modern stream ciphers so if you happen to need a stream cipher you could use one of the eStream finalists. In particular you could use something like Salsa.
