Modifying counter sequence in CTR mode of operation to mitigate IV+Nonce near collision

Question

The CTR mode of operation converts a block cipher into a stream cipher by having it encrypt a series of counter values (which are derived from the nonce+IV). So long as the counter values used with a given key for said block cipher never overlap* and one does not get close to the PRP-PRF distinguishing bound (where the block cipher as a keyed PRP becomes distinguishable from a PRF), the mode of operation is secure with respect to confidentiality.

However, imagine a scenario such that an attacker is able to force a near collision of the IV+nonce pair used for a given key. This means that the counter values and thus the output of the CTR's random stream will overlap. This clearly leads to a distinguisher (and attack) against CTR (You drag the two or more streams of ciphertext that use overlapping counter values and look for plaintext_1 XOR plaintext_2 or similar).

Notably, this scenario can happen because the counter always outputs from the same sequence (just from randomized starting positions). What if we augment the counter values such that it always outputs a distinct sequence for each originating start state?

For example, we can define the following generator for counter values:

#Let LCG(state, period) -> new_state be an LCG of sufficient period matching the original counter's 
# period, ie 2^128 or at least sufficiently large such that the distinguisher for the mode of 
# operation applies before the period.
#LCG() outputs it's full internal state after each update/"clocking".
def get_counter_value(start_state, state = None, period):
    if state = None:
        state = start_state
    new_state = LCG(state, period)
    output_counter_value = (new_state + start_state) % period
    return(output_counter_value, new_state)

# Then we use this in a modified version of CTR mode
def modified_ctr_mode(Block_cipher, key, nonce, IV, plaintext_blocks):
    counter_start = IV || nonce
    ciphertext_blocks = []
    counter_state = None
    period = 2**128
    for block in plaintext_blocks:
        counter_update_output = get_counter_value(counter_start, counter_state, period)
        counter_value = counter_update_output[0]
        counter_state = counter_update_output[1]
        keystream_block = Block_cipher.encrypt(key, counter_value)
        ciphertext_block = xor(keystream_block, block)
        ciphertext_blocks.append(ciphertext_block)
    return(ciphertext_blocks)

From my understanding, this function outputs a distinct and unique sequence for each starting state (i.e., IV+Nonce pair). The sequence is of sufficient period (assuming that the LCG is good in that respect) and the code ensures each sequence is different from sequences generated by other start state.

Does this mitigate the damage that can be done and if so by how much? I am interested in the case where the LCG is parameterized such that it is a good statistical PRNG (i.e., multiplier figure of merit are excellent) and when it is not (i.e., a = 5, c = 1).

EDIT: Does this modification to the derivation of the values that then get encrypted by the block cipher does preserve the same security properties of the CTR mode of operation right? I believe it does but would appreciate a double check on this.

Answer 1

CTR mode relies on each counter value being only used once, i.e. each counter value must only be used to mask a single block of plaintext. The order in which counter values are consumed does not matter. It's common to use the sequence $(\mathrm{I2B}(i), \mathrm{I2B}(i+1), \mathrm{I2B}(i+2), \ldots)$ for a given message, where $i$ is the initial counter value used to encrypt the message and $\mathrm{I2B}$ is an encoding of integers into 128-bit blocks. Generally $\mathrm{I2B}$ is the base 2 representation in either little-endian or big-endian bit order. But you could use any one-to-one function for this $\mathrm{I2B}$ encoding.

You're using the counter values $(\mathrm{I2B}(S(i)), \mathrm{I2B}(S(i+1)), \mathrm{I2B}(S(i+2)), \ldots)$ where $S(x) = R^{x-i}(i)$ and $R$ is a (non-cryptographic) pseudo-random generator. In the best case, where $R$ has a large period, $S$ is one-to-one, i.e. the sequence $(S(i), S(i+1), S(i+2), \ldots)$ takes unique values, and the security of CTR mode is preserved. There is no security advantage, however: an adversary who can control IV values (the value of $i$) can still cause an unfavorable value. In the worst case, where $R$ has a small period, the counter values will repeat, breaking the security of CTR mode.

So your scheme cannot improve security, but can reduce it.

Using a cryptographic random generator could make it impossible for the adversary to impose a particular sequence of counter values. You could use the block cipher with a different key for each message and use that to pseudorandomly generate a counter sequence. But that is considerably more complex and less efficient than just using that per-message key directly in counter mode. If you derive a unique key for each message, you can use counter mode without having to worry about collisions. (Using a unique key per message makes even CBC secure against bad IV choices — but still potentially vulnerable to oracle attacks, and unparallelizable for encryption, so still a worse choice than CTR mode.)