[TLS] On Curve25519 and other possibilities (e.g. ietf256p, ietf384p, ietf521p,

[Michael StJohns <[e-mail]>]

There's been a small but vocal minority agitating for the adoption of 
Curve25519 for use in TLS (and other IETF protocols).  As the discussion 
has gone on, what I haven't seen is compelling evidence that this 
technology has been vetted sufficiently that it would meet the "Best 
Commercial Practices" threshold for safe harbor status for encryption.  
It may eventually get there, but for at least the next few (5-10??) 
years, I would expect businesses to avoid the use in privacy sensitive, 
or financially sensitive operations.

There are also possible IPR issues, definite infrastructure issues (e.g. 
no off the shelf, commercial hardware or software AFAIK), documentation 
issues (not the base curve, but how to incorporate curve data into 
certificates and other protocol messages, and the fact it's key 
agreement only (vs the current EC curves which can be used for both 
signature and agreement).  A long list of items that probably, but not 
definitely, can be resolved.

AFACT, one of the main reasons for looking at Curve25519 (possibly more 
important than performance or security) is that there is a fear that the 
US Government has placed trapdoors in the current set of curves (NIST 
P256, P384, P521 etc).   The argument against the "provably random" 
creation claim with respect to those curves appears to be that many 
"seed" values could have been generated to generate curve parameters and 
those curves tested to find "weak" curves of a particular flavor and the 
seeds for weak curves retained.  In other words, we don't know how the 
seed values were generated and it could be nefarious.  I haven't as yet 
found any argument against the generation process, nor specifically 
against the elliptic curve math.

Given that the EC math in FIPS186, X9.62, X9.63, SP800-56A, SEC1, and 
the various ISO documents is pretty much identical, instead of throwing 
away all that implementation and standardization, how about we just 
generate new curves:

1) 20 organizations publicly contribute random/pseudo-random strings of 
1kbits - they get to decide exactly which bits to send.
1a) discard any of these with detectable bias.
2) Randomly select 10 sets of contributed bits from those remaining 
(using public randomness sources to select those to be retained).
3) Concatenate the bits in a random order (using public randomness 
sources such as stock prices etc to select the order).
4) Run the concatenated data through an entropy extraction process (e.g. 
hash, hmac, other PRF) to produce a seed value of sufficient length. (or 
seed values if all the curves come from this one pass).
5) Generate the curve data and generator points from the seed.
6) Assign IETF OIDs to each curve generated this way.
7) Permanently record ALL the data used to generate the curves so we 
don't have future conspiracy theories.

For most of libraries and hardware devices with which I work, the curve 
data is pretty much static configuration (external table referenced by 
OID) or compilation (ditto but compiled in), or provided as a library 
argument and most libraries have a mechanism to insert or use new curves 
fairly easily - at least within the same family.  I'd recommend that we 
generate curves equivalent in strength to the current NIST curves in all 
of prime, binary and koblitz flavors.

Mike