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

[Nathaniel Smith]

On Wed, Jul 19, 2006 at 01:16:43AM -0400, Jack Lloyd wrote:
> 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.

Right, this is an easy counterexample.  What you need, though, is some
function _that is blind to the content we are worried about colliding
with_ that still has a non-trivial probability of collision.  The
situation under discussion is whether there is a danger that the
string "0000000000000000000000000000000000000000" hard-coded into the
source has a danger of colliding with any real hash, not whether some
sneaky evil function could be constructed.  (And even so... that
construction is pretty darn fragile.  If you make the final stage of
the RNG "output SHA(x + one null byte)" instead, then suddenly it
becomes entirely random again, wrt content hashes :-).)

-- Nathaniel

-- 
.i dei jitfa fanmo xatra