The cryptanalyse is opposed, to some extent, with the Cryptographie. Indeed, if Déchiffrer consists in finding light by means of a key , cryptanalyser is to try to do without the latter.

Even if one describes the cryptanalystes like “breakers of codes”, it is advisable to notice that a algorithm is regarded as broken when an attack makes it possible to find the key by carrying out less operations that via a Attaque by rough force. The algorithm thus broken does not become useless for as much, but its degree of safety, i.e. the median number of operations necessary to decipher it, weakens.

An attack is often characterized by the data which it requires:

• attacks on text quantified only ( ciphertext-only ): the cryptanalyste has quantified specimens of the messages, it can make assumptions on the original messages which it does not have. The cryptanalyse is more difficult from the lack of information at disposal.

• attacks with text clearly known ( known-plaintext attack ): the cryptanalyste has messages or parts of messages in light as well as the quantified versions. The linear Cryptanalyse belongs to this category.
• attacks with text clearly selected ( chosen-plaintext attack ): the cryptanalyste has messages in light, it can generate the quantified versions of these messages with the algorithm which one can consequently regard as a block box. The Cryptanalyse differential is an example of attack to text clearly selected.
• attacks with selected quantified text ( chosen-ciphertext attack ): the cryptanalyste has coded messages and requires the version in light of some of these messages to conduct the attack.

to see the principal article: Levels of attacks

Families of cryptanalytic attacks

There exist several families of the cryptanalytic attacks, most known being the frequential Analyze, the Cryptanalyse differential and the linear Cryptanalyse.

Frequential analysis

The frequential Analyze examines the repetitions of the letters of the coded message in order to find the key. It is ineffective against modern codings such as OF the, RSA. It is mainly used against mono-alphabetical codings which substitute each letter by another and which present a statistical Biais.

The index of coincidence

The Indice of coincidence makes it possible to calculate the probability of repetitions of the letters of the coded message. It is often coupled with the frequential Analyze. That makes it possible to know the type of coding of a message (mono-alphabetical or poly-alphabetical coding) as well as the probable length of the key .

The attack by probable word

The Attaque by probable word consists in supposing the existence of a probable word in the coded message. It is thus possible to deduce the key from it from the message if the selected word is correct. This type of attack was carried out against the machine Enigma during the Second world war.

The attack by dictionary

The Attaque by dictionary consists in testing all the words of a list like key word . It is often coupled with the Attaque by rough force.

The attack by rough force

The Attaque by rough force consists in testing all the possible solutions of passwords or of key S. It is the only means of recovering the key in the most modern and still inviolate algorithms like AES. It is little to use for passwords having a very great number of characters because the time necessary becomes very important. Of the same plusior patents make this method ineffective, like that of Bell or IBM.

Attacks by paradox of the birthdays

The Paradoxe of the birthdays is a probabilistic result which is used in the attacks against the functions of chopping. This paradox makes it possible to give an upper limit of resistance to the collisions of such a function. This limit is about the root of the size of the exit, which means that, for algorithm like MD5 (impressed on 128 bits), to find a collision unspecified with 50% of chance requires 2⁶⁴ choppings of distinct entries.

Modern Cryptanalyse

As of the Seventies appear the modern methods of coding per blocks like OF the. He passably will be studied and attacked what will lead to major attacks in the world of cryptography. The methods presented below are not really generic and of the modifications are necessary to tackle a type of coding given.

Often, one does not attack a full version of the encryption algorithm but an alternative with less turns (in the case of diagrams of the Feistel type or functions of chopping). This preliminary analysis, if it makes it possible to detect vulnerabilities, lets foresee an attack on the complete algorithm.

Linear Cryptanalyse

The linear Cryptanalyse, due to Mitsuru Matsui, consists in making a linear approximation of the internal structure of the method of coding. It goes back to 1993 and proves to be the most effective attack on OF the. The more recent algorithms are insensitive to this attack.

Differential Cryptanalyse

The Cryptanalyse differential is an statistical analysis of the changes in the structure of the method of coding after having slightly modified the entries. With a very great number of disturbances, it is possible to extract the key. This attack goes back to 1990 (presented to the conference Crypto 90 ). It is due to Eli Biham and Adi Shamir. However, it is known now that the originators of knew an alternative of this named attack attacks-T . The recent algorithms (AES, IDEA, etc) are designed to resist this type of attack. The differential attacks are also possible on the functions of chopping, realizing modifications in the control of the attack. Such an attack was conducted against MD5.

Truncated differential Cryptanalyse

As its name indicates it, such a cryptanalyse is interested in differences which affect only part of the variables considered.

Differential Cryptanalyse of a higher nature

The original differential cryptanalyse is a differential of first order. By introducing the equivalent of the Derived S into the cryptographic functions, one can carry out a cryptanalyse with higher degrees. They are “differences in differences of…”.

See for the formal definitions and an example of attack.

Cryptanalyse by impossible differentials

Instead of seeking the probable differences, one reverses the problem and one seeks the differences which will not occur.

The attack boomerang

The Attaque boomerang is a version improved of the differential cryptanalyse invented by David Wagner. It consists in tackling the two halves of an encryption algorithm per block and share of the principle that certain properties, after disturbances of the entries, are not propagated through all the structure.

The right-angled attack

The right-angled Attaque is an extension of the Attaque boomerang, it was invented in 2001 by Eli Biham and its team to tackle their coding Serpent, candidate for the standard AES.

Differential-linear Cryptanalyse

Introduced by Martin Hellman and Langford, the differential-linear Cryptanalyse combines the two principles. The differential attack produces a linear approximation of the algorithm. With this attack, Hellman and Langford could attack a of 8 rounds with only 512 a few second and plaintexts on a PC of the time. This method was also employed to find key weak in IDEA. This type of cryptanalyse was improved by Eli Biham in 2002.

See for more information.

Cryptanalyse χ ²

The Cryptanalyse χ ², concept due to Serge Vaudenay, makes it possible to obtain results similar to linear or differential attacks. The associated statistical analysis makes it possible to be freed from the defects of these last while avoiding having to know the exact operation of coding.

Quadratic Cryptanalyse

The quadratic cryptanalyse is a recent invention of Nicolas Courtois and Josef Pieprzyk. This attack (named attacks XSL ) aims in particular AES and the other codings based on Rijndael. Attack XSL is the subject of many controversies as for its true effectiveness from its heuristic nature. It consists in solving a system of equations of very big size.

Cryptanalyse modulo N

Suggested by Bruce Schneier, David Wagner and John Kelsey in 1999, this technique consists in exploiting the differences in operation (according to a variable Congruence) of the algorithms which use binary rotations. See Cryptanalyse MOD N for the complete article.

Attacks by auxiliary channels

to see the principal article: Attack by auxiliary channels

One distinguishes several attacks which belong to this kind. They consist in exploiting unexpected properties of an algorithm at the time of its Mise in work. Indeed, a “mathematical” safety inevitably does not guarantee a safety during the use in “practice”. In this field, the attacks are numerous and relate to various parameters:

• time put to carry out certain operations (temporal Attaque)

• the noise generated by a computer which quantifies, the processor emits noise which varies according to its consumption and the operations carried out (acoustic Cryptanalyse)
• electricity consumption (analyzes consumption)
• voluntary introduction of errors into the system to cause certain revealing behaviors (Attaque by fault)

An attack based over the response times was conducted by Serge Vaudenay on TLS/SSL, which forced the originators of the standard to make a critical update. The manufacturers of chips of coding aim at levelling the curve of electricity consumption to dissimulate the subjacent operations.

Compromise time/memory

This concept was introduced by Martin Hellman in 1980. It was improved in 1993 by Philippe Oechslin with the concept of Table rainbow, which enabled him for example to tackle the passwords of Windows sessions, when they are stored with the format LanManager, as it is still the case generally. It is about a compromise between a Attaque by rough force and the use of dictionaries. An exhaustive research requires much time indeed whereas a dictionary of all the possible passwords would require place enormously. Thanks to algorithmic processes, one seeks to find a happy medium between these two principles, by building tables of size gérable.

Attacks on the procedures

Codings per block like OF the or AES can quantify only one block of size given (128 bits in the case of AES). To quantify longer data, one uses procedures. A procedure is the manner of chaining several blocks to obtain a coding by flow together. For example, one can cut out the data in blocks of 128 bits and quantify them separately. It is the mode ECB which is vulnerable since the presence of two identical quantified blocks indicates that the two respective blocks in the original message are also identical. Other modes avoid this problem but are not completely free from vulnerabilities. One then uses vectors of initialization which make it possible to avoid the repetition of identical sequences between several coded messages.

Codings by flood (for example RC4) use also a vector of initialization for the same reasons. Such an attack was recently conducted on this subject on the coding of the documents of the continuation Office of Microsoft, which employs RC4. The vector of initialization is there always the same one for a given document; a great number of information can thus be recovered by comparing the result of the coding of a document after light modification.

Attacks by meeting in the medium

To quantify twice with the same algorithm but via two different keys is an opening to an attack of the type meets in the medium. As opposed to what one can think first of all, coding obtained is not equivalent to a coding with a key twice longer (one in the case of does not pass from 2⁵⁶ to 2¹¹² OF). It is indeed enough to test all the keys to decipher the first stage. A result, always quantified is obtained, which is between the two blocks of coding. This result is subjected in its turn with an exhaustive research with all the possible keys. With final, complexity is only multiplied by two. In the case of, one obtains a resistance about 2⁵⁷, this is why 3DES is used which has a final complexity of 2¹¹² operations (in spite of a longer key of 3*56 bits). Thanks to three codings, each exit of the second block of coding must be tested with all the keys, which increases the number of possibilities considerably.

Attacks on the asymmetrical systems

To break a coding ensured by asymmetrical Cryptographie requires other approaches. In the case of RSA, it is the difficulty of the Factorization which ensures the resistance of coding. For ElGamal, it is the problem of the discrete Logarithme which is employed. However, certain faults can appear according to the use which one makes of these algorithms. RSA is vulnerable so exhibitors low magnitude are used (attacks of Don Coppersmith and Wiener). Under particular conditions, a Surchiffrement with RSA can be attacked. The standard PKCS ensures a more robust use of RSA, even if the first outlines of the standard were sensitive to attacks by auxiliary channels (Bleichenbacher).

• temporal Attack

Other analyzed properties

Certain properties observed in the encryption algorithms do not lead inevitably to attacks but make it possible to detect weaknesses in the design, problems which can in hiding others more important.

Weak keys

Certain algorithms are likely to have keys known as weak . If such a key is used to quantify a message first once and that one rechiffre the result, always with the same key, then one obtains the message in light. More formally, E_k (E_k (m))=m. OF the has 4 keys of this kind. There are also keys known as semi-weak . In this case, E_k1 (E_k2 (m))=m.

See the principal article: key weak.

Statistical skew

One can seek if the structure of coding produces statistical Biais. In general, an encryption algorithm is supposed to produce a result close to a generator of uniformly distributed numbers Aléatoire S, so as to give less possible information and to maximize the Entropie. If a skew is observed (for example, one observes more bits with “1” than of bits with “0”) then of the additional analyzes can sometimes make it possible to conceive an attack. Let us quote inter alia attacks on RC6 whose permutations deviate appreciably from the characteristics normally observed in the generators of pseudo-random numbers.

See too

Related articles

• History of the cryptanalyse
• Cryptography

External bond

• Treated cryptanalyse

Random links:

Geometrical continuation | John Weinzweig | Zell (the Moselle) | Couvade | LSG Sky Chiefs