|
Subject: Cryptography FAQ (01/10: Overview)
Date: 18 Feb 1994 15:14:44 GMT
Organization: The Crypt Cabal
Summary: Part 1 of 10 of the sci.crypt FAQ,
Overview. Table ofcontents, contributors, feedback,archives,
administrivia, changes.
Archive-name: cryptography-faq/part01
Version: 1.0
Last-modified: 93/08/23
This is the first of ten parts of the sci.crypt FAQ. The
parts are mostly independent, but you should readthis part before
the rest. We don't have the time to send out missing parts by mail,
so don't ask. Notessuch as ``[KAH67]'' refer to the reference list
in the last part.
Disclaimer:
This document is the product of the Crypt Cabal, a secret
society which serves the NationalSecu---uh, no. Seriously, we're the
good guys, and we've done what we can to ensure the completenessand
accuracy of this document, but in a field of military and commercial
importance like cryptography youhave to expect that some people and
organizations consider their interests more important than open
scientific discussion. Trust only what you can verify firsthand. And
don't sue us.
Many people
have contributed to this FAQ. In alphabetical order:
Eric Bach, Steve Bellovin, Dan Bernstein, Nelson Bolyard,
Carl Ellison, Jim Gillogly, Mike Gleason, DougGwyn, Luke O'Connor,
Tony Patti, William Setzer. We apologize for any omissions.
If you have suggestions, comments, or criticism, please let
the current editors know by sending e-mail
tocrypt-comments@math.ncsu.edu. Bear in mind that this is a work in
progress; there are some questionswhich we should add but haven't
gotten around to yet. In making comments on additions it is
mosthelpful if you are as specific as possible andideally even
provide the actual exact text.
Archives: sci.crypt has been archived since October 1991 on
ripem.msu.edu, though these archives areavailable only to U.S. and
Canadian users. Another site is rpub.cl.msu.edu in
/pub/crypt/sci.crypt/fromJan 1992. Please contact
crypt-comments@math.ncsu.edu if you know of other archives.
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 thenewsgroups sci.crypt,
talk.politics.crypto, sci.answers, and news.answers every 21 days.
Changes: a section at the end of this part 1 lists recent
changes.The fields `Last-Modified' and `Version'at the top of this
part 1 track revisions.
Table of
Contents
-----------------
1. Overview
2. Net Etiquette
2.1. What groups are around? What's a FAQ? Who
am I? Why am I here?
2.2. Do political discussions belong in
sci.crypt?
2.3. How do I present a new encryption scheme in
sci.crypt?
3. Basic Cryptology
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'?
4. Mathematical Cryptology
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?
5. Product Ciphers
5.1. What is a product cipher?
5.2. What makes a product cipher secure?
5.3. What are some group-theoretic properties of
product ciphers?
5.4. What can be proven about the security of a
product cipher?
5.5. How are block ciphers used to encrypt data
longer than the block size?
5.6. Can symmetric block ciphers be used for
message authentication?
5.7. What exactly is DES?
5.8. What is triple DES?
5.9. What is differential cryptanalysis?
5.10. How was NSA involved in the design of DES?
5.11. Is DES available in software?
5.12. Is DES available in hardware?
5.13. Can DES be used to protect classified
information?
5.14. What are ECB, CBC, CFB, and OFB
encryption?
6. Public-Key Cryptography
6.1. What is public-key cryptography?
6.2. How does public-key cryptography solve
cryptography's Catch-22?
6.3. What is the role of the `trapdoor function'
in public key schemes?
6.4. What is the role of the `session key' in
public key schemes?
6.5. What's RSA?
6.6. Is RSA secure?
6.7. What's the difference between the RSA and
Diffie-Hellman schemes?
6.8. What is `authentication' and the `key
distribution problem'?
6.9. How fast can people factor numbers?
6.10. What about other public-key cryptosystems?
6.11. What is the `RSA Factoring Challenge?'
7. Digital Signatures
7.1. What is a one-way hash function?
7.2. What is the difference between public,
private, secret, shared, etc.?
7.3. What are MD4 and MD5?
7.4. What is Snefru?
8. Technical Miscellany
8.1. How do I recover from lost passwords in
WordPerfect?
8.2. How do I break a Vigenere (repeated-key)
cipher?
8.3. How do I send encrypted mail under UNIX?
[PGP, RIPEM, PEM, ...]
8.4. Is the UNIX crypt command secure?
8.5. How do I use compression with encryption?
8.6. Is there an unbreakable cipher?
8.7. What does ``random'' mean in cryptography?
8.8. What is the unicity point (a.k.a. unicity
distance)?
8.9. What is key management and why is it
important?
8.10. Can I use pseudo-random or chaotic numbers
as a key stream?
8.11. What is the correct frequency list for
English letters?
8.12. What is the Enigma?
8.13. How do I shuffle cards?
8.14. Can I foil S/W pirates by encrypting my
CD-ROM?
8.15. Can you do automatic cryptanalysis of
simple ciphers?
8.16. What is the coding system used by VCR+?
9. Other Miscellany
9.1. What is the National Security Agency (NSA)?
9.2. What are the US export regulations?
9.3. What is TEMPEST?
9.4. What are the Beale Ciphers, and are they a
hoax?
9.5. What is the American Cryptogram
Association, and how do I get in touch?
9.6. Is RSA patented?
9.7. What about the Voynich manuscript?
10. References
10.1. Books on history and classical methods
10.2. Books on modern methods
10.3. Survey articles
10.4. Reference articles
10.5. Journals, conference proceedings
10.6. Other
10.7. How may one obtain copies of FIPS and ANSI
standards cited herein?
10.8. Electronic sources
10.9. RFCs (available from [FTPRF])
10.10. Related newsgroups
Changes
-------
930823 L.D.
New sci.crypt archive site (1). NIST [FTPNS], cypherpunk
FTP [FTPCP] sites added (10.6, 10.8), moreinfo on security of RSA
(6.3). Public key basics refined (6.1). RSA Factoring Challenge
added (6.5). AddedChanges section (1). Update of ACA address (9.5).
C. Ellison modifications on compression (8.5) andattack types added
(3.8). Info Security News in (10.5). New DES source [FTPAL].
Article 18264
of news.answers:
Path:
news.columbia.edu!sol.ctr.columbia.edu!destroyer!newsxfer.itd.umich.edu!gumby!wupost!usc!bloom-
beacon.mit.edu!senator-bedfellow.mit.edu!faqserv
From: crypt-comments@math.ncsu.edu
Newsgroups:
sci.crypt,talk.politics.crypto,sci.answers,news.answers,talk.answers
Subject: Cryptography FAQ (02/10: Net Etiquette)
Supersedes:
<cryptography-faq/part02_758782810@rtfm.mit.edu>
Followup-To: poster
Date: 18 Feb 1994 15:14:51 GMT
Organization: The Crypt Cabal
Lines: 91
Approved: news-answers-request@MIT.Edu
Expires: 25 Mar 1994 15:11:15 GMT
Message-ID:
<cryptography-faq/part02_761584275@rtfm.mit.edu>
References:
<cryptography-faq/part01_761584275@rtfm.mit.edu>
Reply-To: crypt-comments@math.ncsu.edu
NNTP-Posting-Host: bloom-picayune.mit.edu
X-Last-Updated: 1993/10/10
Originator: faqserv@bloom-picayune.MIT.EDU
Xref: news.columbia.edu sci.crypt:21374
talk.politics.crypto:2942 sci.answers:899 news.answers:18264
talk.answers:149
Archive-name: cryptography-faq/part02
Last-modified: 93/05/04
This is the second of ten parts of the sci.crypt FAQ. The
parts are mostly independent, but you shouldread 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 thenewsgroups sci.crypt,
talk.politics.crypto, sci.answers, and news.answers every 21 days.
Contents:
2.1. What groups are around? What's a FAQ? Who
am I? Why am I here?
2.2. Do political discussions belong in
sci.crypt?
2.3. How do I present a new encryption scheme in
sci.crypt?
2.1. What
groups are around? What's a FAQ? Who am I? Why am I here?
Read news.announce.newusers and news.answers for a few
weeks. Always make sure to read anewsgroup for some time before you
post to it. You'll be amazed how often the same question can beasked
in the same newsgroup. After a month you'll have a much better sense
of what the readers wantto see.
2.2. Do
political discussions belong in sci.crypt?
No. In fact some newsgroups (notably misc.legal.computing)
were created exactly so that politicalquestions like ``Should RSA be
patented?'' don't get in the way of technical discussions. Many
sci.cryptreaders also read misc.legal.computing, comp.org.eff.talk,
comp.patents, sci.math, comp.compression,et al.; for the benefit of
people who don't care about those other topics, try to put your
postings in theright group.
Questions about microfilm and smuggling and other
non-cryptographic``spy stuff'' don't belong insci.crypt either.
2.3. How do I
present a new encryption scheme in sci.crypt?
``I just came up with this neat method of encryption.
Here's some ciphertext:FHDSIJOYW^&%$*#@OGBUJHKFSYUIRE. Is it
strong?'' Without a doubt questions like this are the mostannoying
traffic on sci.crypt.
If you have come up with an encryption scheme, providing
some ciphertext from it is not adequate.Nobody has ever been
impressed byrandom gibberish. Any new algorithm should be secure
even if the opponent knows the full algorithm (including how any
message key isdistributed) and only the privatekey is kept secret.
There are somesystematic and unsystematic ways to take reasonably
long ciphertexts and decrypt them even without prior knowledge of
the algorithm, but this is a time-consuming and possibly fruitless
exercise which most sci.crypt readers won't bother with.
So what do you do if you have a new encryption scheme?
First of all,find out if it's really new. Lookthrough this FAQ for
references andrelated methods. Familiarize yourself with the
literature and theintroductory textbooks.
When you can appreciate how your cryptosystem fits into the
world atlarge, try to break it yourself! Youshouldn't waste the time
of tensof thousands of readers asking a question which you could
have easily answered on your own.
If you really think your system is secure, and you want to
get some reassurance from experts, you mighttry posting full details
of your system, including working code and a solid theoretical
explanation, to sci.crypt. (Keep in mind that the export of
cryptography is regulated in some areas.)
If you're lucky an expert might take some interest in what
you posted.You can encourage this by offering cash rewards---for
instance, noted cryptographer Ralph Merkle is offering $1000 to
anyone whocan break Snefru-4---but there are no guarantees. If you
don't have enough experience, then most likelyany experts who look
at your system will be able to find a flaw. If this happens, it's
your responsibility to consider the flaw and learn from it, rather
than just add one more layer of complication and come back
foranother round.
A different way to get your cryptosystem reviewed is to
have the NSA look at it. A full discussion of thisprocedure is
outside the scope of this FAQ.
Among professionals, a common rule of thumb is that if you
want to design a cryptosystem, you have tohave experience as a
cryptanalyst.
Article 18266
of news.answers:
Path:
news.columbia.edu!sol.ctr.columbia.edu!destroyer!newsxfer.itd.umich.edu!gumby!wupost!usc!bloom-
beacon.mit.edu!senator-bedfellow.mit.edu!faqserv
From: crypt-comments@math.ncsu.edu
Newsgroups:
sci.crypt,talk.politics.crypto,sci.answers,news.answers,talk.answers
Subject: Cryptography FAQ (03/10: Basic Cryptology)
Supersedes:
<cryptography-faq/part03_758782810@rtfm.mit.edu>
Followup-To: poster
Date: 18 Feb 1994 15:14:59 GMT
Organization: The Crypt Cabal
Lines: 251
Approved: news-answers-request@MIT.Edu
Expires: 25 Mar 1994 15:11:15 GMT
Message-ID:
<cryptography-faq/part03_761584275@rtfm.mit.edu>
References:
<cryptography-faq/part01_761584275@rtfm.mit.edu>
Reply-To: crypt-comments@math.ncsu.edu
NNTP-Posting-Host: bloom-picayune.mit.edu
X-Last-Updated: 1993/10/10
Originator: faqserv@bloom-picayune.MIT.EDU
Xref: news.columbia.edu sci.crypt:21375
talk.politics.crypto:2943 sci.answers:900 news.answers:18266
talk.answers:150
Archive-name: cryptography-faq/part03
Last-modified: 93/08/30
This is the third of ten parts of the sci.crypt FAQ. The
parts are mostly independent, but you should readthe 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.eduas/pub/usenet/news.answers/cryptography-faq/part[xx].
The Cryptography FAQ is posted to thenewsgroups 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 themessengers. So he replaced
every A by a D, every B by a E, and so on through the alphabet.
Onlysomeone 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 seethrough the disguise.
Cryptography isthe art of creating and using cryptosystems.
Cryptanalysis is theart 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 meansany procedure to
convert plaintext into ciphertext. Decryption means any procedure to
convert ciphertextinto plaintext.
A cryptosystem is usually a whole collection of algorithms.
The algorithms are labelled; the labels arecalled 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 peopleare 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 asthey are, in
general, concise, authored by competent people, and well written.
However, these articles aremostly concerned with cryptology as it
has developed in the last 50 years or so, and are more abstractand
mathematical than historical. The Codebreakers by Kahn [KAH67] is
encyclopedic in its history andtechnical detail of cryptology up to
the mid-60's.
Introductory cryptanalysis can be learned from Gaines
[GAI44] or Sinkov [SIN66]. This is recommendedespecially for people
who want to devise their own encryption algorithms since it is a
common mistake totry 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 incryptology.
Consequently several textbooks and books to serve as texts have
appeared. The book ofDenning [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 ofPrice & Davies [PRI84] and Pfleeger
[PFL89].
The books of Konheim [KON81] and Meyer & Matyas [MEY82] are
quite technical books. Both Konheimand Meyer were directly involved
in the development of DES, and both books give a thorough analysis
ofDES. Konheim's book is quite mathematical, with detailed analyses
of many classical cryptosystems.
Meyer and Matyas concentrate on modern cryptographic
methods, especially pertaining to keymanagement and the integration
of security facilities into computer systems and networks. For
morerecent documentation on related areas, try G. Simmons in
[SIM91].
The books of Rueppel [RUE86] and Koblitz [KOB89]
concentrate on the application of number theory andalgebra to
cryptography.
3.3. How does
one go about cryptanalysis?
Classical cryptanalysis involves an interesting combination
of analytical reasoning, application ofmathematical tools, pattern
finding, patience, determination, and luck. The best available
textbooks onthe subject are the Military Cryptanalytics series
[FRIE1]. It is clear that proficiency in cryptanalysis is, forthe
most part, gained through the attempted solution of given systems.
Such experience is considered sovaluable 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. Theseare not the
traditional fare of the cryptanalyst. Computational number theorists
are some of the mostsuccessful 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 thekey. 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 cryptosystemhas
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 hasbeen in use for over 10 years
now, has 2^56, or about 10^17, possible keys. A computation with
thismany operations was certainly unlikely for most users in the
mid-70's. The situation is very differenttoday given the dramatic
decrease in cost per processor operation. Massively parallel
machines threatenthe 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 manageablysmall 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 secrecyof the algorithm.
A strong cryptosystem has a large keyspace, as mentioned
above. It has a reasonably large unicitydistance; see question 8.8.
A strong cryptosystem will certainly produce ciphertext
which appears random to all standard statisticaltests (see, for
example, [CAE90]).
A strong cryptosystem will resist all known previous
attacks. A system which has never been subjected toscrutiny is
suspect.
If a system passes all the tests mentioned above, is it
necessarily strong? Certainly not. Many weakcryptosystems 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-knowndifficult 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 tojust 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
thendecipher the rest of the message. Or he might exploit
``isologs''---the same plaintext enciphered inseveral cryptosystems
or several keys. Thus he might obtain solutions even when
cryptanalytic theorysays he doesn't have a chance.
Sometimes, cryptosystems malfunction or are misused. The
one-time pad, for example, loses all securityif it is used more than
once! Even chosen-plaintext attacks, where the enemy somehow feeds
plaintextinto 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 ofwhat an expert
cryptanalyst could do. And sometimes there is insufficient
motivation for anybody toinvest 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 todetermine the key
which maps oneto the other.This plaintext can be known because it is
standard (astandard greeting, a known header or trailer, ...) or
because it is guessed.If text is guessed to be in amessage, its
position is probablynot known, but a message is usually short enough
that the cryptanalystcan assume the known plaintext is in each
possible position and doattacks for each case in parallel.Inthis
case, the known plaintext canbe something so common that it is
almost guaranteed to be in amessage.
A strong encryption algorithm will be unbreakable not only
under knownplaintext (assuming the enemyknows all the plaintext for
a givenciphertext) but also under "adaptive chosen plaintext" -- an
attackmaking life much easier for the cryptanalyst.In this attack,
the enemygets to choose what plaintext touse and gets to do this
over and over,choosing the plaintext for round N+1 only after
analyzing theresult ofround N.
For example, as far as we know, DES is reasonably strong
even under anadaptive chosen plaintextattack (the attack Biham and
Shamir used).Ofcourse, we do not have access to the secrets
ofgovernment cryptanalyticservices.Still, it is the working
assumption that DES is reasonablystrongunder known plaintext and
triple-DES is very strong under allattacks.
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 thelatter.
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.
Subject: Cryptography FAQ (04/10: Mathematical
Cryptology)
Archive-name: cryptography-faq/part04
Last-modified: 93/08/14
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.
Subject: Cryptography FAQ (05/10: Product
Ciphers)
Archive-name: cryptography-faq/part05
Last-modified: 93/08/14
This is the fifth 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:
5.1. What is a product cipher?
5.2. What makes a product cipher secure?
5.3. What are some group-theoretic properties of
product ciphers?
5.4. What can be proven about the security of a
product cipher?
5.5. How are block ciphers used to encrypt data
longer than the block size?
5.6. Can symmetric block ciphers be used for
message authentication?
5.7. What exactly is DES?
5.8. What is triple DES?
5.9. What is differential cryptanalysis?
5.10. How was NSA involved in the design of DES?
5.11. Is DES available in software?
5.12. Is DES available in hardware?
5.13. Can DES be used to protect classified
information?
5.14. What are ECB, CBC, CFB, OFB, and PCBC
encryption?
5.1. What is a
product cipher?
A product cipher is a block cipher that iterates several
weak operations such as substitution, transposition, modular
addition/multiplication, and linear transformation. (A ``block
cipher'' just means a cipher that encrypts a block of data---8
bytes, say---all at once, then goes on to the next block.) The
notion of product ciphers is due to Shannon [SHA49]. Examples of
modern product ciphers include LUCIFER [SOR84], DES [NBS77],
SP-networks [KAM78], LOKI [BRO90], FEAL [SHI84], PES [LAI90], Khufu
and Khafre [ME91a]. The so-called Feistel ciphers are a class of
product ciphers which operate on one half of the ciphertext at each
round, and then swap the ciphertext halves after each round.
LUCIFER, DES, LOKI, and FEAL are examples of Feistel ciphers.
The following table compares the main parameters of several
product ciphers:
cipher |
block length | key bits | number of rounds
LUCIFER 128 128 16
DES 64 56 16
LOKI 64 64 16
FEAL 64 128
2^x, x >= 5
PES 64 128 8
5.2. What
makes a product cipher secure?
Nobody knows how to prove mathematically that a product
cipher is completely secure. So in practice one begins by
demonstrating that the cipher ``looks highly random''. For example,
the cipher must be nonlinear, and it must produce ciphertext which
functionally depends on every bit of the plaintext and the key.
Meyer [MEY78] has shown that at least 5 rounds of DES are required
to guarantee such a dependence. In this sense a product cipher
should act as a ``mixing'' function which combines the plaintext,
key, and ciphertext in a complex nonlinear fashion.
The fixed per-round substitutions of the product cipher are
referred to as S-boxes. For example, LUCIFER has 2 S-boxes, and DES
has 8 S-boxes. The nonlinearity of a product cipher reduces to a
careful design of these S-boxes. A list of partial design criteria
for the S-boxes of DES, which apply to S-boxes in general, may be
found in Brown [BRO89] and Brickell et al. [BRI86].
5.3. What are
some group-theoretic properties of product ciphers?
Let E be a product cipher that maps N-bit blocks to N-bit
blocks. Let E_K(X) be the encryption of X under key K. Then, for
any fixed K, the map sending X to E_K(X) is a permutation of the set
of N-bit blocks. Denote this permutation by P_K. The set of all
N-bit permutations is called the symmetric group and is written
S_{2^N}. The collection of all these permutations P_K, where K
ranges over all possible keys, is denoted E(S_{2^N}). If E were a
random mapping from plaintexts to ciphertexts then we would expect
E(S_{2^N}) to generate a large subset of S_{2^N}.
Coppersmith and Grossman [COP74] have shown that a very
simple product cipher can generate the alternating group A_{2^N}
given a sufficient number of rounds. (The alternating group is half
of the symmetric group: it consists of all ``even'' permutations,
i.e., all permutations which can be written as an even number of
swaps.) Even and Goldreich [EVE83] were able to extend these results
to show that Feistel ciphers can generate A_{2^N}, given a
sufficient number of rounds.
The security of multiple encipherment also depends on the
group-theoretic properties of a cipher. Multiple encipherment is an
extension over single encipherment if for keys K1, K2 there does not
exist a third key K3 such that
E_K2(E_K1(X)) == E_(K3)(X)(**)
which indicates that encrypting twice with two independent
keys K1, K2 is equal to a single encryption under the third key K3.
If for every K1, K2 there exists a K3 such that eq. (**) is true
then we say that E is a group.
This question of whether DES is a group under this
definition was extensively studied by Sherman, Kaliski, and Rivest
[SHE88]. In their paper they give strong evidence for the hypothesis
that DES is not a group. In fact DES is not a group [CAM93].
5.4. What can
be proven about the security of a product cipher?
Recall from above that P_K is a permutation produced by E
under some key K. The goal of the designer of E is to ensure that
P_K appears to be a random element of S_{2^N}, the symmetric group.
Let R be an element of S_{2^N} selected randomly. We will say that
P_K and R are indistinguishable if an observer given P_K and R in
some order cannot distinguish between these two permutations in
polynomial time. That is, with time bounded resources, the observer
cannot determine which of the permutations is produced by E: the
optimal decision is no better than simply guessing.
Luby and Rackoff [LUB88] have shown that a class of Feistel
ciphers are secure in this sense when the round mapping is replaced
by random boolean functions.
5.5. How are
block ciphers used to encrypt data longer than the block size?
There are four standard ``modes of operation'' (and
numerous non-standard ones as well). The standard modes of
operation are defined in the U.S. Department of Commerce Federal
Information Processing Standard (FIPS) 81, published in 1980. See
the question about ECB below for more details.
Although they are defined for the DES block cipher, the
``modes of operation'' can be used with any block cipher.
5.6. Can
symmetric block ciphers be used for message authentication?
You may use a symmetric cryptosystem block cipher to prove
to yourself that you generated a message, and that the message
wasn't altered after you created it. But you cannot prove these
things to anyone else without revealing your key. Thereafter you
cannot prove anything about messages authenticated with that key.
See ANSI X3.106-1983 and FIPS 113 (1985) for a standard
method of message authentication using DES.
5.7. What
exactly is DES?
DES is the U.S. Government's Data Encryption Standard, a
product cipher that operates on 64-bit blocks of data, using a
56-bit key.
It is defined in FIPS 46-1 (1988) [which supersedes FIPS 46
(1977)]. FIPS are Federal Information Processing Standards
published by NTIS. DES is identical to the ANSI standard Data
Encryption Algorithm (DEA) defined in ANSI X3.92-1981.
5.8. What is
triple DES?
Triple DES is a product cipher which, like DES, operates on
64-bit data blocks. There are several forms, each of which uses the
DES cipher 3 times. Some forms use two 56-bit keys, some use three.
The DES ``modes of operation'' may also be used with triple-DES.
Some people refer to E(K1,D(K2,E(K1,x))) as triple-DES.
This method is defined in chapter 7.2 of the ANSI standard
X9.17-1985 ``Financial Institution Key Management'' and is intended
for use in encrypting DES keys and IVs for ``Automated Key
Distribution''. Its formal name is ``Encryption and Decryption of a
Single Key by a Key Pair'', but it is referenced in other standards
documents as EDE.
That standard says (section 7.2.1): ``Key encrypting keys
may be a single DEA key or a DEA key pair. Key pairs shoud be used
where additional security is needed (e.g., the data protected by the
key(s) has a long security life). A key pair shall not be encrypted
or decrypted using a single key.''
Others use the t |