6
$\begingroup$

When MD5 and SHA1 were broken there was, each time, a scramble to upgrade software and certificates to remove the offending algorithm. However, in each case, the HMAC variant of each hash function was not affected. In fact, unless I missed something, HMAC-MD5 is technically still secure.

In the context of signing data at rest using RSA or ECDSA, where performance is not the critical factor, would it make sense to use HMAC-SHA256 instead of plain SHA256 for the digest function in order to avoid a similar situation in future?

Something like this: $s = k \mathbin\Vert S(k \mathbin\Vert H(m,k))$ where $S$ is some asymmetric signing operation such as RSA or ECDSA, $k$ is a randomly generated key, $H$ is HMAC-SHA256.

$\endgroup$
  • $\begingroup$ ECDSA is a standardized algorithm. Making this change would essentially turn it into something that isn't ECDSA, or would make a non-backwards compatible change to the standard (since we're outputting different data, redefining the hashing step, etc). $\endgroup$ – puzzlepalace Mar 5 at 19:24
  • $\begingroup$ @puzzlepalace Feel free to ignore the ECDSA part if you wish, although I don't see how it particularly matters if we swap the hash step out for HMAC aside from naming conventions. $\endgroup$ – Polynomial Mar 6 at 12:22
  • $\begingroup$ I think the main difference would be that we now need to transmit the HMAC key (as part of the signature or over another channel) to the Verifier. I'm being picky here, I understand the spirit of the question. :) $\endgroup$ – puzzlepalace Mar 6 at 22:14
  • $\begingroup$ @puzzlepalace Yeah. The key is concatenated with the signature in the example I gave. $\endgroup$ – Polynomial Mar 6 at 22:47
  • 1
    $\begingroup$ Concerning the SHA-1 scramble: To me it's worth noting that the reason why there was a scramble was because we had people who were unprepared up until the moment the first publicly announced collision was revealed. It's not because they weren't given advance warning nor was it because no one was lobbying them to upgrade. SHA-1 was broken in 2005. (The full algorithm!) Not around 2017's "SHAtterred". It was still costly to compute a collision using the break before then, but it was only a matter of time before it would be exploited. $\endgroup$ – Future Security Mar 7 at 3:43
7
$\begingroup$

If we view HMAC as a message authentication code or a PRF, this doesn't quite make sense: the security property for a MAC or a PRF assumes that the forger doesn't know the key, but you've given them the key $k$ in the signature. But you have the right intuition that there is something here.

While a signature scheme in terms of $H(m)$ requires $H$ to be collision-resistant, a randomized signature scheme in terms of $H(r, m)$ requires $H$ to have only the much more modest property of enhanced target collision resistance, eTCR, which even MD5 may still exhibit. So yes, what you suggest does seem to improve security in the face of unkeyed collision attacks on hashes like MD5 and SHA-1.

Obviously, if you're looking to be compatible with an existing system that uses ECDSA and can't be modified, the idea won't help you. But modern signature schemes like EdDSA use it as part of the design, and you can always adapt an existing signature scheme to use it—NIST even standardized it in NIST SP 800-106, Randomized Hashing for Digital Signatures. HMAC might work for the purpose too.

If you want more details, there's a lot of history here, so buckle up, buckaroos, for some story time!


Early history: Rabin signatures and the importance of hashing. The first secure signature scheme in history, due to Michael O. Rabin[1], took a public key to be a pair $(n, b)$ of integers and a signature on a message $m$ to be a pair $(s, u)$ of an integer $s$ and a bit string $u$ such that $$s\cdot(s + b) \equiv H(m, u) \pmod n.$$ The signer, of course, knows the secret factors $p$ and $q$ of $n = pq$, in terms of which computation of square roots modulo $n$ is cheap, particularly if $p \equiv q \equiv 3 \pmod 4$. The hashing and randomization served two purposes that Rabin articulated:

  1. Allow the signer to vary $u$ until $H(m, u)$ admits a solution to the equation at all in $s$.
  2. Reduce the probability that the signer accidentally reveals distinct square roots $s \ne s'$ of a common square, which would reveal the factorization of $n$.

We might also add a property that Rabin may have felt too obvious to state:

  1. Compress long messages and destroy any structure, like integer perfect squares whose integer square root could be used to forge signatures.

It's unclear whether active attacks exploiting collisions were considered at this time, but provided that $H$ is collision-resistant, Rabin's scheme remains secure today by the modern standard of existential unforgeability under chosen-message attack (EUF-CMA), assuming suitable parameter sizes. In fact, $H$ may not even need to be collision-resistant, but it's not clear that anyone noticed this until Schnorr a decade later. Soon after Rabin, Hugh C. Williams[2] (paywall-free) showed how to efficiently compute squaring-type signatures deterministically with tweaks when $p \equiv 3 \pmod 8$ and $q \equiv 7 \pmod 8$, obviating the need for randomization to achieve purpose (1).

Hashing, collision resistance, and discrete log signatures. The importance of hashing appears to have been lost on Taher Elgamal initially in his discrete-log-type signature scheme[3], which was trivially breakable as a consequence—a signature under a public key $y$ on a message $m$ is a pair $(r, s)$ of integers such that $$a^m \equiv y^r r^s \pmod p,$$ which, for example, admits the trivial forgery $(0, 0)$ on the message $m = 0$ for any public key. ($p$ is the standard modulus and $a$ is the standard generator of some subgroup of $\mathbb Z/p\mathbb Z$.)

Not everyone neglected hashing, though, and by the late '80s the importance of collision-resistant hashing was in the air: in Claus P. Schnorr's discrete-log-type signature scheme[4], where a signature under a public key $v$ on a message $m$ is a pair $(e, y)$ such that $$e = H(a^y v^e \bmod p, m),$$ Schnorr observed that the hash function $H$ need not be collision-resistant if it is randomized, and therefore could presumably be half the length a naive composition of, e.g., Elgamal with a collision-resistant hash would require for the same security.

The NSA—ahem, I mean, NIST—recognized the importance of collision resistance in a fixed hash in the Digital Signature Standard, FIPS 186, but carefully made the opposite of every good design decision of Schnorr[5] for fear of treading upon a patent, including randomization of the hash. They also, of course, made DSA vulnerable to bad RNGs when making signatures, over the vociferious objections of contemporary cryptographers which NIST casually brushed off[6].

Provable security and industry standardization: RSA-PSS and RSA, Inc. Early standardization of RSA like PKCS#1 v1.5 used an ad hoc way to shoehorn a message hash into an element of $\mathbb Z/n\mathbb Z$—specifically, into a minuscule sparse subspace of $\mathbb Z/n\mathbb Z$ which is useless for studying in relation to the difficulty of computing $e^{\mathit{th}}$ roots of a uniform random element of $\mathbb Z/n\mathbb Z$, which is the RSA problem and which is presumably more closely studied than the RSASSA-PKCS1-v1_5 problem.

In 1996, Mihir Bellare and Phil Rogaway[7] studied the security of RSA- and Rabin-type signature schemes in what more closely resembles the modern framework of ‘provable security’—showing how to use a forger as a subroutine in an otherwise cheap algorithm to compute $e^{\mathit{th}}$ roots modulo $n$, or to factor $n$ in the case of squaring-type schemes. They were able to prove that if $H$ covers the whole of $\mathbb Z/n\mathbb Z$, then forgery of signatures $s$ satisfying the signature equation $$s^e \equiv H(m) \pmod n$$ called RSA-FDH, can be used for an algorithm to compute $e^{\mathit{th}}$ roots modulo $n$.

Bellare and Rogaway weren't satisfied with the specific theorem they proved, though, because its high cost for modest success probability meant nothing in the case where you sign lots and lots of messages. So they considered a randomized variant, a probabilistic signature scheme or PSS, with the signature equation $$s^e \equiv \bigl[r \mathbin\| H(r \mathbin\| m)\bigr] \pmod n,$$ roughly. Randomization in PSS enabled them to easily prove a stronger theorem.* They also observed in their proposal for IEEE P1363[8] that using $H(r \mathbin\| m)$ did not seem to rely on collision resistance of $H$. But what was actually standardized instead uses $H(r \mathbin\| H(m))$, which is vulnerable to collisions in $H$. In particular, this was standardized in IEEE P1363 in 2000 (paywall-free; §12.1.2 ‘EMSA2’, pp. 60–61) and by RSA, Inc., in PKCS #1 v2.1 in 2002 (§9.1 ‘EMSA-PSS’, pp. 33–36).

Coincidentally, I'm sure, this was around the same time that the NSA donated ten million dollars to RSA, Inc., to encourage them to deploy the highly superior Dual_EC_DRBG to their BSAFE customers[9]. Not much later—it is unclear from the public record exactly when, but almost certainly not later than 2007—the governments of the United States and Israel exploited an MD5 collision attack[10] to forge signatures on code-signing certificates in an international incident of industrial sabotage against Iran. Oops.

Formalizing and standardizing collision resilience. In 1989, Moni Naor and Moti Yung introduced universal one-way hash functions or UOWHFs[11] to formalize what one would expect of randomized hashes for digital signatures: if an adversary submits $m$ up front and is then given $r$, it is hard to find $m' \ne m$ such that $H(r, m') = H(r, m)$—essentially a restricted case of second-preimage resistance. In 1997, Bellare and Rogaway had the brilliant innovation of giving the concept a more pronounceable and memorable name, target collision resistance or TCR[12], but in spite of the rebranding the notion received little attention for a decade.

Then, in the mid-2000s, as the foundations of collision resistance were cracking at the seams, cryptographers began to seek ways around it, and dusted off old volumes of Naor and Yung and of Bellare and Rogaway.

  • Phil Rogaway and Tom Shrimpton comprehensively studied relations between various standard notions of security of keyed hash functions—collision resistance, preimage resistance, second-preimage resistance, etc.—and proved implications and gave counterexamples for nonimplications[13]; TCR features as ‘eSec’ or ‘everywhere second-preimage resistant’ in their work.

  • Shai Halevi and Hugo Krawczyk studied randomization of signatures[14], and invented an even better version of TCR called enhanced target collision resistance or eTCR: if an adversary submits $m$ up front and is then given $r$, it is hard to find $(r', m') \ne (r, m)$ such that $H(r', m') = H(r, m)$. This is important for signatures schemes where the randomization $r$ does not naturally figure in as it does in PSS, and where the adversary therefore has latitude to control it—as in your suggested generic use of HMAC to strengthen signatures by randomization. They proposed a generic construction called RMX[15], submitted a now-expired internet-draft to the IETF[16], and persuaded NIST to standardize it as NIST SP 800-106.

Bellare and Rogaway observed that the usual Merkle–Damgård structure doesn't guarantee TCR, which is why Halevi and Krawczyk proposed RMX. But even though collisions have been found in, e.g., MD5 and SHA-1, there doesn't seem to be much evidence that they fail to exhibit eTCR. So while the Merkle–Damgård structure doesn't imply eTCR, the design principle of using $H(r \mathbin\| m)$ instead of $H(m)$ in a signature has been adopted in newer schemes like EdDSA[17] following Schnorr's observation in 1989. It seems unlikely that $\operatorname{HMAC-}\!H_r(m)$ would fail eTCR either even for $H = \operatorname{MD5}$ or $H = \operatorname{SHA1}$.

Conclusion. Today, there is only one signature scheme that new applications should use unless they have exotic needs: Ed25519, which has this kind of collision resilience built-in by design. Legacy applications may be stuck with signature schemes like DSA or RSASSA-PSS that have collision vulnerability built-in by design, but maybe if you're only partly stuck on legacy system—you can't use a new signature primitive because you have auditors clamoring at the door about FIPS, but you can use a legacy signature primitive in a new way—you can adapt it to be collision-resilient by randomizing it with RMX, or perhaps with HMAC, or perhaps even with the simple prefix $H(r \mathbin\| m)$.


* The role of the randomization in these theorems is a little peculiar. Even a single bit of randomization apparently makes a difference in the tightness of the theorems about $e^{\mathit{th}}$ root schemes but not square root schemes[18], which should raise a few eyebrows about the years of effort in the provable security literature that have been dedicated to this single bit of randomization while the US and Israel were at about the same time actually exploiting collisions in MD5 to forge signatures in real standards to wreck Iran's nuclear program.

$\endgroup$
  • $\begingroup$ Another superb answer that clarifies a thorny issue. $\endgroup$ – Patriot Jul 1 at 3:08
4
$\begingroup$

Yes, it helps to use HMAC instead of a hash in digital signature (with the HMAC key $k$ sent along the signature), but only when the signer chooses $k$ unpredictably when signing. The attacker can then no longer exploit a loss of collision resistance in the hash, because the attacker can't chose the message $m$ as a function of $k$, and that tends to make HMAC resist collision, even when the hash is broken; and HMAC does not introduce a risk of altering the massage after signature, since it resists second preimage: given $(m,k)$ or $H(m,k)$ we can't exhibit $(m',k')$ with $H(m,k)=H(m',k')$ and $m\ne m'$.

An easier method is often used to the same effect: the signer chooses an unpredictable value entering the hashed message in its first block (like 16 of the first 64 bytes). For certificates, that can conveniently be the Certificate Serial Number. The huge advantage is that standard signature verification applies, so certificates made in this way can remain secure even if they use a hash with broken collision-resistance in the certificate's signature process.

$\endgroup$
  • $\begingroup$ Amusingly, the property you articulated here—attacker can't find $m' \ne m$ and $r'$ with $H_{r'}(m') = H_r(m)$—is neither TCR, where we require $r' = r$, nor eTCR, where we require $(r', m') \ne (r, m)$ but we may have $m' = m$. It seems unlikely to me that this fine distinction would has any consequences in practice, of course; to my knowledge nobody has ever shown TCR or eTCR weakness of any major hash function anyway. $\endgroup$ – Squeamish Ossifrage Mar 8 at 7:13
  • $\begingroup$ @Squeamish Ossifrage: Yes, I tried to write down the required property to prevent collision attack with the HMAC-instead-of-H thing, it's nothing standard, and a little complex; but I'm confident that it holds even for HMAC-MD5. $\endgroup$ – fgrieu Mar 8 at 7:18

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.