Imagine an application and encryption oracle with the following properties:
b-byte blocks; ciphertext block
Cnis a function of plaintext blocks
Pis a prefix chosen by the adversary and
Sis 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.
The main property that allows this attack to work is low entropy; i.e., the reuse/lack of a nonce. The steps:
b - 1bytes of padding (e.g., all 0s) to allow the first byte of the secret to flow into the block; save the resulting ciphertext block
C0as the target
S0by submitting at most 255 chosen prefixes
p||x, until the output equals
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:
Ouch. This was a little too easy; how do we find the second secret byte
The steps are very similar:
b - 2bytes 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
C0as the target
S1by submitting at most 255 chosen prefixes
p||S0||x, until the output equals
We simply repeat the above process in order to recover the first block of the secret (
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
b - 1bytes of padding (e.g., all 0s); save the resulting ciphertext block
C1as the target
S8by submitting at most 255 chosen prefixes
p||S0||⋯||S7||x, until the output equals
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.