Show that block cipher with CTR is a good PRNG

Awerde

9/1/23, 9:45 AM

Assume that block cipher scheme $(KeyGen, Enc, Dec)$ is CPA-secure. Show that $CTR_{Enc_k(0^n)}$ is a good PRNG.

Counter mode works as follows:

$Y_i = Enc_k(IV + f(i))$

$C_i = Y_i \bigoplus P_i = Y_i \bigoplus \{0^k\}= Y_i$

So the output here is simply $Enc_k(IV + f(i))$. Now, as good PRNG I understand that it needs to be indistinguishable from a random source. Let's assume it's not. So if $X_0$ is our source and $R$ is a truly random source, we have $$|Pr[A(x)=0|x=X_0]-Pr[A(x)=0|x=R]|=\delta$$ and $\delta$ is non-negligible. As we can distinguish the output the blocks aren't independent of each other. So there are some relations between $Enc_k(IV+f(i))$. Here I don't have any ideas on how to proceed. I guess that it is somehow in contradiction with CPA-security but I don't know how to show this.

0 + 0

block-cipher

random-number-generator

chosen-plaintext-attack

ctr

Maarten Bodewes

9/1/23, 11:22 AM

Actually, if you have a small block size I wonder how good a PRNG it can be, because you would not have the possibility for blocks to repeat. I would not bet the same winning number in that lottery for sure. If you run a CTR on an 8 byte block cipher then after $2^{32}$ blocks / 32 GiB of data then one out of $2^{32}$ blocks cannot be generated anymore. I wouldn't call that a good property for a PRNG. I've seen this assignment before, and personally I think it is pretty stupid; they forget all about smaller sizes of the input / output set of the permutation.

Awerde

9/1/23, 5:33 PM

@MaartenBodewes the way you put it, it is very stupid indeed ;) I guess they just forget about it because it's not the main concern here...

Maarten Bodewes

9/1/23, 7:03 PM

I'm not against simplifications, but I am against assignments or examples that try and learn you something, while at the same time teach you something that is *incorrect*. That's trying to let you learn how to run while you're standing on the edge of a cliff. But enough said, I suppose.

Awerde

9/2/23, 6:36 AM

@MaartenBodewes you said you saw this assignment before, maybe you have any hints for me?

Maarten Bodewes

9/2/23, 7:31 AM

I'm not the best person to give hints here possibly when it comes to formal proofs. I'd include the security argument for CTR mode, if it is secure then because of the XOR the the key stream should be fully randomized. Of course you can still assume it is the reverse in your argument, and proof that wrong. A quick search showed up [this lecture](https://www.csa.iisc.ac.in/~arpita/Cryptography15/CT2.pdf) with a CPA proof for CTR.

Maeher

9/2/23, 7:59 AM

@MaartenBodewes Whether or not the statement is true depends on context we were not given. In the context of asymptotic security definitions the statement is absolutely correct. In the context of *concrete* security definitions it depends on the exact paramenters.

Maeher

9/2/23, 8:11 AM

Conceptually the easiest way to understand the proof is imho via a series of hybrid distributions. Start with your distribution $X_0$ and successively apply the security definition of a pseudorandom permutation, the PRP/PRF Switching Lemma and the observation that for a uniformly random function $g : \{0,1\}^n \to \{0,1\}^n$, $g(0)\Vert\cdots\Vert g(N)$ is distributed uniformly. This will finally lead you to a distribution $X_3=R$. For each step along the way you can prove that the distributions are indistinguishable and then apply the triangle inequality to get the statement you want.

Awerde

9/2/23, 8:55 AM

Thank you both, I'm not sure this is the path I should follow - the proof seems to be overly complicated for this kind of task, but thanks anyway ;)

Elon Musk

I sit in a Tesla and translated this thread with Ai:

EN: Show that block cipher with CTR is a good PRNG

TH: แสดงว่ารหัสบล็อกที่มี CTR เป็น PRNG ที่ดี

RO: Arătați că cifrul bloc cu CTR este un PRNG bun

RU: Покажите, что блочный шифр с CTR — хороший PRNG

VI: Chứng tỏ rằng mật mã khối với CTR là một PRNG tốt

Post an answer

Most people don’t grasp that asking a lot of questions unlocks learning and improves interpersonal bonding. In Alison’s studies, for example, though people could accurately recall how many questions had been asked in their conversations, they didn’t intuit the link between questions and liking. Across four studies, in which participants were engaged in conversations themselves or read transcripts of others’ conversations, people tended not to realize that question asking would influence—or had influenced—the level of amity between the conversationalists.