0
$\begingroup$

The use of an increasing IV is not secure for a block cipher. That is, using a random IV for the first message then $\operatorname{IV} + 1$ for the second , $\operatorname{IV}+ 2$ for the 3rd etc. How can I construct an attack to show that this mode is not secure?

$\endgroup$
  • 2
    $\begingroup$ Just for terminology, the main problem here is having a predictable IV. crypto.stackexchange.com/questions/3883/… $\endgroup$ – eckes Mar 30 '19 at 16:39
  • $\begingroup$ The use of an increasing IV is not secure for a block cipher. No that depends on the mode of operation, mainly CBC is not secure, but other modes like GCM mode it is secure (i.e. the IV is a nonce). Block ciphers themselves do not have an IV as input. $\endgroup$ – Maarten Bodewes Aug 23 at 22:58
2
$\begingroup$

A block cipher, per se, does not have a notion of initialization vector. But a randomized or stateful message cipher may. If you're building an application, you should forget the concept of ‘block cipher’ altogether: the fact that some cryptographic magic is built out of a pseudorandom permutation family whose name is spelled A-E-S is not important to you; the security contract of the result, including your obligations and the security you get in exchange, is what's important.

  • For a randomized cipher like AES-CBC, your obligation in the security contract is to choose an IV unpredictably.

    If, given the first message's IV, the adversary can guess the second message's IV, the security contract is voided. This mistake was exploited to recover plaintext in ssh sessions in 2009[1] (paywall-free).

  • For a stateful cipher like AES-CTR, your obligation in the security contract is typically to choose a nonce uniquely, which you can do by counting. (The ‘nonce’, for number used once, is sometimes called an ‘IV’, but some authors—like this one—prefer to reserve the term ‘IV’ for unpredictable ones.)

    It does not matter if the adversary can predict the nonce in advance, as long as the sender never repeats a nonce. As a bonus, you can immediately detect buggy implementations by having the receiver require the nonces to be sequential.

One can always safely use state to choose the IV for a randomized cipher, by deriving it by a pseudorandom function of the number of messages so far; and one can choose a nonce randomly for a stateful cipher, but at risk of nonce collision, so it's not so safe.

All this said, you should really use an authenticated message cipher. Even if an adversary can't read secrets in an encrypted message by eavesdropping, without authentication you might act on adversary-controlled input which causes secrets to leak. Examples of authenticated ciphers include:

  • AES-GCM, with a message sequence number for the 96-bit nonce;
  • NaCl crypto_secretbox_xsalsa20poly1305, with a message sequence number or uniform random nonce, since the 192-bit nonce is large enough to be safely chosen uniformly at random; or,
  • if you must use AES-CBC, at least use it in encrypt-then-MAC composition with HMAC-SHA256 or similar, and the sender must choose the IV unpredictably for each message.
| improve this answer | |
$\endgroup$
  • $\begingroup$ I think the part about CTR does not distinguish the nonce, the IV and the counter used within CTR, to be honest. The nonce is usually just part of the counter value, and the IV is generally the full block size in API's. Generally those use an unsigned big endian counter, so the nonce will be the leftmost bytes within the IV, which is simply the initial counter. The danger is that you can have a unique IVs of 16 bytes, that still manage to repeat counter values if they are too close. $\endgroup$ – Maarten Bodewes Mar 30 '19 at 22:34
  • $\begingroup$ I'm not addressing any internals of AES-CTR. You feed it a message up to (say) 4 GB and a 96-bit nonce (as in AES-GCM), and it returns a ciphertext which is secret as long as you don't repeat the nonce. The fact that there is a per-block counter inside it is just as much an irrelevant implementation detail as the fact that there's a pseudorandom permutation family inside it. As a matter of usage, a message sequence number, i.e. a count of the messages so far, is a very good way to choose a nonce. $\endgroup$ – Squeamish Ossifrage Mar 30 '19 at 22:58
  • $\begingroup$ Also, while the name ‘AES-CTR’ doesn't imply any particular formatting of the AES input, if you're doing $m \oplus \bigl(\operatorname{AES}_k(n) \mathbin\| \operatorname{AES}_k(n + 1) \mathbin\| \operatorname{AES}_k(n + 2) \mathbin\| \cdots\bigr)$ where $n$ is the nonce and $+$ is addition rather than concatenation, you're doing it wrong and violating the security contract that essentially everyone understands the name ‘AES-CTR’ to have, because this is not a nonce-based cipher: it is not enough that $n$ be unique. If you know of APIs that do this, please send them my stern vituperation. $\endgroup$ – Squeamish Ossifrage Mar 30 '19 at 23:05
2
$\begingroup$

How can I construct an attack to show that this mode is not secure?

I assume you're asking about CBC mode (you didn't specify), and while this smells like a homework question, it's been long enough for the assignment to have been due, and so I'll just give you the answer.

What you do is ask to encrypt three consecutive messages, and the first block of the first message has the value $X$, the first block of the second message has value $X \oplus 1$ and the first block of the third message has the value $X$. It doesn't matter that $X$ is, and it doesn't matter what the rest of the messages are.

Because of how CBC works, the first block of the three encrypted messages are the values:

$$AES_k( IV \oplus X )$$

$$AES_k( (IV+1) \oplus (X \oplus 1))$$

$$AES_k( (IV+2) \oplus X) $$

If the lsbit of $IV$ happens to be 0, the $IV+1 = IV \oplus 1$ (as the internal carry in the addition doesn't propagate beyond the lsbit), and so $(IV+1) \oplus (X \oplus 1) = IV \oplus X$, that is, the initial blocks of the first and second ciphertext messages are the same, which can be tested.

And if the lsbit of $IV$ happens to be 1, then the lsbit of $IV+1$ will be 0, and so we have $(IV+2) \oplus X = ((IV+1) \oplus 1) \oplus X = (IV+1) \oplus (X \oplus 1)$ and so the initial blocks of the second and third ciphertext messages are the same, which can also be tested.

So, this shows that the construction does not meet IND_CPA security.

| improve this answer | |
$\endgroup$

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