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

[Ethan Blanton]

Jack Lloyd spake unto us the following wisdom:
> On Tue, Jul 18, 2006 at 06:39:49PM -0700, Zack Weinberg wrote:
> > Perhaps I only say this because I am not a cryptographer at all, but
> > it seems to me that the collision probability results might depend on
> > the assumption that both sides of the potential collision are in fact
> > SHA of some text.  In which case, maybe a bitstream generated by
> > pounding on the keyboard is more likely to collide.
> 
> Nor am I, but I believe the collision probabilities are the same, _if_
> you assume that SHA-1 and your PRNG are both good (ie, behave like a
> random function). However, that adds a second assumption (good PRNG)
> that did not exist before.

For a good cryptographic hash, a = H(b) for every possible a and b
should have the same probability, as far as you or I are concerned.

> SHA-1(a) == SHA-1(b) -> SHA-1 collision found -> weakness in SHA
> 
> a == SHA-1(b) -> Maybe a problem in the RNG, maybe a problem in SHA... maybe
>                  just a strange interaction between the two that you didn't
>                  expect.

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.  ;-)

Ethan

-- 
The laws that forbid the carrying of arms are laws [that have no remedy
for evils].  They disarm only those who are neither inclined nor
determined to commit crimes.
                -- Cesare Beccaria, "On Crimes and Punishments", 1764

signature.asc
Description: Digital signature