Cryptanalysis

The cryptanalysis ( in more recent publications also cryptanalysis ) referred to in the original sense of the study of methods and techniques to gain information from encrypted texts. This information can be used for both the key and the original text. Nowadays, the term cryptanalysis generally, the analysis of cryptographic methods to prove (not just for encryption) with the aim of this either to "break", that is, to withdraw its protective function or to circumvent or their security and to quantify. Cryptanalysis is thus the " counterpart " to cryptography. Both are branches of cryptology.

Steganalysis

Analogous to cryptanalysis, which is focused on cryptography, one can understand the steganalysis as a " counterpart " to steganography. However, in contrast to cryptanalysis, where a cryptographic content exists or is to be analyzed and broken, will initially work at the steganalysis only with the assumption that there is a hidden information in a carrier medium. Only when this assumption could be substantiated, it will try to extract the actual information. In this case methods can be used also in the cryptanalysis.

The security of steganography based on the fact that third parties do not notice their use. Even if they know of a third party to the actual content can not be read in plain text.

Decoding and deciphering

In cryptology, the terms " deciphering " and " decoding" have different meanings: as a ( authorized ) decryption is called the method to reconvert using the known key the ciphertext back to plaintext, and so to be able to read the message. The ( unauthorized ) deciphering the other hand, is the art to wrest the message the ciphertext without knowing the key. Decipher instead of the verb is in cryptanalysis, the expression "break" or colloquially "crack" used.

In archeology, however, that when it comes to the analysis of an old, no longer known writing, the terms decryption and decoding are often used as synonyms.

Methods of cryptanalysis

An important approach of cryptanalysis is to involve all the available information about the subject process, its parameters and the protected data in the analysis. This information can be public, plausible conjectures come from or is brought to you specifically (eg through social engineering ). The type of information available and its control over is divided into different attack scenarios ( see models and statements about security) and qualify the relevance of the attack or the statement of security.

Before mechanical equipment, such as the Enigma or computer cryptography allowed to scramble messages to pseudo - random sequences, the statistic was the strongest weapon to decipher messages. As long as a person encrypts the texts by hand, the algorithm used must simply remain enough to flawlessly implement the message in an acceptable time. These encryption methods are most vulnerable to the statistics. With it, the frequency of certain characters and strings is determined. With the knowledge of the regularities of a language letters and words can be mapped to the plain text to be reconstructed.

Since then reduce computer by its speed and accuracy, the statistical bonds in an encrypted text to almost zero, new analysis techniques must be used to reveal the encryption algorithm to exploit a vulnerability in the algorithm ( as it did the statistics vulnerabilities exploited ) and the key to reconstruct, with the message was encrypted. These complicated mathematical theories and methods are frequently used, for example from algebra or stochastic.

Some of the important attack and analysis:

• Brute- force method: All possible keys are tried in succession. The sequence is optionally selected according to the probability. This method is also useful for modern encryption process if it can be assumed that the use of a relatively weak password. Already on standard computers ( as of 2008) can be tried per second easily several million different key.
• Dictionary attack: All keys from specially made for this purpose password collections are tried in succession. The sequence is optionally selected according to the probability. This method is also useful for modern encryption process if it can be assumed that the use of a relatively simple password.

• Side channel attack: The attacker tries other than the plaintext, the ciphertext and the key must be recorded, other data and from this to gain information about the algorithm and key used. For this purpose are, for example, in question: the duration of the encryption ( timing attack ), the time course of the power consumption of a chip ( Simple / Differential Power Analysis), calculation errors due to extreme environmental conditions (Differential Fault Analysis ), a branching analysis (Simple Branch Prediction Analysis) or the emission of electromagnetic waves ( TEMPEST Attack).
• Linear cryptanalysis: This method was published by Mitsuru Matsui 1993. The method is based on the linear approximation of the most likely code for breaking of block encryption methods.
• Differential cryptanalysis: Differential cryptanalysis was developed in 1991 by Eli Biham and Adi Shamir attack to DES. This attack attempt failed because the differential analysis of the NSA was already known in the development of DES. For differential analysis plaintext pairs with certain differences ( the differences) encrypted to derive the secret key of the symmetric cryptosystem from differences between the cryptograms.
• Man- in-the -middle attack: The attacker is located between two communication partners and can listen to all messages and even modify or insert new messages.
• Algebraic attack: if the cryptographic algorithm operating on a suitable algebraic structure and can be represented by suitable algebraic operations, special properties can be exploited, if necessary, the algebraic structure, to successfully attack the algorithm. Often it is the breaking of the method to solving a system of equations over the structure or a propositional formula attributed. Such attacks are mainly applied to asymmetric methods often operating on finite groups. But even stream encryption method and some block encryption method such as AES, can be modeled algebraically and attacked the more or less successful.
• Attacks on lattice basis reduction: Many cryptographic methods can attack each other by determining a short vector in a given lattice. This method of attack is at a cryptosystem that is based on the grids or the knapsack problem, such as NTRU or the Merkle -Hellman cryptosystem used, but can also - in combination with algebraic methods of attack - in other asymmetric cryptosystems, such B RSA are applied..

Models and comment on the safety

The proof of the security of cryptographic methods can rarely be strict, that is, out in the sense of information theory. More often, the security procedures in the sense of complexity theory is proved, that is, it is attributed to more or less accepted assumptions about the difficulty of computational problems (eg, NP- complete problems, factorization or discrete logarithm ) or other cryptographic methods. In some cases, theoretical models to idealization of components of the process (eg, random oracle model), or options potential attacker (eg, generic algorithms) shall be used; from lessons learned about the safety of a procedure, however, are always seen in the context of the model and are valued in part controversial.

When analyzing the security of cryptographic processes and the resulting statements on the safety different attack and security models are used. So the quality of a statement on the safety depends on a process against certain attackers of the assumed targets of attack and the attack scenario.

Objectives

Statements about the security of a cryptographic method relate generally to specific targets. The possible targets are dependent on the type of cryptographic process. For all cryptographic methods that use a secret key to determine the secret key is the most ambitious target of an attack, as the safety of the procedure is completely undermined.

For encryption method following targets are still relevant:

• Decoding, i.e., the determination of the clear text.
• The attacker must determine to a cipher text and two potential plaintexts, which is the correct plaintext. If this (ie in polynomial time ) is not efficiently possible, this property is referred to as Semantic Security or ciphertext indistinguishability. Semantic Security is considered for both asymmetric and symmetric cryptosystems for. Only probabilistic encryption method can have this property.
• The attacker tries to modify a ciphertext so that the associated new clear text that you would receive if decryption of the altered ciphertext, is related to the original plain text in a given ( known to the attacker ) relation. For example, it could be his aim to change the ciphertext so that a specified number in plain text (eg, a purchase price ) is reduced. An encryption method that is secure against such attacks because an attacker does not have control over the resulting change in plain text in a manipulation of the ciphertext is called Non- Malleable ( to German non- deformability ).
• The attacker attempts to produce a valid ciphertext without knowing the corresponding plaintext. If this (ie in polynomial time ) is not efficiently possible, this property is referred to as plaintext awareness. Only encryption method, in which the cipher texts have a defined structure ( redundancy) can have this property.

With digital signatures and message authentication codes (MAC) are usually considered the target to generate a signature or a MAC to a new message. If the message can be arbitrary, this is called existential forgery. If it must be possible to choose the message free, this is referred to as Selective forgery.

Attack scenarios

Research in the cryptanalysis is today mostly used to process the specification of which are known. This corresponds to Kerckhoffs ' principle, according to which the safety of a procedure should be based only on the secrecy of the key. The secrecy of the algorithm (security through obscurity ) prevents an analysis by the experts and is therefore now regarded as rather counterproductive for safety. Secret cryptographic procedures were repeated uncovered in the past, analyzed and broken (eg GSM, Mifare cards or the encryption of commercial DVDs). Secret proceedings are now rare, mainly in the military and for the protection of classified information (eg chiasm or bubble level), as well as in closed commercial systems, such as pay television, for access control (eg, Mifare ) or digital rights management used.

There are different attack scenarios on an encryption system ( on the strength order):