Hacker News Reader

> 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.

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.

Interesting! I was wondering why KangarooTwelve[1] did something different and appends the customization string instead of prepending it.

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...

> 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.

> doesn't apply to K12 or BLAKE3. Their tree structures make it possible to reuse most of the work you did the first time

not so much in practice, due to the tree structure not being triggered before you hash a chunk (8192 bytes for K12).

Why not just H(H(info) || H(msg)) ? That would seem to me to give you the best of all worlds.

Technically, H(H(info) || msg) is enough, which is what we do in libra: https://github.com/libra/libra/blob/master/crypto/crypto/src...

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))

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.)

> you're much better off doing HMAC(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.

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

    H_{IV}(block0) =
        h(IV, block0)

    H_{IV}(... || blockN) =
        h(H_{IV}(... || block(N-1)), blockN)

(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...

Goes to show how easy it is to mess this up. :\

Meanwhile, always use the HMAC variant liberally in Merkle-Damgaard hashes if a secret token is involved.