1
$\begingroup$

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.

$\endgroup$
0

2 Answers 2

2
$\begingroup$

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.

$\endgroup$
2
$\begingroup$

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!

$\endgroup$
7
  • $\begingroup$ "Exceeding the 64 GiB limit per message instead of generating a new IV is safe: it only decreases this probability." You'd still use a single other IV value, right? And compared to smaller messages there is still a higher chance. I don't get that part, could you explain? $\endgroup$
    – Maarten Bodewes
    Aug 10, 2023 at 14:08
  • $\begingroup$ @MaartenBodewes: I'm comparing strategy A of generating a new uniformly random IV when we reach the 64 GiB limit, to strategy B of keeping on incrementing the whole counter, at equal total amount of data encrypted, and equal amount of IV generation for other causes than exceeding the 64 GiB limit (e.g. different encryption units, resets). The strategy B strictly decreases the probability that there is counter reuse, assuming that the 64GiB limit is exceeded at least once, and there's not so much data that counter reuse is certain. I'll illustrate with $2^{16}$×4 PiB (4 PiB=$2^{48}$ blocks). $\endgroup$
    – fgrieu
    Aug 10, 2023 at 16:04
  • $\begingroup$ With strategy A there are $n=2^{32}$ IV generations, and the probability that any two distinctly generated collide is $p=2^{-96}$, leading to about $p\,n(n-1)/2≈2^{-33}$ of colliding counter. With strategy B there are $n=2^{16}$ IV generations, and if another IV is within $2^{16}-1$ of another there will be a collision. Thus the probability that any two distinctly generated IV values cause a collision is $p=(2^{17}-1)/2^{96}≈2^{-79}$, and now probability of colliding counter is $≈p\,n(n-1)/2≈2^{-48}$. That probability is decreased by $≈2^{15}$ in strategy B. @MaartenBodewes $\endgroup$
    – fgrieu
    Aug 10, 2023 at 16:18
  • $\begingroup$ @fgrieu "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." -- well, the idea is to enable simple, random 128-bit IV's for CTR mode that only get incremented without dividing anything into any "special nonce/counter" pairs or sections, but while still avoiding the partial overlap problem. $\endgroup$
    – ManRow
    Aug 12, 2023 at 5:31
  • 1
    $\begingroup$ @ManRow: there's no doubt that assuming a good TRNG, your proposed technique reduces the possibility of exploitable counter overlap compared to CTR in whatever variant of IV initialization and strategy for long plaintext, often in a significant proportion. My point is that exploitable counter overlap in CTR with sound split of IV and counter part practically only occurs when we do not use a good TRNG. A point could be made that assuming a good TRNG, your proposed technique's main practical advantage is that it helps against key leak by side channel. $\endgroup$
    – fgrieu
    Aug 12, 2023 at 7:30

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.