Score:3

Proper use of AES CTR

cn flag

I've read that AES CTR is only safe if used properly. Therefore, I want to be sure that I use it properly.

  1. The initial vector (IV) can only be used once, it doesn't have to be random. Is it secure to use a counter for one part of the IV, the other part is just some const text. The counter is transmitted to everyone in clear text, while the sensitive part of the message is encrypted. Is it a problem that the next IV is predictable?
  2. I understand that the IV can never repeat, but just in case how many iterations of this condition are required to crack the system. I mean two repeats of the same counter or 100?
  3. Last but not least, does it increase security to use AES-256 over AES-128 to encrypt a 16-byte message?
Score:2
in flag

Here we made a distinction. $nonce \mathbin\|counterpart$ constitutes the $IV$

  • Is it a problem that the next IV is predictable?

No, it is not a problem in the CTR mode, read more in [1]. The $IV= (nonce\mathbin\|counterpart)$ is encrypted and the ciphertext is x-ored with plaintext.

$$C_i = \operatorname{AES-CTR}(nonce\mathbin\|encode(i)) \oplus P_i$$

As long as the $(IV,key)$ pair never repeats there is no problem for your 16-byte assuming that you always start from 0 in the counter for every encryption with a new nonce or new key.

If there is a repeat then the confidentiality is lost.

I understand that the IV can never repeat, but just in case how many iterations of this condition are required to crack the system. I mean two repeats of the same counter or 100?

Two pair is enough to break the confidentiality with crib-and-dragging techniques. It is now automated [2]. If you know one of them then it is trivial to find the other with x-or.

Last but not least, does it increase security to use AES256 over AES128 to encrypt a 16-byte message?

CTR mode is CPA secure as long as it is used properly. AES-128 is secure (mostly)[3] however using AES-256 it will be secure even the quantum adversaries supplied with Grover's Machine.


Note that with CTR mode you can only get CPA security i.e. there is no integrity and authentication. To achieve integrity and authentication one can use AES-GCM(with SIV). SIV mode uses the message to avoid the IV issue. When the IV repeats it leaks only equality of the messages, not the contents.

Proper use of AES CTR

Your obligations: as security contract

  • Select uniform random key $k$ of size 256 and keep it secret, all the time.

  • Select IV and make sure that $(k,IV)$ never repeats even the counter incremented;

    • use a deterministic counter or LFSR to keep the track of the $nonce$, make sure that a new key is exchanged if there is an error/system halt they may be unable to write the last used $nonce$.

    • Or, use random $nonce$, make sure that you are low on the collision of the $nonce$ under the same key.

    • Always start the counter from $0$. If the counter does not start from $0$ there is a dangerous path that may lead IV to repeat if the nonce is the same.

  • Encrypt the message and make sure that it is no longer than $2^{32}$.

    • Guarantee that there is no distinguisher, and
    • Guarantee that the counter never passes all 1 state i.e. never exceed the counter's max value.
  • Store it.

What you get

  • Ind-CPA security and nothing more!

Instead one can use XChaCha20-Poly1305 with 192-bit nonces that the $(IV,key)$ occurrence is negligible. You will get authentication and integrity, too. And since CTR mode is designed for PRFs, XChaCha20 is better to be used with CTR mode ( XChaCha20 uses CTR internally).


Gilles 'SO- stop being evil' avatar
cn flag
No! For CTR, it is not enough for the IV not to repeat. The **counter value** must not repeat.
kelalaka avatar
in flag
@Gilles'SO-stopbeingevil' stop being your nick. Firstly, we are talking about 16-byte, second I said "Guarantee that the counter never passes all 1 state." Where it is said that continue a counter value?
Maarten Bodewes avatar
in flag
I can see how the use of the term IV is used for Nonce + counter, as the IV is only used as initial value - it is the initialization vector after all. As it is defined, the 16 bytes are better named the *counter block*, consisting of the nonce + counter. @Gilles'SO-stopbeingevil' If you adhere to NIST definitions, then just repeating the counter is not sufficient either, as that's only part of the input / counter block, so yeah, terminology.
Gilles 'SO- stop being evil' avatar
cn flag
@MaartenBodewes If you split the counter block into a per-message nonce and a per-block counter value, then the requirement becomes that the per-message nonce does not repeat and that the per-block counter value does not overflow. Not all presentations of CTR mode do that. This answer explicitly defines “IV” as the full initial block consisting of the nonce concatenated with a counter, and it is not enough for _that_ to be unique: the nonce part must be unique. Repeating the nonce with different initial counter values is not sufficient.
kelalaka avatar
in flag
@Gilles'SO-stopbeingevil' the point is I'm well aware of that problem and for 16 byte that was not a problem. I never said to continue a counter value or use a different counter value. The counter starts from 0, continuing to a counter is a dangerous path and not a good security perspective that increases the number of pitfalls. Now, I've made a distinction between the counter and counter part of the IV.
Gilles 'SO- stop being evil' avatar
cn flag
In the highly specific case where all messages are (at most) one block long, then yes, IV and counter value are the same. But that's a very special case which the question is not clearly restricted to (it only comes up in one sub-question). Your answer is now correct from a strict mathematical point of view, but it's still highly misleading since the fact that it's specific to the case of single-block messages, which is a very uncommon scenario, is barely apparent.
kelalaka avatar
in flag
@Gilles'SO-stopbeingevil' I've given the general case in the security contract. I don't like the idea of continuity of the counter. Well, in some constraint environments people need it so that they exchange fewer keys. Still, I don't consider them here. Start the counter from 0. Checking the wording again and again to not mislead...
Gilles 'SO- stop being evil' avatar
cn flag
No, in the general case, with the counter block structured as nonce||counterpart (which not all presentations and implementations of CTR do), the obligation is that the nonce does not repeat. And due to the limited size for the nonce, this practically requires to keep track of previously used nonces, which is not always doable. It's a pitfall of CTR which users tend to get wrong, and your answer encouraged them to get it wrong.
kelalaka avatar
in flag
@Gilles'SO-stopbeingevil' It is possible that one can combine random and container to form nonce, though this requires computation and that requires the life of the key and the number of messages per key. As I said, if there is a problem, exchange a new key. My general advice is to use xChaCha since it has a better nonce range. As Lindell once said, 256-bit block is necessary so that we can have better CTR and GCM bounds. I don't think that I'm leading them to the pitfall, I've already restricted them not to fall into one.
au flag
Also to mention, note that (per design) CTR uses the same algorithm for encryption and decryption. This could lead to unauthorized decryption in some contexts (although that does require to repeat an IV).
Score:1
cn flag

For CTR, the requirement is that the counter value does not repeat (for a given key). The biggest gotcha with counter mode is that it is not enough for the IV (the initial counter value) not to repeat.

It doesn't matter whether the counter value is predictable. If you can arrange for the counter to start at 0 and to increase by 1 for each message block, that's a very good way of using CTR. Note that with multiple messages, this means that the first message uses the counter values $0, 1, 2, \ldots, a$, then the second message uses counter values $a+1, a+2, \ldots, b$, the third message uses $b+1, b+2, \ldots, c$, and so on.

Let me illustrate what goes wrong with a repeating counter value. Let $E$ be the block encryption function and write $\langle n\rangle$ for the encoding of a counter value $n$ as a block. If you send two two-block messages $P_0||P_1$ and $P'_0||P'_1$ (where each $P^{(j)}_i$ represents one block), one with the IV $n$ and the next one with the IV $n+1$, then the respective ciphertexts are $C_0||C_1 = (E(\langle n\rangle) \oplus P_0) || (E(\langle n+1\rangle) \oplus P_1)$ and $C'_0||C'_1 = (E(\langle n+1\rangle) \oplus P'_0) || (E(\langle n+2\rangle) \oplus P_1)$. Note how both these ciphertexts use $E(\langle n+1\rangle)$. An adversary can xor the two ciphertext blocks that use the same counter value, and their encryption mask cancels out: $C_1 \oplus C'_0 = P_1 \oplus P'_0$. This is often enough to guess some or all of the plaintext blocks. For example, many messages contain a known or mostly-known header, and in this example of repeating the counter value this turns into revealing the content of what's 16 bytes after the header in the first message.

If you can't keep track of which counter values have been used, a common technique to avoid repetition is to use a 16-byte random for the IV. This makes the chance of reusing a counter value small enough that it won't happen in practice.

In most cases, you should use a standard authenticated encryption (AEAD) mode instead, for example SIV or or GCM-SIV or GCM or CCM. This has two benefits. One is that the ciphertexts are authenticated: when decrypting, you can verify that the ciphertext was not changed. (It is impossible to verify a ciphertext's authenticity without the secret key. An adversary can still swap two genuine messages, so authenticity does not quite imply integrity.) The other advantage of using a standard AEAD mode is it's enough for security that the counter value does not repeat: there are no other subtle conditions. SIV modes have the advantage that even if the IV accidentally repeats, this can only reveal that the messages are identical, it won't reveal anything about their content.

Using AES-256 rather than AES-128 only improves security against quantum computers, in case they become practical.

kelalaka avatar
in flag
We are talking 16 byte!
Maarten Bodewes avatar
in flag
Fully randomizing the IV can only make the counter repeat earlier, although the difference is relatively small - implementations usually perform a module $2^{128}$ increase of the entire block, so if one counter part is high and one of the next nonce in sequence is low then you'd have a collision before using up all possible counter values. Separating the nonce and counter is probably the best way to proceed, where the initial counter can be initialized to all-zero.
Gilles 'SO- stop being evil' avatar
cn flag
@MaartenBodewes “Fully randomizing the IV can only make the counter repeat earlier” that can't be right. For example, if you take the extreme case of a 1/127-bit split between per-message nonce and per-block counter, this guarantees a repeat of counter values on the third message at most.
Maarten Bodewes avatar
in flag
Say that you have a maximum message size of 2^32 blocks. Then you use the remaining 96 bits as a (random) nonce, and if you use a 32 bit counter to remain within the nonce; that way the increment of the counter cannot create a collision with a counter block with a different nonce. That can however happen if you fully randomize the counter block, as the distance between the counters of two subsequent nonces varies. It is of course not a question of when a repeat is guaranteed, it is about when one is possible or likely.
Gilles 'SO- stop being evil' avatar
cn flag
@MaartenBodewes This assume you can keep track of which nonces have been previously used. I only recommended to use a random IV (occupying the full block) for the case where you _cannot_ keep track of what nonces have been used, so the best you can to is for the non-repeating value to be statistically unique. There is a scenario where deterministic nonce + per-message counter is better, which is when you can keep track of message sequence numbers but don't know the message lengths in advance. That's somewhat common in communication protocols. But it's a bit too out of scope for my answer here.
mangohost

Post an answer

Most people don’t grasp that asking a lot of questions unlocks learning and improves interpersonal bonding. In Alison’s studies, for example, though people could accurately recall how many questions had been asked in their conversations, they didn’t intuit the link between questions and liking. Across four studies, in which participants were engaged in conversations themselves or read transcripts of others’ conversations, people tended not to realize that question asking would influence—or had influenced—the level of amity between the conversationalists.