Chosen prefix, secret suffix attack

Imagine an application and encipher oracle with the following properties:

EK is the encipher oracle; e.g., session-based SIV with static metadata, CBC with a static IV, or even a session-based nonceless MAC function. Believe it or not, it is possible for the adversary to recover the complete secret with minimal effort involving only the encipher direction! In this article, I will show how this attack works.

Recovering the first byte of the secret

The main property that allows this attack to work is low entropy; i.e., the reuse/lack of a nonce. The steps:

  1. Submit a prefix p consisting of b - 1 bytes of padding (e.g., all 0s) to allow the first byte of the secret to flow into the block; save the resulting ciphertext block C0 as the target
  2. Solve for S0 by submitting at most 255 chosen prefixes p||x, until the output equals C0

For sake of clear visualization, let's use a block length of b = 8 bytes, but it is important to note that this attack will work on any block length. This process is visualized as follows:

CPSS

Ouch. This was a little too easy; how do we find the second secret byte S1?

Recovering the second byte

The steps are very similar:

  1. Submit a prefix p consisting of b - 2 bytes of padding (e.g., all 0s) to allow the first two bytes of the secret to flow into the block; save the resulting ciphertext block C0 as the target
  2. Solve for S1 by submitting at most 255 chosen prefixes p||S0||x, until the output equals C0

CPSS

Recovering the remaining bytes

We simply repeat the above process in order to recover the first block of the secret (S0 through S7), but how do we recover the next byte S8? The steps are similar, except that now we are comparing against the second ciphertext block C1:

  1. Submit a prefix p consisting of b - 1 bytes of padding (e.g., all 0s); save the resulting ciphertext block C1 as the target
  2. Solve for S8 by submitting at most 255 chosen prefixes p||S0||⋯||S7||x, until the output equals C1

CPSS

Mitigating the attack

As stated earlier, the enabling factor is low entropy. The correct way of fixing this is to enforce a nonce in the encipher oracle. If this is absolutely not possible, then the application can carefully apply domain separation in every plaintext block. One simple way of accomplishing this is to encode the total number of bytes in the block that represent part of the prefix. By doing this, the attack no longer works:

CPSS

Note that this solution is not ideal, as it requires the application to be aware of specific properties of the encipher oracle (e.g., the block width). Using a nonce is the more universal and elegant solution.

A similar attack

Consider an application that allows the adversary to overwrite the prefix of a secret with a chosen value, instead of concatenating the two values together. A similar attack works:

CPSS

Enforcing a nonce in the encipher oracle mitigates this attack on the cryptographic layer. If the application is designed improperly, this attack may still be possible at the application layer. Consider the example of an improperly implemented password field. If the adversary can replace one byte at a time, then once the correct byte has been found, the application may exhibit a desired behavior (e.g., a successful login).

Conclusion

While the described attacks require somewhat specific circumstances in order to work, it is a sobering reminder of what is possible when nonces are omitted or reused. Both attacks require only a linear number of online queries with respect to plaintext length.