Cryptanalysis

from Wikipedia, the free encyclopedia

The cryptanalysis (in more recent publications also cryptanalysis ) describes in the original sense the study of methods and techniques to obtain information from encrypted texts. This information can be both the key used and the original text. Nowadays, the term cryptanalysis generally refers to the analysis of cryptographic processes (not just for encryption) with the aim of either " breaking " them, ie. H. remove or circumvent their protective function, or demonstrate and quantify their safety. Cryptanalysis is therefore the "counterpart" to cryptography . Both are sub-areas of cryptology .

Bar analysis

Analogous to cryptanalysis, which is focused on cryptography, bar analysis can be understood as the "counterpart" to steganography . In contrast to cryptanalysis, however, where cryptographic content is available and is to be analyzed or broken, the web analysis initially only works with the assumption that there is hidden information in a carrier medium. Only when this assumption can be confirmed will an attempt be made to extract the actual information. Methods from cryptanalysis can also be used.

The security of steganography is based on the fact that third parties do not notice its use. Even if they know about it, third parties should not be able to read the actual content in plain text.

Decryption and deciphering

In cryptology, the terms “ decipherment ” and “ decryption ” have different meanings: (authorized) decryption is the process of converting the ciphertext back into plain text with the help of the known key and thus being able to read the message. The (unauthorized) decipherment, on the other hand, is the art of extracting the message from the ciphertext without knowing the key. Instead of the verb decipher , the expression " break " or colloquially also "crack" is used in cryptanalysis .

In archeology, on the other hand, when it comes to the analysis of an old, no longer known script, the terms decoding and deciphering are often used as synonyms .

Methods of cryptanalysis

An important approach in cryptanalysis is to include all available information about the examined method, its parameters and the protected data in the analysis. This information can be public, it can come from plausible assumptions or it can be obtained specifically (e.g. through social engineering ). The type of information available and its control over it is divided into various attack scenarios (see models and statements on security ) and qualify the relevance of the attack or the statement on security.

Before mechanical devices such as the Enigma or computers made it possible for cryptography to scramble messages into pseudo-random sequences, statistics were the most powerful weapon for deciphering messages. As long as a person encrypts the texts by hand, the algorithm used must remain simple enough to implement the message error-free in a reasonable time. These encryption methods can usually be attacked by statistics. It is used to determine the frequency of certain characters and character strings. With the knowledge of the laws of a language, letters and words can be assigned and the plain text can be reconstructed.

Since computers, thanks to their speed and precision, have reduced the statistical ties in an encrypted text to almost zero, new analysis techniques have to be used to uncover the encryption algorithm, exploit a weak point in the algorithm (just as statistics have already used weak points) and reconstruct the key with that the message was encrypted. Complicated mathematical theories and procedures are often used for this purpose, e.g. B. from algebra or stochastics .

Here are some important attack and analysis methods:

  • Brute force method : All possible keys are tried out one after the other. If necessary, the order is selected according to the probability. This method is also useful with modern encryption methods, if the use of a relatively weak password can be assumed. Even on commercially available computers (as of 2008), several million keys per second can easily be tried out.
  • Dictionary attack: All keys from password collections specially created for this purpose are tried one after the other. If necessary, the order is selected according to the probability. This method is also useful with modern encryption methods if the use of a relatively simple password can be assumed.
It is also possible to try out all possible words. With an active vocabulary of 50,000 words per language, dozens of languages ​​can be tried out within a few seconds, even on standard computers. A single word as a key is therefore very insecure.
  • Side-channel attack : The attacker tries to collect other data in addition to the plain text, the cipher or the key and to gain information about the algorithm and key used. For example: the duration of the encryption (timing attack), the temporal course of the power consumption of a chip (simple / differential power analysis), calculation errors due to extreme environmental conditions (differential fault analysis), a branch analysis (simple branch prediction analysis) or the emission of electromagnetic waves ( TEMPEST attack ).
  • Linear cryptanalysis : This method was published by Mitsuru Matsui in 1993. The method is based on the linear approximation of the most likely key to break block cipher schemes.
  • Differential cryptanalysis : The differential cryptanalysis was developed in 1991 by Eli Biham and Adi Shamir toattack DES . This attack attempt failed because the NSA's differential analysis was already known when DES was developed. In differential analysis, plain text pairs with certain differences (the differences) are encrypted in order to derive the secret key of the symmetrical cryptosystem from the differences in the cipher.
  • Man-in-the-middle attack : The attacker is between two communication partners and can overhear and even change all messages or insert new messages.
  • Algebraic attack methods : If the cryptographic algorithm operates on a suitable algebraic structure or can be represented by suitable algebraic operations, special properties of the algebraic structure can be exploited to successfully attack the algorithm. Often the breaking of the procedure can be traced back to solving a system of equations over the structure or a propositional formula . Such attacks are mainly used on asymmetric methods, which often operate on finite groups. But also stream encryption methods and some block encryption methods , such as. B. AES , can be modeled algebraically and attacked more or less successfully.
  • Attacks by grid base reduction : Many cryptographic methods can be attacked by determining a short vector in a certain grid . This attack method is used in cryptographic methods based on the grid or the backpack problem, such as B. NTRU or the Merkle-Hellman cryptosystem , but can also - in combination with algebraic attack methods - with other asymmetric cryptographic methods, such as. B. RSA can be applied.

Models and statements about safety

The proof of the security of cryptographic procedures can only rarely be strict, i.e. H. in the sense of information theory. The safety of procedures in the sense of complexity theory is proven more frequently , i. H. it is reduced to more or less accepted assumptions about the difficulty of computational problems (e.g. NP-complete problems , factorization or discrete logarithm ) or other cryptographic methods. In some cases, theoretical models are used to idealize components of the process (e.g. random Oracle model ) or the possibilities of potential attackers (e.g. generic algorithms ); The knowledge gained from this about the safety of a process must, however, always be seen in the context of the model and are sometimes evaluated controversially.

When analyzing the security of cryptographic processes and the resulting statements on security, various attack and security models are used as a basis. The quality of a statement about the security of a procedure against certain attackers depends on the assumed targets and the attack scenario.

aims

Statements about the security of a cryptographic process usually relate to specific targets. The possible goals depend on the type of cryptographic method. For all cryptographic processes that use a secret key, the determination of the secret key is the most far-reaching goal of an attack, since it completely undermines the security of the process.

The following targets are also relevant for encryption methods:

  • Decryption, d. H. the determination of the plain text.
  • The attacker must determine which is the correct plaintext for a ciphertext and two potential plaintexts. If this is not possible efficiently (i.e. in polynomial time ), this property is known as semantic security or ciphertext indistinguishability . Semantic security is considered for both asymmetric and symmetric cryptographic methods . Only probabilistic encryption methods can have this property.
  • The attacker tries to change a ciphertext in such a way that the associated new plaintext, which would be obtained if the changed ciphertext were decrypted, has a certain relation (known to the attacker) with the original plaintext. For example, his goal could be to change the ciphertext in such a way that a number given in clear text (e.g. a purchase price) is reduced. An encryption method that is against such attacks secure because an attacker at a manipulation of the ciphertext has no control over the resulting change in plain text, it is called Non-Malleable (to German non Deformable ).
  • The attacker tries to generate a valid ciphertext without knowing the corresponding plaintext. If this is not possible efficiently (i.e. in polynomial time ), this property is known as plain text awareness . Only encryption methods in which the ciphertexts have a defined structure (redundancy) can have this property.

In the case of digital signatures and Message Authentication Codes (MAC), one usually considers the goal of generating a signature or a MAC for a new message. If the message can be anything, it is called Existential Forgery . If it must be possible to choose the message freely, this is called selective forgery .

Attack scenarios

In research today, cryptanalysis is mostly applied to methods whose specification is known. This corresponds to Kerckhoffs' principle , according to which the security of a procedure should only be based on the secrecy of the key. The secrecy of the algorithm ( security through obscurity ) prevents an analysis by the professional world and is therefore seen today as rather counterproductive for security. In the past, secret cryptographic procedures were repeatedly uncovered, analyzed and broken (e.g. with GSM , Mifare cards or the encryption of commercial DVDs ). Today, secret procedures are used less often, mainly in the military sector and for the protection of classified information (e.g. chiasmus or dragonfly ), as well as in closed commercial systems, e.g. B. Pay TV , access control (e.g. Mifare) or digital rights management .

A distinction is made between different attack scenarios on an encryption system (sorted by strength):

Ciphertext Only
Sometimes this method is also known as known ciphertext . The attacker knows one or more ciphertexts and tries with their help to infer the plaintext or the key.
Probable plaintext (probable plaintext)
The attacker has ciphertext and has reason to believe that it contains certain phrases or distinctive words that can be used to attempt analysis. The familiar words are called crib .
For example, the Enigma could be cracked with an initial knowledge that at the beginning the key for the rest of the message (encrypted with an unknown daily key ) was sent twice and then the date and the weather report. You could use it to reconstruct the daily key. This method is also called pattern search .

Known Plaintext
The attacker has ciphertext (s) and the associated plaintext (s). Both are used to determine the key.
A current example is the improvement, published in mid-2006, of an attack on the Wired Equivalent Privacy (WEP) protocol that has been known since 2001 , which is used to authenticate and encrypt wireless LANs . The optimized attack takes advantage of the fact that parts of the encrypted message - the headers of the 802.11 protocol - are predictable.

Chosen plaintext (self-chosen plaintext)
The attacker (cryptanalyst) can freely choose the plaintexts to be encrypted and has access to the corresponding ciphertexts. Compared to the attack with known plain text, this variant has the advantage that the attacker can vary the plain text in a targeted manner and analyze the resulting changes in the ciphertext. Typically, the attacker slips the messages to be encrypted onto the victim in such a way that the victim is not aware of the selection by another person.
The adaptive chosen plaintext attack is a particularly powerful attack scenario . In this case, the attacker can analyze the crypto-texts received so far and, depending on the result, select a new plain text to encrypt (hence "adaptive").
This is the minimum scenario with asymmetric encryption. Since the encryption key is public, the attacker can encrypt messages at will.

Chosen ciphertext (self-chosen ciphertext)
The attacker has the temporary opportunity to decrypt ciphertexts of his choice. This can be done by accessing a hardware system through a break-in; However, this also includes access to unforeseen side effects, such as various error messages after successful or unsuccessful decryption. An example of this is Bleichenbacher's attack on PKCS # 1.
With some cryptosystems , such as Rabin , he is then able to determine the secret key with which the secret texts were encrypted from the data pairs obtained .
Adaptively Chosen Ciphertext (adaptively chosen ciphertext)
Similar to the previous attack, but the attacker has access to the system for a longer period of time and can select a new crypto text for decryption after each analysis.
Chosen Text (text of your choice)
Combination of Chosen Plaintext and Chosen Ciphertext.
Adaptive Chosen Text (adaptive text of your choice)
Combination of Adaptive Chosen Plaintext and Adaptive Chosen Ciphertext.

See also

literature

Web links

Individual evidence

  1. ^ Eli Biham, Adi Shamir: Differential cryptanalysis of DES-like cryptosystems . (PDF) In: Journal of Cryptology . 4, No. 1, January 1991, pp. 3-72. doi : 10.1007 / BF00630563 .
  2. ^ Frank A. Stevenson: Cryptanalysis of Contents Scrambling System . 1999 ( Online ( Memento of March 2, 2000 in the Internet Archive )). Cryptanalysis of Contents Scrambling System ( Memento of the original from February 6, 2003 in the Internet Archive ) Info: The archive link was inserted automatically and has not yet been checked. Please check the original and archive link according to the instructions and then remove this notice.  @1@ 2Template: Webachiv / IABot / www.dvd-copy.com