Fluhrer, Mantin and Shamir attack

Last updated

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.

Contents

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.

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.

Related Research Articles

The MD5 message-digest algorithm is a widely used hash function producing a 128-bit hash value. MD5 was designed by Ronald Rivest in 1991 to replace an earlier hash function MD4, and was specified in 1992 as RFC 1321.

In cryptography, RC4 is a stream cipher. While it is remarkable for its simplicity and speed in software, multiple vulnerabilities have been discovered in RC4, rendering it insecure. It is especially vulnerable when the beginning of the output keystream is not discarded, or when nonrandom or related keys are used. Particularly problematic uses of RC4 have led to very insecure protocols such as WEP.

<span class="mw-page-title-main">Stream cipher</span> Type of symmetric key cipher

A stream cipher is a symmetric key cipher where plaintext digits are combined with a pseudorandom cipher digit stream (keystream). In a stream cipher, each plaintext digit is encrypted one at a time with the corresponding digit of the keystream, to give a digit of the ciphertext stream. Since encryption of each digit is dependent on the current state of the cipher, it is also known as state cipher. In practice, a digit is typically a bit and the combining operation is an exclusive-or (XOR).

In cryptography, an initialization vector (IV) or starting variable is an input to a cryptographic primitive being used to provide the initial state. The IV is typically required to be random or pseudorandom, but sometimes an IV only needs to be unpredictable or unique. Randomization is crucial for some encryption schemes to achieve semantic security, a property whereby repeated usage of the scheme under the same key does not allow an attacker to infer relationships between segments of the encrypted message. For block ciphers, the use of an IV is described by the modes of operation.

In cryptography, a block cipher mode of operation is an algorithm that uses a block cipher to provide information security such as confidentiality or authenticity. A block cipher by itself is only suitable for the secure cryptographic transformation of one fixed-length group of bits called a block. A mode of operation describes how to repeatedly apply a cipher's single-block operation to securely transform amounts of data larger than a block.

Transport Layer Security (TLS) is a cryptographic protocol designed to provide communications security over a computer network. The protocol is widely used in applications such as email, instant messaging, and voice over IP, but its use in securing HTTPS remains the most publicly visible.

Wired Equivalent Privacy (WEP) was a severely flawed security algorithm for 802.11 wireless networks. Introduced as part of the original IEEE 802.11 standard ratified in 1997, its intention was to provide data confidentiality comparable to that of a traditional wired network. WEP, recognizable by its key of 10 or 26 hexadecimal digits, was at one time widely used, and was often the first security choice presented to users by router configuration tools.

Wi-Fi Protected Access (WPA), Wi-Fi Protected Access 2 (WPA2), and Wi-Fi Protected Access 3 (WPA3) are the three security certification programs developed after 2000 by the Wi-Fi Alliance to secure wireless computer networks. The Alliance defined these in response to serious weaknesses researchers had found in the previous system, Wired Equivalent Privacy (WEP).

<span class="mw-page-title-main">Cryptographic hash function</span> Hash function that is suitable for use in cryptography

A cryptographic hash function (CHF) is a hash algorithm that has special properties desirable for a cryptographic application:

In cryptography, a weak key is a key, which, used with a specific cipher, makes the cipher behave in some undesirable way. Weak keys usually represent a very small fraction of the overall keyspace, which usually means that, a cipher key made by random number generation is very unlikely to give rise to a security problem. Nevertheless, it is considered desirable for a cipher to have no weak keys. A cipher with no weak keys is said to have a flat, or linear, key space.

CipherSaber is a simple symmetric encryption protocol based on the RC4 stream cipher. Its goals are both technical and political: it gives reasonably strong protection of message confidentiality, yet it's designed to be simple enough that even novice programmers can memorize the algorithm and implement it from scratch. According to the designer, a CipherSaber version in the QBASIC programming language takes just sixteen lines of code. Its political aspect is that because it's so simple, it can be reimplemented anywhere at any time, and so it provides a way for users to communicate privately even if government or other controls make distribution of normal cryptographic software completely impossible.

Temporal Key Integrity Protocol is a security protocol used in the IEEE 802.11 wireless networking standard. TKIP was designed by the IEEE 802.11i task group and the Wi-Fi Alliance as an interim solution to replace WEP without requiring the replacement of legacy hardware. This was necessary because the breaking of WEP had left Wi-Fi networks without viable link-layer security, and a solution was required for already deployed hardware. However, TKIP itself is no longer considered secure, and was deprecated in the 2012 revision of the 802.11 standard.

In cryptography, a related-key attack is any form of cryptanalysis where the attacker can observe the operation of a cipher under several different keys whose values are initially unknown, but where some mathematical relationship connecting the keys is known to the attacker. For example, the attacker might know that the last 80 bits of the keys are always the same, even though they don't know, at first, what the bits are.

E0 is a stream cipher used in the Bluetooth protocol. It generates a sequence of pseudorandom numbers and combines it with the data using the XOR operator. The key length may vary, but is generally 128 bits.

Py is a stream cipher submitted to eSTREAM by Eli Biham and Jennifer Seberry. It is one of the fastest eSTREAM candidates at around 2.6 cycles per byte on some platforms. It has a structure a little like RC4, but adds an array of 260 32-bit words which are indexed using a permutation of bytes, and produces 64 bits in each round.

<span class="mw-page-title-main">Aircrack-ng</span> Software suite

Aircrack-ng is a network software suite consisting of a detector, packet sniffer, WEP and WPA/WPA2-PSK cracker and analysis tool for 802.11 wireless LANs. It works with any wireless network interface controller whose driver supports raw monitoring mode and can sniff 802.11a, 802.11b and 802.11g traffic. Packages are released for Linux and Windows.

In cryptography, a distinguishing attack is any form of cryptanalysis on data encrypted by a cipher that allows an attacker to distinguish the encrypted data from random data. Modern symmetric-key ciphers are specifically designed to be immune to such an attack. In other words, modern encryption schemes are pseudorandom permutations and are designed to have ciphertext indistinguishability. If an algorithm is found that can distinguish the output from random faster than a brute force search, then that is considered a break of the cipher.

This article summarizes publicly known attacks against block ciphers and stream ciphers. Note that there are perhaps attacks that are not publicly known, and not all entries may be up to date.

VMPC for cryptography is a stream cipher similar to the well known and popular cipher RC4 designed by Ron Rivest. It was designed by Bartosz Żółtak, presented in 2004 at the Fast Software Encryption conference. VMPC is a modification of the RC4 cipher.

The bar mitzvah attack is an attack on the SSL/TLS protocols that exploits the use of the RC4 cipher with weak keys for that cipher. While this affects only the first hundred or so bytes of only the very small fraction of connections that happen to use weak keys, it allows significant compromise of user security, for example by allowing the interception of password information which could then be used for long-term exploitation.

References

  1. ↑ "RSA Security Response to Weaknesses in Key Scheduling Algorithm of RC4". RSA Laboratories. 9 September 2001.
  2. ↑ 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 is based on this Wikipedia article
Text is available under the CC BY-SA 4.0 license; additional terms may apply.
Images, videos and audio are available under their respective licenses.