[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
Re: key-ed MD5 again
> It's easy to check that F(N) does approach 0 for large N, but extremely
> slowly. In fact,
>
> F(N) ~= 2 / (N + log terms).
>
> In the case at hand, suppose the VeryLongText above is 1 MB. This is
> 15,625 blocks of 64bytes; if we feed those to MD5 one block at a time,
> the expected size of the range is diminished by a factor of 15625/2,
> or about 8000. In other words, we've lost 13 bits of the original 128
> bits in the initial state of MD5. If VeryLongText is 1 GB, the same
> calculation shows we'll lose 23 bits.
It should also be noted that calculation of MD5 of long messages
take a longer time, even if the differences between messages
lies only in the initial 64bytes.
So, to explore the accidental match in 120bit MD5 space of 1MB message
takes 15,625/(sqrt(8,000)) more times than exploring the 128 bit
space for 64bit message.
That is, the initial part of longer messages is safer than that of short
messages, I think.
Is it well known, or do I misunderstand something?
Masataka Ohta