Related-key attack

Last updated

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. 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.

Contents

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 confidentiality and integrity algorithms.

Mark Blunden and Adrian Escott described differential related key attacks on five and six rounds of KASUMI. [1] Differential attacks were introduced by Biham and Shamir. Related key attacks were first introduced by Biham. [2] Differential related key attacks are discussed in Kelsey et al. [3]

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 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. More devastating attacks take advantage of certain weak keys 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.

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.

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. 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 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.

Related Research Articles

<span class="mw-page-title-main">Data Encryption Standard</span> Early unclassified symmetric-key block cipher

The Data Encryption Standard is a symmetric-key algorithm for the encryption of digital data. Although its short key length of 56 bits makes it too insecure for modern applications, it has been highly influential in the advancement of cryptography.

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.

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.

Articles related to cryptography include:

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).

In cryptography, a ciphertext-only attack (COA) or known ciphertext attack is an attack model for cryptanalysis where the attacker is assumed to have access only to a set of ciphertexts. While the attacker has no channel providing access to the plaintext prior to encryption, in all practical ciphertext-only attacks, the attacker still has some knowledge of the plaintext. For instance, the attacker might know the language in which the plaintext is written or the expected statistical distribution of characters in the plaintext. Standard protocol data and messages are commonly part of the plaintext in many deployed systems, and can usually be guessed or known efficiently as part of a ciphertext-only attack on these systems.

In cryptography, Khufu and Khafre are two block ciphers designed by Ralph Merkle in 1989 while working at Xerox's Palo Alto Research Center. Along with Snefru, a cryptographic hash function, the ciphers were named after the Egyptian Pharaohs Khufu, Khafre and Sneferu.

In cryptography, LOKI89 and LOKI91 are symmetric-key block ciphers designed as possible replacements for the Data Encryption Standard (DES). The ciphers were developed based on a body of work analysing DES, and are very similar to DES in structure. The LOKI algorithms were named for Loki, the god of mischief in Norse mythology.

IEEE 802.11i-2004, or 802.11i for short, is an amendment to the original IEEE 802.11, implemented as Wi-Fi Protected Access II (WPA2). The draft standard was ratified on 24 June 2004. This standard specifies security mechanisms for wireless networks, replacing the short Authentication and privacy clause of the original standard with a detailed Security clause. In the process, the amendment deprecated broken Wired Equivalent Privacy (WEP), while it was later incorporated into the published IEEE 802.11-2007 standard.

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.

Counter Mode Cipher Block Chaining Message Authentication Code Protocol or CCM mode Protocol (CCMP) is an encryption protocol designed for Wireless LAN products that implements the standards of the IEEE 802.11i amendment to the original IEEE 802.11 standard. CCMP is an enhanced data cryptographic encapsulation mechanism designed for data confidentiality and based upon the Counter Mode with CBC-MAC of the Advanced Encryption Standard (AES) standard. It was created to address the vulnerabilities presented by Wired Equivalent Privacy (WEP), a dated, insecure protocol.

In cryptography, REDOC II and REDOC III are block ciphers designed by Michael Wood (cryptographer) for Cryptech Inc and are optimised for use in software. Both REDOC ciphers are patented.

Stream ciphers, where plaintext bits are combined with a cipher bit stream by an exclusive-or operation (xor), can be very secure if used properly. However, they are vulnerable to attacks if certain precautions are not followed:

<span class="mw-page-title-main">Boomerang attack</span> Form of cryptanalysis

In cryptography, the boomerang attack is a method for the cryptanalysis of block ciphers based on differential cryptanalysis. The attack was published in 1999 by David Wagner, who used it to break the COCONUT98 cipher.

<span class="mw-page-title-main">Wireless security</span> Aspect of wireless networks

Wireless security is the prevention of unauthorized access or damage to computers or data using wireless networks, which include Wi-Fi networks. The term may also refer to the protection of the wireless network itself from adversaries seeking to damage the confidentiality, integrity, or availability of the network. The most common type is Wi-Fi security, which includes Wired Equivalent Privacy (WEP) and Wi-Fi Protected Access (WPA). WEP is an old IEEE 802.11 standard from 1997. It is a notoriously weak security standard: the password it uses can often be cracked in a few minutes with a basic laptop computer and widely available software tools. WEP was superseded in 2003 by WPA, a quick alternative at the time to improve security over WEP. The current standard is WPA2; some hardware cannot support WPA2 without firmware upgrade or replacement. WPA2 uses an encryption device that encrypts the network with a 256-bit key; the longer key length improves security over WEP. Enterprises often enforce security using a certificate-based system to authenticate the connecting device, following the standard 802.11X.

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

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.

IEEE 802.1AE is a network security standard that operates at the medium access control layer and defines connectionless data confidentiality and integrity for media access independent protocols. It is standardized by the IEEE 802.1 working group.

The following outline is provided as an overview of and topical guide to cryptography:

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.

References

  1. Matsui, M., "New block encryption algorithm MISTY", 1997
  2. Biham, Eli. "New types of cryptanalytic attacks using related keys." Journal of Cryptology 7.4 (1994): 229-246.
  3. 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.