RE: Lockless file reading

[David Schwartz]

> In article <MDEHLPKNGKAHNMBLJOLKEEEEFMAA.davids@xxxxxxxxxxxxx> you wrote:

> > Find those GIFs, double-check, and publish immediately.
> > That would be
> > amazingly big news and would probably cause huge numbers of
> > people to switch
> > from MD5 to SHA1 overnight.

> Why is that?

	Because the security of a hash is based upon it being impractical to find
collisions. If you could demonstrate that you could find even a single
collision (by actually doing it), that would reduce confidence in MD5
massively.

> For a hash with n bits there are at least
> 2^y / 2^n = 2^(y-n) files with the same hash, if they have size y bits.
> Three are even more, if you consider all files up to this size.
>
> With n=128 (md5) and y=80000 (10k file) x=2^79872 different files
> with the same
> hash, which is:
[snip]

	So what? You can, in principle, break a 4096-bit RSA key just by brute
force factorization. The security is based upon the difficulty of actually
doing it in practice. The simplicity of doing it in theory is irrelevent.
Yes, in theory you can break any public key encryption scheme or any hash
digest algrithm by brute force trial and error. In practice, however your
children's, children's, children's, children would be long dead before you
got 1% of the way there.

	To date, no full MD5 collisions have been published and until earlier in
this thread, nobody even claimed to have one. And I'll bet $100 to $1 that
the claimant is in error, either because he used only part of the hash or a
hash of the hash, mis-implementing the hash, o actually hashed the same data
twice without realizing it.

	DS


-
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majordomo@xxxxxxxxxxxxxxx
More majordomo info at  http://vger.kernel.org/majordomo-info.html
Please read the FAQ at  http://www.tux.org/lkml/