# CTR overlap with random IV

Problem:

I'm slightly worried about counter repeats in CTR mode when using random IV.

• If you split it (like half IV, half counter), it increases chances of same IV (it is smaller) and limits message length (if less than half).

I would like to somehow get full block IV and half block counter without overlaps.

Proposed solution:

Instead of using random IV as nonce in counter we create new key by encrypting IV with key. We than use that new key for encryption. Counter starts with half zeros and with half of IV or with half of master key to make multi-target attacks harder.

Assume that key, IV, block cipher are all same size.

$$k_{data} = E_{k_{master}}(IV)$$

$$keystream_i = E_{k_{data}}(half(IV) || counter_i)$$

Is this any better/worse?

I'm worried this would weaken the key. Different key and IV combination would give same new key. But this is essentially like simple key derivation function with salt. This should allow every message to get up to birthday bound.

• There is already a guideline counter/LFSR NIST 800-38-a and AES CTR: Random IV Jul 12, 2021 at 21:33
• First approach is perfect, but not practical. Second approach with random IV is kinda limited to number of messages or length of messages as mentioned. Jul 13, 2021 at 6:37
• I think it is best to think of your construct as a KBKDF. In that case the question becomes: how secure is that KDF? But there are several things unclear to me. If you write $k = E_k(IV)$, do you mean that $k$ will be replaced? In that case you've created a stateful protocol. Normally you'd have a $k_{master}$ and multiple $k_{data}$. Furthermore, should we always assume 128 bit AES? A single block encrypt is not going to generate a 192 or 256 bit key. Jul 15, 2021 at 7:34
• Key is replaced only for a message. It does not change master key. I do assume that key is the same size as block cipher. Jul 15, 2021 at 7:48
• I don't know where that $half(k_{master})$ suddenly comes from, but generally you'd never include key information in your key stream. If I remember correctly you first just had a zero based counter. Jul 15, 2021 at 9:51