In light of the NIST Dual EC DRBG scandal, I was intrigued by a NIST slide (slide 9) that said the two points P and Q can be chosen so that the chooser can prove they don't have a backdoor. This seems rather magical to me, so I'm looking for some more information. I'm assuming they're referring to something more substantial than "nothing up my sleeve", which is hardly "proof". Do Safe curves or Koblitz curves have this property?
$\begingroup$
$\endgroup$
7
-
$\begingroup$ I think it is the "nothing up my sleeve" method, as the slide says it is described in the standard. Appendix section A.2 mentions using the SHA-512 hash of a seed bitstring for each parameter. This is basically the "nothing up my sleeve" method. For example, hash a public value such as digits 100-300 of Pi or something like that. $\endgroup$– rmalayterAug 26, 2014 at 3:30
-
$\begingroup$ @rmalayter unfortunately they do not describe the provenance of those seed numbers, so it is probably they were chosen randomly until the hash had some exploitable property $\endgroup$– Richie FrameAug 26, 2014 at 4:00
-
$\begingroup$ @Richie_Frame slide if the NIST presentation in question says "It is also possible to choose (P,Q) so that you can prove you don’t know a backdoor. – We have a mechanism to do this in our standards, but it seems never to have been used." Given appendix A.2 of SP800-90A's description of hashing a seed, isn't hashing a "public" tamper-proof seed a very reasonable interpretation of that slide? $\endgroup$– rmalayterAug 26, 2014 at 4:09
-
$\begingroup$ @rmalayter How is "nothing up my sleeve" proof of anything? Just like they didn't justify their random seed (hence they could have tried random seeds until a backdoor was discovered), they could also try using 200 digits of pi starting at digit 100, 200, 300, ... until something worked out. Then they could still claim "nothing up my sleeve". $\endgroup$– crockeeaAug 26, 2014 at 11:20
-
1$\begingroup$ Asking around a bit, it seems there is an interactive protocol for (actually) proving non-knowledge of a (jointly-computed) discrete log. $\endgroup$– crockeeaAug 26, 2014 at 20:42
|
Show 2 more comments
1 Answer
$\begingroup$
$\endgroup$
You need to clearly distinguish between the DualEC DRBG algorithm and the elliptic curves over which it is defined.
The backdoor in DualEC DRBG needs the attacker to choose P and Q such that they know the scalar $k$ for which $P=kQ$. Pretty much any algorithm which fixes both public keys at the same time without going through private keys is fine. For example you could choose the hex expansion of $\sqrt{2}$ and $\sqrt{3}$, or SHA2(x), SHA2(x+1). This is pretty similar to nothing-up-my-sleeves numbers, but the requirements are pretty weak, since the only thing you need to prevent is the attacker knowing $k$.
Backdooring curves is an entirely different matter. You start with the conjecture that NSA knows a certain fraction of weak curves and tries to choose one of them. To avoid this, the curve must be as rigid as possible, i.e. allow as little choice to the designer as possible. This is where "safecurves" fare better than the common NIST curves. So your question about "safecurves" having this property misses the point.
The only coupling between the DualEC DRBG backdoor and the choice of curve I can think of is is choosing the curve parameters so that particular points have a known relation. I don't know if that's possible at all, but I expect this to require a lot of freedom in choosing the curve, more freedom than even the NIST curves have. Preventing this attack is easy: just include the serialization of the curve parameters in the inputs of the hash used to derive the points.
answered Aug 26, 2014 at 8:23