How good from a randomness point of view are recursively generated sequences using good encryption algorithms?

Let us say I take AES128 which generates good random sequences of outputs for counter inputs. Denote C=E(K,P) to be the output of AES128 with symmetric key K and input block P. Consider the recursively generated sequence

Q(i)=E(K,Q(i-1)) for i=1,2,3,...

  • where Q(0) is a random 128-bit block chosen as the initial seed.
  • Assume that K is also chosen randomly.

Is there a theoretical basis to presume that the sequences Q(i) will also satisfy good randomness properties?

  • $\begingroup$ Thank you Rohit Gupta for editing the question. What is the model of randomness you are suggesting for the recursive sequence? I am interested in the complexity of the sequence as an attribute of randomness. $\endgroup$
    – Viren Sule
    Commented Jan 17, 2023 at 5:10
  • $\begingroup$ AES-OFB generates it's pseudo-random keystream precisely in this way, with P the Initialisation Vector. $\endgroup$
    – fgrieu
    Commented Apr 18, 2023 at 6:09

1 Answer 1



Under standard assumptions on block cipher design (which in the case of AES have been also experimentally tested and no bad surprises have been found) the function $Q$ generating a recursive sequence is a pseudorandom function with the expected properties of such a function, e.g., the average and maximum cycle length.

Given a random $P_0$ expected cycle length is $O(\sqrt{2^{128}}).$ So is the maximum cycle length. This is as well as could be expected for an ideal random function from the space of 128 bit strings to itself. This essentially means that the entropy of the pseudorandom mapping $f$ averaged over possible starting states $P_0$ chosen with uniform probability is about $64$ bits since the randomness is exhausted after the cycle closes.

For the map $g$ a similar claim should hold. The technical details can be tricky but an intuitive argument would be that if the map $g$ had appreciably shorter cycle length (thus lower entropy) it could be used to obtain a weak initial state $K_0$ which would be like discovering a weak key for AES. To the best of our knowledge, no such keys exist.

Original Answer:

The maps below derived from $E_K(P):=E(K,P)$ can be assumed to have pseudorandom properties for the cases $$ f:K\mapsto C:\quad f(K):=E(K,P),\quad \forall \textrm{ fixed } P,\\ g:P\mapsto C:\quad g(P):=E(K,P),\quad \forall \textrm{ fixed } K.\\ $$ If in addition the blocklength is equal to the keylength then they can be assumed to be pseudorandom permutations on the same space $\{0,1\}^n.$ This leads to the conclusion in the comments that the sequences $C(i)=f(C(i-1))$ starting from $C(0)=f(K_0)$ when $C(0)$ is given but $K_0$ is inaccesible should also satisfy randomness tests.

However, this sequence now behaves like a pseudorandom function as opposed to a pseudorandom permutation, traversing the space $\{0,1\}^n.$ Flajolet and Odlyzko, in "Random Mapping Statistics", EUROCRYPT ’89, 329–354 have analyzed the statistics of such maps, in terms of the lengths of the cycles they form, etc. specifically for DES. However, there is theoretical work in this domain from Kolchin as well as from Graham. I think we can consider the (logarithm of) the expected cycle length as one measure of the randomness. Otherwise we can consider the maximum cycle length as a measure of maximum possible randomness.

If we apply Flajolet and Odlyzko's results to AES, we obtain that the expected cycle length of the mapping is $O(\sqrt{2^{128}})$ and and the maximum cycle length of the mapping is of the same order.

See also the question here in mathoverflow and its answers.

However, in real life, we do not have "chosen key" attacks but we do have "chosen plaintext" attacks. The key is the target of the attack. So in terms of modeling real attacks, the roles of the two maps $f,g$ above are not identical. And as I already stated, structural properties of the specific cipher design may also mean that the way $K$ and $P$ are processed through the rounds of the cipher is not the same.

Original answer:

You already assume $E_K(P)\mapsto C$ has good randomness properties: Let us say it is hard to distinguish from a random permutation for any fixed $K$ or fixed $P$ if seen as a multivariate input function with $K$ as an input.

Assuming this, and that the initial state $Q(0)$ is random the sequence $$ Q(i),i\geq 1 $$ is then also random, and will typically not be distinguishable from random until you iterate it more than $k\geq \sqrt{2^{128}}$ times.

Are you interested in more specific properties? Or a different model of randomness?

Note that this is very hard to prove for a specific cipher without the assumption of the block cipher being indistinguishable from a random permutation. You may want to look at the Luby-Rackoff model, for example.

  • $\begingroup$ Thank you for the answer. I agree that by assumption E_K:P\rightarrow C is expected to be a random permutation. Hence the sequence Q(i) should satisfy randomness tests. An associated map is F=E_P:K\rightarrow C defined at a fixed P. An assumption about encryption functions C=E(K,P) that it is infeasible to find K given a (P,C) pair should also make this map a random permutation for any P. Hence inversion of F given C to find K is hard by assumption. Hence the sequences C(i)=F(C(i-1)) starting from C(0)=F(K_0) when C(0) is given but not K_0 should also satisfy randomness tests. $\endgroup$
    – Viren Sule
    Commented Jul 18, 2022 at 14:21
  • $\begingroup$ yes I informally iplied that in my answer as well, however, in block cipher designs the roles of $K$ and $P$ may not be interchangeable, so this would need further proof/verification in general. $\endgroup$
    – kodlu
    Commented Jul 19, 2022 at 1:36

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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