Index: > A B C D E F G H I J K L M N O P Q R S T U V W X Y Z

Home > Cryptanalysis

2.2 Classifying success in cryptanalysis

The results of cryptanalysis can also vary in usefulness. For example, cryptographer Lars Knudsen (1998) classified various types of attack on block ciphers according to the amount and quality of secret information that was discovered:

Total break — the attacker deduces the secret key.
Global deduction — the attacker discovers a functionally equivalent algorithm for encryption and decryption, but without learning the key.
Instance (local) deduction — the attacker discovers additional plaintexts (or ciphertexts) not previously known.
Information deduction — the attacker gains some Shannon information about plaintexts (or ciphertexts) not previously known.
Distinguishing algorithm — the attacker can distinguish the cipher from a random permutation.

Similar considerations apply to attacks on other types of cryptographic algorithm.

2.3 Complexity

Attacks can also be characterised by the amount of resources they require. This can be in the form of:

Time — the number of "primitive operations" which must be performed. This is quite loose; primitive operations could be basic computer instructions, such as addition, XOR, shift, and so forth, or entire encryption methods.
Memory — the amount of storage required to perform the attack.
Data — the quantity of plaintexts and ciphertexts required.

In academic cryptography, a weakness or a break in a scheme is usually defined quite conservatively. Bruce Schneier sums up this approach: "Breaking a cipher simply means finding a weakness in the cipher that can be exploited with a complexity less than brute force. Never mind that brute-force might require 2¹²⁸ encryptions; an attack requring 2¹¹⁰ encryptions would be considered a break...simply put, a break can just be a certificational weakness: evidence that the cipher does not perform as advertised." (Schneier, 2000).

3 Cryptanalysis of asymmetric cryptography

Asymmetric cryptography (or public key cryptography) is cryptography that relies on using two keys; one private, and one public. Such ciphers invariably rely on "hard" mathematical problems as the basis of their security, so an obvious point of attack is to develop methods for solving the problem. The security of two-key cryptography depends on mathematical questions in a way that single-key cryptography generally does not, and conversely links cryptanalysis to wider mathematical research in a new way.

Asymmetric schemes are designed around the (conjectured) difficulty of solving various mathematical problems. If an improved algorithm can be found to solve the problem, then the system is weakened. For example, the security of the Diffie-Hellman key exchange scheme depends on the difficulty of calculating the discrete logarithm. In 1983, Don Coppersmith found a computationally feasible way to find discrete logarithms, and thereby gave to the cryptanalyst a tool with which to break the Diffie-Hellman cryptosystems. Another scheme, the popular RSA algorithm, remains unbroken. Its security depends (in part) upon the difficulty of integer factorisation — a breakthrough in factoring would impact the security of RSA.

In 1980, one could factor a difficult 50-digit number at an expense of 10¹² elementary computer operations. By 1984 the state of the art in factoring algorithms had advanced to a point where a 75-digit number could be factored in 10¹² operations. Advances in computing technology also meant that the operations could be performed much faster, too. Moore's law predicts that computer speeds will continue to increase. Factoring techniques may continue do so as well, but will most likely depend on mathematical insight and creativity, neither of which has ever been successfully predictable. 150-digit numbers of the kind once used in RSA have been factored. The effort was greater than above, but was not unreasonable on fast modern computers. By the start of the 21st century, 150-digit numbers were no longer considered a large enough key size for RSA. Numbers with several hundred digits are still considered too hard to factor in 2004, though methods will probably continue to improve over time, requiring key size to keep pace or new algorithms to be used.

Another distinguishing feature of asymmetric schemes is that, unlike attacks on symmetric cryptosystems, any cryptanalysis has the opportunity to make use of knowledge gained from the public key.

Politics	Business	Finance

Topics: Cryptanalysis Attack Cryptography Ciphers Cipher Example...

CryptanalysisCryptanalysis (from the Greek kryptos and analyein "to loosen" or "to untie") is the study of methods for obtaining the meaning of encrypted information without access to the secret information which is normally required to do so. Typically, this involves

Cryptanalysis of the EnigmaEnigma is the name of a family of ciphering machines made famous by their use in World War II and the successful analysis of the cipher by Allied codebreakers. This article discusses the techniques for solving Enigma and the circumstances in which they we

Non User