Subject: [Cfrg] Constructions of TCR hashing from MD-type functions

From: Shai Halevi <[email-masked]>
Date: Mon, 21 Mar 2005 10:09:54 -0500

John Wilkinson makes a very good argument, as to "why should be
think that an MD-type hash function with a short key is TCR".

There is a recent paper of Hong, Preneel, and Lee, that addresses
that question to some extent (Higher-order universal one-way hash
functions, Asiacrypt 2004, LNCS 2894, pages 201-213). Roughly, they
propose a notion of "order-r universal one-way hash function", and
show that if the compression function is order-r, then using the MD
construction on r blocks (with the same short key everywhere) does
give you a TCR hash function.

The "order-r UOWHF" game is as follows: A hashing key hk is chosen at
random, but is not given to the attacker. The attacker can ask r hashing 
queries m_1...m_r, and get the answers h_i = H_{hk}(m_i). Then you play
the usual TCR game: the attacker commits to message m, gets the hashing
key hk, and needs to find another m' such that H_{hk}(m)=H_{hk}(m').

-- Shai

John Wilkinson <[email-masked]> wrote:

> Most of the discussion on this list seems to be centered around 
> creating a TCR hash function by keying SHA1 through the IV using the 
> construction h(k || m), where k is the key (which is published, once 
> chosen), m is the message, and || denotes concatenation. Keying through 
> the IV is explicitly rejected in the paper [1] cited by Dr. Halevi. 
> Also rejected is the "envelope" construction h(k || m || k). HMAC has 
> no security guarantees if the key is not secret. It is argued in [1] 
> that the TCR of these constructions may be just as easy (or even 
> easier!) to break than the "any collision resistance" (ACR) of the hash 
> function h.
> 
> The constructions with security reduction arguments presented in [1] 
> all have very long keys (much greater than the length of the hash), and 
> the authors make a comment that the common practice of stretching a 
> short key into a long one using a PRF is "of no apparent use in this 
> case". (If anyone can explain why, I'd love to know.) In a signature 
> scheme, the hash value and the key must be signed, and then the key 
> must be sent along with the signature, effectively increasing the 
> length of the signature at least threefold. The authors of [1] suggest 
> that since the birthday "attack" is not applicable to TCR hash 
> functions, new TCR hash functions with 64- or 80-bit lengths could be 
> developed to mitigate the problem of signature length expansion.
> 
> With all the caveats applied in [1] to TCR-based signature schemes, 
> will anyone still prefer them to traditional ACR-based schemes using 
> SHA256 or SHA512? Does anyone have an argument to make that the authors 
> of [1] are overly pessimistic in their assessment of h(k || m) or HMAC 
> as TCR hash functions?
> 
> [1] http://www.cs.ucdavis.edu/~rogaway/papers/tcr-hash-abstract.html

_______________________________________________
Cfrg mailing list
[email-masked]
https://www1.ietf.org/mailman/listinfo/cfrg