Cryptography
key-derivation sha-3 meet-in-the-middle-attack xof
Updated Sat, 21 May 2022 14:17:35 GMT

FIPS 202/SHAKE: insecure 3DES key derivation example


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] nave (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...)

Solution

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.

Comments (4)

  • +0 – $2^{80}$ + $2^{56}$ is $2^{80.000000086}$, so round down? — Jan 04, 2017 at 10:58  
  • +0 – @RichieFrame Ah, yes, now I was off by a bit (which shows I'm a developer I guess, off by one error :P) - fixed, thanks. — Jan 04, 2017 at 10:59  
  • +0 – Changed the final section to more directly answer the question. — Jan 04, 2017 at 15:22  
  • +0 – "The point that the FIPS document tries to make..." - I think the point it was trying to make with the example is domain separation (or lack thereof) (quoting from the document, Section A.2): "... the output length for an XOF does not affect the bits that it produces, which means that the output length is not a necessary input to the function". I believe the domain separation by digesting output size happens in cSHAKE. — Feb 13, 2019 at 23:26  

External Links

External links referenced by this document:

References