View source for Related-key attack

In [[Cryptography|cryptography]], a '''related-key attack''' is any form of [[Cryptanalysis|cryptanalysis]] where the attacker can observe the operation of a [[Cipher|cipher]] under several different [[Key (cryptography)|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.

==KASUMI==
KASUMI is an eight round, 64-bit block cipher with a 128-bit key. It is based upon MISTY1 and was designed to form the basis of the [[3G|3G]] confidentiality and integrity algorithms.

Mark Blunden and Adrian Escott described differential related key attacks on five and six rounds of KASUMI.<ref>Matsui, M., "New block encryption algorithm MISTY", 1997</ref> Differential attacks were introduced by Biham and Shamir. Related key attacks were first introduced by Biham.<ref>Biham, Eli. "New types of cryptanalytic attacks using related keys." Journal of Cryptology 7.4 (1994): 229-246.</ref> Differential related key attacks are discussed in Kelsey et al.<ref>Kelsey, John, Bruce Schneier, and David Wagner. "Key-schedule cryptanalysis of idea, g-des, gost, safer, and triple-des." Advances in Cryptology"CRYPTO’96. Springer Berlin/Heidelberg, 1996.</ref>

==WEP==
An important example of a cryptographic protocol that failed because of a related-key attack is [[Wired Equivalent Privacy]] (WEP) used in [[Wi-Fi]] wireless networks.  Each client [[Engineering:Wireless network interface controller|Wi-Fi network adapter]] and [[Wireless access point|wireless access point]] in a WEP-protected network shares the same WEP key. Encryption uses the [[RC4]] algorithm, a [[Stream cipher|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|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. More devastating attacks take advantage of certain [[Weak key|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.

==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 [[Key derivation function|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 [[Temporal Key Integrity Protocol]] (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]]. A newer version of Wi-Fi Protected Access, WPA2, uses the [[Advanced Encryption Standard|AES]] [[Block cipher|block cipher]] instead of RC4, in part for this reason. There are [[Advanced Encryption Standard#Security|related-key attacks against 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.<!-- I'd like to specifically say that WPA2 uses a hash function or something to generate temporal keys but I can't find a citation.-->  Many older network cards cannot run WPA2.

==References==
{{Reflist}}

{{Cryptography navbox | block | stream}}
{{Attack models in cryptanalysis|state=expanded}}

[[Category:Cryptographic attacks]]

{{Sourceattribution|Related-key attack}}