Re: [Monotone-devel] Re: RFC: Fake IDs

[Jack Lloyd]

On Tue, Jul 18, 2006 at 11:01:32PM -0400, Ethan Blanton wrote:

> If you can find an RNG such that a = SHA-1(b) in any predictable
> fashion, drop me a line and we'll write a paper ... and then get
> moderately famous.  ;-)

That was very sloppy of me. Should have been clear that the SHA(foo)
implied that foo was something in Monotone database. For which an RNG
having bad interactions is (AFICT) trivial:

X = { set of all versions of all source code files ever created }
 (or all valid C source files less than a certain size, or whatever)

RNG:
  choose x \in X at random
  output SHA(x)

Seems like this would meet any reasonable definition of strong random
number generator (at least up to the limits of SHA-1 itself), and yet
might have a substantially higher collision rate with a set of
Monotone content hashes than 1/2^80.

But, of course, IANAC so if I'm going wrong here corrections are
certainly welcome.

-Jack