Prehashing doesn't just solve the storage issue. Imagine you want to sign a 1MB or even 1GB file with a typical hardware token. Without prehashing you'd have to send that entire 1MB or 1GB to the token, which has a throughput on the order of KB/s or maybe MB/s, and process all that data with a CPU clocked at MHz, not GHz. Breaking up the file into chunks doesn't help, and might even make things slower, not to mention the added complexity introduced to your file signature format.
The obvious solution is to hash the data and sign the hash, just as is done for every other signature scheme. The downside is that now your signature scheme is only as strong as the hash. But if it turns out that SHA-512 isn't collision resistant, you have much bigger problems.
PureEdDSA has its elegance, and, sure, use it if you can. But supporting off-chip private keys (e.g. hardware tokens) is sometimes far more important to security. If you're creating an API, keep that in mind.
> if it turns out that SHA-512 isn't collision resistant, you have much bigger problems
Ehhh.. collision resistance is a much harder property than second-preimage resistance, and many protocols don't have strong dependencies on collision resistance. Narrow-ish pipe MD style hash functions are particularly brittle against collisions, since finding one collision immediately gives you an infinite family of collisions.
You could preserve most of the protection against collision resistance with the two layer hashing by having a signer specified nonce at the interior hash. The token couldn't validate that the nonce matched the one it specified, but an attack would require the host be compromised as well. If the nonce was a hash of the EdDSA R value and checked by verifiers too then the fact that the token can't check wouldn't be a problem.
Alternatively, if the inner hash were a tree-structured hash, the token could validate the inner-hash nonce directly. (though depending on the tree, doing it that way might weaken the collision protection).
Regardless, it's not strictly necessary to lose that protection just to enable blind-signing-tokens.
I don't know what's the parent's problem, but "this assumes x holds true" is actually much more clear and straight-forward, which really helps to stay on track with the discussion. At the very least it allows the opponent to ask if there's something available w/o this assumption, which "you have bigger problems" barely does.
A slightly unfortunate trend in protocol design has been to prepend rather than append "info" fields to hash inputs. In other words, we tend to see
H(info || msg)
instead of
H(msg || info)
There are some good reasons to prefer append to prepend. One practical reason is that---related to what's discussed in the article---if we have to compute two values
H(msg || info_1)
H(msg || info_2)
we can do this with just one pass over msg (though admittedly in a non-blackbox way, namely, by saving an intermediate state of the hash computation). In contrast, for a well-designed hash function there should not be any way to save work when computing
H(info_1 || msg)
H(info_2 || msg)
and this lack of work savings is one of the reasons we tend to get prehash modes.
In addition, prepending to msg comes with a range of subtle security issues. As an example, for Merkle-Damgaard hashes like SHA-2 a proper prefix design needs to pad the prefix to a multiple of H's block length. This is to ensure that msg starts on a block boundary, which means that the hash digests as much of msg as possible in a single invocation of the compression function. Otherwise, if msg is short and it gets broken across a block boundary, this can make meet-in-the-middle--style attacks easier.
In contrast, appending the info string guarantees that msg starts at a block boundary, which is a small nicety. Moreover, one can easily guarantee in a black-box way (and independent of the value/encoding/&c of the info string) that msg ends at a block boundary (just by padding msg). This can be useful as a defense against some kinds of power analysis in the case that msg is a secret [1].
To be sure: appending also requires care---and care is always required when a Merkle-Damgaard hash! (Sponges like SHA-3 are more resistant to misuse.) At the very least, whatever is appended to msg should be prefix-free, and you will likely want to stop length extension attacks and related issues (see [2] for further discussion of this).
But in general my take is that the set of footguns for append is a subset of the prepend ones, and I hope that more folks go towards appending in the future.
> Otherwise, if msg is short and it gets broken across a block boundary, this can make meet-in-the-middle--style attacks easier.
Can you elaborate? Take SHA-512/256 with some awkward prefix size, let's say 127 bytes. Which attacks, presumably not side-channel based, become possible?
In any case, I am not convinced in the least by this suffix pitch. Handwaving that "prefix-freeness" needs to be checked, when that's something that is constantly gotten wrong and results in real breaks is a bit naïve. On the other hand, I have real trouble thinking of a real break caused by prefixing. The Ed25519 paper you link to does not point to prefixing as the culprit either; that just happened to be where the key was, and the lack of randomness makes power analysis possible. Without randomness, suffixing would suffer a similar fate.
SHA-512/256 is already quite misuse-resistant, so it's entirely plausible that there's nothing to worry about in this specific case.
But if we limit ourselves to standard Merkle Damgaard hashes (i.e., not ChopMD), then the specific concern is that putting a small amount (say, a few bytes) of msg at the end of one block lets us, in effect, look for collisions between two M-D hash functions where one has an attacker-chosen IV. Here, the key property is that the IV space is large enough to be useful but small enough to be feasibly searchable.
For SHA-2, this does not currently appear to be a problem, but the conservative move is to rule this out by construction. HMAC does this, for example (and as I'm certain you know, HMAC-SHA-1 remains plausibly secure in spite of all of the attacks on SHA-1).
Regarding prefix-freeness: I completely agree with you that this is easy to get wrong, and I didn't intend to hand-wave about this in the least. Note, however, that the requirement for prefix-freeness obtains for both prepend and append! So this isn't actually an argument against appending.
Regarding the power analysis: apologies, I should have been clearer on this point. One interpretation of the Ed25519 paper I linked is that the issue has to do with putting the secret in the same block as attacker-controlled bytes, because this gives the attacker a lot more power to extract information about the secret via power analysis. Even without randomness, this attack would be much harder to pull off (perhaps even impossible) if the secret were padded to a full block length.
My point was just: don't put secrets and attacker-controlled data in the same block. And suffixing always lets us do this by applying a padding routine that is independent of the info string to msg.
> But in general my take is that the set of footguns for append is a subset of the prepend ones, and I hope that more folks go towards appending in the future.
But length-extension attacks are only a problem for H(private || public-but-extensible) constructions, aren't they? AFIAK, H(public-but-extensible || private) cannot be attacked using a stock length-extension attack. So there's at least one attack that prepending is safe against, which appending is not.
may help against length extension (e.g., if we try to use H as a MAC), whereas
H(private || public)
certainly does not!
As stated, though, this is only a heuristic: depending on the application, we'd want to prove something about the construction under an appropriate assumption. (Frequently for Merkle Damgaard hash functions one makes some assumption about the compression function, e.g., that it's collision resistant or that it's a random oracle, and then proves something about the whole construction. This is the content of [2] in my prior message.)
A few things to note, though:
1. In my prior post I was implicitly assuming that info was short and/or fixed-length, whereas msg could be very long, but I wasn't making any assumptions about public vs. private. In the EdDSA case, notice that in
H(nonce_key || message)
nonce_key (the "info" string) is secret and message is public! So we might heuristically worry about length extension here, but it turns out not to be an issue.
(In more detail: this value is treated as a 512-bit integer r that is implicitly reduced mod the order of the curve25519 group, roughly 2^252, when computing R = rB. We can think of this modular reduction as similar to a ChopMD construction like SHA-512/256, which prevents length extension. Moreover, extracting r from R would require computing a discrete log!)
2. Continuing the above thought: in most instances when we try to use H in a MAC-like construction, the key is relatively short and/or fixed-length, whereas the message is potentially long. So in this case "appending" is consistent with "secret at the end."
(You're absolutely right, though, that my prior message was not particularly clear on this point.)
3. In many of the cases I was discussing in the prior message, both info and msg are public. So if we want to defend against length extension generically, we need some other approach regardless of the concatenation order. Usually one would use ChopMD, HMAC, or a prefix-free encoding; see [2] from my prior post.
> In contrast, for a well-designed hash function there should not be any way to save work when computing...
This property, that making a small change at the front of the message requires repeating almost all of the work to re-hash the whole message, doesn't apply to K12 or BLAKE3. Their tree structures make it possible to reuse most of the work you did the first time. (This is essentially the same thing as being able to hash different parts of the message in parallel, which is the design goal of both algorithms.)
With BLAKE3, if you wanted to force someone to repeat all the work, the cleanest way to do it would be to change the key.
There are a lot of things that are much safer to do with SHA-3 (as in Libra) than with SHA-2.
If H is in the SHA-2 family, you're much better off doing
HMAC(info, msg)
than
H(H(info) || msg)
In particular, HMAC has provable security properties that the latter construction does not. (HMAC is immune to length extension, it remains secure even when the M-D compression function is quite non-ideal, etc.)
In terms of security this may be true. But the whole point in this discussion is to avoid having to re-hash msg multiple times for different values of info.
D'oh. Of course. One thing we could do in this case is use NMAC rather than HMAC.
First, let's more explicitly define a Merkle Damgaard function in terms of its compression function and initialization vector. For some compression function
h(prior, next)
(here, think of `prior` as b bits---say, 256---and `next` as 2b bits) we can define a Merkle Damgaard hash with explicit initialization vector IV as
(here, blockX represents an input block of 2b bits; I'm assuming we'll pad the message, say, the way SHA-2 does).
Now we can define HMAC-SHA-256 in terms of the above notation as
HMAC(key, msg) = H_{oiv}(H_{iiv}(msg))
where
oiv = h(sha256iv, key XOR opad)
iiv = h(sha256iv, key XOR ipad)
(here, h is the SHA-256 compression function and sha256iv is the standards-specified IV for SHA-256). Here, I'm slightly glossing over the way `key` is padded, but the point is that in HMAC the key inputs are always expanded or squashed to exactly one block in length, which means that the key is effectively being used to create two initialization vectors, one for the inner call to H and a different one (with overwhelming probability) for the outer call.
This is related to the reason that HMAC(info, msg) doesn't let us reuse the hashing work for different info strings: the inner H's IV depends on info, so we have to recompute the whole inner hash. When info is public, however, there's no need to make the inner IV depend on info---it can just as well be some other fixed public string. Said another way, we can use a generalization of HMAC called NMAC, which we can define as follows:
NMAC(oiv, iiv, msg) = H_{oiv}(H_{iiv}(msg))
one natural way to do this would be
NMAC(f(info), sha256iv, msg)
for some reasonable function f. A natural one is
f(info) = h(sha256iv, H(info) || 0000...0000)
where the zero padding is b bits. Re-writing this in terms of H without explicit IVs, we have
H(H(info) || 0000...0000 || H(msg))
which is very reasonable to compute (and is related to a construction in the Coron et al paper I linked [2] in my original note). Note that the zero padding between H(info) and H(msg) is crucial if we want to be able to leverage the NMAC analysis. Intuitively, we don't want the outer IV to depend on msg, so we have to push msg into the next block.
I should also note that all of the above is a bit far afield from where we started, and it probably seems like we've come full circle to prepending again! The kind of exercise in this post is essentially expanding my comment that "you will want to stop length extension attacks and related issues"---this is one way to do it, but by no means the only way. For example, if we want to use the info string for domain separation and be able to reuse work hashing msg, you could do something like:
H(fixed_zeros_block || H(msg || info) || info)
This puts msg in prefix position (good for reuse), uses a different IV for inner and outer hash (good for preventing length extension), and always appends info to the input to H (good for domain separation).
There has been a lot of work studying the security of NMAC and HMAC, and the upshot is that both constructions protect us really well from non-idealities in the compression function for secret IVs, though somewhat less well for public ones. Off the top of my head, one further nice reference is https://eprint.iacr.org/2006/043
Ah, quick update to the above (can't edit anymore):
the final construction I posted in the above message is not good for arbitrary messages, because if msg starts with an all-zeros block then the inner and outer hash invocations won't have different IVs (which is bad).
If msg is structured in a way that guarantees that it doesn't have an all-zeros block as a prefix, then this construction is fine, but that does seem quite fragile...
The obvious solution is to hash the data and sign the hash, just as is done for every other signature scheme. The downside is that now your signature scheme is only as strong as the hash. But if it turns out that SHA-512 isn't collision resistant, you have much bigger problems.
PureEdDSA has its elegance, and, sure, use it if you can. But supporting off-chip private keys (e.g. hardware tokens) is sometimes far more important to security. If you're creating an API, keep that in mind.