Regarding: Pseudorandomness, Pseudorandomgenerators and Padding

Question

Hey there guys and gals,

so I am right now studying topics regarding pseudorandomness.

1. I was wondering why, for example with CBC-MAC oder a regular CBC blockcipher, we use padding instead of a PRG. If the block size is not a whole multiple of the clear text m, we could just use a PRG with the seed as the last block of m ? Or would that be "deterministic" since the seed is not selected truly random ? If so what is the point of enlarging an already random generated seed ? We could just create a new random number with the wanted length ?

2. Which brings me to point 2, I generally can not think of an example where a PRG is used. I know theres a method in java that acts the same way to generate a number between a lower and an upper bound, but in terms of crypto I am clueless.

3. A pseudorandom function / pseudorandom permutation is only "truly" random, when the key is picked randomly ? Same goes for the seed of a PRG ?

I know this might be all over the place :) I appreciate your time & effort

Answer 1

I can give little comments about each of the three evoqued points:

1. Padding and PRGs: One of the (main) points of using PRGs is to turn around the Shannon's famous "restriction": the key space must be as large ( or larger) than the message space. So, if you suggest to use only "random" sampling, as with seeds selection, instead of using a PRG to "enlarge" that seed to something larger but pseudorandom, you are actually putting a big bottleneck on the practical aspect of cryptography. Put it simply, it's inefficient to do so for every application of cryptography, i.e., don't forget that you need to send the entire generated keys somehow to the other parties. PRGs are deterministic, yes, but a good PRG can't be distinguished apart from a truly random source of bits with more than a negligible probability. So you can just use secure PRGs and make your life easier. For (particularly) CBC-MAC, I think you can use PRG as padding! but doing so is not quite efficient for applications.
2. The use of PRGs: PRGs are useful in stream-cipher cryptography, c.f. chacha20, RC4. Even some "PRGs" that come with programming libraries are in fact based (although often not quite obvious) on initial seeds that are generally fixed or generated using the current timestamp. So, these are just kind of (bad) PRGs. You can use these "moderate" PRGs to generate for example numbers in some interval to test for primarily for subsequent use in other cryptographic constructions (but that can be devastating is some cases). You can also use these PRGs to generate some test vectors and of course for any other non-cryptographic applications.
3. PRF, PRP and PRG: PRX stands for "Pseudorandom X", in contrast to a "truly random X". The motivation here is that to build efficient constructions, we may sacrifice a little amount of randomness. Put it once again informally, we can satisfy ourselves with only pseudorandom constructions as long as "nobody" can exploit efficiently this "difference" and breaks the security. So, PRFs, PRPs and PRGs are secure only if the keys are picked randomly, but they cannot be transformed, by no means, to a truly random constructions. A truly random function has no key at all but it is sampled randomly from the set of all possible functions. This set is extremely large, hence, this whole thing is not practical.