← Back to context

Comment by pclmulqdq

2 years ago

There is a final standardization step where NIST selects constants, and this is done without always consulting with the research team. Presumably, these are usually random, but the ones chosen for the Dual-EC DRBG algorithm seem to have been compromised. SHA-3 also had some suspicious constants/padding, but that wasn't shown to be vulnerable yet.

9 comments

pclmulqdq

Reply
tptacek  2 years ago

The problem with Dual EC isn't the sketchy "constants", but rather the structure of the construction, which is a random number generator that works by doing a public key transformation on its state. Imagine CTR-DRBG, but standardized with a constant AES key. You don't so much wonder about the provenance of the key so much as wonder why the fuck there's a key there at all.

I don't know of any cryptographer or cryptography engineer that takes the SHA3 innuendo seriously. Do you?

Additional backstory that might be helpful here: about 10 years ago, Bernstein invested a pretty significant amount of time on a research project designed to illustrate that "nothing up my sleeves" numbers, like constants formed from digits of pi, e, etc, could be used to backdoor standards. When we're talking about people's ability to cast doubt on standards, we should keep in mind that the paragon of that idea believes it to be true of pi.

I'm fine with that, for what it's worth. Cryptography standards are a force for evil. You can just reject the whole enterprise of standardizing cryptography of any sort, and instead work directly from reference designs from cryptographers. That's more or less how Chapoly came to be, though it's standardized now.

  • pclmulqdq  2 years ago

    I do know a few cryptographers who were suspicious of SHA-3 when it came out, but after some napkin math and no obvious hole was found, they were fine with it. The actual goal of that extra padding was to get extra one bits in the input to avoid possible pathological cases.

    My understanding of the Dual-EC problem may be different than yours. As I understand it, the construction is such that if you choose the two constants randomly, it's fine, but if you derived them from a known secret, the output was predictable for anyone who knows the secret. The NIST did not provide proof that the constants used were chosen randomly.

    Random choice would be equivalent to encrypting with a public key corresponding to an unknown private key, while the current situation has some doubt about whether the private key is known or not.

    • hovav  2 years ago

      Even with a verifiably random key, Dual EC is still unacceptable.

      First, because its output has unacceptable biases [1,2].

      Second, because its presence allows an attacker to create a difficult-to-detect backdoor simply by replacing the key, as apparently happened with Juniper NetScreen devices [3,4].

      --- [1] Kristian Gjøsteen, Comments on Dual-EC-DRBG/NIST SP 800-90, draft December 2005. Online: https://web.archive.org/web/20110525081912/https://www.math....

      [2] Berry Schoenmakers and Andrey Sidorenko, Cryptanalysis of the Dual Elliptic Curve Pseudorandom Generator, May 2006. Online: https://eprint.iacr.org/2006/190.pdf

      [3] Stephen Checkoway, Jacob Maskiewicz, Christina Garman, Joshua Fried, Shaanan Cohney, Matthew Green, Nadia Heninger, Ralf-Philipp Weinmann, Eric Rescorla, and Hovav Shacham, A Systematic Analysis of the Juniper Dual EC Incident, October 2016. Online: https://www.cs.utexas.edu/~hovav/dist/juniper.pdf

      [4] Ben Buchanan, The Hacker and the State, chapter 3, Building a Backdoor. Harvard University Press, February 2020.

      2 replies →