EdDSA, Ed25519, Ed25519-IETF, Ed25519ph, Ed25519ctx, HashEdDSA, PureEdDSA, WTF?
cryptologie.net
cryptologie.net
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.
Does it though? Most protocols are moving towards preimage resistance nowadays.
That being said, ed25519ph is easier to protect against fault attacks, see https://github.com/jedisct1/libsodium/issues/170
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.
H(info || msg)
H(msg || info)
H(msg || info_1)
H(msg || info_2)
H(info_1 || msg)
H(info_2 || msg)
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.
I thought it was a bit annoying because it doesn't allow you to pre-compute the customization string, but I hadn't think of your usecase.
[1]: https://tools.ietf.org/html/draft-irtf-cfrg-kangarootwelve-0...
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.
not so much in practice, due to the tree structure not being triggered before you hash a chunk (8192 bytes for K12).
the downside is that you are potentially doing more hashing, which is not true if you pre-compute the H(info) (and the absorption of H(info))
If H is in the SHA-2 family, you're much better off doing
HMAC(info, msg)
H(H(info) || msg)
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.
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)
H_{IV}(block0) =
h(IV, block0)
H_{IV}(... || blockN) =
h(H_{IV}(... || block(N-1)), blockN)
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)
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))
NMAC(f(info), sha256iv, msg)
f(info) = h(sha256iv, H(info) || 0000...0000)
H(H(info) || 0000...0000 || H(msg))
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)
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
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...
Goes to show how easy it is to mess this up. :\
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.
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 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.
H(public || private)
H(private || public)
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)
(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.