Related-key attack
Encyclopedia
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 he doesn't know, at first, what the bits are. This appears, at first glance, to be an unrealistic model; it would certainly be unlikely that an attacker could persuade a human cryptographer to encrypt plaintexts under numerous secret keys related in some way. However, modern cryptography is implemented using complex computer protocols, often not vetted by cryptographers, and in some cases a related-key attack is made very feasible.
(WEP) used in WiFi
wireless networks. Each client Wi-Fi network adapter and wireless access point
in a WEP-protected network shares the same WEP key. Encryption uses the RC4
algorithm, a stream cipher
. It is essential that the same key never be used twice with a stream cipher. To prevent this from happening, WEP includes a 24-bit initialization vector
(IV) in each message packet. The RC4 key for that packet is the IV concatenated with the WEP key. WEP keys have to be changed manually and this typically happens infrequently. An attacker therefore can assume that all the keys used to encrypt packets share a single WEP key. This fact opened up WEP to a series of attacks which proved devastating. The simplest to understand uses the fact that the 24-bit IV only allows a little under 17 million possibilities. Because of the birthday paradox
, it is likely that for every 4096 packets, two will share the same IV and hence the same RC4 key, allowing the packets to be attacked. Far more deadly attacks take advantage of certain weak key
s in RC4 and eventually allow the WEP key itself to be recovered. In 2005, agents from the U.S. Federal Bureau of Investigation
publicly demonstrated the ability to do this with widely available software tools in about three minutes.http://www.smallnetbuilder.com/index.php?option=com_content&task=view&id=24251&Itemid=100
or other key derivation function
.
For example, a replacement for WEP, Wi-Fi Protected Access
(WPA), uses three levels of keys: master key, working key and RC4 key. The master WPA key is shared with each client and access point and is used in a protocol called TKIP to create new working keys frequently enough to thwart known attack methods. The working keys are then combined with a longer, 48-bit IV to form the RC4 key for each packet. This design mimics the WEP approach enough to allow WPA to be used with first-generation Wi-Fi network cards, some of which implemented portions of WEP in hardware. However, not all first-generation access points can run WPA.
Another, more conservative approach is to employ a cipher designed to prevent related-key attacks altogether, usually by incorporating a strong key schedule
. A newer version of Wi-Fi Protected Access, WPA2, uses the AES
block cipher
instead of RC4, in part for this reason. There are related-key attacks against reduced-round AES, but unlike those against RC4, they're far from practical to implement, and WPA2's key generation functions may provide some security against them. Many older network cards cannot run WPA2.
Cryptography
Cryptography is the practice and study of techniques for secure communication in the presence of third parties...
, a related-key attack is any form of cryptanalysis
Cryptanalysis
Cryptanalysis is the study of methods for obtaining the meaning of encrypted information, without access to the secret information that is normally required to do so. Typically, this involves knowing how the system works and finding a secret key...
where the attacker can observe the operation of a cipher
Cipher
In cryptography, a cipher is an algorithm for performing encryption or decryption — a series of well-defined steps that can be followed as a procedure. An alternative, less common term is encipherment. In non-technical usage, a “cipher” is the same thing as a “code”; however, the concepts...
under several different keys
Key (cryptography)
In cryptography, a key is a piece of information that determines the functional output of a cryptographic algorithm or cipher. Without a key, the algorithm would produce no useful result. In encryption, a key specifies the particular transformation of plaintext into ciphertext, or vice versa...
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 he doesn't know, at first, what the bits are. This appears, at first glance, to be an unrealistic model; it would certainly be unlikely that an attacker could persuade a human cryptographer to encrypt plaintexts under numerous secret keys related in some way. However, modern cryptography is implemented using complex computer protocols, often not vetted by cryptographers, and in some cases a related-key attack is made very feasible.
WEP
An important example of a cryptographic protocol that failed because of a related-key attack is Wired Equivalent PrivacyWired Equivalent Privacy
Wired Equivalent Privacy is a weak security algorithm for IEEE 802.11 wireless networks. Introduced as part of the original 802.11 standard ratified in September 1999, its intention was to provide data confidentiality comparable to that of a traditional wired network...
(WEP) used in WiFi
WIFI
WIFI is a radio station broadcasting a brokered format. Licensed to Florence, New Jersey, USA, the station is currently operated by Florence Broadcasting Partners, LLC.This station was previously owned by Real Life Broadcasting...
wireless networks. Each client Wi-Fi network adapter and wireless access point
Wireless access point
In computer networking, a wireless access point is a device that allows wireless devices to connect to a wired network using Wi-Fi, Bluetooth or related standards...
in a WEP-protected network shares the same WEP key. Encryption uses the RC4
RC4
In cryptography, RC4 is the most widely used software stream cipher and is used in popular protocols such as Secure Sockets Layer and WEP...
algorithm, a stream cipher
Stream cipher
In cryptography, a stream cipher is a symmetric key cipher where plaintext digits are combined with a pseudorandom cipher digit stream . In a stream cipher the plaintext digits are encrypted one at a time, and the transformation of successive digits varies during the encryption...
. It is essential that the same key never be used twice with a stream cipher. To prevent this from happening, WEP includes a 24-bit initialization vector
Initialization vector
In cryptography, an initialization vector is a fixed-size input to a cryptographic primitive that is typically required to be random or pseudorandom...
(IV) in each message packet. The RC4 key for that packet is the IV concatenated with the WEP key. WEP keys have to be changed manually and this typically happens infrequently. An attacker therefore can assume that all the keys used to encrypt packets share a single WEP key. This fact opened up WEP to a series of attacks which proved devastating. The simplest to understand uses the fact that the 24-bit IV only allows a little under 17 million possibilities. Because of the birthday paradox
Birthday paradox
In probability theory, the birthday problem or birthday paradox pertains to the probability that, in a set of n randomly chosen people, some pair of them will have the same birthday. By the pigeonhole principle, the probability reaches 100% when the number of people reaches 366. However, 99%...
, it is likely that for every 4096 packets, two will share the same IV and hence the same RC4 key, allowing the packets to be attacked. Far more deadly attacks take advantage of certain weak key
Weak key
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, if one generates a random key to encrypt a message, weak keys are very...
s in RC4 and eventually allow the WEP key itself to be recovered. In 2005, agents from the U.S. Federal Bureau of Investigation
Federal Bureau of Investigation
The Federal Bureau of Investigation is an agency of the United States Department of Justice that serves as both a federal criminal investigative body and an internal intelligence agency . The FBI has investigative jurisdiction over violations of more than 200 categories of federal crime...
publicly demonstrated the ability to do this with widely available software tools in about three minutes.http://www.smallnetbuilder.com/index.php?option=com_content&task=view&id=24251&Itemid=100
Preventing related-key attacks
One approach to preventing related-key attacks is to design protocols and applications so that encryption keys will never have a simple relationship with each other. For example, each encryption key can be generated from the underlying key material using a cryptographic hash functionCryptographic hash function
A cryptographic hash function is a deterministic procedure that takes an arbitrary block of data and returns a fixed-size bit string, the hash value, such that an accidental or intentional change to the data will change the hash value...
or other key derivation function
Key derivation function
In cryptography, a key derivation function derives one or more secret keys from a secret value such as a master key or other known information such as a password or passphrase using a pseudo-random function...
.
For example, a replacement for WEP, Wi-Fi Protected Access
Wi-Fi Protected Access
Wi-Fi Protected Access and Wi-Fi Protected Access II are two security protocols and security certification programs developed by the Wi-Fi Alliance to secure wireless computer networks...
(WPA), uses three levels of keys: master key, working key and RC4 key. The master WPA key is shared with each client and access point and is used in a protocol called TKIP to create new working keys frequently enough to thwart known attack methods. The working keys are then combined with a longer, 48-bit IV to form the RC4 key for each packet. This design mimics the WEP approach enough to allow WPA to be used with first-generation Wi-Fi network cards, some of which implemented portions of WEP in hardware. However, not all first-generation access points can run WPA.
Another, more conservative approach is to employ a cipher designed to prevent related-key attacks altogether, usually by incorporating a strong key schedule
Key schedule
[[Image:DES-key-schedule.png|thumbnail|220px|The key schedule of DES [[Image:DES-key-schedule.png|thumbnail|220px|The key schedule of DES [[Image:DES-key-schedule.png|thumbnail|220px|The key schedule of DES ("[[Image:DES-key-schedule.png|thumbnail|220px|The key schedule of DES ("...
. A newer version of Wi-Fi Protected Access, WPA2, uses the AES
Advanced Encryption Standard
Advanced Encryption Standard is a specification for the encryption of electronic data. It has been adopted by the U.S. government and is now used worldwide. It supersedes DES...
block cipher
Block cipher
In cryptography, a block cipher is a symmetric key cipher operating on fixed-length groups of bits, called blocks, with an unvarying transformation. A block cipher encryption algorithm might take a 128-bit block of plaintext as input, and output a corresponding 128-bit block of ciphertext...
instead of RC4, in part for this reason. There are related-key attacks against reduced-round AES, but unlike those against RC4, they're far from practical to implement, and WPA2's key generation functions may provide some security against them. Many older network cards cannot run WPA2.