Re: EC weirdness

[Adam Petcher]

On 7/19/2018 3:36 PM, Michael StJohns wrote:


On 7/16/2018 4:42 PM, Adam Petcher wrote:

Though it has the additional benefit...


Actually...

The implementation may also need...


Nope...


I think that you interpreted my statements a bit more specifically that 
I intended. I was speaking in more general terms about ECC libraries in 
the JDK and elsewhere, because they are all motivated by the same 
forces. You may wan to read what I wrote again so you will more easily 
understand my position below.




In the scheme, G' is secret.  This is basically the EC version of 
https://en.wikipedia.org/wiki/SPEKE.


I may do a bit more archeology and see whether there are actual 
dependencies on the build in curve data (e.g. PKCS11).  If not, I may 
try and provide a patch refactoring out that limitation and doing a 
more thorough separation of the math from the packaging.


I've been seeing a lot of interest in PAKE lately, so it may be 
worthwhile for us to do some work to support common PAKE schemes, 
especially if this support can be provided on top of existing DH 
implementations with small modifications. Though I think SPEKE can be 
implemented in other ways, and I'm still not convinced that this example 
provides enough motivation to support arbitrary base points.


Here are some other approaches you may want to consider:

1) Use three-party Diffie-Hellman. You can view the password as some 
other party for whom nobody knows the private key, but authorized 
parties know the public key. I think this accomplishes the same thing, 
and I find it more agreeable than supporting arbitrary base points in 
KeyPairGenerator. In pseudocode:


PublicKey passwordKey = Hash(password)...
KeyPairGenerator kpg = ...
KeyAgreement ka = ...
KeyPair myPair = ka.generateKeyPair();
ka.init(myPair.getPrivate());
Key keyToBob = ka.doPhase(passwordKey, false);
Key keyFromBob = exchangeWithBob(keyToBob);
ka.doPhase(keyFromBob, true);
byte[] sharedSecret = ka.generateSecret()

Of course, you run into the problem that many DH implementations in the 
JDK only support two-party DH. You could start by seeing if this works 
with the "DiffieHellman" service. Adding support for multi-party DH 
would be trivial for X25519/X448, but may be harder for the older ECC 
implementation.


2) If you are willing to use the JDK 11 early access build, and use an 
internal API, then you can do what you want using X25519/X448 and the 
XECOperations class. It doesn't really allow arbitrary base points, but 
you can freely do scalar-point multiplications. I'm assuming this isn't 
what you want, but let me know if you want more details on how to use 
this class.


3) If there is sufficient demand for it (and someone who is willing to 
implement it), we might want to consider adding a crypto service for 
some standard PAKE scheme.

Re: EC weirdness

[Michael StJohns]

On 7/16/2018 4:42 PM, Adam Petcher wrote:
I think the reason for the hard-coded curves is largely historical, 
and I don't know of a security-related reason for it (other than the 
prevention of insecure parameters). Though it has the additional 
benefit that it simplifies the interface a lot, because the 
implementation for a curve is not completely determined by the domain 
parameters. 


Actually - they are.  An ECGenParameterSpec  (basically a named curve) 
is turned into an ECParameterSpec  (the actual curve and G stuff) which 
is turned into an AlgorithmSpecification of type (SunEC, EC) which 
strangely tries to do a reverse lookup of the parameter spec to get a 
name for the curve.   (That's not exactly it, but its close in spirit).


The implementation may also need to know which optimized finite field 
implementation, precomputed tables, etc to use. Looking up all of 
these things at once can be a lot simpler than trying to specify them 
over an interface.


Nope - that's not it.  The underlying C code mostly uses generic bignum 
operations on the curve parameters rather than pre-computed things.


My guess is that there were some dependencies on named curves in the EC 
library and the EC related stuff in the PKCS11 library.




I'm trying to figure out if your problem motivates support for 
arbitrary base points, or if there is another way to get what you 
want. Is the base point a secret in your scheme? Either way, can you 
implement your scheme using KeyAgreement (e.g. using the "base point" 
as the public key and a random integer as the private key)? What if 
ECDH KeyAgreement supported three-party Diffie-Hellman, or you extract 
a point from generateSecret()? Would that help?


In the scheme, G' is secret.  This is basically the EC version of 
https://en.wikipedia.org/wiki/SPEKE.  Two key pairs generated on P-256' 
(e.g. same curve params, but with G'), can use ECDH to get to the same 
shared secret.   If your key pair wasn't generated with G', then you 
can't get to the same secret with someone who's key pair was.


This is sort of an IOT experiment - I don't want to have to do an 
explicit authorization via a certificate binding a public key.  I can 
generate a group G', and have all the various devices generate a key 
pair using that G'.   The ability to get a pairwise shared secret with 
another device proves the membership in the group to that other device 
and vice versa.


The problem with using ECDH is that generic ECDH operations throw away 
the Y coordinate.  I can do xG' -> X'  using the SunEC ECDH, but what I 
actually get as a result is the scalar X'.x.


I've been trying to avoid using external libraries, but I'll probably 
end up using the BC point math stuff to make this work.


I may do a bit more archeology and see whether there are actual 
dependencies on the build in curve data (e.g. PKCS11).  If not, I may 
try and provide a patch refactoring out that limitation and doing a more 
thorough separation of the math from the packaging.


Later, Mike




On 7/13/2018 9:30 PM, Michael StJohns wrote:

Hi -

Every so often I run into some rather strange things in the way the 
Sun EC classes were built.  Most recently, I was trying to use the 
SunEC provider to do a PACE like protocol.  Basically, the idea was 
to be able to generate public key points on the P-256 curve, but with 
a different base point G (knowledge of G' or having a public key 
generated from G' would allow you to do a valid ECDH operation, keys 
with disjoint points would not).


I was able to generate a normal key pair using ECGenParameterSpec 
with a name, so I grabbed the ECParameterSpec from the public key, 
made a copy of most of the stuff (curve, cofactor), but substituted 
the public point W from the key pair I'd just generated, and passed 
that in as G to the new parameter spec.  I tried to initialize the 
KPG with my *almost* P-256 spec, and it failed with "unsupported curve".


Looking into the code and tracing through 
sun.crypto.ec.ECKeyPairGenerator to the native code, I'm once again 
surprised that all of the curves are hard coded into the C native 
code, rather than being passed in as data from the Java code.


Is there a good security reason for hard coding the curves at the C 
level that I'm missing?


This comes under the heading of unexpected behavior rather than a bug 
per se I think.   Although - I'd *really* like to be able to pass a 
valid ECParameterSpec in to the generation process and get whatever 
keys are appropriate for that curve and base point.


Later, Mike

EC weirdness

[Michael StJohns]

Hi -

Every so often I run into some rather strange things in the way the Sun 
EC classes were built.  Most recently, I was trying to use the SunEC 
provider to do a PACE like protocol.  Basically, the idea was to be able 
to generate public key points on the P-256 curve, but with a different 
base point G (knowledge of G' or having a public key generated from G' 
would allow you to do a valid ECDH operation, keys with disjoint points 
would not).


I was able to generate a normal key pair using ECGenParameterSpec with a 
name, so I grabbed the ECParameterSpec from the public key, made a copy 
of most of the stuff (curve, cofactor), but substituted the public point 
W from the key pair I'd just generated, and passed that in as G to the 
new parameter spec.  I tried to initialize the KPG with my *almost* 
P-256 spec, and it failed with "unsupported curve".


Looking into the code and tracing through 
sun.crypto.ec.ECKeyPairGenerator to the native code, I'm once again 
surprised that all of the curves are hard coded into the C native code, 
rather than being passed in as data from the Java code.


Is there a good security reason for hard coding the curves at the C 
level that I'm missing?


This comes under the heading of unexpected behavior rather than a bug 
per se I think.   Although - I'd *really* like to be able to pass a 
valid ECParameterSpec in to the generation process and get whatever keys 
are appropriate for that curve and base point.


Later, Mike