Subject: Re: kcrypto vs randomness

From: Don Davis <[email-masked]>
Date: Fri, 19 Sep 2003 17:41:13 -0400

> To: [email-masked]
> Subject: kcrypto vs randomness
> From: Simon Josefsson <[email-masked]>
> Date: Fri, 19 Sep 2003 01:05:25 +0200
>
> Hello,
>
> while studying IV carry in AES-CTS, I noticed that
> several times, but draft-ietf-krb-wg-crypto-05 uses
> the word "random" never discuss random number quality
> (nor reference RFC 1750).
>
> Specifically: must the confounder be a cryptographically
> strong random number?
>
> If yes, I think a warning in the security consideration
> of kcrypto is warranted, that the entropy source may be
> exhausted quickly if the encryption scheme is used
> frequently.  Compare, e.g., Kerberos 5 'rsh' that would
> waste 8 bytes of entropy for every character you type.
>
> If no, it would be good to make that 'no' explicit, so
> that people aren't forced to use strong random numbers
> as a conservative measure, just because the specification
> is unclear.

[please copy me explicitly on any replies or commentary,
because i don't subscribe to the list].

the confounder doesn't need to be truly random, nor even 
cryptographically random.  here's what _is_ necessary in 
a confounder generator:

   * if the generator repeats itself periodically,
     then the period should be very long, so that
     each confounder-&-message combination is 
     effectively unique.
   * similarly, similar bitstrings should be widely
     separated from one another, in the generator's
     output-sequence.   more precisely, it's bad if
     the Hamming distance between successive confoun-
     ders is small, as happens with a counter.  (the
     Hamming distance between two strings is the number
     of bitwise  differences between the strings.) 

in practice, a fast & weak PRNG can produce good confoun-
ders, as long as the PRNG has good-enough statistical
properties.  the classic linear-congruential generator
isn't good enough, because it has a short period, and
also because its low- order bits repeat very frequently.
marsaglia's multiply- with-carry rng is just about as
fast as the LCG, but has a long period and much better
statistical behavior.  so, MWC with well-chosen parameters
is fine for generating confounders.

the confounder serves much the same purpose as an IV;
both act as random message-padding, serving to mix with
a stereotyped message in a plaintext-driven cipher.
the main difference is that a confounder appears as
part of a message block, while an IV is a dummy message-
block, all by itself.  accordingly, steve bellovin's
critique of excessively non-random confounders applies
to confounders, just much as to IVs:

     "The problem arises if you use a counter as an IV,
      or some other source with a low Hamming distance
      between successive IVs, for encryption in CBC mode.
      ... If the IV doesn't differ much from the previous
      IV, and the actual plaintext block doesn't differ
      much from the previous packet's, then the effective
      plaintext won't differ much, either.  This meanse
      that you have pairs of ciphertext blocks combined
      with plaintext blocks that differ in just a few bit
      positions.  This can be a wedge for assorted crypt-
      analytic attacks."   [from rfc 2405, p. 5]

here are some pertinent quotes from the draft, explaining
why the draft stipulates use of a confounder: 

page 2:
   Use of a random confounder prepended to the plaintext
   is recommended.  It should not be possible to determine
   if two ciphertexts correspond to the same plaintext,
   without knowledge of the key.

page 7:
   encrypt (specific-key, state, octet string)->(state, octet string)
      ...Some random factor such as a confounder should be
      included so that an observer cannot know if two messages
      contain the same plaintext, even if the cipher state and
      specific keys are the same.

page 12:
   encryption/decryption functions, E and D
      ...
      The encryption function is not required to use CBC
      mode, but is assumed to be using something with similar
      properties.  In particular, prepending a cipher-block-
      size confounder to the plaintext should alter the entire
      ciphertext (comparable to choosing and including a random
      initial vector for CBC mode).

page 34-5:
   The use of a random confounder is an important means of
   preventing an attacker from making effective use of protocol
   exchanges as an encryption oracle.  In Kerberos version 4,
   the encryption of constant plaintext to constant ciphertext
   makes an effective encryption oracle for an attacker.  The
   use of random confounders in [Kerb1510] frustrates this sort
   of chosen-plaintext attack.

page 43:
      Also, the
      prepended confounder in the existing algorithms is roughly
      equivalent to a per-message initialization vector that is
      revealed in encrypted form.

						- don davis

-

---

From: Sam Hartman <[email-masked]>
Date: Sun, 21 Sep 2003 17:51:14 -0400

>>>>> "Don" == Don Davis <[email-masked]> writes:

    Don> [please copy me explicitly on any replies or commentary,
    Don> because i don't subscribe to the list].

    Don> the confounder doesn't need to be truly random, nor even
    Don> cryptographically random.  here's what _is_ necessary in a
    Don> confounder generator:

    Don>    * if the generator repeats itself periodically, then the
    Don> period should be very long, so that each confounder-&-message
    Don> combination is effectively unique.  * similarly, similar
    Don> bitstrings should be widely separated from one another, in
    Don> the generator's output-sequence.  more precisely, it's bad if
    Don> the Hamming distance between successive confoun- ders is
    Don> small, as happens with a counter.  (the Hamming distance
    Don> between two strings is the number of bitwise differences
    Don> between the strings.)

Why is the second constraint true for an ideal block cipher?

If it is not true for an ideal block cipher but is true for practical
block ciphers, what attack is easier?