2
$\begingroup$

A block cipher in counter mode creates a key stream by:

$$z_i = E_K(IV || i)$$

Where $IV$ is some chosen initialisation vector (with some length $l$ less that $n$ bits) and $i$ is the binary representation of the number $i$ in $n-l$ bits. The keystream is then $z_1 || z_2 || z_3 || \cdot \cdot \cdot$

How can we distinguish between such a key stream and a truly random bit sequence?

|improve this question
$\endgroup$
  • 2
    $\begingroup$ What you are describing is not the counter mode, but something similar to the output feedback mode (OFB), in which $z_0 = E_K(IV), z_i = E_K ( z_{i-1})$. Watch out for your definition of $z_0$, the IV should not be part of the keystream. $\endgroup$ – cygnusv Jun 5 '15 at 7:10
  • $\begingroup$ Usually we don't allow substantial changes to questions, but in this case CTR mode was meant according to title, so I guess we should allow it in this case. Note that the comment above was for a previous version of the question. $\endgroup$ – Maarten - reinstate Monica♦ Jun 5 '15 at 9:06
  • $\begingroup$ Beware that there are multiple ways of treating the IV for CTR mode. Many implementations use the entire block size as counter. In other words, IV right padded with zeros may be the starting value of $i$. Oh, and welcome Chris :) $\endgroup$ – Maarten - reinstate Monica♦ Jun 5 '15 at 9:29
1
$\begingroup$

Stream ciphers are often used as pseudo random number generators so as long as the key isn't known you generally can't.

There may be some statistical properties that may distinguish it from a hardware RNG as it is produces a well distributed key stream.

If you generate enough bits from it you may find out that it never repeats blocks in the key stream. $E_k$ is a pseudo random permutation (PRP); permutations always map one distinct input to one particular output, so the output is unique for a particular input. Of course the chances of generating a particular output are $1 \over n$ where $n$ is the block size, so you cannot use this property without a lot of key stream data.

If you ignore this statistical fact then you can run out of space in $i$. If $i$ repeats, so does the key stream. This is why counter mode requires a unique counter, and why counter mode is only considered secure for a certain amount of data. How much depends on the size of $i$ for a particular $IV$.

|improve this answer
$\endgroup$
  • $\begingroup$ Thanks for your answer and sorry about the edit - i had meant to describe the counter mode but completely wasn't thinking. $\endgroup$ – mchristos Jun 5 '15 at 9:50
  • $\begingroup$ I'm more worried that your answer is virtually identical to mine. If you want to answer your own question then you can do this by submitting them both at the same time. $\endgroup$ – Maarten - reinstate Monica♦ Jun 5 '15 at 10:02
  • $\begingroup$ Thanks for the accept. Note that I also upvoted your answer, as it has a bit more details on the birthday paradox argument. $\endgroup$ – Maarten - reinstate Monica♦ Jun 7 '15 at 8:56
  • $\begingroup$ Thank you! Yeah sorry about posting another answer I just thought it was a more clear and direct answer to my question. The idea came from you. $\endgroup$ – mchristos Jun 7 '15 at 22:01
2
$\begingroup$

For a truly random stream, since there are $2^n$ possible $n$-bit blocks, we expect a repeated n-bit block after looking at (roughly) the first $2^{n/2}$ blocks, by the birthday paradox argument.

For the stream generated by this block cipher, provided that each input block is distinct (i.e. the counter does not start repeating) , the output blocks are distinct (since the block cipher is a permutation). So choosing the IV length small enough (or indeed taking the whole block for the counter and not using an IV), we are guaranteed that no block is repeated for the first $2^k$ blocks, where $k \leq n$ is the length of the counter.

This way, provided $k$ is large enough, we can distinguish between two such streams by searching for a repeated block.

|improve this answer
$\endgroup$

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.