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

[Jack Lloyd]

On Tue, Jul 18, 2006 at 10:37:49PM -0700, Nathaniel Smith wrote:
> 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 :-).)

Hmmm... I am being very bad about stating my assumptions
tonight. Should probably not post here after having a beer... My
original post was WRT generating content hashes randomly (eg direct
output of a PRNG rather, than a counter or output of SHA), for which I
think my point applies.

While IANAC, I spend enough time reading crypto papers that I consider
"the RNG used is not this function, or one like it" to be a strong
assumption on the RNG - you can take a supposedly strong hash
function, a supposedly strong PRNG, use them together in Monotone (in
the sense of generating psuedo-content hashes from the PRNG) and end
up with major problems. I agree this is a somewhat academic /
non-real-world point (ie, this won't stop me from using Monotone), but
still I think it is a point that worth making - while my particular
example is obviously bizarre, it implies that there is a security
dependence on the PRNG beyond simply that it produce random bits.

-Jack