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

Nicko van Someren mac_crypto@vmeng.com
Wed, 7 Apr 2004 12:53:56 +0100

It's not clear to me that you need all this complexity.  All you need 
if to arrange that the attacker does not know exactly what will be 
signed until it has been signed.  So you append some randomness from a 
good random number source to the end of the file just before you sign 
it, and you're safe.


On 6 Apr 2004, at 16:43, R. A. Hettinga wrote:
> --- begin forwarded text
> Date: Tue, 6 Apr 2004 10:33:54 +0100
> To: "R. A. Hettinga" <rah@shipwright.com>
> Cc: cryptography@metzdowd.com
> Subject: Re: [Mac_crypto] Apple should use SHA! (or stronger) to
> authenticate software releases
> User-Agent: Mutt/1.3.28i
> From: Zefram <zefram@fysh.org>
> This disucssion suggests a simple countermeasure: put something at the
> beginning of the package that depends on all the significant content
> of the package.  For example, the first file in the archive could be
> a list of digests of individual files.  This means an attacker has to
> either process the entire archive in searching for a collision or find
> tweakable space not covered by the leading checksum file.
> Having such dead space (not trivially checksummed) is quite likely in
> an uncompressed archive.  For example, tar pads each file to an 
> integral
> multiple of its block size.  However, compression of the entire archive
> will make such space more difficult to arrange.
> A more extreme approach that removes that risk entirely is to take
> the digest of two concatenated copies of the package.  Precalculation
> can still be used to speed up the search for a collision, but the
> unoptimisable tail is now guaranteed to be at least as long as the
> entire package.  I see a couple of potentially useful variations on 
> this:
> 	0. publish Digest(Digest(Archive) || Archive)
> 		(similar to Digest(Archive || Archive))
> 	1. publish Digest(Archive || Tail) where Tail is large and public
> 		(increases difficulty by a fixed amount that depends on
> 		the length of Tail -- suitable for small packages)
> Are these approaches sound?  I'm a crypto-plumber, not a cryptographer.
> I'm wondering whether we can define a new type of cryptographic 
> primitive
> here: the non-precomputable message digest.  The interesting feature of
> an NPCMD would be that computing the digests of two related messages
> cannot be optimised to take any less time than the computation of the
> digests of two unrelated messages of the same sizes.  The suggestions
> I made above are clearly not NPCMDs, but if one does
> 	M[0] = M   ; original message
> 	M[i+1] = Digest(M[i]) || M[i]
> 	D = Digest(M[n])   ; final digest
> with Digest being a good conventional message digest, then this 
> appears to
> approach a NPCMD as n approaches infinity.  Of course, computation time
> for this construction is linear in n (for a particular message size),
> so this is not a practical way to achieve this goal.  Can a NPCMD be
> done in a more reasonable time?  I imagine structures that might lead
> to O(l*log(l)) time, where l is the message length, but that's just
> my speculation.
> -zefram
> --- end forwarded text