[Cfrg] Security concerns regarding short hashes

["D. J. Bernstein" <[e-mail]>]

The Curve25519 paper estimated "roughly 2^80 elliptic-curve additions"
for a 1-year ECC attack using a billion-dollar cluster with standard
2005-era chip technology, and concluded that this attack would have
"only about a 2^-90 chance" of breaking Curve25519.

Ten years later, chips have >100x more transistors, and some attackers
are now known to be spending even more money, so 2^90 elliptic-curve
additions seem feasible. It's not hard to extrapolate. At some point
quantum computers will become the top threat, but it's easy to imagine
standard attacks reaching 2^100 elliptic-curve additions before then.
Fortunately, these attacks would have only about a 1/2^50 chance of
breaking Curve25519, i.e., about 1 chance in 1000000000000000.

What happens if we use EdDSA with a half-size (128-bit) hash function,
allowing the signature compression discussed on page 9 of the original
Ed25519 paper? Recall that the signature (R,S) of a message M satisfies

   SB = R + H(R,A,M)A

where A is the public key, and conversely anything satisfying this
equation will be accepted as a valid signature. Compression produces
(H(R,A,M),S), which is only 48 bytes instead of 64 bytes, since H(R,A,M)
has 16 bytes while R has 32.

The attacker now searches through 2^100 possibilities for another
message M' with H(R,A,M') = H(R,A,M); maybe even more possibilities,
depending on how fast H is compared to an elliptic-curve addition. This
succeeds, producing (R,S) as a signature of this forged message M', with
probability 1/2^28, i.e., 1 chance in a few hundred million. Similar
comments apply to other signature schemes.

Is "breakable by feasible large-scale attacks with probability 1/2^28" a
matter of concern? Maybe, maybe not---but, either way, it is not the
same quantitative security level as "breakable by feasible large-scale
attacks with probability 1/2^50". This attack contradicts Mike's claim
that shortening H in this way is "without losing security"; mixing up
these security levels is like mixing up the single-key security levels
of a 128-bit cipher and a 150-bit cipher.

Even worse, if H is any _narrow-pipe_ 128-bit hash function, then the
following generic attack algorithm increases the probability from 1/2^28
up to essentially 1, after the attacker sees a plausible number of
signatures, say signatures with points R_1,R_2,...,R_{2^{28}}:

   * Force an internal collision between R_1 and R_2, i.e., a collision
     of the hash states obtained in hashing extensions of R_1 and R_2,
     by trying many extension blocks (R_1,A,M_1) and (R_2,A,M_2). Do the
     same for R_3 and R_4, for R_5 and R_6, etc. This takes 2^27*2^64
     hash computations.

   * Starting from the hash state h_{1,2} from R_1 and R_2, and the hash
     state h_{3,4} from R_3 and R_4, add another block to force an
     internal collision between h_{1,2} and h_{3,4}, i.e., an internal
     collision between R_1,R_2,R_3,R_4. Do the same for R_5,R_6,R_7,R_8
     etc. This takes 2^26*2^64 hash computations.

   * Continue in the same way to find a single hash state h obtained as
     a collision of 28-block extensions of all of the R_i's. The whole
     computation takes essentially 2^28*2^64 hash computations.

   * Starting from h, try further extensions until bumping into _any_ of
     the 2^28 hash values used in the legitimate signatures. This is a
     multiple-target preimage attack, taking only 2^100 hash
     computations.

This is similar to the "herding" attack of Kelsey and Kohno, except that
the "herding" attack starts from one input and aims for any state in the
"diamond", while this attack starts from the right tip of the "diamond"
and aims for any state in an externally specified list of targets.

Saying "This attack doesn't break wide-pipe hash functions" is missing
the point. The point is that single-target preimage attacks aren't the
only way---and, in a large class of examples, aren't the best way---to
attack the hash-security property that's needed here. This means that to
figure out the actual security level of any particular hash function H
you have to analyze this security property for H; you can't rely on
analyses of the single-target preimage security of H. Unfortunately, as
far as I know, the necessary security analysis hasn't been done for any
of the wide-pipe hash functions H that have been suggested.

Why doesn't this concern apply to H with a larger output? Easy: any
attack of this type against H implies a _multiple-target_ preimage
attack against H; any N-target preimage attack can be converted into a
single-target preimage attack that's >=1/N times as effective; and now
we're talking about functions H that are explicitly designed to have
single-target preimage security far above 2^128, so dividing by N still
stays above 2^128. This security buffer is exactly what's missing for a
function H with a 128-bit output, whether or not H is wide-pipe.

One can try squeezing a 256-bit hash to, say, 192 bits, and arguing that
a user won't sign 2^64 messages (2^50 is a reasonable limit). However,
it's not clear that the issues here are limited to single-user attacks.
Multiple users will certainly sign a total of more than 2^64 messages,
and then it's entirely possible that this squeezing loses security. The
necessary analysis again hasn't been done---and how many applications
will notice the difference between a 64-byte signature and a 56-byte
signature?

The only way to confidently maintain security is to use a >=256-bit
hash. Schnorr's compression then can't save anything, so there's no
reason to think about it further. With compression out of the picture,
using a double-size (i.e., 512-bit) hash doesn't affect the signature
size. Double-size hashes are also helpful for key derivation and nonce
generation (see, e.g., the PRF notes in my previous message), and having
all of these operations use a single hash function is helpful for
implementors and auditors.

Dan Brown's proposal replaces SHA-512 with SHA-384 for key derivation
and nonce generation (and with a truncated form of SHA-384 for the
Schnorr hash). It's again clear that this reduces the security level at
least somewhat compared to EdDSA (the seed has only 128 bits), and one
would have to do more analysis to see whether there are further losses.

These security issues illustrate the dangers of trying to achieve
"cryptographic balance" through chopping every system component down to
the minimum size that can reach some predetermined security level---it's
much too easy to misunderstand the attack space and chop some components
down too far. Sometimes I see people saying that the simple, safe thing
to do is "more secure than necessary", but this isn't a problem per se.
Occasionally _poor system performance_ is a problem, but this problem is
almost always caused by a small number of major bottlenecks, so it
doesn't justify touching any of the other system components.

---Dan