How does randomized hashing defeat collision attack?

Question

SEC#1 recommends randomized hashing when using SHA-1 with ECDSA; SPHINCS+ uses randomized hashing in WOTS+ to defeat collision attack so as to reduce signature size.

How does a randomized hashing defeat collision attack? What are the limitations?

Answer 1

In randomized hashing for Merkle-Damgard based hash function (like MD5, SHA1, SHA2) the input preprocessed with a salt before hashing applied. This process doesn't modify the underlying hash function uses it as a black box, It is proposed by Shai Halevi and Hugo Krawczyk in 2007;

• Strengthening Digital Signatures via Randomized Hashing

For MD based hash functions. They defined the Target Collision Resistant (TCR) as;

a family of hash functions $\{H_r\}_r\in R$ (for some set $R$) is target collision-resistant if no efficient attacker $A$ can win the following game, except with insignificant probability:

• A chooses a first message $M$, then receives a random value $r \in_R R$, and it needs to find a second message $M' \neq M$ such that $H_r(M_0) = H_r(M)$. The value $r$ is called a hashing key, or a salt.

and they also defined the Enhanced Target Collision Resistant (eTCR) since signature schemes like DSA don't support to sign the salt $r$. To support this they use relaxing the conditions to strengthen the mode of operation. This scheme is

sufficiently strong to ensure the security of the resultant signatures even if we only apply the underlying signature to $H_r(M )$ and do not sign the salt $r$.

The game is played as;

• A chooses a first message $M$, then receives a random value $r \in_R R$, the salt r, the attacker can supply a second message $M'$ and a second salt $r'$, and it is considered successful if $(r, M ) \neq (r', M' )$ but $H_r (M ) = H_{r'} (M')$.

and it needs to find a second message $M' \neq M$ such that $H_r(M_0) = H_r(M)$. The value $r$ is called a hashing key, or a salt.

They define two methods as;

1. $$H_r^c(m_1, \ldots , m_L) \overset{def}{=} H^c(m_1 \oplus r,\ldots, m_L\oplus r).$$ This scheme is TCR under second-preimage resisantce (SPR) ^*. This suit RSA signature since we can extend the modulus so that the $r$ can be signed, too.

2. And the below scheme is eCTR under SPR, too ^*, This is useful for DSA like algorithms in which signing additional data, $r$, is not easy.

   $$\tilde{H_r^c}(M)\overset{def}{=} H_r^c(0|M) = H^c(r, m_1 \oplus r,\ldots, m_L\oplus r).$$

They designed their scheme so that the security of the resultant signature scheme does not depend on the resistance of the hash function to off-line collision attacks. In short, they related the security of their scheme to the second-preimage resistance of the compression functions.

---

_{^* Actually, the proofs rely on two properties that related to SPR. e-SPR is the real hardness of collision resistance of $H_r$ and $\tilde{H_r}$. And, c-SPR, which is related to the hierarchy of collision resistance.}

Note 1: There is a web page that shows how this and similar method can be easily applied to NSS Library and Firefox.

Note 2: The extended version of the paper is here ( and it is not https!)