On Wed, Nov 16, 2005 at 02:09:24AM +0200, Oded Arbel wrote: > On Tuesday, 15 בNovember 2005 20:55, Lionel Elie Mamane wrote:
>> 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. > Actually, 2^63 last time I checked (5 minutes ago). Yes, that "3" there was covered by the "about" :-) > So that shaves about 2^17 from our result which brings the total of > time down to 200 thusand years. Err... No. The scenario you were giving was about *accidental* collision, wasn't it? Accidental collision isn't touched by the fact that one can do it on purpose to create a collision with less work. So it is still 10 billion years. If we are discussing someone doing this on purpose, then we must ask how much time he would need to generate a collision. And he can do much more than one SHA-1 hash per second. Works of the size of 2^64 are on the scale of possibility of well-funded organisations (IBM, SCO, governments) or even large scale cooperating volunteer organisations: distributed.net has broken by brute-force 64 bit ciphers with DONATED computing power. And it doesn't even have to cost a lot. If you have a lot of computers (because you have a lot of employees, and one computer per employee), then you can run a background low-priority job on every computer of every employee and you have the equivalent of a (or several?) super-computer(s) at your disposition. Anyway, my computer can do about 2*10^6 SHA-1 hashes per second. Even my very old Celeron (who must do something like 500MHz) can do 300,000/s. So let's say 10^6 for an "average" computer nowadays. Let's say you have 100,000 employees worldwide. You can thus do 10^11 SHA-1's per second, or about ... 2^36.5 SHA-1's per second. Currently, you thus need about 2^26.5 s to generate a collision, that is three years. And that's if the attack is not improved mathematically in this time frame. >> 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. > That's funky - I didn't know that. For the purpose of fooling kernel > developers, you'd still need to have both A and B at least looking > like C code or maybe even compiling, which I suspect would be quite > a problem. Compiling is easy, you just choose M and S so that A/B is in a comment C-code wise. Having A and B look reasonable to the human eye is a different story altogether :) -- 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]
