|
|
 |
|
 |
Cryptanalysis is the art of
deciphering encrypted communications without knowing the proper
keys. There are many cryptanalytic techniques. Some of the more
important ones for a system implementor are described below.
- Ciphertext-only attack: This is the situation where the
attacker does not know anything about the contents of the message,
and must work from ciphertext only. In practice it is quite often
possible to make guesses about the plaintext, as many types of
messages have fixed format headers. Even ordinary letters and
documents begin in a very predictable way. For example, many
classical attacks use frequency analysis of the ciphertext,
however, this does not work well against modern ciphers.
Modern cryptosystems are not weak against ciphertext-only
attacks, although sometimes they are considered with the added
assumption that the message contains some statistical bias.
- Known-plaintext attack: The attacker knows or can guess
the plaintext for some parts of the ciphertext. The task is to
decrypt the rest of the ciphertext blocks using this information.
This may be done by determining the key used to encrypt the data,
or via some shortcut.
One of the best known modern
known-plaintext attacks is linear cryptanalysis against block
ciphers.
- Chosen-plaintext attack: The attacker is able to have
any text he likes encrypted with the unknown key. The task is to
determine the key used for encryption.
A good example of
this attack is the differential cryptanalysis which can be applied
against block ciphers (and in some cases also against hash
functions).
Some cryptosystems, particularly RSA,
are vulnerable to chosen-plaintext attacks. When such algorithms
are used, care must be taken to design the application (or
protocol) so that an attacker can never have
chosen plaintext
encrypted.
- Man-in-the-middle attack: This attack is relevant for
cryptographic communication and key exchange
protocols. The
idea is that when two parties, A and B, are exchanging keys for
secure communication (e.g., using Diffie-Hellman),
an adversary positions himself between A and B on the
communication line. The adversary then intercepts the signals that
A and B send to each other, and performs a key exchange with A and
B separately. A and B will end up using a different key, each of
which is known to the adversary. The adversary can then decrypt
any communication from A with the key he shares with A, and then
resends the communication to B by encrypting it again with the key
he shares with B. Both A and B will think that they are
communicating securely, but in fact the adversary is hearing
everything.
The usual way to prevent the man-in-the-middle
attack is to use a public key cryptosystem capable of providing
digital signatures. For set up, the parties must know each others
public keys in advance. After the shared secret has been
generated, the parties send digital signatures of it to each
other. The man-in-the-middle can attempt to forge these
signatures, but fails because he cannot fake the signatures.
This solution is sufficient in the presence of a way to
securely distribute public keys. One such way is a certificate
hierarchy such as X.509. It is used for example in IPSec.
- Correlation between the secret key and the output of
the cryptosystem is the main source of information to the
cryptanalyst. In the easiest case, the information about the
secret key is directly leaked by the cryptosystem. More
complicated cases require studying the correlation (basically, any
relation that would not be expected on the basis of chance alone)
between the observed (or measured) information about the
cryptosystem and the guessed key information.
For example,
in linear (resp. differential) attacks against block ciphers the
cryptanalyst studies the known (resp. chosen) plaintext and the
observed ciphertext. Guessing some of the key bits of the
cryptosystem the analyst determines by correlation between the
plaintext and the ciphertext whether she guessed correctly. This
can be repeated, and has many variations.
The differential
cryptanalysis introduced by Eli Biham and Adi Shamir in late
1980's was the first attack that fully utilized this idea against
block ciphers (especially against DES). Later Mitsuru Matsui came
up with linear cryptanalysis which was even more effective against
DES. More recently, new attacks using similar ideas have been
developed.
Perhaps the best introduction to this material
is the proceedings of EUROCRYPT and CRYPTO throughout the 1990's.
There can be found Mitsuru Matsui's discussion of linear
cryptanalysis of DES, and the ideas of truncated differentials by
Lars Knudsen (for example, IDEA cryptanalysis). The book by Eli
Biham and Adi Shamir about the differential cryptanalysis of DES
is the "classical" work on this subject.
The correlation
idea is fundamental to cryptography and several researchers have
tried to construct cryptosystems which are provably secure against
such attacks. For example, Knudsen and Nyberg have studied
provable security against differential cryptanalysis.
- Attack against or using the underlying hardware: in the
last few years as more and more small mobile crypto devices have
come into widespread use, a new category of attacks has become
relevant which aim directly at the hardware implementation of the
cryptosystem.
The attacks use the data from very fine
measurements of the crypto device doing, say, encryption and
compute key information from these measurements. The basic ideas
are then closely related to those in other correlation attacks.
For instance, the attacker guesses some key bits and attempts to
verify the correctness of the guess by studying correlation
against her measurements.
Several attacks have been
proposed such as using careful timings of the device, fine
measurements of the power consumption, and radiation patterns.
These measurements can be used to obtain the secret key or other
kinds information stored on the device.
This attack is
generally independent of the used cryptographical algorithms and
can be applied to any device that is not explicitly protected
against it.
More information about differential power
analysis is available at http://www.cryptography.com/.
- Faults in cryptosystems can lead to cryptanalysis and
even the discovery of the secret key. The interest in
cryptographical devices lead to the discovery that some
algorithms behaved very badly with the introduction of small
faults in the internal computation.
For example, the usual
implementation of RSA private key operations are very suspectible
to fault attacks. It has been shown that by causing one bit of
error at a suitable point can reveal the factorization of the
modulus (i.e. it reveals the private key).
Similar ideas
have been applied to a wide range of algorithms and devices. It is
thus necessary that cryptographical devices are designed to be
highly resistant against faults (and against malicious
introduction of faults by cryptanalysts).
- Quantum computing: Peter Shor's paper on polynomial
time factoring and discrete logarithm algorithms
with quantum
computers has caused growing interest in quantum computing.
Quantum computing is a recent field of research that uses quantum
mechanics to build computers that are, in theory, more powerful
than modern serial computers. The power is derived from the
inherent parallelism of quantum mechanics. So instead of doing
tasks one at a time, as serial machines do, quantum computers can
perform them all at once. Thus it is hoped that with
quantum
computers we can solve problems infeasible with serial machines.
Shor's results imply that if quantum computers could be
implemented effectively then most of public key cryptography will
become history. However, they are much less effective against
secret key cryptography.
Current state of the art of
quantum computing does not appear alarming, as only very small
machines have been implemented. The theory of quantum computation
gives much promise for better performance than serial computers,
however, whether it will be realized in practice is an open
question.
Quantum mechanics is also a source for new ways
of data hiding and secure communication with the potential of
offering unbreakable security, this is the field of quantum
cryptography. Unlike quantum computing, many successful
experimental implementations of quantum cryptography have been
already achieved. However, quantum cryptography is still some way
off from being realized in commercial applications.
- DNA cryptography: Leonard Adleman (one of the inventors
of RSA) came up with the idea of using DNA as
computers. DNA
molecules could be viewed as a very large computer capable of
parallel execution. This parallel nature could give DNA computers
exponential speed-up against modern serial computers.
There are unfortunately problems with DNA computers, one
being that the exponential speed-up requires also exponential
growth in the volume of the material needed. Thus in practice DNA
computers would have limits
on their performance. Also, it is
not very easy to build one.
There are many other
cryptographic attacks and cryptanalysis techniques. However, these
are probably the most important ones for an application designer.
Anyone contemplating to design a new cryptosystem should have a much
deeper understanding of these issues. Good places to start looking
for information are the excellent books Handbook
of Applied Cryptography by Menezes, van Oorschot, and Vanstone
and Applied
Cryptography by Schneier.
| |
|
