[Mac_crypto] Apple should use SHA! (or stronger) to authenticate software releases

[Nicko van Someren]

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.

	Nicko

---------------------------------------------------------------------
The Cryptography Mailing List
Unsubscribe by sending "unsubscribe cryptography" to majordomo at metzdowd.com