Because a block cipher is a PRP and thus bijective, the fact that the input in CTR mode never repeats means that each block of keystream will be unique. This creates a distinguisher from random data following the birthday bound if enough data is encrypted even before the counter repeats, especially if the block size is too small. Stream ciphers like ChaCha20 avoid this issue by feeding a counter into a PRF instead of a PRP, meaning blocks of keystream will repeat according to the birthday bound.

Is it feasible to mitigate this problem with a PRP by feeding the nonce and counter through a very fast and deterministic hashing function first? Because the input to the block cipher is not secret in CTR mode, it would not need to be a secure hash function. All it would need to do is admit collisions due to the birthday bound, allowing for a repeating block in the keystream after roughly $2^{n/2}$ blocks.

Is this correct? If so, what is the fastest hash function which has the required properties?

  • 2
    $\begingroup$ I think it would need to be a secure hash function, otherwise we could force it to generate identical key streams at will. $\endgroup$
    – Ella Rose
    Jan 28 '19 at 6:01
  • 1
    $\begingroup$ If you want to use AES or a typical block cipher, the solution to this problem is dual CTR streams with different keys, but identical inputs. It is still reversible but no longer has guaranteed block uniqueness, and you get to use the primitive you already have (at half speed). And while block uniqueness is very important in CTR mode, it is not in dual CTR, because the location of duplicates is key dependent and pseudorandom, just like the block cipher output. $CTR_{k1}(nonce+counter) \oplus CTR_{k2}(nonce+counter)$ $\endgroup$ Jan 28 '19 at 10:11
  • $\begingroup$ Combination of two stream ciphers may offer some further insight... $\endgroup$
    – Paul Uszak
    Jan 28 '19 at 22:18

I'm reading the question as generating a keystream per: $S_i\gets E_K(F(\mathrm{IV},i))$ where $F$ is a public function built from a hash function; for incremental index $i$ starting from $0$ and public random $\mathrm{IV}$, with $F$ having a sizable collision rate when $i$ varies; and for $E$ a block cipher with secret key $K$.

That is quite insecure: the location of the collisions, that is values of $i$, $j$ with $i\ne j$ and $F(\mathrm{IV},i)=F(\mathrm{IV},j)$, can be found by an adversary from the public $\mathrm{IV}$. And then knowledge that $K_i=K_j$ can be used to mount an attack allowing decryption of some plaintext fragment from partially known plaintext.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.