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`C`

is a function of plaintext blocks_{n}`P`

_{0},…,P_{n} - The application returns
`E`

, where_{K}(P||S)`P`

is a prefix chosen by the adversary and`S`

is a secret appended by the application

`E`

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._{K}

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

- 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`C`

as the target_{0} - Solve for
`S0`

by submitting at most 255 chosen prefixes`p||x`

, until the output equals`C`

_{0}

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:

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

?

The steps are very similar:

- 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`C`

as the target_{0} - Solve for
`S1`

by submitting at most 255 chosen prefixes`p||S0||x`

, until the output equals`C`

_{0}

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 `C`

:_{1}

- Submit a prefix
`p`

consisting of`b - 1`

bytes of padding (e.g., all 0s); save the resulting ciphertext block`C`

as the target_{1} - Solve for
`S8`

by submitting at most 255 chosen prefixes`p||S0||⋯||S7||x`

, until the output equals`C`

_{1}

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:

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.

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:

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).

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.