[Top][All Lists]
[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
Re: [Monotone-devel] Re: RFC: Fake IDs
From: |
Nathaniel Smith |
Subject: |
Re: [Monotone-devel] Re: RFC: Fake IDs |
Date: |
Tue, 18 Jul 2006 22:37:49 -0700 |
User-agent: |
Mutt/1.5.11+cvs20060403 |
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
- [Monotone-devel] RFC: Fake IDs, Zack Weinberg, 2006/07/18
- [Monotone-devel] Re: RFC: Fake IDs, Graydon Hoare, 2006/07/18
- Re: [Monotone-devel] Re: RFC: Fake IDs, Zack Weinberg, 2006/07/18
- Re: [Monotone-devel] Re: RFC: Fake IDs, Jack Lloyd, 2006/07/18
- Re: [Monotone-devel] Re: RFC: Fake IDs, Nathaniel Smith, 2006/07/18
- Re: [Monotone-devel] Re: RFC: Fake IDs, Zack Weinberg, 2006/07/18
- Re: [Monotone-devel] Re: RFC: Fake IDs, Jack Lloyd, 2006/07/18
- Re: [Monotone-devel] Re: RFC: Fake IDs, Ethan Blanton, 2006/07/18
- Re: [Monotone-devel] Re: RFC: Fake IDs, Jack Lloyd, 2006/07/19
- Re: [Monotone-devel] Re: RFC: Fake IDs,
Nathaniel Smith <=
- Re: [Monotone-devel] Re: RFC: Fake IDs, Zack Weinberg, 2006/07/19
- [Monotone-devel] Re: RFC: Fake IDs, Graydon Hoare, 2006/07/19
- Re: [Monotone-devel] Re: RFC: Fake IDs, Daniel Carosone, 2006/07/19
- Re: [Monotone-devel] Re: RFC: Fake IDs, Daniel Carosone, 2006/07/19
- Re: [Monotone-devel] Re: RFC: Fake IDs, Jack Lloyd, 2006/07/19
- [Monotone-devel] Re: RFC: Fake IDs, Graydon Hoare, 2006/07/18
- Re: [Monotone-devel] Re: RFC: Fake IDs, Zack Weinberg, 2006/07/18
- Re: [Monotone-devel] Re: RFC: Fake IDs, Nathaniel Smith, 2006/07/19
- [Monotone-devel] Re: RFC: Fake IDs, Graydon Hoare, 2006/07/19
- Re: [Monotone-devel] Re: RFC: Fake IDs, Nathaniel Smith, 2006/07/19