Cryptanalysis (from the
Greek kryptós, "hidden", and
analýein, "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 knowing how the system works and
finding a
secret key. In non-technical
language, this is the practice of
codebreaking or
cracking the code, although these phrases also
have a specialised technical meaning (see
code).
"Cryptanalysis" is also used to refer to any attempt to circumvent
the security of other types of
cryptographic algorithms and
protocols in general, and not just
encryption. However, cryptanalysis
usually excludes methods of attack that do not primarily target
weaknesses in the actual
cryptography,
such as
bribery,
physical coercion,
burglary,
keystroke
logging, and
social
engineering, although these types of attack are an important
concern and are often more effective than traditional
cryptanalysis.
Even though the goal has been the same, the methods and techniques
of cryptanalysis have changed drastically through the history of
cryptography, adapting to increasing cryptographic complexity,
ranging from the pen-and-paper methods of the past, through
machines like
Enigma in
World War II, to the computer-based schemes of
the present. The results of cryptanalysis have also changed — it is
no longer possible to have unlimited success in codebreaking, and
there is a hierarchical classification of what constitutes a rare
practical attack. In the mid-1970s, a new class of cryptography was
introduced:
asymmetric
cryptography. Methods for breaking these
cryptosystems are typically radically different
from before, and usually involve solving carefully-constructed
problems in
pure mathematics, the
best-known being
integer
factorization.
History of cryptanalysis
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
Although the actual word "
cryptanalysis" is relatively
recent (it was coined by
William
Friedman in 1920), methods for breaking
codes and
ciphers
are much older. The first known recorded explanation of
cryptanalysis was given by 9th-century
Arabian
polymath,
Al-Kindi
(also known as "Alkindus" in Europe), in
A Manuscript on
Deciphering Cryptographic Messages. This treatise includes a
description of the method of
frequency analysis (
Ibrahim Al-Kadi, 1992- ref-3).
Italian scholar
Giambattista della Porta
was author of a seminal work on cryptanalysis "De Furtivis
Literarum Notis".
Frequency analysis is the basic
tool for breaking most
classical
ciphers. In natural languages, certain letters of the
alphabet appear more frequently than others; in
English, "
E" is
likely to be the most common letter in any sample of
plaintext. Similarly, the
digraph "TH" is the most likely pair
of letters in English, and so on. Frequency analysis relies on a
cipher failing to hide these
statistics.
For example, in a
simple
substitution cipher (where each letter is simply replaced with
another), the most frequent letter in the
ciphertext would be a likely candidate for "E".
Frequency analysis of such a cipher is therefore relatively easy,
provided that the ciphertext is long enough to give a reasonably
representative count of the letters of the alphabet that it
contains.
In Europe during the 15th and 16th centuries, the idea of a
polyalphabetic substitution
cipher was developed, among others by the French diplomat
Blaise de Vigenère
(1523-96). For some three centuries, the
Vigenère cipher, which uses a repeating
key to select different encryption alphabets in rotation, was
considered to be completely secure (
le chiffre
indéchiffrable—"the indecipherable cipher"). Nevertheless,
Charles Babbage (1791–1871) and
later, independently,
Friedrich
Kasiski (1805–81) succeeded in breaking this cipher. During
World War I, inventors in several
countries developed
rotor cipher
machines such as
Arthur
Scherbius'
Enigma, in an attempt
to minimise the repetition that had been exploited to break the
Vigenère system.
In practice, frequency analysis relies as much on
linguistic knowledge as it does on
statistics, but as ciphers became more complex,
mathematics became more important in
cryptanalysis. This change was particularly evident before and
during
World War II, where efforts to
crack
Axis ciphers required new levels
of mathematical sophistication. Moreover, automation was first
applied to cryptanalysis in that era with the Polish
Bomba device, the British
Bombe development of it, the use of
punched card equipment, and in the
Colossus computers—the first electronic
digital computers to be controlled by a program.
Modern cryptanalysis
Even though computation was used to great effect in cryptanalysis
in World War II, it also made possible new methods of cryptography
orders of magnitude more complex
than ever before. Taken as a whole, modern cryptography has become
much more impervious to cryptanalysis than the pen-and-paper
systems of the past, and now seems to have the upper hand against
pure cryptanalysis. The historian
David
Kahn notes,
"Many are the cryptosystems offered by the
hundreds of commercial vendors today that cannot be broken by any
known methods of cryptanalysis. Indeed, in such systems
even a chosen plaintext attack, in which a selected plaintext is
matched against its ciphertext, cannot yield the key that unlock
other messages. In a sense, then, cryptanalysis is
dead. But that is not the end of the story.
Cryptanalysis may be dead, but there is - to mix my metaphors -
more than one way to skin a cat.".
Kahn goes on to mention increased opportunities for interception,
bugging,
side
channel attacks and
quantum
computers as replacements for the traditional means of
cryptanalysis.
Kahn may have been premature in his cryptanalysis postmortem; weak
ciphers are not yet extinct, and cryptanalytic methods employed by
intelligence agencies remain unpublished. In
academia, new designs are regularly presented, and
are also frequently broken: the 1984
block
cipher Madryga was found to be
susceptible to
ciphertext-only
attacks in 1998;
FEAL-4, proposed as a
replacement for the
DES
standard encryption algorithm, was demolished by a spate of attacks
from the academic community, many of which are entirely practical.
In
industry, too, ciphers are not free from
flaws: for example, the
A5/1,
A5/2 and
CMEA algorithms,
used in
mobile phone technology, can
all be broken in hours, minutes or even in real-time using
widely-available computing equipment. In 2001,
Wired Equivalent Privacy (WEP), a
protocol used to secure
Wi-Fi wireless networks, was shown to be
susceptible to a practical
related-key attack. This weakness was not
actually caused by weakness in the actual cryptographic algorithm
itself, but rather that it was used improperly within the protocol
in a way which compromised its strength.
The results of cryptanalysis
Successful cryptanalysis has undoubtedly influenced history; the
ability to read the presumed-secret thoughts and plans of others
can be a decisive advantage, and never more so than during wartime.
For example, in
World War I, the
breaking of the
Zimmermann
Telegram was instrumental in bringing the United States into
the war. In
World War II, the
cryptanalysis of the German ciphers — including the
Enigma machine and the
Lorenz cipher — has been credited with
everything between shortening the end of the European war by a few
months to determining the eventual result (see
ULTRA).
The United States also benefited from the cryptanalysis of the
Japanese PURPLE code (see MAGIC).
Governments have long recognised the
potential benefits of cryptanalysis for intelligence, both military and
diplomatic, and established dedicated organisations devoted to
breaking the codes and ciphers of other nations, for example,
GCHQ and the NSA, organisations which are still very active
today. In 2004, it was reported that the United
States had broken Iranian
ciphers. (It is unknown, however, whether this was pure
cryptanalysis, or whether other factors were involved:
[553]).
Types of cryptanalytic attack
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:
- What knowledge and capabilities are
needed as a prerequisite?
- How much additional secret information is deduced?
- How much effort is required? (What is the computational complexity?)
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:
- 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.
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^{128} encryptions; an attack requiring
2^{110} 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 10
^{12} 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
^{12}
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, which are still
in the early phases of development, have potential use in
cryptanalysis. For example,
Shor's
Algorithm could factor large numbers in
polynomial time, in effect breaking some
commonly used forms of public-key encryption.
By using
Grover's algorithm on a
quantum computer, brute-force key search can be made quadratically
faster. However, this could be countered by increasing the key
length.
Methods of cryptanalysis
Classical cryptanalysis:
Symmetric algorithms:
Hash functions:
Attack models:
Side channel attacks:
Network attacks:
External attacks:
See also
General
Historic cryptanalysts
National
External links
References
- Crypto History
- Singh, Simon
(1999) p. 17
- Singh, Simon
(1999) pp. 45-51
- Singh, Simon
(1999) pp. 63-78
- Singh, Simon
(1999) p. 116
- David Kahn,
Remarks on the 50th Anniversary of the National Security
Agency, November 1, 2002.
- Ibrahim A. Al-Kadi ,"The origins of cryptology: The
Arab contributions”, Cryptologia, 16(2) (April 1992)
pp. 97–126.
- Friedrich L. Bauer: "Decrypted Secrets". Springer 2002. ISBN
3-540-42674-4
- Helen Fouché Gaines, "Cryptanalysis", 1939, Dover. ISBN
0-486-20097-3
- David Kahn, "The Codebreakers - The Story of Secret
Writing", 1967. ISBN 0-684-83130-9
- Lars R. Knudsen: Contemporary Block Ciphers.
Lectures on Data Security 1998: 105-126
- Bruce Schneier, " Self-Study Course in Block Cipher Cryptanalysis",
Cryptologia, 24(1) (January 2000), pp. 18–34.
- Abraham Sinkov, Elementary
Cryptanalysis: A Mathematical Approach, Mathematical
Association of America, 1966. ISBN 0-88385-622-0
- Christopher Swenson, Modern
Cryptanalysis: Techniques for Advanced Code Breaking, ISBN
978-0470135938
- Friedman, William F.,
Military
Cryptanalysis, Part I, ISBN 0-89412-044-1
- Friedman, William F.,
Military
Cryptanalysis, Part II, ISBN 0-89412-064-6
- Friedman, William F.,
Military
Cryptanalysis, Part III, Simpler Varieties of Aperiodic
Substitution Systems, ISBN 0-89412-196-0
- Friedman, William F.,
Military
Cryptanalysis, Part IV, Transposition and Fractionating
Systems, ISBN 0-89412-198-7
- Friedman, William F. and
Lambros D. Callimahos, Military Cryptanalytics, Part I,
Volume 1, ISBN 0-89412-073-5
- Friedman, William F. and
Lambros D. Callimahos, Military Cryptanalytics, Part I,
Volume 2, ISBN 0-89412-074-3
- Friedman, William F. and
Lambros D. Callimahos, Military Cryptanalytics, Part II,
Volume 1, ISBN 0-89412-075-1
- Friedman, William F. and
Lambros D. Callimahos, Military Cryptanalytics, Part II,
Volume 2, ISBN 0-89412-076-X