Attack model
In cryptanalysis, attack models or attack types[1] are a classification of cryptographic attacks specifying the kind of access a cryptanalyst has to a system under attack when attempting to "break" an encrypted message (also known as ciphertext) generated by the system. The greater the access the cryptanalyst has to the system, the more useful information he can get to utilize for breaking the cypher.
In cryptography, a sending party uses a cipher to encrypt (transform) a secret plaintext into a ciphertext, which is sent over an insecure communication channel to the receiving party. The receiving party uses an inverse cipher to decrypt the ciphertext to obtain the plaintext. A secret knowledge is required to apply the inverse cipher to the ciphertext. This secret knowledge is usually a short number or string called a key. In a cryptographic attack a third party cryptanalyst analyzes the ciphertext to try to "break" the cipher, to read the plaintext and obtain the key so that future enciphered messages can be read. It is usually assumed that the encryption and decryption algorithms themselves are public knowledge and available to the cryptographer, as this is the case for modern ciphers which are published openly. This assumption is called Kerckhoffs's principle.
Models
Some common attack models are:
- Ciphertext-only attack (COA) - in this type of attack it is assumed that the cryptanalyst has access only to the ciphertext, and has no access to the plaintext. This type of attack is the most likely case encountered in real life cryptanalysis, but is the weakest attack because of the cryptanalyst's lack of information. Modern ciphers are required to be very resistant to this type of attack. In fact, a successful cryptanalysis in the COA model usually requires that the cryptanalyst must have some information on the plaintext, such as its distribution, the language in which the plaintexts are written in, standard protocol data or framing which is part of the plaintext, etc.[2]
- Brute force attack or exhaustive key search - in this attack every possible key is tried until the correct one is found. Every cipher except the unbreakable Information-theoretically secure methods like the one time pad is vulnerable to this method, and as its difficulty does not depend on the cipher but only on the key length - it's not considered a real cryptanalysis of the cipher. If the key has N bits, there are 2N possible keys to try, so a brute-force attack can recover the cipher in a worst-case time proportional to 2N and an average time of 2N-1. This is often used as a standard of comparison for other attacks. Brute-force can be applied in ciphertext-only settings, but the cryptanalyst must have enough information about the plaintext (at least N bits) to allow the identification of the correct key once it is tried.
- Known-plaintext attack (KPA) - in this type of attack it is assumed that the cryptanalyst has access to at least a limited number of pairs of plaintext and the corresponding enciphered text. An interesting example dates back to World War II, during which the Allies used known-plaintexts in their successful cryptanalysis of the Enigma machine cipher. The plaintext samples are called "cribs"; the term originated at Bletchley Park, the British World War II decryption operation.[3][4] Very early on cribs were produced from stolen plaintext and intercepted ciphertext, and as such qualify for their classification as a known-plaintext attack. However, as knowledge and experience increased, the known-plaintexts were actually generated mostly through a series of intelligent guesses based on gained experience and logic, and not through a channel providing direct access to these plaintext. Technically the latter attacks are classified as the harder-to-execute ciphertext-only attacks.
- Chosen-plaintext attack (CPA) - in this attack the cryptanalyst is able to choose a number of plaintexts to be enciphered and have access to the resulting ciphertext. This allows him to explore whatever areas of the plaintext state space he wishes and may allow him to exploit vulnerabilities and nonrandom behavior which appear only with certain plaintexts. In the widely used public-key cryptosystems, the key used to encrypt the plaintext is publicly distributed and anyone may use it, allowing the cryptanalyst to create ciphertext of any plaintext he wants. So public-key algorithms must be resistant to all chosen-plaintext attacks.
- Adaptive chosen-plaintext attack (CPA2) - in this attack the analyst can choose a sequence of plaintexts to be encrypted and have access to the ciphertexts. At each step he has the opportunity to analyze the previous results before choosing the next plaintext. This allows him to have more information when choosing plaintexts than if he was required to choose all the plaintexts beforehand as required in the chosen-plaintext attack.
- Chosen-ciphertext attack (CCA) - in this attack the analyst can choose arbitrary ciphertext and have access to plaintext decrypted from it. In an actual real life case this would require the analyst to have access to the communication channel and the recipient end.
- Lunchtime attack or midnight attack - In this variant it is assumed the cryptanalyst can only have access to the system for a limited time or a limited number of plaintext-ciphertext pairs, after which he must show progress. The name comes from the common security vulnerability in which an employee signs into his encrypted computer and then leaves it unattended while he goes to lunch, allowing an attacker a limited-time access to the system.
- Adaptive chosen-ciphertext attack (CCA2) - in this attack he can choose a series of ciphertexts and see the resulting plaintexts, with the opportunity at each step to analyze the previous ciphertext-plaintext pairs before choosing the next ciphertext.
- Open key model attacks - where the attacker has some knowledge about the key for the cipher being attacked.[5]
- Related-key attack - in this attack the cryptanalyst has access to ciphertext encrypted from the same plaintext using other (unknown) keys which are related to the target key in some mathematically defined way. For example, the analyst might know that the last N bits of the keys are identical. This is relevant because modern computer encryption protocols generate keys automatically, leading to the possibility of relations between them. The Wired Equivalent Privacy (WEP) privacy protocol which was used to protect WiFi internet devices was found to be vulnerable to a related-key attack due to a weakness in RC4.
- Known-key distinguishing attack and chosen-key distinguishing attack, where an attacker can distinguish ciphertext from random along with the knowledge or ability to choose the key.[5]
- Side-channel attack - This is not strictly speaking a cryptanalytic attack, and does not depend on the strength of the cipher. It refers to using other data about the encryption or decryption process to gain information about the message, such as electronic noise produced by encryption machines, sound produced by keystrokes as the plaintext is typed, or measuring how much time various computations take to perform.
Different attack models are used for other cryptographic primitives, or more generally for all kind of security systems. Examples for such attack models are:
References
- ^ Information Security Laboratory (powerpoint)
- ^ Bruce Schneier (2000). "Cryptography". Secrets & Lies: Digital Security in a Networked World (Hardcover ed.). Wiley Computer Publishing Inc. pp. 90–91. ISBN 0-471-25311-1.
- ^ Gordon Welchman, The Hut Six Story: Breaking the Enigma Codes, p. 78.
- ^ Michael Smith, "How It Began: Bletchley Park Goes to War," in B. Jack Copeland, ed., Colossus: The Secrets of Bletchley Park's Codebreaking Computers.
- ^ a b Elena Andreeva; Andrey Bogdanov; Bart Mennink (8 July 2014). Towards Understanding the Known-Key Security of Block Ciphers. FSE 2014.
Further reading
- Niels Ferguson; Bruce Schneier (2003). "Introduction to Cryptography: Attacks". In Carol A. Long (ed.). Practical Cryptography (Hardcover ed.). Wiley Publishing Inc. pp. 30–32. ISBN 0-471-22894-X.
- Susan Hansche; John Berti; Chris Hare (2004). "6 - Cryptography: Cryptoanalysis and attacks". Official (ISC)² Guide to the CISSP Exam (Hardcover ed.). Auerbach Publications. pp. 389–393. ISBN 0-8493-1707-X.
- Stinson, Douglas R. (19 July 2004). "A Polemic on Notions of Cryptographic Security". University of Waterloo Centre for Applied Cryptographic Research. Archived from the original on 15 May 2011.