The question is exactly what it says on the tin. If $n$ is the block size in bits of a block cipher, then why does outputting $2^{0.5 \times n}$ block in counter mode become a problem when there is no repetition of the keystream until after $2^{n}$ blocks have been output?
$\begingroup$
$\endgroup$
2
-
1$\begingroup$ A duplicate ciphertext block leaks that the corresponding plaintext blocks were different. $\endgroup$– CodesInChaosNov 30, 2017 at 17:30
-
1$\begingroup$ Duplicate? crypto.stackexchange.com/q/51518/49826 $\endgroup$– Squeamish OssifrageDec 3, 2017 at 0:32
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
The security proof and bounds, such as those on page 18 of BDJR's 97 paper, can be read to derive some understanding of what going beyond the bound means.
At a high level, the notion is that you model the adversary as querying an oracle who either performs encryption of the provided data with CTR or returns random values. If the adversary can not distinguish between the two then the scheme is argued to be secure.
Now with respect to the bound you mention, if you give me $2^n$ blocks of zeros to encrypt and I give you back $2^n$ distinct blocks then you should feel confident I used CTR mode. After $2^{n/2}$ blocks of random values you have a good probability of having observed a duplicate if I am giving you random values.
answered Nov 30, 2017 at 19:22