On Tue, Nov 15, 2005 at 06:42:23PM +0200, Oded Arbel wrote:
> On Tuesday, 15 בNovember 2005 18:14, Baruch Even wrote:
>> Omer Zak wrote:
>>> THE QUESTION:
>>> According to the above git README, objects in git are named by
>>> their SHA1 hashes. So, what happens if two objects have the same
>>> SHA1 hash, unlikely as it might be?
>> The world ends.
>> I haven't checked for a long time now but I don't think there is any
>> safeguard for such a case.
>
> Actually, AFAIK, there is such a safe guard - The Laws of Mathematics.
> Which clearly describe the mind boggling improbability of such a
> case.
> A simple (and completely inaccurate) example would go something like
> this: Suppose for a second that a million kernel hackers would
> labour day and night to produce one random file each, every
> second.
So about 2^20 files per second.
> Such a horde would take over 4 decillion years (million
> billion billion billion years) to produce such a collision.
They'd take about 2^60 seconds. That is about 10^18 seconds. There are
about 3*10^7 s to a year, so they'd take about 3*10^10 years, so
"merely" 10 billion years.
Looks like you are confusing collision resistance and second preimage
resistance (or preimage resistance).
> (*) I know there was some talk about colliding SHA1 ("breaking" it), but
> at best that would reduce the key size to be collided to 80 bit
> (IIRC)
No. 80 bits of "anniversary" collision resistance is the _design_
strength of SHA-1. Breaking it is making collisions with less work
than that (2^80 SHA-1 hashings). What has _already_ happened is that
methods for collision construction in about 2^60 hashings have been
found, and are likely to be improved upon.
> which is still huge and in any way it only makes sense for very
> short data chunks - no where near the complexity of a run of the
> mill kernel source file.
No. Due to the way SHA-1 works (treating chunks of data in a greedy
manner, which makes it vulnerable to length-extension attacks), once
you have created a collision for small blocks A and B, you can:
- choose a prefix M freely (the size must be congruent to a constant
modulo another constant)
- concatenate A and B, respectively
- choose a suffix S freely
And then MAS and MBS have same SHA-1 hash. So as big blocks as you
want.
--
Lionel
=================================================================
To unsubscribe, send mail to [EMAIL PROTECTED] with
the word "unsubscribe" in the message body, e.g., run the command
echo unsubscribe | mail [EMAIL PROTECTED]
