|
History of cryptanalysis Main article: History of cryptography. Cryptanalysis has coevolved together with cryptography, and the contest can be traced through the history of cryptography — new ciphers being designed to replace old broken designs, and new cryptanalytic techniques invented to crack the improved schemes. In practice, they are viewed as two sides of the same coin: in order to create secure cryptography, you have to design against possible cryptanalysis. Classical cryptanalysis
Modern cryptanalysis
The results of cryptanalysis
Characterising attacks Cryptanalytic attacks vary in potency and how much of a threat they pose to real-world cryptosystems. A certificational weakness is a theoretical attack that is unlikely to be applicable in any real-world situation; the majority of results found in modern cryptanalytic research are of this type. Essentially, the practical importance of an attack is dependent on the answers to the following three questions: Prior knowledge: scenarios for cryptanalysis Cryptanalysis can be performed under a number of assumptions about how much can be observed or found out about the system under attack. As a basic starting point it is normally assumed that, for the purposes of analysis, the general algorithm is known; this is Kerckhoffs' principle of "the enemy knows the system". This is a reasonable assumption in practice — throughout history, there are countless examples of secret algorithms falling into wider knowledge, variously through espionage, betrayal and reverse engineering. (On occasion, ciphers have been reconstructed through pure deduction; for example, the German Lorenz cipher and the Japanese Purple code, and a variety of classical schemes). Other assumptions include: These types of attack clearly differ in how plausible they would be to mount in practice. Although some are more likely than others, cryptographers will often take a conservative approach to security and assume the worst-case when designing algorithms, reasoning that if a scheme is secure even against unrealistic threats, then it should also resist real-world cryptanalysis as well. The assumptions are often more realistic than they might seem upon first glance. For a known-plaintext attack, the cryptanalyst might well know or be able to guess at a likely part of the plaintext, such as an encrypted letter beginning with "Dear Sir", or a computer session starting with "LOGIN:". A chosen-plaintext attack is less likely, but it is sometimes plausible: for example, you could convince someone to forward a message you have given them, but in encrypted form. Related-key attacks are mostly theoretical, although they can be realistic in certain situations, for example, when constructing cryptographic hash functions using a block cipher. 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: Similar considerations apply to attacks on other types of cryptographic algorithm. Complexity Attacks can also be characterised by the amount of resources they require. This can be in the form of: 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 2128 encryptions; an attack requiring 2110 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). 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 faster way to find discrete logarithms (in certain groups), and thereby requiring cryptographers to use larger groups (or different types of groups). RSA's security depends (in part) upon the difficulty of integer factorization — a breakthrough in factoring would impact the security of RSA. In 1980, one could factor a difficult 50-digit number at an expense of 1012 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 1012 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 2005, 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. Quantum computing applications for cryptanalysis Quantum computers have potential for use in cryptanalysis. Because quantum states can exist in superposition (ie, entangled), a new paradigm for computation is possible. Peter Shor of Bell Labs proved the possibility, and various teams have demonstrated one or another aspect of quantum computer engineering in the years since. Thus far, only very limited proof of possibility designs have been demonstrated. There is, at this writing, no credible prospect of an actual, usable, quantum computer. However, were a quantum computer to be built, many things would change. Parallel computation would likely become the norm, and some aspects of cryptography would change. In particular, since a quantum computer would be able to conduct extremely fast brute force key searches, key lengths now considered effectively beyond any brute force attacker's resources would become practical. Key lengths necessary to be beyond a quantum computer's capacity would be longer, probably considerably longer. Some popular writers have declared that no encryption would remain secure when quantum computers become available. Others claim that simply adding bits to key lengths will prohibit brute force attacks, even with quantum computers. A second possibility is that increased computational power may make possible non brute force key search attacks against one or more currently impregnable algorithms, or classes of algorithms. For instance, not all progress in prime factorisation has been due to algorithmic improvements. Some has been due to increasing computer power, and the existence of working quantum computers may considerably advance factorization thus increasing the vulnerability of some cryptographic algorithms. This much is perhaps foreseeable, if not clearly. What cannot be anticipated is a theoretical breakthrough, requiring quantum computing, which would make possible currently impractical (or even unknown) attacks. In the absence of a method for predicting breakthroughs, we will simply have to wait. It is unknown whether there is a polynomial time encryption algorithm for which decryption requires exponential time, even for a quantum computer. Methods of cryptanalysis Classical cryptanalysis: Symmetric algorithms: Other methods: See also | |||||||||||||||
|
| ||||||||||||||||
 |
|
| |