2
$\begingroup$

CSPRNGs have 2 design requirements:

  1. output unpredictability,

  2. back-tracing resistance.

In addition to which, NIST SP 800-90Ar1 added other features such as a) instance customization/personalization, b) operation administration (reseeding counter, etc.).

Of the three functions listed on Wikipedia page for CSPRNG, key and salt generation can be accomplished with any KDF (even ones based on plain hash functions), and nonce can be accomplished with a simple counter.

And with the introduction of dedicated-purpose XOFs in the SHA3 standard, the problem of producing arbitrary-length string from a finite-length one becomes solved along the way.

Both XOFs and KDFs are much easier to implement and use practically, so what's the point of designing DRBGs in the "NIST-SP-800-90A" way?

$\endgroup$
  • $\begingroup$ Note that CSPRNG's as defined by NIST have functions to add entropy to the RNG through their Update methods. That's something that is commonly missing from XOF's and KDF's (let alone stream ciphers). I think this detail is often overlooked. $\endgroup$ – Maarten Bodewes Apr 11 at 18:34
3
$\begingroup$

I don't know what the rationale behind the designs in the NIST SP800-90 standards were—internal discussions may be obtainable by public records requests—but I can hypothesize a few reasons:

  1. Backtracking resistance. While SP800-90C does cover KDFs (like HKDF and SP800-108), and while sponges are available now, there's more work to be done in SP800-90A to attain backtracking resistance:

    • A mere KDF, e.g. HMAC with a counter, does not necessarily provide backtracking resistance on its own unless you iterate it (like HKDF-Expand could be construed to do, but only for each info parameter independently). Although it's not too difficult to show that this is safe—the expected length to cycle in the iteration of a large uniform random function is only square root of large, and it can't be much different for a pseudorandom function—application developers aren't going to prove this themselves and auditors want guidance from a standard.

    • A mere sponge XOF, e.g. SHAKE128, does not provide backtracking resistance on its own: if the full state is ever compromised, then you can simply evaluate Keccak in reverse until you get all the old outputs. There are various ways you could work around this, but there's no one obvious natural way.

  2. Hysterical raisins. NIST SP800-90A predated sponge constructions, so the tools at hand were:

    • pseudorandom permutations (block ciphers) like AES
    • variable-input fixed-output hash functions like SHA-256
    • fixed-input variable-output hash functions like Salsa20 or AES-CTR
    • public-key cryptography for making back doors

    Although Salsa20 used the model of a random permutation $\pi$ in the form $x \mapsto \pi(x) + x$ to approximate a random function, which in turn was used in ‘CTR mode’ to approximate a one-time pad, the pervasive design principle of building everything out of a single permutation—like we see now with Keccak, in SHA-3 and KangarooTwelve and Kravatte and Strobe, and even with other permutations like Gimli in libhydrogen—had yet to reach prominence.

  3. Cost of collision resistance. There seems to be a much higher cost to collision resistance than to preimage resistance. But DRBGs don't need collision resistance. So, e.g., AES-CTR_DRBG can presumably be faster than HKDF-SHA256 or SHAKE128. (Of course, you could use a much faster Keccak sponge like the 12-round KangarooTwelve or even the 6-round Kravatte but they're not among the SHA-3 functions.)

  4. Avenue for Dual_EC_DRBG. It seems implausible that NIST would choose to standardize DRBG interface and security requirements only to introduce a back door—it's so foundational for so much cryptography that standardization would be well within NIST's purview even without the back door. But the prospect of attacking this foundation could have motivated NSA to push slightly harder for NIST to standardize it.

That said, you're unlikely to get the real answer unless (a) you file a FOIA request to get the internal design discussions, or (b) someone from NIST hangs out here.

$\endgroup$
0
$\begingroup$

Of the three functions listed on Wikipedia page for CSPRNG, key and salt generation can be accomplished with any KDF (even ones based on plain hash functions), and nonce can be accomplished with a simple counter.

Key generation unavoidably requires some sort of random generator because keys must ultimately be selected at random. Yes, there is such a thing as key derivation, but every derived key must have some less-derived key as its "ancestor" (so to speak), and the resulting tree must ultimately be rooted in some random choices. KDFs and XOFs can play a part in random generation but are not sufficient to accomplish it.

There will always be a need for private sources of random bits in cryptography, which means something like DRBGs. (Which could well use KDFs or XOFs as internal components, but that's another story.)

$\endgroup$
  • $\begingroup$ But a CSPRNG/DRBG is a kind of KDF. The question here is: why don't the NIST generators in SP800-90A use KDFs or XOFs as internal components? (Note this is not about physical entropy sources, as in SP800-90B.) $\endgroup$ – Squeamish Ossifrage Apr 9 at 21:06
  • 1
    $\begingroup$ @SqueamishOssifrage: I don't agree with your perspective that a DRBG is a kind of KDF. As I think of it, a KDF is a practical realization of a randomness extractor and/or a private random function, while a DRBG is a practical realization of an on-demand random bit source. And under this way of looking at it—in terms of what ideal objects they can instantiate in practice—the internal implementation details are not wholly relevant. $\endgroup$ – Luis Casillas Apr 9 at 21:34
  • 1
    $\begingroup$ I should clarify: I meant that a DRBG serves as the expansion part of a KDF, not as the extraction part of the KDF. $\endgroup$ – Squeamish Ossifrage Apr 11 at 1:42
  • $\begingroup$ @SqueamishOssifrage: This risks becoming a discussion in the comments section, but my take is that NIST's DRBG concept isn't just a PRG (random seed → expanded pseudorandom stream), it's a PRG with extra functionality (e.g., feeding entropy to the generator as an ongoing concern) that's extraneous for a key derivation application but essential or useful in a nondeterministic random generator context. It's not that you couldn't use a DRBG the way you propose, it's that it's not closely tailored to that. $\endgroup$ – Luis Casillas Apr 11 at 17:35
  • $\begingroup$ There's an easy way to do that still using a KDF: apply the KDF extractor to the old seed and the new entropy (apportioned into IKM or salt as you see fit). I agree that the interface isn't the same, but the question is why the internal components are custom-built and not simply defined in terms of a KDF (or XOF). $\endgroup$ – Squeamish Ossifrage Apr 11 at 21:39
-1
$\begingroup$

Sponge functions were only finalised in conference in 2007, whilst the initial NIST document came out in 2006. The DRBG behaviour of block ciphers and hashes has been known a lot earlier than 2006. So the repeatedly squeezed sponge technique was not available at the time of NIST's original publication, and even had it had been, it would not have been analysed/tested.

Economic might means that many countries follow the States' lead on technology and it's certification. So in order to use your piece of 'stuff', it may have to have NIST /FIPS certification. Whilst FIPS and NIST complement each other, especially in US financial and (non military) governmental circles, NIST makes FIPSes.

So in summary, it's more of a legal requirement, not a mathematical one. If the contract says "NIST-SP-800-90A", then "NIST-SP-800-90A" it. XOFs and KDFs are not usable at all in that context.

But you're right, and Sponge-based pseudo-random number generators is a good example design. However strong KDFs might not be great. Anything like Argon2 with low/trivial settings would negate their very purpose bringing more appropriate constructs into play.

Notes:

  1. In addition to your points #1 and #2, there is #3, Resistance against state recovery (§4.2 of the linked document). It is as it sounds.

  2. RadioGatún (2006) preceded the formal sponge, but seems to be been overlooked even though it was in a NIST competition.

  3. Perhaps(?) NIST will revise again and incorporate XOFs in the future following SHA-3 2014 Workshop

  4. Many good folks will have worked on NIST-SP-800-90A. It is interesting then that page iii specifically has this acknowledgement, mentioning two people by name - "The National Institute of Standards and Technology (NIST) gratefully acknowledges and appreciates contributions by Mike Boyle and Mary Baish from NSA for assistance in the development of this Recommendation. NIST also thanks the many contributions by the public and private sectors".
  5. See Federal Information Security Modernization Act of 2014 § 3553 "Authority and functions of the Director and the Secretary" for opinion regarding #4.
$\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.