expand domain separation discussion in Security Considerations

[kwantam]

After discussing with @reyzin today, it seems like we can go a little further with the domain separation discussion in Security Considerations.

Specifically: right now we append DST inside expand-message-xmd and expand-message-xof. For xof this isn't a problem because we expect it to be used with SHAKE-128 or a similar hash that has an indifferentiability proof. expand-message-xmd, on the other hand, has some subtleties that we should discuss further in how it interacts with domain separation in the invoking protocol.

Specifically, it's possible to use -xmd with either prefix or suffix domain separation, which is handy for protocols that prefer to use prefix domain separation (and there are reasons to do this; see below). Since -xmd prepends an all-zeros block to the front of the input to H when computing b_0, this is easy: just prepend some tag of length at most one block that's guaranteed to have a nonzero byte.

(For the b_i computations (i >= 1), domain separation is automatic with overwhelming probability: the first output-block-length bytes is a random value ~that is never revealed to the adversary~ (EDIT: might not be this easy...), so it's infeasible for the adversary to generate a collision and thereby differentiate -xmd from a hash function.)

So: I think we ought to add a note in Security Considerations that calls attention to this fact, because it may help future implementors to avoid footguns when using SHA-2 and other M-D functions.

---

The reason invoking protocols might wish to use prefix rather than suffix domain separation with Merkle-Damgaard hash functions is that some ways of turning M-D into an indifferentiable function are fragile when composed with other protocols, and in some cases this fragility can be avoided by prefixing rather than suffixing the DST. (To be clear: the way -xmd is constructed it is not fragile in the way I am about to describe.)

Consider two different protocols, Px and Py, each of which uses a M-D hash as an indifferentiable function by fixing the length of the M-D input and appending a domain separation tag. Let's call these fixed lengths Lx and Ly, respectively. Notice that this rules out any length extension attack against either Px or Py, because there is precisely one length allowed for each protocol.

Now consider the case that Ly > Lx such that we have

• Inside Px: H(input1 || DST1)
• Inside Py: H(input2 || DST2), where input2 = input1 || DST1 || padding || ... (imagine padding is the standard padding that, say, SHA-2 would add to the end of Px's HASH invocation).

Oops! Now Py's use of H becomes differentiable: first we observe the output from Px's H invocation, then we do a length extension attack to predict the output of Py's invocation! This is subtle and unfortunate: we couldn't differentiate Py's random oracle on its own (because of the fixed-length input), but composed with Px we can differentiate Py's random oracle.

OK, so why bother with this example? Because, as @reyzin pointed out to me, if DST had been in the front, there'd be no such attack.

---

To be clear: I am not suggesting any change to -xmd! But I think we should point out to readers that it's flexible in the way that other protocols can domain separate from it.

[chris-wood]

This seems like a reasonable clarification. (Thanks, @reyzin!) Are you suggesting we add the example? I think noting prefix or suffix domain separation properties of -xmd is probably sufficient.

[kwantam]

Not totally clear we need to add an example. So probably, as you say, just want to discuss considerations for domain separating from xmd in front and in back.

[chris-wood]

Would you mind if I took a crack at this?

[kwantam]

I'm still thinking through one case trying to convince myself that prefix domain separation really works. (Pointed out by, who else? @reyzin :+1:).

The issue is that the adversary obviously can compute b_0 on its own and try to somehow force a collision. For example, imagine that we have a protocol that calls hash_to_field on some (msg,dst) pair that the adversary knows, and in some other place in the protocol allows the adversary to generate a hash input, like H(DST2 || msg2). If DST2 is short, the adversary can grind (msg,dst) pairs until he gets a b_0 value that collides with DST2 and then set msg2 to b_0_remaining || I2OSP(1, 1) || DST_prime. This will cause the H invocation to output exactly the same value as b_1 inside of expand_message_xmd, which is bad if H is supposed to be an independent random oracle. (Here, let b_0_remaining be the string such that b_0 = DST2 || b_0_remaining.)

The way to handle this with the current xmd design is to make sure DST2 is reasonably long (preferably an entire block). Then the attacker has to break the hash function to cause b_0 to collide with DST2.

An alternative would be to slightly tweak the xmd design, in particular, doing something like

F_pad = 0xFF..FF   // one block long; any fixed value other than 0 works
b_1 = H(F_pad || b_0 || I2OSP(1, 1) || DST_prime)
b_i = H(F_pad || strxor(b_0, b_(i-1)) || I2OSP(i, 1) || DST_prime)

Then every invocation of H has a fixed (non-adversarially-controlled) block at the front, which trivially means that we get domain separation from any prefix DST not equal to the padding block. As now, implementors can optimize by precomputing h(IV, F_pad) and then using this value as the IV; so it's possible to avoid the cost of the extra padding.

I don't love the idea of changing XMD again, though...

[kwantam]

OK, I thought about it some more. I don't think we should change xmd, because there's basically no way to make this completely foolproof with M-D hashes.

I think the right thing to do is to split it into two cases:

• suffix domain separation: this is fine. For M-D hashes, the calling protocol still has to be sure that length extension attacks are not a problem in their use of the hash. If in doubt, an easy and safe way to do this is simply to use expand_message_xmd with a different DST and the desired output length (presumably something like 1 hash output length).

• prefix domain separation: this is fine as long as the length of the prefix domain separation tag used in the invoking protocol is at least k bits, for k the security parameter (e.g., 16 bytes for 128-bit security).