Re: [TLS] Safe ECC usage

[Kyle Hamilton <[e-mail]>]

Dr Bernstein,

That's all well and good, but perhaps should you try to figure out how your
functions can in fact be used in such standards as TLS without having to
resort to pulling hens' teeth?

Or perhaps apply your (admittedly much better than mine) intellect to
figure out how to create a single public key from a single private key
which can be used for both signing and key derivation, thus permitting
consolidation of both into a single X.509 Certificate structure?  The lack
of this is in fact a major impediment to using self-signed certificates as
containers for curve25519 public keys.

Granted, I've been severely out of touch for quite a while, and it's
possible that (e.g.) Ed25519 permits the use of the same public key in this
manner (even though Ed25519 has a peculiar recordkeeping requirement which
makes it less than ideal).  If it does, please accept my humble apology.
If it does not, however, I'd like to ask you to design a function which can
be used for both signature and derivation from the same public key, so as
to create a clear path forward for at least one (if not more)
externally-developed elliptical function for ease of integration into the
preexisting TLS (and perhaps more importantly PKI) infrastructure.

BULLRUN's first major visible success was in inducing everyone to think
about "how do you know it's who you think you're talking to?", completely
ignoring SSLv1's opportunistic encryption.  Netscape carried this further
by simply refusing to speak with SSL sites that didn't authenticate
themselves.  I don't know if there is any webserver out there that will do
TLS without an identity certificate, and even if there is I doubt there is
a client that will communicate in those conditions.  So, we need at the
very least a self-signed certificate to carry the public key used to derive
the shared key.

(Also, while I've hopefully got your attention, have you any plan to create
an x64 ABI for Curve25519?  I'm currently having to use it via a COM
wrapper I hacked up in C#, 64-bit processes calling via COM to a 32-bit
process which exports only one function that COM doesn't mandate:
curve25519(). This is insecure to COM-debug capable processes at the very
least, as it requires that the caller provide the caller's private key over
a public data bus.)

I have the utmost respect for your knowledge and intellect, but without
having a plan to fit your function into a common framework, there is simply
no way to use the function you keep trying to promote.

-Kyle H

(Note: I would -love- to find out that I'm wrong, on any or all of this.)


On Thu, Sep 26, 2013 at 8:27 AM, D. J. Bernstein <[e-mail]> wrote:

> Modern elliptic-curve cryptography solidly takes care of all of the
> "brittleness" mentioned in this thread, and is much easier than RSA to
> implement securely. Compare https://twitter.com/tweetnacl to the amount
> of code required to implement similar functionality in OpenSSL.
>
> Peter Gutmann writes:
> > potentially NSA-influenced values like P256
>
> There is indisputably an unexplained seed c49d3608 86e70493 6a6678e1
> 139d26b7 819f7e90 for the NIST P-256 curve mod 2^256-2^224+2^192+2^96-1,
> and similarly for the other NIST curves. This was identified by the 2005
> Brainpool standard as a major issue for the NIST curves; it has also
> been highlighted recently by Bruce Schneier.
>
> Fortunately, one can design high-security elliptic curves that don't
> have any unexplained constants. That's what I did with Curve25519.
> Curve25519 is the curve y^2=x^3+486662x^2+x mod 2^255-19; every number
> here is completely explained in the Curve25519 paper.
>
> > even without NSA skullduggery make a nice single target for attack.
>
> There have already been several detailed studies of the cost of finding
> multiple discrete logs on the same curve (authors: Escott, Sager,
> Selkirk, Tsapakidis, Kuhn, Struik, Hitchcock, Montague, Carter, Dawson,
> Lee, Cheon, Hong, Bernstein, Lange). Basically, if finding one ECC key
> costs 2^128, then finding 1000000 keys costs 1000*2^128, and the first
> key found will still cost 2^128. For comparison, finding 1000000 AES
> keys costs the same 2^128 as finding a single key, and the first AES key
> will be found with cost only 2^128/1000000.
>
> Yaron Sheffer writes:
> > The recipient needs to test that the received point is actually on
> > the relevant curve.
>
> This is certainly an issue for the NIST curves. Fortunately, this test
> is completely unnecessary for x-coordinate ECC using twist-secure curves
> such as Curve25519. I introduced this approach at ECC 2001, using the
> smaller curve y^2=x^3+7530x^2+x mod 2^226-5 as an illustration.
>
> Peter Gutmann writes:
> > For example if you used the recommended (until not too long ago) way
> > to generate your k for (EC)DSA then you'd leak a tiny bit of your
> > private key on each signature (again, that nasty propensity of DLP
> > algorithms to leak the private key).
>
> Ed25519 has three levels of defense against this type of problem.
>
> First, k is chosen as a random 512-bit string, many bits larger than the
> group order l (around 2^252). This is overkill (compare to the 64 bits
> in Algorithm 2 in Section 4.1.1 of BSI Technical Guideline TR-03111) but
> also an inexpensive and comprehensive defense.
>
> Second, the group order l is very close to a power of 2, specifically
> within 2^125 of 2^252, so the bias would be unnoticeable even if k were
> as small as 256 bits.
>
> Third, k is actually produced in a deterministic way as a secret hash,
> so the k-generation mechanism is fully testable---there's no need to
> worry about the implementor accidentally choosing a biased RNG.
>
> ---D. J. Bernstein
>    Research Professor, Computer Science, University of Illinois at Chicago
> _______________________________________________
> TLS mailing list
> [e-mail]
> https://www.ietf.org/mailman/listinfo/tls
>