# Proving Non-Existence of ECC Backdoors

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?

-
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. –  rmalayter Aug 26 '14 at 3:30
@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 –  Richie Frame Aug 26 '14 at 4:00
@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? –  rmalayter Aug 26 '14 at 4:09
@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". –  Eric Aug 26 '14 at 11:20
@Eric if you believe in the security properties of SHA-512, trying different seeds until something worked out would take 2^200 trials or more. So their "proof" would rest upon the security of a well-studied primitive. That is not an uncommon form of crypto proof. –  rmalayter Aug 26 '14 at 14:27

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