Fluhrer, Mantin, and Shamir attack

Fluhrer, Mantin, and Shamir attack

In cryptography, the Fluhrer, Mantin, and Shamir attack allows an attacker to recover the key in an RC4 encrypted stream from a large number of messages in that stream.

Background

The Fluhrer, Mantin and Shamir (FMS) attack takes advantage of a weakness in the RC4 key scheduling algorithm to reconstruct the key from a number of collected encrypted messages. The FMS attack gained popularity in tools such as AirSnort and aircrack, both of which attack WEP encrypted wireless networks.

For this discussion, we 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

We will also use the below pseudo-random generation algorithm (PRGA).

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 "m"th byte of the keystream can derive the "m+1"th byte due to a weakness in the PRNG used to generate the keystream. Because the first byte of the plaintext comes from the WEP SNAP header, an attacker can assume she can derive the first byte of the keystream from B oplus 0xAA. From there, she only needs an IV in the form left (a+3, n-1, x ight ) for key index a origin 0, element value space n (256 since 8 bits make a byte), and any X. To start, the attacker needs IVs of left (3, 255, x ight ). 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 [] ". She fills the S-box "S [] " with sequential values from 0 to n as RC4 does when initializing the S-box from a known "K [] ". She then performs 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 left (O - j - Sleft [i ight ] ight ) mod n = Kleft [i ight ] , 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, she 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, she 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, she can store messages for later sequential attack on later words once she knows earlier words. Again, she only needs messages with weak IVs, and can discard others. Through this process, she can gather a large number of messages for attack on the entire key; in fact, she 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 her to attack.

References

*


Wikimedia Foundation. 2010.

Игры ⚽ Поможем решить контрольную работу

Look at other dictionaries:

  • RC4 — In cryptography, RC4 (also known as ARC4 or ARCFOUR meaning Alleged RC4, see below) is the most widely used software stream cipher and is used in popular protocols such as Secure Sockets Layer (SSL) (to protect Internet traffic) and WEP (to… …   Wikipedia

  • RC4 —  Ne doit pas être confondu avec Route coloniale 4. Schéma d un tour de RC4 RC4 est un algorithme de chiffrement à flot conçu en 1987 par Ronald Rivest, l un des inventeurs du …   Wikipédia en Français

  • IEEE 802.11 — is a set of standards for wireless local area network (WLAN) computer communication, developed by the IEEE LAN/MAN Standards Committee (IEEE 802) in the 5 GHz and 2.4 GHz public spectrum bands.General descriptionThe 802.11 family includes over… …   Wikipedia

  • BitTorrent protocol encryption — Protocol encryption (PE), message stream encryption (MSE), or protocol header encrypt (PHE)[1] are related features of some peer to peer file sharing clients, including BitTorrent clients. They attempt to enhance privacy and confidentiality. In… …   Wikipedia

  • WEP — Wired Equivalent Privacy (WEP)  алгоритм для обеспечения безопасности сетей Wi Fi. Используется для обеспечения конфиденциальности и защиты передаваемых данных авторизированных пользователей беспроводной сети от прослушивания. Существует две …   Википедия

  • FMS — ist die Abkürzung für: Fachmittelschule, auch Fachmaturitätsschule, weiterführende Schulausbildung in der Schweiz False Memory Syndrom, seelische Beschwerden aufgrund einer Pseudoerinnerung fast mounting system, ein Schnellmontagesystem unter… …   Deutsch Wikipedia

  • Wireless security — An example wireless router, that can implement wireless security features Wireless security is the prevention of unauthorized access or damage to computers using wireless networks. Many laptop computers have wireless cards pre installed. The… …   Wikipedia

  • Wired Equivalent Privacy — (WEP) is a deprecated algorithm to secure IEEE 802.11 wireless networks. Wireless networks broadcast messages using radio and are thus more susceptible to eavesdropping than wired networks. When introduced in 1999, WEP was intended to provide… …   Wikipedia

  • Cracking of wireless networks — is the penetration of wireless networks. A wireless network can be penetrated in a number of ways. These ways vary greatly in the level of computer skill and commitment they require. Once within a network, a skilled hacker can modify software,… …   Wikipedia

  • Timeline of cryptography — Below is a timeline of notable events related to cryptography.BCE *3500s The Sumerians develop cuneiform writing and the Egyptians develop hieroglyphic writing. *1500s The Phoenicians develop an alphabet *600 500 Hebrew scholars make use of… …   Wikipedia

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”