On 5 Apr 2004, at 23:43, Arnold G. Reinhold wrote:

Having a tail 2 MB or longer may make the processing time comparable to finding an SHA1 collision, but it is still a 64-bit problem and thus requires far less memory than finding an SHA1 collision.

Just because SHA-1 is O(2^80) and this problem is O(2^64) does NOT necessarily mean that this problem is easier in practice. Complexity orders are helpful for comparing like with like, and helpful when working out what's best in the limit as the sizes go up, but they give no immediate information about the absolute cost.

Incidentally, there are attacks on hash functions that do not require masses of memory. The amount of memory only determines how much effort you have to apply to find the exact solution once you've found where to look. In particular, changing the amount of memory does not change the O() order of the complexity!

Upon reflection, if the attacker can arrange the specific case in which the original and the bogus files are exactly the same length, and that all the information in the file after the part that the "tweakable" section is the the same in both files, then you can make use of the limited memory of the hash functions and look for collisions right after the tweakable part, which means you get to ignore the length of the tail of the file. In these circumstances the attack you describe is probably practical, at least for governments if not for Microsoft.


The Cryptography Mailing List
Unsubscribe by sending "unsubscribe cryptography" to [EMAIL PROTECTED]

Reply via email to