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.