# What's up with unnamed elliptic curves in e-passports?

At my work I deal with the cryptographic aspects of the international E-Passport specification (the crypto chips embedded in your passports, the kiosks at airports that talk to them, and the certificate authorities that issue their certs).

The relevant standards document is BSI TR-03110-3.

Section A.2.1.1. Standardized Domain Parameters provides a list of NIST and Brainpool curves that are allowed. Cool. Section A.2.1.2. Explicit Domain Parameters provides a mechanism for you to use any domain parameters you want.

My question is: Are they on drugs? Coming up with safe domain parameters is non-trivial. I suppose some countries' passport offices have cryptographers on staff who know what to look for in parameter generation, but not all. That seems like an awful lot of rope to hang yourself with for no real gain. Can anyone shed more light on why they would allow this?

• NIST and Brainpool have mathematical attacks discovered against them? News to me; all Bernstein and Lange point out is that a) it's slightly trickier to have a (cache/timing) side channel resistant implementation of them (and they don't address DPA-type side channels, would appear to be relevant to embedded chips in e-passports), and b) for the NIST curves, some of the curve parameters are unexplained (and so the curve inventors might conceivably have put in a back door, although no such mechanism for doing so has been proposed) – poncho Aug 26 '16 at 2:19
• @poncho Ok fair. If I change that line to "coming up with safe domain parameters is non-trivial" would you be happy with it? – Mike Ounsworth Aug 26 '16 at 2:23
• The prominently Bad Thing that I see with A.2.1.2. Explicit Domain Parameters is that it makes the software checking signatures more complex, thus more brittle; and its testability a nightmare. As explained in the answers, generation of safe EC parameters does not seem quite rocket science. – fgrieu Aug 26 '16 at 12:10
• @fgrieu I agree that testing is a nightmare. For example it's not obvious if FIPS or Common Criteria does any testing at all around unnamed curves. – Mike Ounsworth Aug 26 '16 at 12:14
• Common Criteria will require to test all curves you claim in your Security Target. – user27950 Aug 30 '16 at 4:59

I don't have any visibility into the BSI standardization process, and so this is a guess; I suspect one of two things happened:

• This is a potential way to deal with someone figuring out how to break both Brainpool and NIST curves (but not arbitrary elliptic curves; if they managed that, this hook won't help). In that case, if someone did that (or if we suspect they might have), we can update the passports without modifying the spec or the readers.

• This is a political compromise; some entity with political power pushed it into the BSI spec; possibly because they were card manufacturers that were already using other curves (and BSI decided they didn't want to endorse those curves for whatever reason); possibly because it gave someone a competitive advantage (our password validation equipment does it, our competitor's does not; forcing this in will delay our competitor) or possibly because some bureaucrat got it into their head that this was a good idea.

As for whether coming up with safe domain parameters is non-trivial, well, yeah, it's not something you'd want to hand off to an intern; however the known potential attacks against elliptic curves are well documented; it's not that difficult for someone who knows what they're doing to come up with curve parameters that make all known attacks infeasible. In fact, there's this paper where they suggest literally creating a fresh elliptic curve for every single key exchange.

• Hmm, ok. The point here seems to be that coming up with safe domain parameters isn't as hard as I thought. Thanks. – Mike Ounsworth Aug 26 '16 at 3:14
• Bouncy Castle even has an implementation for generating domain parameters. It takes waaaay too much time, but it does work. – Maarten - reinstate Monica Aug 26 '16 at 11:40

Political reasons likely wins. E.g. France has an own set of domain parameters. Note that when the spec was created that the Brainpool curves where rather new.

Generating safe parameters is not trivial, but we're talking countries here. Most of them will simply copy what's out there or buy a solution, but a few of the more advanced ones can try other curves they've generated themselves, in their own secure environments. Note that you'd still use $F(p)$ or $F(2^m)$ curves, so any generic attacks will still be present, whichever curve is used. You cannot just insert one of the "Safe Curves".

It's of course absolute hell to test all possible configurations (which is required if you're building a solution that needs to read out ePassports) and IMHO there are way too many optional elements in the spec. Problem is that setting up a registry among all possible countries - and then updating the software - is next to impossible as well. Otherwise just a number could have sufficed.

• I don't think you need to be on drugs to make questionable decisions in standards. Plenty of people are able to do so without illegal substances. I'm not sure if this one counts though. Technically you would just choose e.g. a single ECC 384 bit curve, but try and get everybody to back that. Generating domain parameters is not that hard, convincing everybody that they're safe is. – Maarten - reinstate Monica Aug 26 '16 at 11:56
• The French curve FRP256v1 is published on the Journal Officiel, with some extra explanations given by ANSSI. But how it was generated seems to be a state secret, making things worse than for the NIST P256 curve, where we have an alleged generation method, if not the seed. – fgrieu Aug 26 '16 at 12:00
• @fgrieu Yeah, just amended my comment above to say the same :P Note that the curve is protecting the security of the citizens of France. So they probably don't care too much. Brainpool curves are clearly defined for more generic use. – Maarten - reinstate Monica Aug 26 '16 at 12:01

Why should anyone be "on nuts" because he gives the system integrator the freedom to choose the curve he wants? If they didn't give that freedom, I am pretty sure that many people would say: "Well, they force us to use that curves. There is surely a backdoor in there!".

On the other hand, A2.1.1 claims that one SHOULD use standardized domain parameters.