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).
• If you start with full block IV, counters may overlap.

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.

If you can say there's a limit on the amount of data that gets encrypted in a single stream, you can split the IV into a random part and a counter part (e.g. 64 bits of random, generated once per stream) and the counter part (starting at 0). You can split it anyway you want, you just need to worry about the birthday problem for the random size.

Or just use a different key for each stream and start the counter at 0. Never need to worry about overlap in that situation.