[Cfrg] Applications of target collisions: Pre or post-dating MD5-based RFC 3161 time-stamp tokens

[Christian Rechberger]

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 at 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 at metzdowd.com