In cryptography, the Fluhrer, Mantin and Shamir attack is a stream cipher attack on the widely used RC4 stream cipher. The attack allows an attacker to recover the key in an RC4 encrypted stream from a large number of messages in that stream.
The Fluhrer, Mantin and Shamir attack applies to specific key derivation methods, but does not apply in general to RC4-based SSL (TLS), since SSL generates the encryption keys it uses for RC4 by hashing, meaning that different SSL sessions have unrelated keys.[1] However, the closely related bar mitzvah attack, based on the same research and revealed in 2015, does exploit those cases where weak keys are generated by the SSL keying process.
YouTube Encyclopedic
-
1/1Views:579
-
2 3 Attacks on stream ciphers and the one time pad 24 min
Transcription
In this segment, we're gonna look at attacks on the one time pad, and some things you need to be careful with when you use the stream cipher. But before we do that, let's do a quick review of where we were. So recall that the one time pad encrypts messages by XORing the message and a secret key, where the secret key is as long as the message. Similarly, decryption is done by similarly XORing the cipher text, and the same secret key. When the key is uniform and random, we prove that the one-time pad has this information theoretic security that Shannon called perfect secrecy. A problem was, of course, the keys are as long as the message, so the one-time pad is very difficult to use. We then talked about a way to make the one time pad practical by using a pseudo random generator that expands a short seed into a much larger message and the way a stream cypher worked, essentially using a pseudo random generator, was in the same way as the one time pad, basically, but rather than using a truly random pad, we used this pseudo random pad that's expanded to be as long as the message from the short key that's given as input to the generator. We said now the security no longer relies on perfect secrecy because stream ciphers cannot be perfectly secure. Instead security relies on properties of the pseudo random generator and we said that the pseudo random generator essentially needs to be unpredictable, but in fact it turns out that definition is a little bit hard to work with and we're going to see a better definition of security for PRGs in about two segments. But in this segment we're going to talk about attacks on the one time pad. And the first attack I want to talk about is what's called the two time pad attack, okay? so remember that the one time pad is called "one time" pad because the pad can only be used to encrypt a single message. I want to show you that if the same pad is used to encrypt more than one message, then security goes out the window, and basically an eavesdropper can completely decrypt encrypted messages. So let's look at an example. So here we have two messages m1 and m2 that are encrypted using the same pad. So the resulting ciphertext, C1 and C2, again basically are encryptions of these messages, m1 and m2, but both are encrypted using the same pad. Now suppose an eavesdropper intercepts C1 and C2, and he obtains, he basically has both C1 and C2. The natural thing for the eavesdropper to do is actually compute the XOR of C1 and C2 and what does he get when he computes this XOR? So I hope everybody sees that, basically, once you XOR C1 and C2, the pads cancel out, and essentially, what comes out of this is the XOR of the plaintext messages. And it turns out that English basically has enough redundancy, such that if I give you the XOR of two plaintext messages, you can actually recover those two mesages completely. More importantly for us is these messages are encoded using ASCII. In fact, ASCII encodings has enough redundancy, such that given the XOR of two ASCII encoded messages, you can recover the original messages back. So, essentially, given these XORs, you can recover both messages. So the thing to remember here is if you ever use the same pad to encrypt multiple messages an attack who intercepts the resulting ciphertexts can eventually recover the existing plaintexts without too much work. So, the stream cipher key or the one time pad key should never ever, ever, ever be used more than once. So, let's look at some examples where this comes up in practice. It's a very common mistake to use the stream cipher key, or a one time pad key more than once. Now, let me show you some examples where this comes up. So you know to avoid these mistakes, when you build your own systems. The first example is a historic example. At the beginning of the 1940s, where the Russians actually used a one time pad to encrypt various mesages. Unfortunately, the pads that they were using were generated by a human by throwing dice. And so, you know, the human would throw these dice, and write down the results of these throws. And the collected throws would then form the pads that were used for encryption. Now, because it was kind of laborious for them to generate these pads, it seems wasteful to use the pads to encrypt just one message. So the ended up using these pads to encrypt multiple messages. And US intelligence was actually able to intercept these two time pads. These ciphertexts that were encrypted using the same pad, applied to different messages. And it turns out, over a period of several years, they we're able to decrypt something like 3,000 plain texts just by intercepting these ciphertexts. The project is called Project Venona It's actually a fascinating of cryptanalysis, just because the two time pad is insecure. More importantly, I want to talk about more recent examples that come up in networking protocols, so let me give you an example from Windows NT, in a product called the, point-to-point transfer protocol. This is a protocol for a client wishing to communicate securely with a server. The client and the server both share a secret key here, and they both send messages to one another. So, here, we'll denote the messages from the client by m1. So, the client sends a message, the server responds, the client sends a message, the server responds, the client sends a message, the server responds, and so on and so forth. Now, the way PPTP works is, basically, the entire interaction, from the client to the server, is considered as one stream. In other words, what happens is, the messages m1, and m2 and m3, are kind of viewed as one long stream. Here, these two parallel lines means concatenation. So, essentially, we're concatenating all the messages from the client to the server into one long stream. And all that stream is encrypted using the stream cipher with key K. So that's perfectly fine. I mean, there's nothing wrong with that. This messages are encrypted, are treated as one long stream, and they're all encrypted using the same key. The problem is, the same thing is happening also on the server side. In other words, all the messages from the server are also treated as one long stream. So here, they're all concatenated together. And encrypted using, unfortunately, the same pseudo-random seed, in other words, using the same stream cipher key. So basically what's happening here is you see an effect that the two time pad is taking place where the set of messages from the client is encrypted using the same one time pad as a set of messages from the server. The lesson here is that you should never use the same key to encrypt traffic in both directions. In fact, what you need to do is have one key for interaction between the client and the server and one key for interaction between the server and the client. The way I like to write this is really that the shared key k really is a pair of keys. One key is used to encrypt messages from server to client, and one key is used to encrypt messages from client to server. So these are two separate keys that are used, and both sides, of course, know this key. So both sides have this pair of keys, okay? and they can both encrypt. So one is used to encrypt messages in one direction and one is used to encrypt messages in the other direction. So another important example of the two time pad comes up in Wi-Fi communication, particularity in the 80211B protocol. So all of you I'm sure know that the 80211 contains an encryption layer and the original encryption layer was called WEP and WEP fortunately for us is actually a very badly designed protocol so that I can always use it as an example of how not to do things. There are many, many mistakes inside of WEP and here I want to use it as an example of how the two time pad came about. So let me explain how WEP works. So in WEP, there's a client and, and access point. Here's the client, here's the access point. They both share a secret key K. And then, when they wanna transmit a message to one another. Say these are frames, that they transmit to one another. Let's say the client wants to send. A frame containing the plain text M to the axis point, what he would do is first of all he appends some sort of check sum to this plain text. The check sum is not important at this point, what is important is then this new calculation gets encrypted using a stream cypher where the stream cypher key is this concatenation of a value IV and a long term key K. So this IV is a 24 bit string. Okay, this IV is a 24 bit string, and you can imagine that it starts from zero and perhaps it's a counter that counts increments by one for every packet. The reason they did this was the designers of Wep realized that in a stream cypher, the key is only supposed to be used to encrypt one message. So they said well, let's go ahead and change the key after every frame. And the way they changed the key essentially was by prepending this IV to it. And you notice this I-V changes on every packet. So it increments by one on every packet. And the idea, then, is sent in the clear along with the cipher text. So the recipient knows the key K. He knows what the I-V is. He can rederive the PRG of IV concatenating K. And then decrypts the cipher text to recover the original message M. Now the problem with this of course is the IV is only 24 bits long. Which means that there are only two to the 24 possible IV's. Which means that after sixteen million frames are transmitted. Essentially the IV has to cycle. And once it cycles after 60 million frames. Essentially we get a two time path. The same IV will be used to encrypt two different messages. The TK never changes. It's a long term key. And as a result, that same key, namely the IV concatenated K would be used to encrypt two different frames, and the attacker can then figure out the plain text of both frames. So that's one problem. And the worst problem is in fact that on many 80211 cards, if you powercycle the card, the IV will reset back to zero. And as a result, everytime you powercycle the card, essentially you'll be encrypting the next payload using zero concatenated K So after every powercycle, you'll be using the zero concatenated K key to encrypt many, many, many times the same packets. So you see how in WEP, the same pad could be used to encrypt many different messages as soon as the IV is repeated. There is nothing to prevent the IV from repeating after a powercycle. Or am repeating after every sixteen million frames which isn't that many frames in a busy network. So while we are talking about WEP. I want to mention one more mistake that was done in WEP. This is a pretty significant mistake and let's see how we might design it better. So you notice that the designers of WEP basically wanted to use a different key for every packet. Okay. So every frame is encrypted using a different key is concatonation of IV and K. Unfortunately. They didn't randomize the keys and the keys are actually, if you look at the key for frame number one, well, you know, it will be this concatenation of one and k. We'll just feel this 24 bits. Then the key for frame number two is the concatenation of two and k. The key for frame number three is the concatenation of three and k. So the keys are very closely related to one another. And I should probably mention also that these keys themselves can be 104 bits so that the resulting PRG key. Is actually 104 plus 24 bytes which is 128 bytes. Unfortunately these keys are very much related to one another. These are not random keys. You notice they all have the same suffix of 104 bytes. And it turns out the pseudo-random generator used in Wep is not designed to be secure when you use related keys that are so closely related. In other words, the majority of these keys are basically the same. And in fact, for the PRG that's used in WEP. That PRG is called, RSC four. We'll talk about that more in the next segment. It turns out there's an attack. It was discovered by Fluhrer, Mantin and Shamir back in 2001, that shows that after about ten to the six of, after about a million frames. You can recover the secret key. Can recover key. So, this is kind of a disastrous attack that says essentially all you have to do is listen to a million frames. These frames basically. As we said they're all generated from a very common seed, namely a 104 bits of these seeds are all the same. The fact that they've used such closely related keys is enough to actually recover the original key. And it turns out even after the 2001 attack, better attacks have come out that show that these related keys are very much disastrous and in fact these days something like 40,000 frames are sufficient. And so that, within a matter of minutes, you can actually recover the secret key in any WEP network. So WEP provides no security at all for two reasons. First of all, it can resolve in the two time pad. But more significantly, because these keys are so closely related, it's actually possible to recover the key by watching just a few cipher texts. And by the way, we'll see that well, when we do a security analysis of these steps of constructions. In a few segments, we'll start talking about how to analyze these steps of constructions. We'll see that when we have related keys like this, in fact, our security analysis will fail. We won't be able to get the proof to go through. So one could ask what should the designers of a WEP should have done, instead? Well, one approach is to basically treat the frames, you know M1, M2, M3. Each, each one is a separate frame transmitter from the client to the server. He could have treated them as one long stream, and then XOR them potentially. Using the pseudo random generator as one long stream. So the first segment of the pad would have been used to encrypt M1. The second segment of the pad would have been used to encrypt M2. The third segment of the pad would have been used to encrypt M3. And so on and so forth. So they basically could never have had to change the key because the entire interaction is viewed as one long stream. But they chose to have a different key for every frame. So if you want to do that, a better way to do that is, rather than slightly modifying this IV that just slightly modifies the prefix of the key, of the PRG key. A better way to do that is to use a PRG again. So essentially, what you could do is you will take your long term key. And then feed that directly through a PRG. So now we get a long stream of bits that look essentially random. And then the initial segment could be used, the first segment could be used as the key, or frame number one. And then the second segment would be used as the key for, you know, key for frame number two. And so on and so forth. The third segment would be used to encrypt frame #three and so on and so forth, okay? So the nice thing about this is now, essentially, by doing this, each frame has a pseudo-random key. These keys, now, have no relation to one another. They look like random keys. And as a result, if the PRG is secure for random Cs, it was also be secure on this input. Because these keys essentially look as though they're independent of one another. We'll see how to do this analysis formally once we talk about these types of constructions. Since this two-time pad attack comes up so often in practice, it's such a common mistake, I want to give one more example where it comes up so you know how to avoid it. The last example I want to give is in the context of disk encryption. So imagine we have a certain file and maybe the file begins with, you know, the words to Bob. And then the contents of the file follows when this is stored on disk of course the file is gonna get so here we have our disk here, the file is going to get broken into blocks. And each block will be, you know, when we actually store this on a disk, you know, things will be encrypted. You know, so maybe to Bob will go into the first block and then the rest of the content will go into the remaining blocks. But of course this is all incrypted so I'll kind of use these lines here to denote the fact that this is encrypted. And an attacker looking at the disk has no idea what the contents of the message is. But now suppose that at a later time, user goes ahead and modifies, basically fires up the editor. It modifies the file, so now instead of saying to Bob, it says to Eve. And nothing else changes in the file, that's the only change that was made. When the user then saves this modified file to disk, basically he's gonna re encrypt it again. And so the same thing is gonna happen. The file is gonna get broken into blocks. You know, now the file's gonna say to Eve. And everything, of course, is gonna be encrypted. So again, I'll, put these lines here. Now an attacker looking at the disc, taking a snapshot of the disc before the edits. And then looking again at the disc after the edits. What he will see is that the only thing that changed is this little segment here. That's now different. Everything else looks exactly the same. So the attacker, even though he doesn't know what actually happened to the file within the file or what changed, he knows exactly the location where the edits took place. And so the fact that the one-time path or a stream cypher encrypts one bit at a time means that if one change takes place, then it's very easy to tell where that change occurred instantly. That leaks information that the attacker shouldn't actually learn. Ideally you'd like to say that even if the file changed just a little bit. Entire contents of the file should change. Or maybe at least the entire contents of the blocks should change. Here you can see the attacker even knows within the block where the change was actually made, okay. So in fact, because of this, it's usually a bad idea to use stream cyphers for disk encryption. And essentially this is another example of a two-time pad attack because the same pad is used to encrypt two different messages. This, they happen to be very similar, but nevertheless these are two different messages, and the attacker can learn what the change was and in fact he might be able to even learn what the actual changed words were, as a result of this. Okay, so the lesson here is generally we need to do something different for disk encryption. We'll talk about what to do for disk encryption in a later segment, but essentially the one-time pad is generally not a good idea for encrypting blocks on disks. So just again to summarize the two-time pad attack, we saw that you're supposed, I hope I've convinced you that you're never ever, ever supposed to use a stream cypher key more than once. Even though there are natural settings where that might happen, you have to take care and make sure that you're not using the same key more than once. So for network traffic typically what you're supposed to do is every session would have its own key. Within the session the message from the client and the server look as one complete stream. It would be encrypted using one key. Is, the messages from the server to the client would be treated as one stream and encrypted using a different key. And then for this encryption typically would not use a stream cypher because. As changes are made to the file, he would be leaking information about the contents of the file. Okay, so that concludes our brief discussion of the two time pad. Next attack I want to mention. Is a fact that the one time path and stream cyphers in general provide no integrity at all. All they do is they try to provide confidentiality when the key's only used once. They provide no integrity at all but even worse than that it's actually very easy to modify cypher text and have known effects on the corresponding plain text. So let me explain what I mean by that. This property, by the way, is called malleability, and we'll see what I mean by that in just a second. So imagine we have some message M that gets encrypted. So, here, it gets encrypted using a stream cipher. And the cipher text, of course, is then gonna be, M XOR a K. Now an attacker intercepts the cypher text. Well, that doesn't tell him what's, what the plain text is but what he can do is now beyond eavesdropping he can actually become an active attacker and modify the cypher text. So when I say modify the cypher text let's suppose that he XOR the cypher text with a certain value P. Whats called a sub-permutation key. Well, the resulting cipher text then becomes M XOR K, XOR P. So now I'll ask you, when we decrypt the cipher text, what is it going to decrypt to? Well I hope everybody sees manipulating the XORs Basically the decryption becomes M XOR P So you notice that by XOR with this pad P, the attacker was able to have a very specific effect on the resulting plain text. Okay. So a summary is basically you can modify the cypher text. These modifications are undetected. But even worse, they're undetected, they have a very specific impact on the resulting plain text. Namely whatever you XOR the cipher text with is going to have that exact effect on the plain text. So to see where this can be dangerous, let's look at a particular example. Suppose the user sends an email that starts with the words from Bob. In the attacker intercepts the corresponding cypher text. He doesn't know what the cypher text is but let's just for the sake of it let's pretend that he actually knows that this message is actually from Bob. What he wants to do is he wants to modify the ciphertext so that the plain text would now look like it came from somebody else. Say, he wants to make it look like this message actually came from Alice. All he has is the ciphertext. Well, what he can do is he can XOR with a certain three characters. We'll see what those three characters are in just a second. And such that the resulting ciphertext is actually an encryption of the message from Eve. And so that now when the user decrypts that. All of a sudden he'll see, Hey, this message is from Eve. It's not, he'll think this message is from Eve, not from Bob. And that might cause you know, the wrong thing to take place. So here the attacker, even though he himself could not have created a cypher text that says from Eve, by modifying an existing cypher text all of a sudden he was able to make the cypher text that he could not have done without intercepting at least one cypher text. So again by intercepting one cypher text he was able to change it so not it looks like it's from Eve, rather than from Bob. So just to be specific, let's look what these three characters need to be, so let's look at the word Bob. And I'm going to write it in askee. So Bob in askee corresponds to 42 hex six f hex and 62 hex. So little b is encoded as 62, little o is encoded as six f. The word eve is encoded as 45 hex, 76 hex, and 65 hex. Now when I XOR these two words, I'm literally going to x over them as bit strings. So Bob XOR eve, it's not difficult to see that what I get are the three characters zero, seven. Nineteen and 07. So really what these three characters here are going to be. Are simply 07, nineteen, and 07. And by XORing these three characters at the right positions into the cipher text, the attacker was able to chance the cipher text to look like it came from Eve rather than from Bob. So this is an example where having a predictable impact on the cipher text can actually cause quite a bit of problems. And this is this property called malleability. And we say that the one time pad is malleable because it's very easy to compute in cipher texts, and make prescribed changes to the corresponding plain text. So to prevent all this, I'm gonna do that, actually, in two or three lectures. And we're gonna basically show how to add integrity to encryption mechanisms in general. But right now I want you to remember that the one time pad by itself has no integrity and is completely insecure against attackers that actually modify the cipher texts.
Background
The Fluhrer, Mantin and Shamir (FMS) attack, published in their 2001 paper "Weaknesses in the Key Scheduling Algorithm of RC4",[2] takes advantage of a weakness in the RC4 key scheduling algorithm to reconstruct the key from encrypted messages. The FMS attack gained popularity in network attack tools including AirSnort, weplab, and aircrack, which use it to recover the key used by WEP protected wireless networks.
This discussion will use the below RC4 key scheduling algorithm (KSA).
begin ksa(with int keylength, with byte key[keylength])
for i from 0 to 255
S[i] := i
endfor
j := 0
for i from 0 to 255
j := (j + S[i] + key[i mod keylength]) mod 256
swap(S[i],S[j])
endfor
end
The following pseudo-random generation algorithm (PRGA) will also be used.
begin prga(with byte S[256])
i := 0
j := 0
while GeneratingOutput:
i := (i + 1) mod 256
j := (j + S[i]) mod 256
swap(S[i],S[j])
output S[(S[i] + S[j]) mod 256]
endwhile
end
The attack
The basis of the FMS attack lies in the use of weak initialization vectors (IVs) used with RC4. RC4 encrypts one byte at a time with a keystream output from prga(); RC4 uses the key to initialize a state machine via ksa(), and then continuously modifies the state and generates a new byte of the keystream from the new state. Theoretically, the key stream functions as a random one-time pad, as a pseudo-random number generator controls the output at each step.
With certain IVs, an attacker knowing the first byte of the keystream and the first m bytes of the key can derive the (m + 1)th byte of the key due to a weakness in the KSA. Because the first byte of the plaintext comes from the WEP SNAP header, an attacker can assume they can derive the first byte of the keystream from B ⊕ 0xAA (the SNAP header is almost always 0xAA). From there, they only need an IV in the form (a + 3, n − 1, x) for key index a equal to 0, element value space n equal to 256 (since 8 bits make a byte), and any x. To start, the attacker needs IVs of (3, 255, x). WEP uses 24-bit IVs, making each value one byte long.
To start, the attacker utilizes the IV as the first 3 elements in K[ ]. They fill the S-box S[ ] with sequential values from 0 to n as RC4 does when initializing the S-box from a known K[ ]. They then perform the first 3 iterations of ksa() to begin initializing the S-box.
After the third step, the attacker can possibly, but not definitely, derive the fourth byte of the key using the keystream output O by computing (O − j − S[i]) mod n = K[i], with the value i = 3 at this step.
At this point, the attacker does not yet have the fourth byte of the key. This algorithm does not regenerate the next byte of the key; it generates a possible value of the key. By collecting multiple messages—for example WEP packets—and repeating these steps, the attacker will generate a number of different possible values. The correct value appears significantly more frequently than any other; the attacker can determine the value of the key by recognizing this value and selecting it as the next byte. At this point, they can start the attack over again on the fifth byte of the key.
Although the attacker cannot attack words of the key out of order, they can store messages for later sequential attack on later words once they know earlier words. Again, they only need messages with weak IVs, and can discard others. Through this process, they can gather a large number of messages for attack on the entire key; in fact, they can store only a short portion of the beginning of those messages, just enough to carry the attack out as far as the word of the key the IV will allow them to attack.
References
- ^ "RSA Security Response to Weaknesses in Key Scheduling Algorithm of RC4". RSA Laboratories. 9 September 2001.
- ^ Fluhrer, S., Mantin, I., and A. Shamir, "Weaknesses in the Key Scheduling Algorithm of RC4", Selected Areas of Cryptography: SAC 2001, Lecture Notes in Computer Science Vol. 2259, pp 1-24, 2001.
See also
This page was last edited on 19 February 2024, at 19:54