FIPS 202/SHAKE: insecure 3DES key derivation example

Question

I'm trying to understand the following passage from FIPS 202 (the SHA-3 standard), discussing the SHAKE functions' correlated outputs for different output lengths and the risks they induce in some protocols. The example they give is this (appendix A.2, "Additional Consideration for Extendable-Output Functions," p. 25):

[A] naïve (and non-approved) way for two parties to agree to derive a 112-bit Triple DES key from a message designated as $keymaterial$ would be to compute $SHAKE128(keymaterial, keylength)$, where $keylength$ is 112. However, if an attacker is able to induce one of the parties to use a different value for $keylength$, say 168 bits, but the same value for $keymaterial$, then the two parties will end up with the following keys:

• $SHAKE128(keymaterial, 112) = \mathbf{fg}$
• $SHAKE128(keymaterial, 168) = \mathbf{fgh}$,

where the bolded letters of the digest represent 56-bit strings, e.g., the parts of a Triple DES key.

Because of the structure of Triple DES, these keys are vulnerable to attack.

I'm trying to understand this example more concretely. So far what I can make out is this scenario:

• Alice and Bob have established a shared secret $keymaterial$, and are now supposed to both compute $SHAKE128(keymaterial, 112) = fg$, and instantiate 3DES with keys $f, g, f$.
• Eve however tricks Alice into computing $SHAKE128(keymaterial, 168)$. So now:
  • Alice's encryption function is $E^{3DES}_{f, g, h} = E^{DES}_f \circ D^{DES}_g \circ E^{DES}_h$;
  • Bob's decryption function is $D^{3DES}_{f, g, f} = D^{DES}_f \circ E^{DES}_g \circ D^{DES}_f$.
• The composition of Alice's encryption and Bob's decryption functions is $D^{3DES}_{f, g, f} \circ E^{3DES}_{f, g, h} = (D^{DES}_f \circ E^{DES}_g \circ D^{DES}_f) \circ (E^{DES}_f \circ D^{DES}_g \circ E^{DES}_h)$.
• Simplifying adjacent inverses in that equation, we get $D^{3DES}_{f, g, f} \circ E^{3DES}_{f, g, h} = D^{DES}_f \circ E^{DES}_h$.
• This function is vulnerable to a meet-in-the-middle attack.

If I'm on the right track here at all, where I'm getting stuck is: what larger scenario allows Eve to take advantage of this? I can picture this scenario:

• Eve has these powers:
  • Trick Alice and Bob into misderiving their 3DES keys as described;
  • Choose messages for Alice to encrypt and observe Bob's decryptions of them.
• Eve uses these to mount a meet-in-the-middle attack that recovers $f$ and $h$ in $2^{57}$ time.

So now Eve knows that $SHAKE128(keymaterial, 168) = fgh$ for some unknown $g \in \{0, 1\}^{56}$. This certainly allows Eve to bruteforce $g$ within an additional $2^{56}$ tries, but if $SHAKE128$ is preimage-resistant it should still be difficult for Eve to recover $keymaterial$. So are the dangerous scenarios those where $keymaterial$ is a long-term key, so that Alice and Bob will communicate many times with the same derived $f$ and $g$?

(I worry this might be a bit of a yes/no question, but I figure I must have something wrong above...)

Answer 1

There may well be situations where Eve does not have to trick anybody; in the scenario in FIPS 202 the parties badly use the XOF so the mistake is not necessarily triggered by Eve.

---

The equations in your question are really not needed. My guess is that you're making it more complex than it needs to be.

Say that Alice and Bob use 3DES with 2 keys $f$ and $g$ then attacking that two-key 3DES key means overcoming a security strength of ~80 bits (given that the chosen plaintext attacks on 2 key 3DES are possible, but hey, we're not excluding any attack here).

Once key $f$ and $g$ are known the key $h$ can simply be brute forced, as single DES only has a strength of 56 bits - the strength of DES itself. However, that means a maximum number of operations of $2^{80} + 2^{56}$, not $2^{80} \times 2^{56}$. In other words, the resulting scheme has a strength of ~80 bits instead of the promised 112 bits offered by three-key 3DES. Removing 32 bits of security certainly counts as a break in any scheme.

---

The final conclusion that you've written down: that this would be mainly an issue with long-term (or at least often used) keys seems correct.

The point that the FIPS document tries to make is that you should not ever reuse output of the XOF, even if the output size differs - for example when used as underlying function of a Key Derivation Function (KDF).

This indeed has nothing to do with the security of the XOF itself.

Answer 2

My cursory glance says you are absolutely correct in your assumption, which is why the example was given in FIPS-202 to begin with, because it is problematic.

$keymaterial$ would still be safe, but $f$ and $h$ are recoverable, which would then allow a bruteforcing of $g$, all in a practical amount of time. If Alice and Bob realize the problem, they may not assume it is malicious, and simply fix the key derivation to be correct, not realizing they are now vulnerable. This is exacerbated by protocols with known blocks of predictable data, so that an attacker would not need to force a party to encrypt a specific message.

They even give a method of eliminating the problem, which is to include the length or type (EDE2 vs EDE3) of the output as part of $keymaterial$, so that the outputs are no longer related.