4 ms·
You're absolutely right that H(public || private) may help against length extension (e.g., if we try to use H as a MAC), whereas H(private || public)
by kwantam 7y ago
You're absolutely right that
H(public || private)
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.