Encrypting random IV in CTR mode (no nonce!)

Question

Use of plain random-IV's in CTR mode, without any special "nonces/counters" (or any "dedicated" bits!), can lead to problems with "partial overlaps", whereby attackers can execute known-plaintext-attacks if there is a collision in the keystreams used for encryption.

But, what if we just simply use that random IV also as the "key" as well? For example, let's say $K$ is our original key and we generate a random initialization vector $K' = IV$ to encrypt some plaintext $P$. The ciphertext would simply be $$C = E_K(K') \; || \; \text{CTR}_{K'}(P)$$

where

• $E_X(P)$ = ECB-encrypt $P$ with key $X$, and
• $\text{CTR}_X(P)$ = CTR-encrypt $P$ with key $X$ and a "zero" initialization vector (all zeroes).

Likewise, to decrypt $C$, we only run $D_K(C_1)$ once to retrieve $K'$, and then simply decrypt the rest of $C$ as usual with key $K'$. This allows for parallel encryptions and decryptions just like in CTR mode as well (as only 1 $D_K(C_1)$ operation is required to retrieve $K'$ for any length of message).

Thus, while an attacker may know a specific initial block $E_K(K')$ and ensuing "keystream" $$E_{K'}(0), E_{K'}(1), \ldots, E_{K'}(m)$$

they'll have no way of "linking" it to any unknown plaintext-ciphertext pair, which itself could simply use any other random $K^{\prime\prime} \ne K^\prime$. And also, because all $K,K^\prime,K^{\prime\prime},\ldots$ are kept secret from the attacker anyway, and aren't expected to repeat either...

---

*Edit: for reference, I'd be using a strong 128-bit cipher like AES here that would be hard to brute-force...

*Edit #2: it turns out we can simply use a zero-IV in the $CTR$ step since every message gets encrypted with a different "message key" anyway.

Answer 1

For one, you wouldn't call it an IV, it would be a data or message key. And we'd generally use a key wrapping mechanism or a KDF instead of encrypting the data key using a single block encrypt. Otherwise: yes, using different keys is one of the tricks to get around limitations of a mode of operation.

I'd personally try and use more random bits and AES-256 in this case because otherwise a collision of keys would be easy to detect and multi-target attacks could become easier as well. You could also still use, say, a random IV.

Answer 2

Contrary to "no nonce!" in the title, the proposed system does assume the "random initialization vector" $K'$ is a number used once. A reuse of $K'$ leads to keystream reuse in the CTR part. Further, such reuse is readily detectable by identical $E_K(K')$ at start of $C$, thus exploitation of reused $K'$ is just as feasible as exploitation of IV reuse in traditional CTR mode.

I argue that in standard CTR practice (described below), IV reuse is by far the most likely cause of counter reuse, thus the proposed system does not markedly reduce the risk of exploitation of counter reuse.

In standard practice, the IV is 96-bit, the counter is a 128-bit block, and is preset to the IV times $2^{32}$, such that counter reuse will occur only if

• there is IV reuse
• or the plaintext is more than $2^{32}$ 128-bit blocks without change of IV, and some further (unlikely) condition on IV is met.

It follows that

• For plaintexts each no more than 64 GiB (larger than a dual-layer Blu-ray Disc), the only possible cause of counter reuse is IV reuse.
• For uniform random choice of IV and plaintexts limited to 64 GiB, the probability that counter reuse becomes a security threat is less than $2^{-33}$ (at time of writing: less than the probability that a random person on earth happens to be you) after $2^{32}$ (>4 billions) plaintext are encrypted with the same key.
• Exceeding the 64 GiB limit per message instead of generating a new IV is safe: it only decreases this probability (see these comments).

Therefore, with said standard practice, the only likely cause of counter reuse is IV reuse due to improper method to generate the random IV. E.g. using a defective TRNG, which many times has led to attack.

I see no reason why such mishap would be much less likely when generating the question's $K'$ than when generating a traditional random IV. Also, in the question, a guess of $K'$ is disastrous, when a guess of the IV in CTR mode is usually moot (the worse I can think of is allowing to detect when encryption was made, or enabling some real-time power analysis attack without having to store the acquired samples until the counter is known). Thus securely generating $K'$ can be more difficult than securely generating an IV.

More generally, when we have to fear that we can't generate a random number, we are in trouble. If we are confident that we can make a reliable long-term session counter $C$ that adversaries won't be able to tamper with, and that we can keep secret in the long term an auxiliary random key $K_\text{aux}$, an option to consider is to generate the random number (be it IV or $K'$) by incrementing $C$ then encrypting $C$ with $K_\text{aux}$. However, that's not clearly easier than reliably generating random numbers in the first place!