5
$\begingroup$

Are there any specific CSPRNG's that cannot be used as randomness extractor within a TRNG?

In other words, can you simply provide enough entropy gathered from a good entropy source as seed in any CSPRNG, and be done with it?

I've got the strong feeling that the properties of a CSPRNG are largely overlapping that of randomness extraction, but Wikipedia claims that the properties of a (generic) PRNG may not necessarily overlap.

However, the general PRG definition does not specify that a weakly random source must be used, and while in the case of an extractor, the output should be statistically close to uniform, in a PRG it is only required to be computationally indistinguishable from uniform, a somewhat weaker concept.

I presume that any hash based extractor should work, as it hashes the input. Hashing the entropy is - as far as I understood - considered a good method of extracting the randomness out of the entropy.

The only property that I can come up with that should be required from a CSPRNG is that it has to mix in all the data containing the entropy.

Notes regarding NIST SP 800-90B:

  • It is not necessary here to let the TRNG be a full entropy source as defined in that document; CSPRNG's are normally used to generate more output than the amount of entropy provided;
  • Chapter 6.4 contains requirements for the randomness extractor;
Improve this question
$\endgroup$
6
  • 2
    $\begingroup$ I guess for a PRNG you usually have a short input and longer output, while in a randomness extractor it is the other way around. That might be the key point of difference. $\endgroup$
    – Paŭlo Ebermann
    Commented Jul 27, 2014 at 19:41
  • $\begingroup$ @PaŭloEbermann that's the thought that crept up to me as well when I was typing up the question and reading through the NIST specs. Still, I think it is interesting to see what happens if you indiscriminately supply entropy to a CSPRNG. Will there be some CSPRNG's that cannot handle that situation? Or is the security definition of a CSPRNG defined in such a way that it must operate correctly given enough entropy? $\endgroup$
    – Maarten Bodewes ♦
    Commented Jul 27, 2014 at 22:13
  • $\begingroup$ Based upon the answers it has become clear that there is some confusion about what you mean by CSPRNG (e.g., the distinction between CSPRNG and PRG). I suggest you edit the question to give us your definition of what you mean by CSPRNG: do you mean something like Yarrow, /dev/urandom, etc? or something like AES-CTR, RC4, etc.? $\endgroup$
    – D.W.
    Commented Jul 28, 2014 at 21:29
  • $\begingroup$ @D.W. Something like Yarrow yes (although I don't know why you came up with that particular one), as indicated I started off from the Wiki page, which states that a CSPRNG has some properties that may not be compatible with a randomness extractor. Actually they seem quite different to me, but I guess you can still use a CSPRNG for practical post processing of random entropy, if the CSPRNG allows it. Hence I left the question open. /dev/urandom is not an algorithm and a block cipher in counter more or a stream cipher can only be building blocks for CSPRNG's it seems to me. $\endgroup$
    – Maarten Bodewes ♦
    Commented Jul 28, 2014 at 21:55
  • $\begingroup$ @D.W. Was that a multiple choice question? For the latter - at least AES-CTR, they are OK if you have a fully random seed as key I suppose. $\endgroup$
    – Maarten Bodewes ♦
    Commented Jul 28, 2014 at 21:56

2 Answers 2

Reset to default
4
$\begingroup$

Some CSPRNGs accept a constant width seed. That means they could only be used as randomness extractors for that input size; no less, no more. For example, AES-128 CTR_DRBG CSPRNG (from 800-90A) would only accept 256 bits of seed for the key and initial vector in total.

Further, if the input is not fully random (as you'd expect with a randomness extractor), they can be vulnerable to related-key attacks. When used as a random number generator the key is usually assumed to be uniformly random – e.g. AES-128 CTR_DRBG requires exactly 256 bits of entropy in the seed, unless a KDF is used for randomness extraction.

Improve this answer
$\endgroup$
3
  • 1
    $\begingroup$ @D.W. Don't go into overdrive now. I presumed (and the link to 90A kind of points this out) that CTR_DRBG was meant. It is specified in 10.2.1 of that document. This seems to be a CSPRNG to me, including seeding and reseeding and whatnot. Of course, you could wonder if the reseeding process cannot be used to add in additional entropy. Otus, could you point to this paragraph and name instead of AES-128 CTR CSPRNG (if I'm correct)? That does not seem to be the official name. $\endgroup$
    – Maarten Bodewes ♦
    Commented Jul 28, 2014 at 22:37
  • $\begingroup$ @owlstead, OK, I've edited the answer accordingly, and to try to make it match my understanding. Now the answer makes more sense to me. AES CTR_DRBG is different from AES CTR. $\endgroup$
    – D.W.
    Commented Jul 28, 2014 at 22:49
  • $\begingroup$ Sorry, my naming was indeed sloppy. Now it makes sense, I hope. $\endgroup$
    – otus
    Commented Jul 29, 2014 at 7:34
8
$\begingroup$

There is some relationship between the two notions, but a CSPRNG is designed to be computationally secure (secure against adversaries with bounded computation time), whereas a randomness extractor is required to be information-theoretically secure (unconditionally secure against adversaries with unbounded computation time). So, they're different primitives.

I would not expect a typical CSPRNG to be a secure randomness extractor. Typically CSPRNGs use computationally secure primitives, like AES etc.; they don't make any attempt or claims of providing security against adversaries with unlimited computing power.

Also, CSPRNGs are often designed to address other issues as well, such as recovery from state compromise (robustness against state compromise extension attacks), efficient use of the available entropy, and ability to stretch a finite amount of entropy into an unlimited stream of pseudorandom bits (e.g., using a PRG).

CSPRNGs are practical primitives, intended for applied cryptography, and were invented by applied cryptographers. Randomness extractors have typically been studied in the theoretical literature and are rarely (if ever) used in practice, for a variety of reasons, and were invented by theoreticians for studying fundamental theoretical questions. These differences reflect differences in the goals and values of those two communities.

We can also compare randomness extractors to pseudorandom generators (PRGs), but again, they're very different. PRG's are not designed to act as a randomness extractor, so there is no reason whatsoever to expect any particular PRG to do a good job at randomness extraction. Indeed, I'd expect that many secure PRG's might be perfectly good as a PRG but no good at all as a randomness extractor. The purpose of a randomness extractor is designed to take a non-uniformly distributed seed and turn it into a uniformly distributed output. That's very different from the task that PRG's are designed for. PRG's are designed to be secure if their seed is distributed uniformly at random. There is no guarantee whatsoever that they will be secure if the seed is distributed non-uniformly, and indeed, for some secure PRGs, they might be insecure when used with a non-uniformly distributed seed.

In short, if you take a CSPRNG or a PRG, I would not expect it to necessarily act as a secure randomness extractor. They're just different things.

Improve this answer
$\endgroup$
1
  • 1
    $\begingroup$ Your answer has a lot more information than the one of Otus, and as learning is concerned it is of more value. However, I think otus came closer with regards to providing an answer. +1 none-the-less of course. $\endgroup$
    – Maarten Bodewes ♦
    Commented Jul 28, 2014 at 19:15

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.