8
$\begingroup$

It is said that a predictable IV is dangerous, because you can do adaptive chosen plaintext attacks. But if the IV is never seen to the attacker, is it still dangerous? What I mean, is that the IV is predictable - it is incremented for every message, but never communicated - the attacker only knows it increases by one, but not the exact value. Can they still attack from that information alone?

Edit: I'm asking if it is ok to just increment the IV for every message given that the attacker doesn't know the initial IV

Improve this question
$\endgroup$
8
  • 2
    $\begingroup$ The IV doesn't have to be secret so I'm not sure what your question is. Can you elaborate more on these attacks? $\endgroup$
    – Elias
    Commented Jan 29, 2017 at 20:21
  • 1
    $\begingroup$ Also see: crypto.stackexchange.com/q/3883/23623 $\endgroup$
    – SEJPM
    Commented Jan 29, 2017 at 20:32
  • 1
    $\begingroup$ Bit with crypto.stackexchange.com/q/3883/23623 the attacker knows the IV, while in here they only know it is the previous one incremented by one, but don't know the previous IV $\endgroup$
    – Kethan
    Commented Jan 29, 2017 at 20:34
  • 2
    $\begingroup$ Consider messages where the first block only differs in the bit corresponding to the least significant bit of the counter in your IV. $\endgroup$
    – CodesInChaos
    Commented Jan 29, 2017 at 21:00
  • 1
    $\begingroup$ You can simply encrypt the counter first. Then the output becomes unpredictable again. $\endgroup$
    – Maarten Bodewes ♦
    Commented Jan 29, 2017 at 23:35

1 Answer 1

Reset to default
12
$\begingroup$

If a nonce $N_i$ is even, then the binary numeral for it its increment $N_{i+1} = N_i + 1$ differs from $N_i$ only in its least significant bit; and if $N_i$ is odd, its increment is even. This means we can adapt chosen-plaintext attacks against CBC with counter nonces (e.g., from section 4 of this Rogaway paper) to target your scheme. Given an block cipher $E_k$ with random secret key $k$ and block size $n$, a secret initial nonce $N_1$, and nonce generation rule $N_i = N_{i-1}+1 \mod 2^n$ known to the attacker:

  1. Ask the oracle to encrypt $0^n$ (the one-block plaintext with all zero bits), getting back $C_1 = E_k(N_1 \oplus 0^n)$.
  2. Ask the oracle to encrypt $0^{n-1}1$ (the one-block plaintext with all zero bits except for the least significant), getting back $C_2 = E_k(N_2 \oplus 0^{n-1}1)$.
  3. Ask the oracle to encrypt $0^n$ again, getting back $C_3 = E_k(N_3 \oplus 0^n)$.
  4. If either $C_1 = C_2$ or $C_2 = C_3$, the attacker knows with high probability they're talking to an encryption oracle. Otherwise the attacker knows they're talking to a random oracle.

Proof. If $N_1$ is even, then its least sigificant bit is $0$, meaning that $N_2 = N_1 \oplus 0^{n-1}1$, and then, given that $C_2 = E_k(N_2 \oplus 0^{n-1}1)$:

$$ \begin{align} C_2 &= E_k(N_1 \oplus 0^{n-1}1 \oplus 0^{n-1}1) \\ C_2 &= E_k(N_1) \\ C_2 &= E_k(N_1 \oplus 0^n) \\ C_2 &= C_1 \end{align} $$

If $N_1$ is odd, its least sigificant bit is $1$, $N_2$'s is $0$, and $N_3$ differs from $N_2$ only in its LSB: $N_3 = N_2 \oplus 0^{n-1}1$. So given that $C_3 = E_k(N_3 \oplus 0^n)$:

$$ \begin{align} C_3 &= E_k(N_2 \oplus 0^{n-1}1 \oplus 0^n) \\ C_3 &= E_k(N_2 \oplus 0^{n-1}1) \\ C_3 &= C_2 \\ \end{align} $$

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.