Chosen prefix, secret suffix attack

Imagine an application and encryption oracle with the following properties:

  • Nonce reuse resistance: reusing a nonce does not immediately result in keystream reuse
  • Online: the plaintext is split into b-byte blocks; ciphertext block Cn is a function of plaintext blocks P0,…,Pn
  • The application returns EK(P||S), where P is a prefix chosen by the adversary and S is a secret appended by the application

EK is the encryption 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 using only the encryption 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 the 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 encryption 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 encryption 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 individual bytes of a secret with a chosen value, instead of concatenating the two values together. A similar attack works:

CPSS

Enforcing a nonce in the encryption oracle mitigates this attack at 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.