[Cryptography] Fw: how could ECC params be subverted & other evidence

[John Kelsey]

> Date: Tue, 10 Sep 2013 13:42:57 +0200
> From: Adam Back <adam at cypherspace.org>
> To: "Perry E. Metzger" <perry at piermont.com>
> Cc: Alexander Klimov <alserkli at inbox.ru>, Cryptography List
> <cryptography at metzdowd.com>, Adam Back <adam at cypherspace.org>
> Subject: Re: [Cryptography] how could ECC params be subverted & other
> 
...
> The important potential backdoor is NIST 186-3 curves in Peter
> Fairbrother's reply, and I think that would be a good place to focus
> analysis.  

I've talked a bit with someone I know with some background in the math here, who didn't see an obvious way for these curves to have been cooked.  I don't have the number theory to have an opinion, but if someone can point me to an explanation of how they might have been cooked, I would very much appreciate it.  I imagine any such potential backdoor will be very easy to get my management to take seriously right now.  And that three months ago, we would not have been at all worried.  I forsee a rather large change in institutional culture at NIST.  

> (DRBG is largely irrelevant due suspected compromised state since
> 2007, and very limited use.  It is also a different type of issue -
> not backdoored curves, arguably backdoored parameters).

It sure looks now like Dual EC DRBG was backdoored from the leaks and news stories, though I don't know of any hard proof.  But we (NIST) have put SP 800-90 back up for public comment and have issued a bulletin telling people to stop using it until we figure out what to do about it.  (The alternatives are to remove it or to fix it.)

This DRBG was in the X9.82 document when I joined NIST and came onto the project in 2003.  If you go to our website (csrc.nist.gov) you can see old slides and documents, and you can check the wayback machine to verify we haven't changed them.  (We also had a public workshop, and participants may still have old copies of the documents.)  This shows the development of the standard over time.  I think the P and Q were the same in those old documents.  If so, this tells you how far back this effort goes--at least to 2003, perhaps further back.  I believe the X9.82 effort had been going on several years before that, though not making much progress--I'm not sure how long ago Dual EC DRBG was put in.  I paid very little attention to the number theoretic constructions (two originally, one in the final version) because I didn't and don't think I know enough number theory to evaluate them.

When we heard about the issue of selection of points (in an X9 meeting, I think in 2006 or early 2007), we discussed the issue, and it didn't seem like a serious threat.  I sure didn't think the people I was working with on the document were trying to slip weak stuff in.  Instead, it looked like they had generated some parameters randomly and hadn't worried about proving where the parameters came from.  

This seemed like a really weird place to put a backdoor, because it was insanely slow, and it seemed unlikely to get any significant use.  And I, at least, had internalized the idea that we weren't going to get intentional bad advice or sabotage from another part of the federal government.  (Accidental screw-ups, sure, but not intentional engineered vulnerabilities.) At the time, the solution we came to--allow the use of the default points (which some people had allegedly baked into implementations in anticipation of the standard) and also allow generation of your own points, seemed adequate.    

But that was assuming a different world than we live in, apparently.  If NSA had a program of intentionally inserting weaknesses in crypto standards, and inserted at least one into a NIST standard, then any potential backdoor parameters we have are scary as hell.  No way can we leave them in a standard people are expecting to use.  Having such a program burns a hell of a lot of bridges, too.  I still don't *know* if this is true--convincing newspaper stories often get stuff wrong, and convincing leaked documents may not be authentic.  But it sure looks like the way to bet, now.

--John