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

2004-04-06 Thread Zefram
R. A. Hettinga wrote:
   In practice you'll probably find something that you can alter in
the last few hundred KB but still the raw processing cost will be a few
orders of magnitude harder than a simple hash collision problem.
[etc.]

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

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


Re: yahoo to use public key technology for anti-spam

2003-12-09 Thread Zefram
[EMAIL PROTECTED] wrote:
Does anybody know what has become of the low-tech,
no-cryptography-needed RMX DNS record entry proposal?

It seems to still exist -- draft-danisch-dns-rr-smtp-03 is dated 2003-10
-- though it should have been abandoned long ago in favour of similar but
superior proposals.  draft-fecyk-dmp (formerly draft-fecyk-dsprotocol),
which has almost identical capabilities, is also still in active
development.  There's also a more flexible version of the idea, which
I skimmed through when it was announced and now can't recall the name of.

-zefram

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