Comment by 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.

6 comments

pclmulqdq

Reply
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.

  • denton-scratch  2 years ago

    > Even with a verifiably random key

    What's a "verifiably random" key?

    • pclmulqdq  2 years ago

      "Verifiably random" means produced using a process where it isn't possible for you to know the outcome. In this case, saying "the key is [X], which is the SHA-2 hash of [Y]" would allow you to know that they couldn't choose [X] without breaking SHA-2.