Defensive programming

[Chuck Swiger]

Paul Miller wrote:
[ ... ]
> What in the world are collision resistant hashes?

The following (from the manpage for "/dev/random") provides a pretty good 
description of a specific implementation of a collision-resistant hash.

This is used to generate randomized TCP sequence numbers, syncache cookies, and 
other low-level network details to avoid or mitigate against certain attacks 
(like "man-in-the-middle", where the attacker guesses the next TCP sequence 
number for someone else's connection):

"    Sources of randomness from the environment include inter-keyboard tim-
      ings, inter-interrupt timings from some interrupts, and other events
      which are both (a) non-deterministic and (b) hard for an outside observer
      to measure.  Randomness from these sources are added to an "entropy
      pool", which is periodically mixed using the MD5 compression function in
      CBC mode.  As random bytes are mixed into the entropy pool, the routines
      keep an estimate of how many bits of randomness have been stored into the
      random number generator's internal state.

      When random bytes are desired, they are obtained by taking the MD5 hash
      of a counter plus the contents of the "entropy pool".  The reason for the
      MD5 hash is so that we can avoid exposing the internal state of random
      number generator.  Although the MD5 hash does protect the pool, each ran-
      dom byte which is generated from the pool reveals some information which
      was derived from the internal state, and thus increases the amount of
      information an outside attacker has available to try to make some guesses
      about the random number generator's internal state.  For this reason, the
      routine decreases its internal estimate of how many bits of "true random-
      ness" are contained in the entropy pool as it outputs random numbers.

      If this estimate goes to zero, the routine can still generate random num-
      bers; however it may now be possible for an attacker to analyze the out-
      put of the random number generator, and the MD5 algorithm, and thus have
      some success in guessing the output of the routine.  Phil Karn (who
      devised this mechanism of using MD5 plus a counter to extract random num-
      bers from an entropy pool) calls this "practical randomness", since in
      the worst case this is equivalent to hashing MD5 with a counter and an
      undisclosed secret.  If MD5 is a strong cryptographic hash, this should
      be fairly resistant to attack."

-Chuck