Cryptography is an indispensable tool for protecting information in computer systems. In this course you will learn the inner workings of cryptographic systems and how to correctly use them in real-world applications. The course begins with a detailed discussion of how two parties who have a shared secret key can communicate securely when a powerful adversary eavesdrops and tampers with traffic. We will examine many deployed protocols and analyze mistakes in existing systems. The second half of the course discusses public-key techniques that let two parties generate a shared secret key. Throughout the course participants will be exposed to many exciting open problems in the field and work on fun (optional) programming projects. In a second course (Crypto II) we will cover more advanced cryptographic tasks such as zero-knowledge, privacy mechanisms, and other forms of encryption.
Real-World Stream Ciphers
Loading...
Из курса от партнера Stanford University
Cryptography I
2504 оценки
Из урока
Course overview and stream ciphers
Week 1. This week's topic is an overview of what cryptography is about as well as our first example ciphers. You will learn about pseudo-randomness and how to use it for encryption. We will also look at a few basic definitions of secure encryption.
Познакомьтесь с преподавателями
Dan BonehProfessor
Computer Science
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.
Ознакомьтесь с нашим каталогом
Присоединяйтесь бесплатно и получайте персонализированные рекомендации, обновления и предложения.
Coursera делает лучшее в мире образование доступным каждому, предлагая онлайн-курсы от ведущих университетов и организаций.
© Coursera Inc., 2019 Все права защищены.
