home *** CD-ROM | disk | FTP | other *** search
/ ftp.pasteur.org/FAQ/ / ftp-pasteur-org-FAQ.zip / FAQ / cryptography-faq / part04 < prev    next >
Encoding:
Internet Message Format  |  2003-03-20  |  11.1 KB

  1. Path: senator-bedfellow.mit.edu!dreaderd!not-for-mail
  2. Message-ID: <cryptography-faq/part04_1048071134@rtfm.mit.edu>
  3. Supersedes: <cryptography-faq/part04_1046174591@rtfm.mit.edu>
  4. Expires: 23 Apr 2003 10:52:14 GMT
  5. References: <cryptography-faq/part01_1048071134@rtfm.mit.edu>
  6. X-Last-Updated: 1994/07/05
  7. Newsgroups: sci.crypt,talk.politics.crypto,sci.answers,news.answers,talk.answers
  8. Subject: Cryptography FAQ (04/10: Mathematical Cryptology)
  9. Approved: news-answers-request@MIT.Edu
  10. Followup-To: poster
  11. From: crypt-comments@math.ncsu.edu
  12. Organization: The Crypt Cabal
  13. Reply-To: crypt-comments@math.ncsu.edu
  14. Originator: faqserv@penguin-lust.MIT.EDU
  15. Date: 19 Mar 2003 10:52:36 GMT
  16. Lines: 210
  17. NNTP-Posting-Host: penguin-lust.mit.edu
  18. X-Trace: 1048071156 senator-bedfellow.mit.edu 3937 18.181.0.29
  19. Xref: senator-bedfellow.mit.edu sci.crypt:233108 talk.politics.crypto:46669 sci.answers:15076 news.answers:248028 talk.answers:6515
  20.  
  21. Archive-name: cryptography-faq/part04
  22. Last-modified: 93/10/10
  23.  
  24. This is the fourth of ten parts of the sci.crypt FAQ. The parts are
  25. mostly independent, but you should read the first part before the rest.
  26. We don't have the time to send out missing parts by mail, so don't ask.
  27. Notes such as ``[KAH67]'' refer to the reference list in the last part.
  28.  
  29. The sections of this FAQ are available via anonymous FTP to rtfm.mit.edu 
  30. as /pub/usenet/news.answers/cryptography-faq/part[xx]. The Cryptography 
  31. FAQ is posted to the newsgroups sci.crypt, talk.politics.crypto, 
  32. sci.answers, and news.answers every 21 days.
  33.  
  34.  
  35.  
  36. Contents:
  37.  
  38. 4.1. In mathematical terms, what is a private-key cryptosystem?
  39. 4.2. What is an attack?
  40. 4.3. What's the advantage of formulating all this mathematically?
  41. 4.4. Why is the one-time pad secure?
  42. 4.5. What's a ciphertext-only attack?
  43. 4.6. What's a known-plaintext attack?
  44. 4.7. What's a chosen-plaintext attack?
  45. 4.8. In mathematical terms, what can you say about brute-force attacks?
  46. 4.9. What's a key-guessing attack? What's entropy?
  47.  
  48.  
  49. Reader, beware: This section is highly mathematical. Well, maybe not
  50. _highly_ mathematical, but it's got a bunch of symbols and scary-looking
  51. formulas. You have been warned.
  52.  
  53.  
  54. 4.1. In mathematical terms, what is a private-key cryptosystem?
  55.  
  56.   A private-key cryptosystem consists of an encryption system E and a
  57.   decryption system D. The encryption system E is a collection of
  58.   functions E_K, indexed by ``keys'' K, mapping some set of
  59.   ``plaintexts'' P to some set of ``ciphertexts'' C. Similarly the
  60.   decryption system D is a collection of functions D_K such that
  61.   D_K(E_K(P)) = P for every plaintext P. That is, succesful decryption
  62.   of ciphertext into plaintext is accomplished using the same key
  63.   (index) as was used for the corresponding encryption of plaintext
  64.   into ciphertext. Such systems, where the same key value is used to
  65.   encrypt and decrypt, are also known as ``symmetric'' cryptoystems.
  66.  
  67. 4.2. What is an attack?
  68.  
  69.   In intuitive terms a (passive) attack on a cryptosystem is any method
  70.   of starting with some information about plaintexts and their
  71.   corresponding ciphertexts under some (unknown) key, and figuring out
  72.   more information about the plaintexts. It's possible to state
  73.   mathematically what this means. Here we go.
  74.  
  75.   Fix functions F, G, and H of n variables. Fix an encryption system E,
  76.   and fix a distribution of plaintexts and keys.
  77.  
  78.   An attack on E using G assuming F giving H with probability p is an
  79.   algorithm A with a pair f, g of inputs and one output h, such that
  80.   there is probability p of computing h = H(P_1,...,P_n), if we have
  81.   f = F(P_1,...,P_n) and g = G(E_K(P_1),...,E_K(P_n)). Note that this
  82.   probability depends on the distribution of the vector (K,P_1,...,P_n).
  83.  
  84.   The attack is trivial (or ``pointless'') if there is probability at
  85.   least p of computing h = H(P_1,...,P_n) if f = F(P_1,...,P_n) and
  86.   g = G(C_1,...,C_n). Here C_1,...,C_n range uniformly over the possible
  87.   ciphertexts, and have no particular relation to P_1,...,P_n. In other
  88.   words, an attack is trivial if it doesn't actually use the encryptions
  89.   E_K(P_1),...,E_K(P_n).
  90.  
  91.   An attack is called ``one-ciphertext'' if n = 1, ``two-ciphertext'' if
  92.   n = 2, and so on.
  93.  
  94. 4.3. What's the advantage of formulating all this mathematically?
  95.  
  96.   In basic cryptology you can never prove that a cryptosystem is secure.
  97.   Read part 3: we keep saying ``a strong cryptosystem must have this
  98.   property, but having this property is no guarantee that a cryptosystem
  99.   is strong!''
  100.  
  101.   In contrast, the purpose of mathematical cryptology is to precisely
  102.   formulate and, if possible, prove the statement that a cryptosystem is
  103.   strong. We say, for example, that a cryptosystem is secure against
  104.   all (passive) attacks if any nontrivial attack against the system (as
  105.   defined above) is too slow to be practical. If we can prove this
  106.   statement then we have confidence that our cryptosystem will resist
  107.   any (passive) cryptanalytic technique. If we can reduce this statement
  108.   to some well-known unsolved problem then we still have confidence that
  109.   the cryptosystem isn't easy to break.
  110.  
  111.   Other parts of cryptology are also amenable to mathematical
  112.   definition. Again the point is to explicitly identify what assumptions
  113.   we're making and prove that they produce the desired results. We can
  114.   figure out what it means for a particular cryptosystem to be used
  115.   properly: it just means that the assumptions are valid.
  116.  
  117.   The same methodology is useful for cryptanalysis too. The cryptanalyst
  118.   can take advantage of incorrect assumptions. Often he can try to
  119.   construct a proof of security for a system, see where the proof fails,
  120.   and use these failures as the starting points for his analysis.
  121.   
  122. 4.4. Why is the one-time pad secure?
  123.  
  124.   By definition, the one-time pad is a cryptosystem where the
  125.   plaintexts, ciphertexts, and keys are all strings (say byte strings)
  126.   of some length m, and E_K(P) is just the sum (let's say the exclusive
  127.   or) of K and P.
  128.  
  129.   It is easy to prove mathematically that there are _no_ nontrivial
  130.   single-ciphertext attacks on the one-time pad, assuming a uniform
  131.   distribution of keys. Note that we don't have to assume a uniform
  132.   distribution of plaintexts. (Here's the proof: Let A be an attack,
  133.   i.e., an algorithm taking two inputs f, g and producing one output h,
  134.   with some probability p that h = H(P) whenever f = F(P) and
  135.   g = G(E_K(P)) (i.e., g = G(K + P)). Then, because the distribution of
  136.   K is uniform and independent of P, the distribution of K + P must also
  137.   be uniform and independent of P. But also the distribution of C is
  138.   uniform and independent of P. Hence there is probability exactly p
  139.   that h = H(P) whenever f = F(P) and g = G(C), over all P and C. Thus
  140.   a fortiori A is trivial.)
  141.  
  142.   On the other hand the one-time pad is _not_ secure if a key K is used
  143.   for more than one plaintext: i.e., there are nontrivial
  144.   multiple-ciphertext attacks. So to be properly used a key K must be
  145.   thrown away after one encryption. The key is also called a ``pad'';
  146.   this explains the name ``one-time pad.''
  147.  
  148.   Also, a computer-based pseudo-random number generator does _not_ 
  149.   qualify as a true one-time pad because of its deterministic 
  150.   properties. See `pseudo-random number generators as key stream'.
  151.  
  152. 4.5. What's a ciphertext-only attack?
  153.  
  154.   In the notation above, a ciphertext-only attack is one where F is
  155.   constant. Given only some information G(E_K(P_1),...,E_K(P_n)) about
  156.   n ciphertexts, the attack has to have some chance of producing some
  157.   information H(P_1,...,P_n) about the plaintexts. The attack is trivial
  158.   if it has just as good a chance of producing H(P_1,...,P_n) when given
  159.   G(C_1,...,C_n) for random C_1,...,C_n.
  160.  
  161.   For example, say G(C) = C, and say H(P) is the first bit of P. We can
  162.   easily write down an attack---the ``guessing attack,'' which simply
  163.   guesses that H(P) is 1. This attack is trivial because it doesn't use
  164.   the ciphertext: it has a fifty-fifty chance of guessing correctly no
  165.   matter what. On the other hand there is an attack on RSA which
  166.   produces one bit of information about P, with 100% success, using C.
  167.   If it is fed a random C then the success rate drops to 50%. So this is
  168.   a nontrivial attack.
  169.  
  170. 4.6. What's a known-plaintext attack?
  171.  
  172.   The classic known-plaintext attack has F(P_1,P_2) = P_1,
  173.   G(C_1,C_2) = (C_1,C_2), and H(P_1,P_2) depending only on P_2.
  174.   In other words, given two ciphertexts C_1 and C_2 and one decryption
  175.   P_1, the known-plaintext attack should produce information about the
  176.   other decryption P_2.
  177.  
  178.   Note that known-plaintext attacks are often defined in the literature
  179.   as producing information about the key, but this is pointless: the
  180.   cryptanalyst generally cares about the key only insofar as it lets him
  181.   decrypt further messages.
  182.  
  183. 4.7. What's a chosen-plaintext attack?
  184.  
  185.   A chosen-plaintext attack is the first of an increasingly impractical
  186.   series of _active_ attacks on a cryptosystem: attacks where the
  187.   cryptanalyst feeds data to the encryptor. These attacks don't fit into
  188.   our model of passive attacks explained above. Anyway, a
  189.   chosen-plaintext attack lets the cryptanalyst choose a plaintext and
  190.   look at the corresponding ciphertext, then repeat until he has figured
  191.   out how to decrypt any message. More absurd examples of this sort of
  192.   attack are the ``chosen-key attack'' and ``chosen-system attack.''
  193.  
  194.   A much more important form of active attack is a message corruption
  195.   attack, where the attacker tries to change the ciphertext in such a
  196.   way as to make a useful change in the plaintext.
  197.  
  198.   There are many easy ways to throw kinks into all of these attacks:
  199.   for instance, automatically encrypting any plaintext P as
  200.   T,E_K(h(T+R+P),R,P), where T is a time-key (sequence number) chosen anew
  201.   for each message, R is a random number, and h is a one-way hash
  202.   function. Here comma means concatenation and plus means exclusive-or.
  203.  
  204. 4.8. In mathematical terms, what can you say about brute-force attacks?
  205.  
  206.   Consider the following known-plaintext attack. We are given some
  207.   plaintexts P_1,...,P_{n-1} and ciphertexts C_1,...,C_{n-1}. We're
  208.   also given a ciphertext C_n. We run through every key K. When we find
  209.   K such that E_K(P_i) = C_i for every i < n, we print D_K(C_n).
  210.  
  211.   If n is big enough that only one key works, this attack will succeed
  212.   on valid inputs all the time, while it will produce correct results
  213.   only once in a blue moon for random inputs. Thus this is a nontrivial
  214.   attack. Its only problem is that it is very slow if there are many
  215.   possible keys.
  216.  
  217. 4.9. What's a key-guessing attack? What's entropy?
  218.  
  219.   Say somebody is using the one-time pad---but isn't choosing keys
  220.   randomly and uniformly from all m-bit messages, as he was supposed to
  221.   for our security proof. In fact say he's known to prefer keys which
  222.   are English words. Then a cryptanalyst can run through all English
  223.   words as possible keys. This attack will often succeed, and it's much
  224.   faster than a brute-force search of the entire keyspace.
  225.  
  226.   We can measure how bad a key distribution is by calculating its
  227.   entropy. This number E is the number of ``real bits of information''
  228.   of the key: a cryptanalyst will typically happen across the key within
  229.   2^E guesses. E is defined as the sum of -p_K log_2 p_K, where p_K is
  230.   the probability of key K.
  231.