[56646] in cryptography@c2.net mail archive
Re: [Cfrg] Applications of target collisions: Pre or post-dating
daemon@ATHENA.MIT.EDU (Christian Rechberger)
Fri Oct 27 13:07:43 2006
X-Original-To: cryptography@metzdowd.com
X-Original-To: cryptography@metzdowd.com
Date: Fri, 27 Oct 2006 16:33:31 +0200
From: Christian Rechberger <Christian.Rechberger@tugraz.at>
To: Alfonso De Gregorio <adg@crypto.lo.gy>
Cc: "Weger, B.M.M. de" <b.m.m.d.weger@TUE.nl>,
"Steven M. Bellovin" <smb@cs.columbia.edu>, ietf-pkix@imc.org,
hash-forum@nist.gov, cfrg@ietf.org, cryptography@metzdowd.com
In-Reply-To: <4541F6EF.5000704@crypto.lo.gy>
Alfonso De Gregorio wrote:
> Hi Steven, hi Benne,
>
> Yes, this is a sweet and sour truth. We are not getting closer to
> preimage attacks. We are getting more far away from considering preimage
> and second-preimage resistance sufficient hash-function requirements for
> the real-world security of some protocols.
>
Hi everyone,
agreed to all you've said, still there are special examples where
bridging this gap seems closer. Consider a special type of preimage
resistance, CTFP (Chosen Target Forced Prefix), which was introduced by
John Kelsey and Tadayoshi Kohno in their paper "Herding Hash Functions
and the Nostradamus Attack" at Eurocrypt 2006.
If new methods like the one developed by Marc Stevens for MD5 are
sufficiently fast (just being faster than a birthday attack is not
enough in this setting), then also herding attacks can be faster.
Hence finding a preimage for MD5 in this special setting would be faster
than for a good MD-style hash function with the given output size.
Collision search for full SHA-1 (especially in this setting) does not
seem to be fast enough to allow this speed-up of herding attacks.
However, according to our experiments, with some new methods and
reducing SHA-1 to e.g. 75% of its steps, this changes.
Note that the effort for finding a preimage by looking for lots of
collisions in this setting would still be prohibitive in practice. For
MD5 and even more so for SHA-1.
Note also that this does not allow to draw conclusions on the standard
preimage or 2nd-preimage resistance of the mentioned algorithms. This
seems a different and challenging problem.
Best regards,
Christian Rechberger
--
Christian Rechberger <Christian.Rechberger@iaik.tugraz.at>
Krypto Group - IAIK - TU Graz, Inffeldgasse 16a, A-8010 Graz, Austria
http://www.iaik.tugraz.at/research/krypto/
phone: +43 (0)316 873 5534 --- fax: +43 (0)316 873 5594
---------------------------------------------------------------------
The Cryptography Mailing List
Unsubscribe by sending "unsubscribe cryptography" to majordomo@metzdowd.com
