Cryptography-Digest Digest #388, Volume #10 Mon, 11 Oct 99 06:13:02 EDT
Contents:
Cryptography FAQ (03/10: Basic Cryptology) ([EMAIL PROTECTED])
Cryptography FAQ (04/10: Mathematical Cryptology) ([EMAIL PROTECTED])
----------------------------------------------------------------------------
From: [EMAIL PROTECTED]
Crossposted-To: talk.politics.crypto,sci.answers,news.answers,talk.answers
Subject: Cryptography FAQ (03/10: Basic Cryptology)
Date: 11 Oct 1999 09:45:14 GMT
Reply-To: [EMAIL PROTECTED]
Archive-name: cryptography-faq/part03
Last-modified: 93/10/10
This is the third of ten parts of the sci.crypt FAQ. The parts are
mostly independent, but you should read the first part before the rest.
We don't have the time to send out missing parts by mail, so don't ask.
Notes such as ``[KAH67]'' refer to the reference list in the last part.
The sections of this FAQ are available via anonymous FTP to rtfm.mit.edu
as /pub/usenet/news.answers/cryptography-faq/part[xx]. The Cryptography
FAQ is posted to the newsgroups sci.crypt, talk.politics.crypto,
sci.answers, and news.answers every 21 days.
Contents:
3.1. What is cryptology? Cryptography? Plaintext? Ciphertext? Encryption? Key?
3.2. What references can I start with to learn cryptology?
3.3. How does one go about cryptanalysis?
3.4. What is a brute-force search and what is its cryptographic relevance?
3.5. What are some properties satisfied by every strong cryptosystem?
3.6. If a cryptosystem is theoretically unbreakable, then is it
guaranteed analysis-proof in practice?
3.7. Why are many people still using cryptosystems that are
relatively easy to break?
3.8. What are the basic types of cryptanalytic `attacks'?
3.1. What is cryptology? Cryptography? Plaintext? Ciphertext? Encryption? Key?
The story begins: When Julius Caesar sent messages to his trusted
acquaintances, he didn't trust the messengers. So he replaced every A
by a D, every B by a E, and so on through the alphabet. Only someone
who knew the ``shift by 3'' rule could decipher his messages.
A cryptosystem or cipher system is a method of disguising messages so
that only certain people can see through the disguise. Cryptography is
the art of creating and using cryptosystems. Cryptanalysis is the art
of breaking cryptosystems---seeing through the disguise even when
you're not supposed to be able to. Cryptology is the study of both
cryptography and cryptanalysis.
The original message is called a plaintext. The disguised message is
called a ciphertext. Encryption means any procedure to convert
plaintext into ciphertext. Decryption means any procedure to convert
ciphertext into plaintext.
A cryptosystem is usually a whole collection of algorithms. The
algorithms are labelled; the labels are called keys. For instance,
Caesar probably used ``shift by n'' encryption for several different
values of n. It's natural to say that n is the key here.
The people who are supposed to be able to see through the disguise are
called recipients. Other people are enemies, opponents, interlopers,
eavesdroppers, or third parties.
3.2. What references can I start with to learn cryptology?
For an introduction to technical matter, the survey articles given
in part 10 are the best place to begin as they are, in general,
concise, authored by competent people, and well written. However,
these articles are mostly concerned with cryptology as it has
developed in the last 50 years or so, and are more abstract and
mathematical than historical. The Codebreakers by Kahn [KAH67] is
encyclopedic in its history and technical detail of cryptology up
to the mid-60's.
Introductory cryptanalysis can be learned from Gaines [GAI44] or
Sinkov [SIN66]. This is recommended especially for people who want
to devise their own encryption algorithms since it is a common
mistake to try to make a system before knowing how to break one.
The selection of an algorithm for the DES drew the attention of
many public researchers to problems in cryptology. Consequently
several textbooks and books to serve as texts have appeared. The
book of Denning [DEN82] gives a good introduction to a broad range
of security including encryption algorithms, database security,
access control, and formal models of security. Similar comments
apply to the books of Price & Davies [PRI84] and Pfleeger [PFL89].
The books of Konheim [KON81] and Meyer & Matyas [MEY82] are quite
technical books. Both Konheim and Meyer were directly involved in
the development of DES, and both books give a thorough analysis of
DES. Konheim's book is quite mathematical, with detailed analyses
of many classical cryptosystems. Meyer and Matyas concentrate on
modern cryptographic methods, especially pertaining to key management
and the integration of security facilities into computer systems and
networks. For more recent documentation on related areas, try
G. Simmons in [SIM91].
The books of Rueppel [RUE86] and Koblitz [KOB89] concentrate on
the application of number theory and algebra to cryptography.
3.3. How does one go about cryptanalysis?
Classical cryptanalysis involves an interesting combination of
analytical reasoning, application of mathematical tools, pattern
finding, patience, determination, and luck. The best available
textbooks on the subject are the Military Cryptanalytics series
[FRIE1]. It is clear that proficiency in cryptanalysis is, for
the most part, gained through the attempted solution of given
systems. Such experience is considered so valuable that some of the
cryptanalyses performed during WWII by the Allies are still
classified.
Modern public-key cryptanalysis may consist of factoring an integer,
or taking a discrete logarithm. These are not the traditional fare
of the cryptanalyst. Computational number theorists are some of the
most successful cryptanalysts against public key systems.
3.4. What is a brute-force search and what is its cryptographic relevance?
In a nutshell: If f(x) = y and you know y and can compute f, you can
find x by trying every possible x. That's brute-force search.
Example: Say a cryptanalyst has found a plaintext and a corresponding
ciphertext, but doesn't know the key. He can simply try encrypting the
plaintext using each possible key, until the ciphertext matches---or
decrypting the ciphertext to match the plaintext, whichever is faster.
Every well-designed cryptosystem has such a large key space that this
brute-force search is impractical.
Advances in technology sometimes change what is considered
practical. For example, DES, which has been in use for over 10 years
now, has 2^56, or about 10^17, possible keys. A computation with
this many operations was certainly unlikely for most users in the
mid-70's. The situation is very different today given the dramatic
decrease in cost per processor operation. Massively parallel
machines threaten the security of DES against brute force search.
Some scenarios are described by Garron and Outerbridge [GAR91].
One phase of a more sophisticated cryptanalysis may involve a
brute-force search of some manageably small space of possibilities.
3.5. What are some properties satisfied by every strong cryptosystem?
The security of a strong system resides with the secrecy of the key
rather than with the supposed secrecy of the algorithm.
A strong cryptosystem has a large keyspace, as mentioned above. It
has a reasonably large unicity distance; see question 8.8.
A strong cryptosystem will certainly produce ciphertext which appears
random to all standard statistical tests (see, for example, [CAE90]).
A strong cryptosystem will resist all known previous attacks. A
system which has never been subjected to scrutiny is suspect.
If a system passes all the tests mentioned above, is it necessarily
strong? Certainly not. Many weak cryptosystems looked good at first.
However, sometimes it is possible to show that a cryptosystem is
strong by mathematical proof. ``If Joe can break this system, then
he can also solve the well-known difficult problem of factoring
integers.'' See part 6. Failing that, it's a crap shoot.
3.6. If a cryptosystem is theoretically unbreakable, then is it
guaranteed analysis-proof in practice?
Cryptanalytic methods include what is known as ``practical
cryptanalysis'': the enemy doesn't have to just stare at your
ciphertext until he figures out the plaintext. For instance, he might
assume ``cribs''---stretches of probable plaintext. If the crib is
correct then he might be able to deduce the key and then decipher the
rest of the message. Or he might exploit ``isologs''---the same
plaintext enciphered in several cryptosystems or several keys. Thus
he might obtain solutions even when cryptanalytic theory says he
doesn't have a chance.
Sometimes, cryptosystems malfunction or are misused. The one-time pad,
for example, loses all security if it is used more than once! Even
chosen-plaintext attacks, where the enemy somehow feeds plaintext into
the encryptor until he can deduce the key, have been employed. See
[KAH67].
3.7. Why are many people still using cryptosystems that are
relatively easy to break?
Some don't know any better. Often amateurs think they can design
secure systems, and are not aware of what an expert cryptanalyst
could do. And sometimes there is insufficient motivation for anybody
to invest the work needed to crack a system.
3.8. What are the basic types of cryptanalytic `attacks'?
A standard cryptanalytic attack is to know some plaintext matching a
given piece of ciphertext and try to determine the key which maps one
to the other. This plaintext can be known because it is standard (a
standard greeting, a known header or trailer, ...) or because it is
guessed. If text is guessed to be in a message, its position is probably
not known, but a message is usually short enough that the cryptanalyst
can assume the known plaintext is in each possible position and do
attacks for each case in parallel. In this case, the known plaintext can
be something so common that it is almost guaranteed to be in a message.
A strong encryption algorithm will be unbreakable not only under known
plaintext (assuming the enemy knows all the plaintext for a given
ciphertext) but also under "adaptive chosen plaintext" -- an attack
making life much easier for the cryptanalyst. In this attack, the enemy
gets to choose what plaintext to use and gets to do this over and over,
choosing the plaintext for round N+1 only after analyzing the result of
round N.
For example, as far as we know, DES is reasonably strong even under an
adaptive chosen plaintext attack (the attack Biham and Shamir used). Of
course, we do not have access to the secrets of government cryptanalytic
services. Still, it is the working assumption that DES is reasonably
strong under known plaintext and triple-DES is very strong under all
attacks.
To summarize, the basic types of cryptanalytic attacks in order of
difficulty for the attacker, hardest first, are:
cyphertext only: the attacker has only the encoded message from which
to determine the plaintext, with no knowledge whatsoever of the
latter.
A cyphertext only attack is usually presumed to be possible, and
a code's resistance to it is considered the basis of its
cryptographic security.
known plaintext: the attacker has the plaintext and corresponding
cyphertext of an arbitrary message not of his choosing. The
particular message of the sender's is said to be `compromised'.
In some systems, one known cyphertext-plaintext pair will
compromise the overall system, both prior and subsequent
transmissions, and resistance to this is characteristic of a
secure code.
Under the following attacks, the attacker has the far less likely
or plausible ability to `trick' the sender into encrypting or
decrypting arbitrary plaintexts or cyphertexts. Codes that resist
these attacks are considered to have the utmost security.
chosen plaintext: the attacker has the capability to find the
cyphertext corresponding to an arbitrary plaintext message of his
choosing.
chosen cyphertext: the attacker can choose arbitrary cyphertext and
find the corresponding decrypted plaintext. This attack can show
in public key systems, where it may reveal the private key.
adaptive chosen plaintext: the attacker can determine the cyphertext
of chosen plaintexts in an interactive or iterative process based on
previous results. This is the general name for a method of attacking
product ciphers called `differential cryptanalysis'.
The next part of the FAQ gives the mathematical detail behind the
various types of cryptoanalytic attacks.
------------------------------
From: [EMAIL PROTECTED]
Crossposted-To: talk.politics.crypto,sci.answers,news.answers,talk.answers
Subject: Cryptography FAQ (04/10: Mathematical Cryptology)
Date: 11 Oct 1999 09:45:16 GMT
Reply-To: [EMAIL PROTECTED]
Archive-name: cryptography-faq/part04
Last-modified: 93/10/10
This is the fourth of ten parts of the sci.crypt FAQ. The parts are
mostly independent, but you should read the first part before the rest.
We don't have the time to send out missing parts by mail, so don't ask.
Notes such as ``[KAH67]'' refer to the reference list in the last part.
The sections of this FAQ are available via anonymous FTP to rtfm.mit.edu
as /pub/usenet/news.answers/cryptography-faq/part[xx]. The Cryptography
FAQ is posted to the newsgroups sci.crypt, talk.politics.crypto,
sci.answers, and news.answers every 21 days.
Contents:
4.1. In mathematical terms, what is a private-key cryptosystem?
4.2. What is an attack?
4.3. What's the advantage of formulating all this mathematically?
4.4. Why is the one-time pad secure?
4.5. What's a ciphertext-only attack?
4.6. What's a known-plaintext attack?
4.7. What's a chosen-plaintext attack?
4.8. In mathematical terms, what can you say about brute-force attacks?
4.9. What's a key-guessing attack? What's entropy?
Reader, beware: This section is highly mathematical. Well, maybe not
_highly_ mathematical, but it's got a bunch of symbols and scary-looking
formulas. You have been warned.
4.1. In mathematical terms, what is a private-key cryptosystem?
A private-key cryptosystem consists of an encryption system E and a
decryption system D. The encryption system E is a collection of
functions E_K, indexed by ``keys'' K, mapping some set of
``plaintexts'' P to some set of ``ciphertexts'' C. Similarly the
decryption system D is a collection of functions D_K such that
D_K(E_K(P)) = P for every plaintext P. That is, succesful decryption
of ciphertext into plaintext is accomplished using the same key
(index) as was used for the corresponding encryption of plaintext
into ciphertext. Such systems, where the same key value is used to
encrypt and decrypt, are also known as ``symmetric'' cryptoystems.
4.2. What is an attack?
In intuitive terms a (passive) attack on a cryptosystem is any method
of starting with some information about plaintexts and their
corresponding ciphertexts under some (unknown) key, and figuring out
more information about the plaintexts. It's possible to state
mathematically what this means. Here we go.
Fix functions F, G, and H of n variables. Fix an encryption system E,
and fix a distribution of plaintexts and keys.
An attack on E using G assuming F giving H with probability p is an
algorithm A with a pair f, g of inputs and one output h, such that
there is probability p of computing h = H(P_1,...,P_n), if we have
f = F(P_1,...,P_n) and g = G(E_K(P_1),...,E_K(P_n)). Note that this
probability depends on the distribution of the vector (K,P_1,...,P_n).
The attack is trivial (or ``pointless'') if there is probability at
least p of computing h = H(P_1,...,P_n) if f = F(P_1,...,P_n) and
g = G(C_1,...,C_n). Here C_1,...,C_n range uniformly over the possible
ciphertexts, and have no particular relation to P_1,...,P_n. In other
words, an attack is trivial if it doesn't actually use the encryptions
E_K(P_1),...,E_K(P_n).
An attack is called ``one-ciphertext'' if n = 1, ``two-ciphertext'' if
n = 2, and so on.
4.3. What's the advantage of formulating all this mathematically?
In basic cryptology you can never prove that a cryptosystem is secure.
Read part 3: we keep saying ``a strong cryptosystem must have this
property, but having this property is no guarantee that a cryptosystem
is strong!''
In contrast, the purpose of mathematical cryptology is to precisely
formulate and, if possible, prove the statement that a cryptosystem is
strong. We say, for example, that a cryptosystem is secure against
all (passive) attacks if any nontrivial attack against the system (as
defined above) is too slow to be practical. If we can prove this
statement then we have confidence that our cryptosystem will resist
any (passive) cryptanalytic technique. If we can reduce this statement
to some well-known unsolved problem then we still have confidence that
the cryptosystem isn't easy to break.
Other parts of cryptology are also amenable to mathematical
definition. Again the point is to explicitly identify what assumptions
we're making and prove that they produce the desired results. We can
figure out what it means for a particular cryptosystem to be used
properly: it just means that the assumptions are valid.
The same methodology is useful for cryptanalysis too. The cryptanalyst
can take advantage of incorrect assumptions. Often he can try to
construct a proof of security for a system, see where the proof fails,
and use these failures as the starting points for his analysis.
4.4. Why is the one-time pad secure?
By definition, the one-time pad is a cryptosystem where the
plaintexts, ciphertexts, and keys are all strings (say byte strings)
of some length m, and E_K(P) is just the sum (let's say the exclusive
or) of K and P.
It is easy to prove mathematically that there are _no_ nontrivial
single-ciphertext attacks on the one-time pad, assuming a uniform
distribution of keys. Note that we don't have to assume a uniform
distribution of plaintexts. (Here's the proof: Let A be an attack,
i.e., an algorithm taking two inputs f, g and producing one output h,
with some probability p that h = H(P) whenever f = F(P) and
g = G(E_K(P)) (i.e., g = G(K + P)). Then, because the distribution of
K is uniform and independent of P, the distribution of K + P must also
be uniform and independent of P. But also the distribution of C is
uniform and independent of P. Hence there is probability exactly p
that h = H(P) whenever f = F(P) and g = G(C), over all P and C. Thus
a fortiori A is trivial.)
On the other hand the one-time pad is _not_ secure if a key K is used
for more than one plaintext: i.e., there are nontrivial
multiple-ciphertext attacks. So to be properly used a key K must be
thrown away after one encryption. The key is also called a ``pad'';
this explains the name ``one-time pad.''
Also, a computer-based pseudo-random number generator does _not_
qualify as a true one-time pad because of its deterministic
properties. See `pseudo-random number generators as key stream'.
4.5. What's a ciphertext-only attack?
In the notation above, a ciphertext-only attack is one where F is
constant. Given only some information G(E_K(P_1),...,E_K(P_n)) about
n ciphertexts, the attack has to have some chance of producing some
information H(P_1,...,P_n) about the plaintexts. The attack is trivial
if it has just as good a chance of producing H(P_1,...,P_n) when given
G(C_1,...,C_n) for random C_1,...,C_n.
For example, say G(C) = C, and say H(P) is the first bit of P. We can
easily write down an attack---the ``guessing attack,'' which simply
guesses that H(P) is 1. This attack is trivial because it doesn't use
the ciphertext: it has a fifty-fifty chance of guessing correctly no
matter what. On the other hand there is an attack on RSA which
produces one bit of information about P, with 100% success, using C.
If it is fed a random C then the success rate drops to 50%. So this is
a nontrivial attack.
4.6. What's a known-plaintext attack?
The classic known-plaintext attack has F(P_1,P_2) = P_1,
G(C_1,C_2) = (C_1,C_2), and H(P_1,P_2) depending only on P_2.
In other words, given two ciphertexts C_1 and C_2 and one decryption
P_1, the known-plaintext attack should produce information about the
other decryption P_2.
Note that known-plaintext attacks are often defined in the literature
as producing information about the key, but this is pointless: the
cryptanalyst generally cares about the key only insofar as it lets him
decrypt further messages.
4.7. What's a chosen-plaintext attack?
A chosen-plaintext attack is the first of an increasingly impractical
series of _active_ attacks on a cryptosystem: attacks where the
cryptanalyst feeds data to the encryptor. These attacks don't fit into
our model of passive attacks explained above. Anyway, a
chosen-plaintext attack lets the cryptanalyst choose a plaintext and
look at the corresponding ciphertext, then repeat until he has figured
out how to decrypt any message. More absurd examples of this sort of
attack are the ``chosen-key attack'' and ``chosen-system attack.''
A much more important form of active attack is a message corruption
attack, where the attacker tries to change the ciphertext in such a
way as to make a useful change in the plaintext.
There are many easy ways to throw kinks into all of these attacks:
for instance, automatically encrypting any plaintext P as
T,E_K(h(T+R+P),R,P), where T is a time-key (sequence number) chosen anew
for each message, R is a random number, and h is a one-way hash
function. Here comma means concatenation and plus means exclusive-or.
4.8. In mathematical terms, what can you say about brute-force attacks?
Consider the following known-plaintext attack. We are given some
plaintexts P_1,...,P_{n-1} and ciphertexts C_1,...,C_{n-1}. We're
also given a ciphertext C_n. We run through every key K. When we find
K such that E_K(P_i) = C_i for every i < n, we print D_K(C_n).
If n is big enough that only one key works, this attack will succeed
on valid inputs all the time, while it will produce correct results
only once in a blue moon for random inputs. Thus this is a nontrivial
attack. Its only problem is that it is very slow if there are many
possible keys.
4.9. What's a key-guessing attack? What's entropy?
Say somebody is using the one-time pad---but isn't choosing keys
randomly and uniformly from all m-bit messages, as he was supposed to
for our security proof. In fact say he's known to prefer keys which
are English words. Then a cryptanalyst can run through all English
words as possible keys. This attack will often succeed, and it's much
faster than a brute-force search of the entire keyspace.
We can measure how bad a key distribution is by calculating its
entropy. This number E is the number of ``real bits of information''
of the key: a cryptanalyst will typically happen across the key within
2^E guesses. E is defined as the sum of -p_K log_2 p_K, where p_K is
the probability of key K.
------------------------------
** FOR YOUR REFERENCE **
The service address, to which questions about the list itself and requests
to be added to or deleted from it should be directed, is:
Internet: [EMAIL PROTECTED]
You can send mail to the entire list (and sci.crypt) via:
Internet: [EMAIL PROTECTED]
End of Cryptography-Digest Digest
******************************
