Conceptual feedback on new ECC JEP

classic Classic list List threaded Threaded
37 messages Options
12
Reply | Threaded
Open this post in threaded view
|

Conceptual feedback on new ECC JEP

Adam Petcher
I'm starting work on yet another ECC JEP[1], this time with the goal of
developing improved implementations of existing algorithms, rather than
implementing new ones. The JEP will re-implement ECDH and ECDSA for the
256-, 384-, and 521-bit NIST prime curves. The new implementation will
be all Java, and will resist side-channel attacks by not branching on
secrets. It will go in a new provider which is not in the provider list
in the java.security file by default. So it will need to be manually
enabled by changing the configuration or putting the new provider name
in the code. It will only support a subset of the API that is supported
by the implementation in SunEC. In particular, it will reject any
private keys with scalar values specified using BigInteger (as in
ECPrivateKeySpec), and its private keys will not return scalar values as
BigInteger (as in ECPrivateKey.getS()).

Please take a look and send me any feedback you have. I'm especially
looking for suggestions on how this new implementation should fit into
the API. I would prefer to have it enabled by default, but I can't think
of a way to do that without either branching on secrets in some cases
(converting a BigInteger private key to an array) or breaking
compatibility (throwing an exception when it gets a BigInteger private key).

[1] https://bugs.openjdk.java.net/browse/JDK-8204574

Reply | Threaded
Open this post in threaded view
|

Re: Conceptual feedback on new ECC JEP

Michael StJohns
On 8/23/2018 1:50 PM, Adam Petcher wrote:
> It will only support a subset of the API that is supported by the
> implementation in SunEC. In particular, it will reject any private
> keys with scalar values specified using BigInteger (as in
> ECPrivateKeySpec), and its private keys will not return scalar values
> as BigInteger (as in ECPrivateKey.getS()).

Um... why?   EC Private keys are integers.... I've said this multiple
times and - with the single exception of EDDSA keys because of a very
idiosyncratic (and IMHO short-sighted) RFC specification - all of the EC
private keys of whatever curve can be expressed as integers.

Mike


Reply | Threaded
Open this post in threaded view
|

Re: Conceptual feedback on new ECC JEP

Adam Petcher
On 9/1/2018 2:03 PM, Michael StJohns wrote:

> On 8/23/2018 1:50 PM, Adam Petcher wrote:
>> It will only support a subset of the API that is supported by the
>> implementation in SunEC. In particular, it will reject any private
>> keys with scalar values specified using BigInteger (as in
>> ECPrivateKeySpec), and its private keys will not return scalar values
>> as BigInteger (as in ECPrivateKey.getS()).
>
> Um... why?   EC Private keys are integers.... I've said this multiple
> times and - with the single exception of EDDSA keys because of a very
> idiosyncratic (and IMHO short-sighted) RFC specification - all of the
> EC private keys of whatever curve can be expressed as integers.
>

The explanation is in the JEP:

"The existing API for ECC private keys has some classes that specify
private scalar values using BigInteger. There is no way to get a value
out of a BigInteger (into, for example, a fixed-length array) without
branching."

There is no problem with making private keys integers in the API. The
problem is specifically with BigInteger and its implementation.
BigInteger stores the value in the shortest int array possible. To
access the value, you need to branch on the length of the array, which
leaks whether the high-order bits of the private key are 0.


Reply | Threaded
Open this post in threaded view
|

Re: Conceptual feedback on new ECC JEP

Michael StJohns
Below

On 9/4/2018 8:57 AM, Adam Petcher wrote:

> On 9/1/2018 2:03 PM, Michael StJohns wrote:
>
>> On 8/23/2018 1:50 PM, Adam Petcher wrote:
>>> It will only support a subset of the API that is supported by the
>>> implementation in SunEC. In particular, it will reject any private
>>> keys with scalar values specified using BigInteger (as in
>>> ECPrivateKeySpec), and its private keys will not return scalar
>>> values as BigInteger (as in ECPrivateKey.getS()).
>>
>> Um... why?   EC Private keys are integers.... I've said this multiple
>> times and - with the single exception of EDDSA keys because of a very
>> idiosyncratic (and IMHO short-sighted) RFC specification - all of the
>> EC private keys of whatever curve can be expressed as integers.
>>
>
> The explanation is in the JEP:
>
> "The existing API for ECC private keys has some classes that specify
> private scalar values using BigInteger. There is no way to get a value
> out of a BigInteger (into, for example, a fixed-length array) without
> branching."
>
> There is no problem with making private keys integers in the API. The
> problem is specifically with BigInteger and its implementation.
> BigInteger stores the value in the shortest int array possible. To
> access the value, you need to branch on the length of the array, which
> leaks whether the high-order bits of the private key are 0.
>
>

*buzz* wrong answer.   Sorry.   The internal storage of the key can be
anything you want it to be if you want to prevent a non-constant-time
issue for normal calculation.  But the import/export of the key really
isn't subject to the cargo cult "must not branch" dogma - hint - I'm
moving across a security boundary line anyway.    So if I do a
"getEncoded()" or a "getS()" on an ECPrivateKey object or provide a
BigInteger on an ECPrivateKeySpec there is no additional threat over the
presence of the private key bits in public space.

If you believe this to be such a problem, then I'd suggest instead
updating BigInteger to allow for BigEndian or LittleEndian encoding
input/output and fix the constant time issue there inside the
implementation rather than breaking public APIs.

Alternately, I guess you could throw some sort of exception if someone
tries to call getS() or getEncoded().  Or you could do what PKCS11 does
for non-extractable private keys and only class the private key as a
PrivateKey - make it opaque.  But then how do you create the key from
stored information?

Later, Mike

Reply | Threaded
Open this post in threaded view
|

Re: Conceptual feedback on new ECC JEP

Adam Petcher
On 9/4/2018 2:01 PM, Michael StJohns wrote:

> Below
>
> *buzz* wrong answer.   Sorry.   The internal storage of the key can be
> anything you want it to be if you want to prevent a non-constant-time
> issue for normal calculation.  But the import/export of the key really
> isn't subject to the cargo cult "must not branch" dogma - hint - I'm
> moving across a security boundary line anyway.    So if I do a
> "getEncoded()" or a "getS()" on an ECPrivateKey object or provide a
> BigInteger on an ECPrivateKeySpec there is no additional threat over
> the presence of the private key bits in public space.

I think what you are suggesting is that the implementation should
convert between BigInteger and the internal representation when
necessary. The problem with this approach is that it is too easy to
inadvertently supply a BigInteger to the implementation, and this would
result in a branch. I understand that this branch may be acceptable in
some circumstances, but we would need something in the API to tell the
implementation whether it is okay to branch or not. I think the simplest
way to do that is to have a provider that never branches. If branching
is okay, then SunEC can be used.

>
> If you believe this to be such a problem, then I'd suggest instead
> updating BigInteger to allow for BigEndian or LittleEndian encoding
> input/output and fix the constant time issue there inside the
> implementation rather than breaking public APIs.

BigInteger wasn't designed for this sort of thing, and changing it so
that supports constant-time encoding/decoding is a massive undertaking,
if it is even possible. It would be more reasonable to add a new public
type for integers that supports constant-time operations, but I don't
think that helps us here.

>
> Alternately, I guess you could throw some sort of exception if someone
> tries to call getS() or getEncoded().  Or you could do what PKCS11
> does for non-extractable private keys and only class the private key
> as a PrivateKey - make it opaque.  But then how do you create the key
> from stored information?

That's essentially the plan. Calling PrivateKey::getEncoded will return
null, which is a convention for non-extractable keys. Trying to convert
from/to an ECPrivateKeySpec using the KeyFactory in the new provider
will result in an exception---so you won't have an object to call getS()
on.

To create the key from stored information, the best way is to construct
a PKCS8EncodedKeySpec using the encoded key. If you are starting with a
BigInteger, and if branching is acceptable, you can use the KeyFactory
from SunEC to convert an ECPrivateKeySpec to PrivateKey to get the
encoded value.

Reply | Threaded
Open this post in threaded view
|

Re: Conceptual feedback on new ECC JEP

Michael StJohns
On 9/4/2018 3:19 PM, Adam Petcher wrote:
I think what you are suggesting is that the implementation should convert between BigInteger and the internal representation when necessary. The problem with this approach is that it is too easy to inadvertently supply a BigInteger to the implementation, and this would result in a branch. I understand that this branch may be acceptable in some circumstances, but we would need something in the API to tell the implementation whether it is okay to branch or not. I think the simplest way to do that is to have a provider that never branches. If branching is okay, then SunEC can be used.

Basically yes.  

But I don't understand what you mean by "inadvertently supply a BigInteger"?  AFAICT, you "supply" a BigInteger in an ECPrivateKeySpec and you retrieve one when you call getEncoded() or getS().    Your implementation would convert between the BigInteger and internal representation during the use of the engineGeneratePrivate() method of the KeyFactorySpi and would convert from your internal representation when exporting S, or encoding something as PKCS8.

Again - you're wrongly conflating interface requirements with implementation requirements. 

And how do you expect to move key material between SunEC and this implementation?  See below for my commentary on that.


That's essentially the plan. Calling PrivateKey::getEncoded will return null, which is a convention for non-extractable keys. Trying to convert from/to an ECPrivateKeySpec using the KeyFactory in the new provider will result in an exception---so you won't have an object to call getS() on.
That's not what PKCS11 does - it just gives you a "PrivateKey" object with an internal type of sun.security.pkcs11.P11Key.  While that object is not type safe exactly, it is provider safe.

You're still wanting to use the various EC classes of java.security, java.security.spec, and java.security.interfaces, but you're unwilling to actually meet their contracts for some really suspect reasons.



To create the key from stored information, the best way is to construct a PKCS8EncodedKeySpec using the encoded key. If you are starting with a BigInteger, and if branching is acceptable, you can use the KeyFactory from SunEC to convert an ECPrivateKeySpec to PrivateKey to get the encoded value.

Umm... what? 

If you were doing NewEC -> SunEC manually (getEncoded() -> KeySpec) - you'll need to end up emitting a PKCS8 blob using RFC5915, which - unsurprisingly has  BigEndian INTEGERs  (yes, its an octet string, but the encoding is specified by RFC3447 as pretty much the big endian encoding of an integer).  E.g. it may look opaque from Java's point of view, but it's not really opaque. (See below)

Or have you got a different way of encoding the PKCS8 blob for the new provider?  E.g. point me at a specification please.

My head hurt when I tried to work through the various cases of translating a private key from your provider to SunEC or to BouncyCastle and vice versa.  Basically, if you don't support the getS() call, then KeyFactory.translateKey() will fail.  (Below from sun.security.ec.ECKeyFactory.java - the SunEC provider's implementation).

 private PrivateKey implTranslatePrivateKey(PrivateKey key)
            throws InvalidKeyException {
        if (key instanceof ECPrivateKey) {
            if (key instanceof ECPrivateKeyImpl) {
                return key;
            }
            ECPrivateKey ecKey = (ECPrivateKey)key;
            return new ECPrivateKeyImpl(
                ecKey.getS(),
                ecKey.getParams()
            );
        } else if ("PKCS#8".equals(key.getFormat())) {
            return new ECPrivateKeyImpl(key.getEncoded());
        } else {
            throw new InvalidKeyException("Private keys must be instance "
                + "of ECPrivateKey or have PKCS#8 encoding");
        }
    



4.1 I2OSP

I2OSP converts a nonnegative integer to an octet string of a specified length. I2OSP (x, xLen) Input: x nonnegative integer to be converted xLen intended length of the resulting octet string Output: X corresponding octet string of length xLen Error: "integer too large" Steps: 1. If x >= 256^xLen, output "integer too large" and stop. 2. Write the integer x in its unique xLen-digit representation in base 256: x = x_(xLen-1) 256^(xLen-1) + x_(xLen-2) 256^(xLen-2) + ... + x_1 256 + x_0, where 0 <= x_i < 256 (note that one or more leading digits will be zero if x is less than 256^(xLen-1)). 3. Let the octet X_i have the integer value x_(xLen-i) for 1 <= i <= xLen. Output the octet string X = X_1 X_2 ... X_xLen.

Reply | Threaded
Open this post in threaded view
|

Re: Conceptual feedback on new ECC JEP

Adam Petcher
On 9/4/2018 5:20 PM, Michael StJohns wrote:

> On 9/4/2018 3:19 PM, Adam Petcher wrote:
>> I think what you are suggesting is that the implementation should
>> convert between BigInteger and the internal representation when
>> necessary. The problem with this approach is that it is too easy to
>> inadvertently supply a BigInteger to the implementation, and this
>> would result in a branch. I understand that this branch may be
>> acceptable in some circumstances, but we would need something in the
>> API to tell the implementation whether it is okay to branch or not. I
>> think the simplest way to do that is to have a provider that never
>> branches. If branching is okay, then SunEC can be used.
>
> Basically yes.
>
> But I don't understand what you mean by "inadvertently supply a
> BigInteger"?  AFAICT, you "supply" a BigInteger in an ECPrivateKeySpec
> and you retrieve one when you call getEncoded() or getS().    Your
> implementation would convert between the BigInteger and internal
> representation during the use of the engineGeneratePrivate() method of
> the KeyFactorySpi and would convert from your internal representation
> when exporting S, or encoding something as PKCS8.
>

I mean that the JCA client code may put a private key value in an
ECPrivateKeySpec and give it to the KeyFactory of the new ECC
implementation. Also problematic is calling getS() on an ECPrivateKey
from the new implementation and converting the private key to a
BigInteger. Both of these situations may leak some bits of the private
key value into side channels, and the use of the "NewEC" provider is an
assertion by the programmer/environment that these side-channel leaks
are unacceptable. So the new provider will prevent these problems by
rejecting ECPrivateKeySpec in its KeyFactory, and by returning null from
getS(). BigInteger will not be used by engineGeneratePrivate when the
spec is a PKCS8EncodedKeySpec (the only option). BigInteger is also not
required to encode/decode a PKCS#8 private key.

> Again - you're wrongly conflating interface requirements with
> implementation requirements.
>
> And how do you expect to move key material between SunEC and this
> implementation?  See below for my commentary on that.
>
>
>> That's essentially the plan. Calling PrivateKey::getEncoded will
>> return null, which is a convention for non-extractable keys. Trying
>> to convert from/to an ECPrivateKeySpec using the KeyFactory in the
>> new provider will result in an exception---so you won't have an
>> object to call getS() on.
> That's not what PKCS11 does - it just gives you a "PrivateKey" object
> with an internal type of sun.security.pkcs11.P11Key.  While that
> object is not type safe exactly, it is provider safe.
>
> You're still wanting to use the various EC classes of java.security,
> java.security.spec, and java.security.interfaces, but you're unwilling
> to actually meet their contracts for some really suspect reasons.
>

Sorry, I referred to the wrong methods in my last e-mail.
ECPrivateKey::getS will return null in the new implementation. The
getEncoded method will return the encoded key, as usual. The second
sentence referred to ECPrivateKeySpec::getS, which will remain
unchanged, but you won't be able to use ECPrivateKeySpec with the new
provider.

I don't believe my proposal violates the contracts of any of these
classes, but if you believe that it does (after the correction above),
then let me know which contracts are violated.

>
>>
>> To create the key from stored information, the best way is to
>> construct a PKCS8EncodedKeySpec using the encoded key. If you are
>> starting with a BigInteger, and if branching is acceptable, you can
>> use the KeyFactory from SunEC to convert an ECPrivateKeySpec to
>> PrivateKey to get the encoded value.
>
> Umm... what?
>
> If you were doing NewEC -> SunEC manually (getEncoded() -> KeySpec) -
> you'll need to end up emitting a PKCS8 blob using RFC5915, which -
> unsurprisingly has  BigEndian INTEGERs (yes, its an octet string, but
> the encoding is specified by RFC3447 as pretty much the big endian
> encoding of an integer). E.g. it may look opaque from Java's point of
> view, but it's not really opaque. (See below)
>
> Or have you got a different way of encoding the PKCS8 blob for the new
> provider?  E.g. point me at a specification please.
>

There is no issue with integers or endianness. The problem is
specifically with BigInteger---it uses a variable-length representation,
and it's spec does not give any guarantees about branching. The PKCS#8
encoding is fine because it is fixed length, so I can directly use the
privateKey octet string (with bytes reversed, if necessary) in a
branchless double-and-add loop.

> My head hurt when I tried to work through the various cases of
> translating a private key from your provider to SunEC or to
> BouncyCastle and vice versa.  Basically, if you don't support the
> getS() call, then KeyFactory.translateKey() will fail. (Below from
> sun.security.ec.ECKeyFactory.java - the SunEC provider's implementation).
>
>>  private PrivateKey implTranslatePrivateKey(PrivateKey key)
>>             throws InvalidKeyException {
>>         if (key instanceof ECPrivateKey) {
>>             if (key instanceof ECPrivateKeyImpl) {
>>                 return key;
>>             }
>>             ECPrivateKey ecKey = (ECPrivateKey)key;
>>             return new ECPrivateKeyImpl(
>>                 ecKey.getS(),
>>                 ecKey.getParams()
>>             );
>>         } else if ("PKCS#8".equals(key.getFormat())) {
>>             return new ECPrivateKeyImpl(key.getEncoded());
>>         } else {
>>             throw new InvalidKeyException("Private keys must be
>> instance "
>>                 + "of ECPrivateKey or have PKCS#8 encoding");
>>         }
>

The code above could be improved by using the PKCS#8 encoding when
getS() returns null.

The only way to get private keys in or out of the new provider is
through a PKCS#8 encoding. Moving keys to/from another provider that
supports ECPrivateKeySpec but not PKCS#8 encoding can be accomplished by
translating the specs---possibly with the help of a KeyFactory that
supports both, like the one in SunEC.


Reply | Threaded
Open this post in threaded view
|

Re: Conceptual feedback on new ECC JEP

Michael StJohns
On 9/5/2018 2:47 PM, Adam Petcher wrote:

> On 9/4/2018 5:20 PM, Michael StJohns wrote:
>
>> On 9/4/2018 3:19 PM, Adam Petcher wrote:
>>> I think what you are suggesting is that the implementation should
>>> convert between BigInteger and the internal representation when
>>> necessary. The problem with this approach is that it is too easy to
>>> inadvertently supply a BigInteger to the implementation, and this
>>> would result in a branch. I understand that this branch may be
>>> acceptable in some circumstances, but we would need something in the
>>> API to tell the implementation whether it is okay to branch or not.
>>> I think the simplest way to do that is to have a provider that never
>>> branches. If branching is okay, then SunEC can be used.
>>
>> Basically yes.
>>
>> But I don't understand what you mean by "inadvertently supply a
>> BigInteger"?  AFAICT, you "supply" a BigInteger in an
>> ECPrivateKeySpec and you retrieve one when you call getEncoded() or
>> getS().    Your implementation would convert between the BigInteger
>> and internal representation during the use of the
>> engineGeneratePrivate() method of the KeyFactorySpi and would convert
>> from your internal representation when exporting S, or encoding
>> something as PKCS8.
>>
>
> I mean that the JCA client code may put a private key value in an
> ECPrivateKeySpec and give it to the KeyFactory of the new ECC
> implementation. Also problematic is calling getS() on an ECPrivateKey
> from the new implementation and converting the private key to a
> BigInteger. Both of these situations may leak some bits of the private
> key value into side channels, and the use of the "NewEC" provider is
> an assertion by the programmer/environment that these side-channel
> leaks are unacceptable. So the new provider will prevent these
> problems by rejecting ECPrivateKeySpec in its KeyFactory, and by
> returning null from getS(). BigInteger will not be used by
> engineGeneratePrivate when the spec is a PKCS8EncodedKeySpec (the only
> option). BigInteger is also not required to encode/decode a PKCS#8
> private key.

BigInteger is not required to encode a PKCS8 key, but its trivial to
translate from BigInteger to PKCS8 and vice versa.  Note that
internally, the current BigInteger stores the magnitude as an array of
int in big endian order and stores the sign separately.  The BigInteger
(int sigNum, byte[] magnitude) constructor mostly just copies the
magnitude bytes over (and converts 4 bytes to an integer) for positive
integers.   While the current BigInteger doesn't have a byte[]
BigInteger.getMagnitude() call, it would be trivial to subclass
BigInteger to copy the magnitude bytes (without branching) out.

In any event, for NewEC to OldEc - you do use the sign/magnitude call to
create the BigInteger - no leaking on the part of NewEC, and once it
gets to OldEC its not your problem.  For OldEc to NewEc you copy the
BigInteger to NewBigInteger (trivial wrapper class) and do a
getMagnitude().

>
>> Again - you're wrongly conflating interface requirements with
>> implementation requirements.
>>
>> And how do you expect to move key material between SunEC and this
>> implementation?  See below for my commentary on that.
>>
>>
>>> That's essentially the plan. Calling PrivateKey::getEncoded will
>>> return null, which is a convention for non-extractable keys. Trying
>>> to convert from/to an ECPrivateKeySpec using the KeyFactory in the
>>> new provider will result in an exception---so you won't have an
>>> object to call getS() on.
>> That's not what PKCS11 does - it just gives you a "PrivateKey" object
>> with an internal type of sun.security.pkcs11.P11Key. While that
>> object is not type safe exactly, it is provider safe.
>>
>> You're still wanting to use the various EC classes of java.security,
>> java.security.spec, and java.security.interfaces, but you're
>> unwilling to actually meet their contracts for some really suspect
>> reasons.
>>
>
> Sorry, I referred to the wrong methods in my last e-mail.
> ECPrivateKey::getS will return null in the new implementation. The
> getEncoded method will return the encoded key, as usual. The second
> sentence referred to ECPrivateKeySpec::getS, which will remain
> unchanged, but you won't be able to use ECPrivateKeySpec with the new
> provider.
>
> I don't believe my proposal violates the contracts of any of these
> classes, but if you believe that it does (after the correction above),
> then let me know which contracts are violated.
While the contract for getEncoded() explicitly allows for a null result,
getS() of ECPrivateKey does not.    This more than any other reason
appears to be why the PKCS 11 provider represents the ECPrivateKey as a
simple PrivateKey object.

>
>>
>>>
>>> To create the key from stored information, the best way is to
>>> construct a PKCS8EncodedKeySpec using the encoded key. If you are
>>> starting with a BigInteger, and if branching is acceptable, you can
>>> use the KeyFactory from SunEC to convert an ECPrivateKeySpec to
>>> PrivateKey to get the encoded value.
>>
>> Umm... what?
>>
>> If you were doing NewEC -> SunEC manually (getEncoded() -> KeySpec) -
>> you'll need to end up emitting a PKCS8 blob using RFC5915, which -
>> unsurprisingly has  BigEndian INTEGERs (yes, its an octet string, but
>> the encoding is specified by RFC3447 as pretty much the big endian
>> encoding of an integer). E.g. it may look opaque from Java's point of
>> view, but it's not really opaque. (See below)
>>
>> Or have you got a different way of encoding the PKCS8 blob for the
>> new provider?  E.g. point me at a specification please.
>>
>
> There is no issue with integers or endianness. The problem is
> specifically with BigInteger---it uses a variable-length
> representation, and it's spec does not give any guarantees about
> branching. The PKCS#8 encoding is fine because it is fixed length, so
> I can directly use the privateKey octet string (with bytes reversed,
> if necessary) in a branchless double-and-add loop.

Yup - and see the above for how to use BigInteger.  Note that you MUST
provide the bytes in BigEndian order for the current version of how to
encode an ec private key as PKCS8.  You must also provide exactly N
bytes including any leading (or for little endian - trailing) '0's to
pad it out.  Which looks to me like a possible requirement to test and
branch.

>
>> My head hurt when I tried to work through the various cases of
>> translating a private key from your provider to SunEC or to
>> BouncyCastle and vice versa.  Basically, if you don't support the
>> getS() call, then KeyFactory.translateKey() will fail. (Below from
>> sun.security.ec.ECKeyFactory.java - the SunEC provider's
>> implementation).
>>
>>>  private PrivateKey implTranslatePrivateKey(PrivateKey key)
>>>             throws InvalidKeyException {
>>>         if (key instanceof ECPrivateKey) {
>>>             if (key instanceof ECPrivateKeyImpl) {
>>>                 return key;
>>>             }
>>>             ECPrivateKey ecKey = (ECPrivateKey)key;
>>>             return new ECPrivateKeyImpl(
>>>                 ecKey.getS(),
>>>                 ecKey.getParams()
>>>             );
>>>         } else if ("PKCS#8".equals(key.getFormat())) {
>>>             return new ECPrivateKeyImpl(key.getEncoded());
>>>         } else {
>>>             throw new InvalidKeyException("Private keys must be
>>> instance "
>>>                 + "of ECPrivateKey or have PKCS#8 encoding");
>>>         }
>>
>
> The code above could be improved by using the PKCS#8 encoding when
> getS() returns null.
So implementing your provider requires other providers to change?
Because?   Do you expect BouncyCastle and NSS to change as well?

E.g.  This gets called by KeyFactorySpi.engineTranslateKey for bouncycastle:

>     public BCECPrivateKey(
>         ECPrivateKey key,
>         ProviderConfiguration configuration)
>     {
>         this.d = key.getS();
> <<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<
>         this.algorithm = key.getAlgorithm();
>         this.ecSpec = key.getParams();
>         this.configuration = configuration;
>     }


>
> The only way to get private keys in or out of the new provider is
> through a PKCS#8 encoding. Moving keys to/from another provider that
> supports ECPrivateKeySpec but not PKCS#8 encoding can be accomplished
> by translating the specs---possibly with the help of a KeyFactory that
> supports both, like the one in SunEC.
>
*pounds head against table*   Bits are bits are bits.  Creating a
PKCS8EncodedKeySpec gets you a byte array which you can convert to a
BigInteger by decoding the PKCS8 structure and taking the PKCS8
PrivateKey octets and doing new BigInteger (1, privateKeyOctets).

That doesn't require ASN1 integer representation (e.g. leading byte is
zero if high bit is set) and doesn't cause a branch.

In any event, if I'm copying things out of NewEC then I'm responsible
for any of the interface weirdness with respect to timing attacks.


Later, Mike



Reply | Threaded
Open this post in threaded view
|

Re: Conceptual feedback on new ECC JEP

Adam Petcher
On 9/5/2018 5:53 PM, Michael StJohns wrote:

>
> BigInteger is not required to encode a PKCS8 key, but its trivial to
> translate from BigInteger to PKCS8 and vice versa.  Note that
> internally, the current BigInteger stores the magnitude as an array of
> int in big endian order and stores the sign separately. The BigInteger
> (int sigNum, byte[] magnitude) constructor mostly just copies the
> magnitude bytes over (and converts 4 bytes to an integer) for positive
> integers.   While the current BigInteger doesn't have a byte[]
> BigInteger.getMagnitude() call, it would be trivial to subclass
> BigInteger to copy the magnitude bytes (without branching) out.
>
> In any event, for NewEC to OldEc - you do use the sign/magnitude call
> to create the BigInteger - no leaking on the part of NewEC, and once
> it gets to OldEC its not your problem.  For OldEc to NewEc you copy
> the BigInteger to NewBigInteger (trivial wrapper class) and do a
> getMagnitude().

See the code for BigInteger[1]. The sign/magnitude constructor calls
stripLeadingZeroBytes (line 405) on the magnitude to convert it to an
int array. This method compares the leading values in the byte array to
zero in a short-circuit expression in a for loop (line 4298). So this
constructor branches on the value that is supplied to it, and it cannot
be used in a branchless implementation.

I don't know how to write this branchless getMagnitude method that you
are proposing. I would need to convert from a variable-length int array
to a fixed-length byte array. In doing this, I can't branch on the
length of the variable-length array, because doing so would leak whether
the high-order bits of the key are zero. If you know how to do this,
then please provide some code to illustrate how it is done.

[1]
http://hg.openjdk.java.net/jdk/jdk/file/805807f15830/src/java.base/share/classes/java/math/BigInteger.java


> While the contract for getEncoded() explicitly allows for a null
> result, getS() of ECPrivateKey does not.    This more than any other
> reason appears to be why the PKCS 11 provider represents the
> ECPrivateKey as a simple PrivateKey object.

Good point. There is no need for the private keys for this provider to
implement ECPrivateKey, since there is only one method that is
effectively unimplemented. We should use a new implementation class (not
ECPrivateKeyImpl) that implements PrivateKey, not ECPrivateKey.

> So implementing your provider requires other providers to change?
> Because?   Do you expect BouncyCastle and NSS to change as well?

I think the situation is improved by not having the new private keys
implement ECPrivateKey. Then the JDK ECKeyFactory code does not need to
change, and neither do other providers, assuming they behave in a
similar way. Though I think it is acceptable if other providers don't
behave this way, and therefore cannot translate private keys from this
new provider. I've updated the JEP to indicate that interoperability
with these providers is a non-goal.

>
>>
>> The only way to get private keys in or out of the new provider is
>> through a PKCS#8 encoding. Moving keys to/from another provider that
>> supports ECPrivateKeySpec but not PKCS#8 encoding can be accomplished
>> by translating the specs---possibly with the help of a KeyFactory
>> that supports both, like the one in SunEC.
>>
> *pounds head against table*   Bits are bits are bits.  Creating a
> PKCS8EncodedKeySpec gets you a byte array which you can convert to a
> BigInteger by decoding the PKCS8 structure and taking the PKCS8
> PrivateKey octets and doing new BigInteger (1, privateKeyOctets).
>
> That doesn't require ASN1 integer representation (e.g. leading byte is
> zero if high bit is set) and doesn't cause a branch.

See above for my explanation of why this solution does, in fact, branch.

Reply | Threaded
Open this post in threaded view
|

Re: Conceptual feedback on new ECC JEP

Michael StJohns
On 9/6/2018 9:53 AM, Adam Petcher wrote:

> On 9/5/2018 5:53 PM, Michael StJohns wrote:
>
>>
>> BigInteger is not required to encode a PKCS8 key, but its trivial to
>> translate from BigInteger to PKCS8 and vice versa. Note that
>> internally, the current BigInteger stores the magnitude as an array
>> of int in big endian order and stores the sign separately. The
>> BigInteger (int sigNum, byte[] magnitude) constructor mostly just
>> copies the magnitude bytes over (and converts 4 bytes to an integer)
>> for positive integers.   While the current BigInteger doesn't have a
>> byte[] BigInteger.getMagnitude() call, it would be trivial to
>> subclass BigInteger to copy the magnitude bytes (without branching) out.
>>
>> In any event, for NewEC to OldEc - you do use the sign/magnitude call
>> to create the BigInteger - no leaking on the part of NewEC, and once
>> it gets to OldEC its not your problem.  For OldEc to NewEc you copy
>> the BigInteger to NewBigInteger (trivial wrapper class) and do a
>> getMagnitude().
>
> See the code for BigInteger[1]. The sign/magnitude constructor calls
> stripLeadingZeroBytes (line 405) on the magnitude to convert it to an
> int array. This method compares the leading values in the byte array
> to zero in a short-circuit expression in a for loop (line 4298). So
> this constructor branches on the value that is supplied to it, and it
> cannot be used in a branchless implementation.
>
> I don't know how to write this branchless getMagnitude method that you
> are proposing. I would need to convert from a variable-length int
> array to a fixed-length byte array. In doing this, I can't branch on
> the length of the variable-length array, because doing so would leak
> whether the high-order bits of the key are zero. If you know how to do
> this, then please provide some code to illustrate how it is done.

Simple way to do this is to extend BigInteger and fix these perceived
problems.  You may have to replace/replicate pretty much everything, but
as long as it has a BigInteger signature when output, you're good to
go.  Actually, do that - clone BigInteger.java as SafeBigInteger.java,
have extend java.math.BigInteger and change out the things that bother
you.   I checked - BigInteger is not a final class so this should work.

  E.g. as long as *I* can call the functions I need to call on the
object you exported, I'm fine with it.

In any event, you're still missing the point here.  You're EXPORTING the
key from your provider to other providers which probably already don't
care that much about the one in 256 (approx - slightly larger)  time
where exporting the key might leak the fact of leading zero bits.

>
> [1]
> http://hg.openjdk.java.net/jdk/jdk/file/805807f15830/src/java.base/share/classes/java/math/BigInteger.java
>
>
>> While the contract for getEncoded() explicitly allows for a null
>> result, getS() of ECPrivateKey does not.    This more than any other
>> reason appears to be why the PKCS 11 provider represents the
>> ECPrivateKey as a simple PrivateKey object.
>
> Good point. There is no need for the private keys for this provider to
> implement ECPrivateKey, since there is only one method that is
> effectively unimplemented. We should use a new implementation class
> (not ECPrivateKeyImpl) that implements PrivateKey, not ECPrivateKey.

*pounds head on table*  Sure.  And then you can't use any translation
features and then you break all the code.

>
>> So implementing your provider requires other providers to change?
>> Because?   Do you expect BouncyCastle and NSS to change as well?
>
> I think the situation is improved by not having the new private keys
> implement ECPrivateKey. Then the JDK ECKeyFactory code does not need
> to change, and neither do other providers, assuming they behave in a
> similar way. Though I think it is acceptable if other providers don't
> behave this way, and therefore cannot translate private keys from this
> new provider. I've updated the JEP to indicate that interoperability
> with these providers is a non-goal.

OK.  At this point you're no longer calling this an EC key. Make sure
you catch all the places where ECPrivateKey is used instead of
PrivateKey.  I think you're incredibly short sighted and not a lot of
folks will implement this, but go for it.  I think its a *really* bad
idea and that you're fixing the wrong problems.

>
>>
>>>
>>> The only way to get private keys in or out of the new provider is
>>> through a PKCS#8 encoding. Moving keys to/from another provider that
>>> supports ECPrivateKeySpec but not PKCS#8 encoding can be
>>> accomplished by translating the specs---possibly with the help of a
>>> KeyFactory that supports both, like the one in SunEC.
>>>
>> *pounds head against table*   Bits are bits are bits.  Creating a
>> PKCS8EncodedKeySpec gets you a byte array which you can convert to a
>> BigInteger by decoding the PKCS8 structure and taking the PKCS8
>> PrivateKey octets and doing new BigInteger (1, privateKeyOctets).
>>
>> That doesn't require ASN1 integer representation (e.g. leading byte
>> is zero if high bit is set) and doesn't cause a branch.
>
> See above for my explanation of why this solution does, in fact, branch.
>
See my commentary on why this still doesn't matter.

Later, Mike


Reply | Threaded
Open this post in threaded view
|

Re: Conceptual feedback on new ECC JEP

Adam Petcher
I'm only going to respond to one of your points in detail, see inline below.

For the other points, I don't think we are going to agree. You want the
implementation to be more interoperable, and I have stated that the
level of interoperability that you want is not a goal of the JEP. This
is supposed to be a more secure software ECC implementation, with
corresponding restrictions on its API. I will be happy with it if the
API is just functional enough to allow us to use it in SunJSSE, with
some non-trivial modifications to the SunJSSE code. In the initial
release of this new provider, it should only be enabled by users who are
willing to accept this tradeoff between security and
usability/interoperability, and who are willing to modify existing code
to make the new provider work.

On 9/7/2018 12:43 PM, Michael StJohns wrote:

>
> Simple way to do this is to extend BigInteger and fix these perceived
> problems.  You may have to replace/replicate pretty much everything,
> but as long as it has a BigInteger signature when output, you're good
> to go.  Actually, do that - clone BigInteger.java as
> SafeBigInteger.java, have extend java.math.BigInteger and change out
> the things that bother you. I checked - BigInteger is not a final
> class so this should work.

Thanks for the suggestion. I agree that this might work, but it would
greatly increase the scope/effort of this JEP. There might also be other
solutions that require less effort (e.g. new types of keys/specs that
hold values as integers, but not BigInteger) that should be considered.
I've updated the JEP to record this suggestion, and to indicate that it
is out of scope. We can always enhance the interface/implementation later.
Reply | Threaded
Open this post in threaded view
|

Re: Conceptual feedback on new ECC JEP

Anthony Scarpino
In reply to this post by Adam Petcher
Adam,

I tend to agree with Mike that disallowing import/export of keys using BigInteger is not the value of a branchless implementation.  As you point out in the JEP the provider is greatly hindered by this design choice. I feel it would be better to implementing the BigInteger parts and have a property to shut them off for a pure branchless implementation.  That should allow the provider to be used in the default provider list and the ‘opt-in’ would be the property to turn off BigInteger or any other branching situation.  I am concerned the desire for a purest provider will result in it being unused.  Documentation can be clear about the import/export situation, the preference toward PKCS8EncodedKeySpec, and the property to lock it down.

Tony

> On Aug 23, 2018, at 10:50 AM, Adam Petcher <[hidden email]> wrote:
>
> I'm starting work on yet another ECC JEP[1], this time with the goal of developing improved implementations of existing algorithms, rather than implementing new ones. The JEP will re-implement ECDH and ECDSA for the 256-, 384-, and 521-bit NIST prime curves. The new implementation will be all Java, and will resist side-channel attacks by not branching on secrets. It will go in a new provider which is not in the provider list in the java.security file by default. So it will need to be manually enabled by changing the configuration or putting the new provider name in the code. It will only support a subset of the API that is supported by the implementation in SunEC. In particular, it will reject any private keys with scalar values specified using BigInteger (as in ECPrivateKeySpec), and its private keys will not return scalar values as BigInteger (as in ECPrivateKey.getS()).
>
> Please take a look and send me any feedback you have. I'm especially looking for suggestions on how this new implementation should fit into the API. I would prefer to have it enabled by default, but I can't think of a way to do that without either branching on secrets in some cases (converting a BigInteger private key to an array) or breaking compatibility (throwing an exception when it gets a BigInteger private key).
>
> [1] https://bugs.openjdk.java.net/browse/JDK-8204574
>

Reply | Threaded
Open this post in threaded view
|

Re: Conceptual feedback on new ECC JEP

Adam Petcher
This is a good suggestion. I don't have particularly strong feelings
about using separate providers vs a property in a single provider. I
think the fundamental issues are the same, and this choice mostly
affects API details.

Do you think this should be a system property, security property, or
something else? Should it be modifiable at any time? Perhaps it has to
be in order to address Mike's desire to put the provider in
"import/export mode". Would the property affect existing keys? Again, I
think it would have to, so you can generate a key, turn off branchless
mode, and then export it. What about curves other than P256, P384, and
P521? We can't do branchless operations in those curves, so any attempt
to use them when this property is enabled would result in an exception.

The questions above are for everybody, if you have thoughts on any of
this, please share. My initial thoughts are that using a property may
give us some additional flexibility, and may improve the interface, but
the main cost is additional complexity in the implementation, since
we'll need to implement some checks that would otherwise be accomplished
by provider selection and having separate code.

On 9/7/2018 1:53 PM, Anthony Scarpino wrote:

> Adam,
>
> I tend to agree with Mike that disallowing import/export of keys using BigInteger is not the value of a branchless implementation.  As you point out in the JEP the provider is greatly hindered by this design choice. I feel it would be better to implementing the BigInteger parts and have a property to shut them off for a pure branchless implementation.  That should allow the provider to be used in the default provider list and the ‘opt-in’ would be the property to turn off BigInteger or any other branching situation.  I am concerned the desire for a purest provider will result in it being unused.  Documentation can be clear about the import/export situation, the preference toward PKCS8EncodedKeySpec, and the property to lock it down.
>
> Tony
>
>> On Aug 23, 2018, at 10:50 AM, Adam Petcher <[hidden email]> wrote:
>>
>> I'm starting work on yet another ECC JEP[1], this time with the goal of developing improved implementations of existing algorithms, rather than implementing new ones. The JEP will re-implement ECDH and ECDSA for the 256-, 384-, and 521-bit NIST prime curves. The new implementation will be all Java, and will resist side-channel attacks by not branching on secrets. It will go in a new provider which is not in the provider list in the java.security file by default. So it will need to be manually enabled by changing the configuration or putting the new provider name in the code. It will only support a subset of the API that is supported by the implementation in SunEC. In particular, it will reject any private keys with scalar values specified using BigInteger (as in ECPrivateKeySpec), and its private keys will not return scalar values as BigInteger (as in ECPrivateKey.getS()).
>>
>> Please take a look and send me any feedback you have. I'm especially looking for suggestions on how this new implementation should fit into the API. I would prefer to have it enabled by default, but I can't think of a way to do that without either branching on secrets in some cases (converting a BigInteger private key to an array) or breaking compatibility (throwing an exception when it gets a BigInteger private key).
>>
>> [1] https://bugs.openjdk.java.net/browse/JDK-8204574
>>

Reply | Threaded
Open this post in threaded view
|

Re: Conceptual feedback on new ECC JEP

roger riggs
Hi,

In general, System properties should be avoided, they add complexity to
configurations and
especially if they change sensitive behavior.  In any case, the defaults
should be secure-by-default;
not the other way around.

Perhaps two different providers, one secure and one more secure.

$.02, Roger


On 9/7/2018 3:08 PM, Adam Petcher wrote:

> This is a good suggestion. I don't have particularly strong feelings
> about using separate providers vs a property in a single provider. I
> think the fundamental issues are the same, and this choice mostly
> affects API details.
>
> Do you think this should be a system property, security property, or
> something else? Should it be modifiable at any time? Perhaps it has to
> be in order to address Mike's desire to put the provider in
> "import/export mode". Would the property affect existing keys? Again,
> I think it would have to, so you can generate a key, turn off
> branchless mode, and then export it. What about curves other than
> P256, P384, and P521? We can't do branchless operations in those
> curves, so any attempt to use them when this property is enabled would
> result in an exception.
>
> The questions above are for everybody, if you have thoughts on any of
> this, please share. My initial thoughts are that using a property may
> give us some additional flexibility, and may improve the interface,
> but the main cost is additional complexity in the implementation,
> since we'll need to implement some checks that would otherwise be
> accomplished by provider selection and having separate code.
>
> On 9/7/2018 1:53 PM, Anthony Scarpino wrote:
>> Adam,
>>
>> I tend to agree with Mike that disallowing import/export of keys
>> using BigInteger is not the value of a branchless implementation.  As
>> you point out in the JEP the provider is greatly hindered by this
>> design choice. I feel it would be better to implementing the
>> BigInteger parts and have a property to shut them off for a pure
>> branchless implementation.  That should allow the provider to be used
>> in the default provider list and the ‘opt-in’ would be the property
>> to turn off BigInteger or any other branching situation.  I am
>> concerned the desire for a purest provider will result in it being
>> unused. Documentation can be clear about the import/export situation,
>> the preference toward PKCS8EncodedKeySpec, and the property to lock
>> it down.
>>
>> Tony
>>
>>> On Aug 23, 2018, at 10:50 AM, Adam Petcher <[hidden email]>
>>> wrote:
>>>
>>> I'm starting work on yet another ECC JEP[1], this time with the goal
>>> of developing improved implementations of existing algorithms,
>>> rather than implementing new ones. The JEP will re-implement ECDH
>>> and ECDSA for the 256-, 384-, and 521-bit NIST prime curves. The new
>>> implementation will be all Java, and will resist side-channel
>>> attacks by not branching on secrets. It will go in a new provider
>>> which is not in the provider list in the java.security file by
>>> default. So it will need to be manually enabled by changing the
>>> configuration or putting the new provider name in the code. It will
>>> only support a subset of the API that is supported by the
>>> implementation in SunEC. In particular, it will reject any private
>>> keys with scalar values specified using BigInteger (as in
>>> ECPrivateKeySpec), and its private keys will not return scalar
>>> values as BigInteger (as in ECPrivateKey.getS()).
>>>
>>> Please take a look and send me any feedback you have. I'm especially
>>> looking for suggestions on how this new implementation should fit
>>> into the API. I would prefer to have it enabled by default, but I
>>> can't think of a way to do that without either branching on secrets
>>> in some cases (converting a BigInteger private key to an array) or
>>> breaking compatibility (throwing an exception when it gets a
>>> BigInteger private key).
>>>
>>> [1] https://bugs.openjdk.java.net/browse/JDK-8204574
>>>
>

Reply | Threaded
Open this post in threaded view
|

Re: Conceptual feedback on new ECC JEP

Xuelei Fan-2
In reply to this post by Adam Petcher
Hi,

I have not had a chance to review this JEP yet.  Personally, if
possible, I would expect there is no public APIs update so that more
applications can benefit from the enhancement, and SunJSSE could
benefits from more crypto providers.   I'm not sure if it is possible or
not now, or how could we minimize the APIs update.  I will see if I
could be here next week.  Please go ahead if you have an agreement
before I look into this JEP.

Thanks,
Xuelei

On 9/7/2018 12:08 PM, Adam Petcher wrote:

> This is a good suggestion. I don't have particularly strong feelings
> about using separate providers vs a property in a single provider. I
> think the fundamental issues are the same, and this choice mostly
> affects API details.
>
> Do you think this should be a system property, security property, or
> something else? Should it be modifiable at any time? Perhaps it has to
> be in order to address Mike's desire to put the provider in
> "import/export mode". Would the property affect existing keys? Again, I
> think it would have to, so you can generate a key, turn off branchless
> mode, and then export it. What about curves other than P256, P384, and
> P521? We can't do branchless operations in those curves, so any attempt
> to use them when this property is enabled would result in an exception.
>
> The questions above are for everybody, if you have thoughts on any of
> this, please share. My initial thoughts are that using a property may
> give us some additional flexibility, and may improve the interface, but
> the main cost is additional complexity in the implementation, since
> we'll need to implement some checks that would otherwise be accomplished
> by provider selection and having separate code.
>
> On 9/7/2018 1:53 PM, Anthony Scarpino wrote:
>> Adam,
>>
>> I tend to agree with Mike that disallowing import/export of keys using
>> BigInteger is not the value of a branchless implementation.  As you
>> point out in the JEP the provider is greatly hindered by this design
>> choice. I feel it would be better to implementing the BigInteger parts
>> and have a property to shut them off for a pure branchless
>> implementation.  That should allow the provider to be used in the
>> default provider list and the ‘opt-in’ would be the property to turn
>> off BigInteger or any other branching situation.  I am concerned the
>> desire for a purest provider will result in it being unused.  
>> Documentation can be clear about the import/export situation, the
>> preference toward PKCS8EncodedKeySpec, and the property to lock it down.
>>
>> Tony
>>
>>> On Aug 23, 2018, at 10:50 AM, Adam Petcher <[hidden email]>
>>> wrote:
>>>
>>> I'm starting work on yet another ECC JEP[1], this time with the goal
>>> of developing improved implementations of existing algorithms, rather
>>> than implementing new ones. The JEP will re-implement ECDH and ECDSA
>>> for the 256-, 384-, and 521-bit NIST prime curves. The new
>>> implementation will be all Java, and will resist side-channel attacks
>>> by not branching on secrets. It will go in a new provider which is
>>> not in the provider list in the java.security file by default. So it
>>> will need to be manually enabled by changing the configuration or
>>> putting the new provider name in the code. It will only support a
>>> subset of the API that is supported by the implementation in SunEC.
>>> In particular, it will reject any private keys with scalar values
>>> specified using BigInteger (as in ECPrivateKeySpec), and its private
>>> keys will not return scalar values as BigInteger (as in
>>> ECPrivateKey.getS()).
>>>
>>> Please take a look and send me any feedback you have. I'm especially
>>> looking for suggestions on how this new implementation should fit
>>> into the API. I would prefer to have it enabled by default, but I
>>> can't think of a way to do that without either branching on secrets
>>> in some cases (converting a BigInteger private key to an array) or
>>> breaking compatibility (throwing an exception when it gets a
>>> BigInteger private key).
>>>
>>> [1] https://bugs.openjdk.java.net/browse/JDK-8204574
>>>
>
Reply | Threaded
Open this post in threaded view
|

Re: Conceptual feedback on new ECC JEP

Anthony Scarpino
In reply to this post by Adam Petcher


> On Sep 7, 2018, at 12:08 PM, Adam Petcher <[hidden email]> wrote:
>
> This is a good suggestion. I don't have particularly strong feelings about using separate providers vs a property in a single provider. I think the fundamental issues are the same, and this choice mostly affects API details.
>
> Do you think this should be a system property, security property, or something else? Should it be modifiable at any time?

I would say a security property

> Perhaps it has to be in order to address Mike's desire to put the provider in "import/export mode". Would the property affect existing keys? Again, I think it would have to, so you can generate a key, turn off branchless mode, and then export it.

My thought was the property would allow the branchless import/export for that java instance.   Not turning it on and off during operations.  I think the value of the branchless operation is in the usage of the algorithms. If an app wants to use a pure branchless provider the property can be set or never use the APIs with BigInteger in them.

One could avoid the property completely by just documenting clearly the interfaces that branched and then leave it to the app developer, but from the email discussion with Mike it sounded like you preferred strong controls on the provider.

> What about curves other than P256, P384, and P521? We can't do branchless operations in those curves, so any attempt to use them when this property is enabled would result in an exception.

I wasn’t going to propose anything further than your existing curves, but it would be nice if branchful curves could be added to eventual replace SunEC.  I know that isn’t the intent of this JEP and depends if you want to expand it.

>
> The questions above are for everybody, if you have thoughts on any of this, please share. My initial thoughts are that using a property may give us some additional flexibility, and may improve the interface, but the main cost is additional complexity in the implementation, since we'll need to implement some checks that would otherwise be accomplished by provider selection and having separate code.

A branchless and branchful provider is also an fine idea. You’d know better on the code impact between two providers vs a property. A branchful class extending the branchless class may create the seperation your looking for.

Tony

>
>> On 9/7/2018 1:53 PM, Anthony Scarpino wrote:
>> Adam,
>>
>> I tend to agree with Mike that disallowing import/export of keys using BigInteger is not the value of a branchless implementation.  As you point out in the JEP the provider is greatly hindered by this design choice. I feel it would be better to implementing the BigInteger parts and have a property to shut them off for a pure branchless implementation.  That should allow the provider to be used in the default provider list and the ‘opt-in’ would be the property to turn off BigInteger or any other branching situation.  I am concerned the desire for a purest provider will result in it being unused.  Documentation can be clear about the import/export situation, the preference toward PKCS8EncodedKeySpec, and the property to lock it down.
>>
>> Tony
>>
>>> On Aug 23, 2018, at 10:50 AM, Adam Petcher <[hidden email]> wrote:
>>>
>>> I'm starting work on yet another ECC JEP[1], this time with the goal of developing improved implementations of existing algorithms, rather than implementing new ones. The JEP will re-implement ECDH and ECDSA for the 256-, 384-, and 521-bit NIST prime curves. The new implementation will be all Java, and will resist side-channel attacks by not branching on secrets. It will go in a new provider which is not in the provider list in the java.security file by default. So it will need to be manually enabled by changing the configuration or putting the new provider name in the code. It will only support a subset of the API that is supported by the implementation in SunEC. In particular, it will reject any private keys with scalar values specified using BigInteger (as in ECPrivateKeySpec), and its private keys will not return scalar values as BigInteger (as in ECPrivateKey.getS()).
>>>
>>> Please take a look and send me any feedback you have. I'm especially looking for suggestions on how this new implementation should fit into the API. I would prefer to have it enabled by default, but I can't think of a way to do that without either branching on secrets in some cases (converting a BigInteger private key to an array) or breaking compatibility (throwing an exception when it gets a BigInteger private key).
>>>
>>> [1] https://bugs.openjdk.java.net/browse/JDK-8204574
>>>
>

Reply | Threaded
Open this post in threaded view
|

Re: Conceptual feedback on new ECC JEP

Adam Petcher
See inline below.

It also occurred to me that we could use Provider properties here. We
have the "ImplementedIn" property, and we can similarly add a standard
"Branchless" property. I think my preferred solution is still to use
separate providers, and perhaps use a read-only "Branchless" property to
aid in provider selection. That is, JCA client code that supports the
branchless API (that is, no BigInteger) could loop through the providers
until it finds one with the "Branchless" property set. This same
mechanism could be used to select a provider that allows branching in an
environment where the highest-priority provider is branchless.

We may also be able to set the "Branchless" property at runtime to
influence the behavior of a single provider. But this would introduce a
lot of complication, and I think it is starting to get away from the
intended use of these properties.

On 9/7/2018 7:07 PM, Anthony Scarpino wrote:

>> On Sep 7, 2018, at 12:08 PM, Adam Petcher <[hidden email]> wrote:
>>
>> This is a good suggestion. I don't have particularly strong feelings about using separate providers vs a property in a single provider. I think the fundamental issues are the same, and this choice mostly affects API details.
>>
>> Do you think this should be a system property, security property, or something else? Should it be modifiable at any time?
> I would say a security property
>
>> Perhaps it has to be in order to address Mike's desire to put the provider in "import/export mode". Would the property affect existing keys? Again, I think it would have to, so you can generate a key, turn off branchless mode, and then export it.
> My thought was the property would allow the branchless import/export for that java instance.   Not turning it on and off during operations.  I think the value of the branchless operation is in the usage of the algorithms. If an app wants to use a pure branchless provider the property can be set or never use the APIs with BigInteger in them.
>
> One could avoid the property completely by just documenting clearly the interfaces that branched and then leave it to the app developer, but from the email discussion with Mike it sounded like you preferred strong controls on the provider.

The issues related to branching are too subtle, and I don't think we
should expose any of it to the developer except "use this
provider/property/algorithm to indicate that branching on secrets is
unacceptable." Moreover, I'm intimately familiar with all of these
issue, and yet I still don't have confidence in my own ability to switch
SunJSSE over to using a branchless ECC implementation, unless I have
strong enforcement in the provider. It would be too easy for me to
simply miss an existing call to getS() or a use of ECPrivateKeySpec.

If we only have a single provider, and a security property that has been
set to indicate that branching is unacceptable in that provider, then I
think that means that there is no way to change the value of the
property and use private keys as BigInteger in that JVM process without
using some other (third party) provider. Though maybe I'm
misunderstanding something about your proposal.

>
>> What about curves other than P256, P384, and P521? We can't do branchless operations in those curves, so any attempt to use them when this property is enabled would result in an exception.
> I wasn’t going to propose anything further than your existing curves, but it would be nice if branchful curves could be added to eventual replace SunEC.  I know that isn’t the intent of this JEP and depends if you want to expand it.

Sure, but for this JEP, we need to be concerned about how the API can be
misused, and a branching implementation is obtained when a branchless
one is expected. The developer shouldn't be expected to know that three
of the curves have branchless implementations, and using any other curve
will result in branching. So any global "don't branch" property would
need to cause the use of any other curve to fail.
Reply | Threaded
Open this post in threaded view
|

Re: Conceptual feedback on new ECC JEP

Xuelei Fan-2
In reply to this post by Adam Petcher
Can I have the links to the new formulas that you will be used?  Are
they part of any current standards?

Thanks,
Xuelei

On 8/23/2018 10:50 AM, Adam Petcher wrote:

> I'm starting work on yet another ECC JEP[1], this time with the goal of
> developing improved implementations of existing algorithms, rather than
> implementing new ones. The JEP will re-implement ECDH and ECDSA for the
> 256-, 384-, and 521-bit NIST prime curves. The new implementation will
> be all Java, and will resist side-channel attacks by not branching on
> secrets. It will go in a new provider which is not in the provider list
> in the java.security file by default. So it will need to be manually
> enabled by changing the configuration or putting the new provider name
> in the code. It will only support a subset of the API that is supported
> by the implementation in SunEC. In particular, it will reject any
> private keys with scalar values specified using BigInteger (as in
> ECPrivateKeySpec), and its private keys will not return scalar values as
> BigInteger (as in ECPrivateKey.getS()).
>
> Please take a look and send me any feedback you have. I'm especially
> looking for suggestions on how this new implementation should fit into
> the API. I would prefer to have it enabled by default, but I can't think
> of a way to do that without either branching on secrets in some cases
> (converting a BigInteger private key to an array) or breaking
> compatibility (throwing an exception when it gets a BigInteger private
> key).
>
> [1] https://bugs.openjdk.java.net/browse/JDK-8204574
>
Reply | Threaded
Open this post in threaded view
|

Re: Conceptual feedback on new ECC JEP

Adam Petcher
The paper[1] containing the proposed formulas is referenced in the JEP.
As far as I know, they are not part of any standard. If you know of any
standardized, complete EC point arithmetic formulas, then let me know. I
think it is okay to use these formulas as long as they produce the same
result as the operations in Section 2.2 of SEC 1[2].

[1] https://eprint.iacr.org/2015/1060.pdf
[2] http://www.secg.org/sec1-v2.pdf


On 9/10/2018 2:23 PM, Xuelei Fan wrote:

> Can I have the links to the new formulas that you will be used?  Are
> they part of any current standards?
>
> Thanks,
> Xuelei
>
> On 8/23/2018 10:50 AM, Adam Petcher wrote:
>> I'm starting work on yet another ECC JEP[1], this time with the goal
>> of developing improved implementations of existing algorithms, rather
>> than implementing new ones. The JEP will re-implement ECDH and ECDSA
>> for the 256-, 384-, and 521-bit NIST prime curves. The new
>> implementation will be all Java, and will resist side-channel attacks
>> by not branching on secrets. It will go in a new provider which is
>> not in the provider list in the java.security file by default. So it
>> will need to be manually enabled by changing the configuration or
>> putting the new provider name in the code. It will only support a
>> subset of the API that is supported by the implementation in SunEC.
>> In particular, it will reject any private keys with scalar values
>> specified using BigInteger (as in ECPrivateKeySpec), and its private
>> keys will not return scalar values as BigInteger (as in
>> ECPrivateKey.getS()).
>>
>> Please take a look and send me any feedback you have. I'm especially
>> looking for suggestions on how this new implementation should fit
>> into the API. I would prefer to have it enabled by default, but I
>> can't think of a way to do that without either branching on secrets
>> in some cases (converting a BigInteger private key to an array) or
>> breaking compatibility (throwing an exception when it gets a
>> BigInteger private key).
>>
>> [1] https://bugs.openjdk.java.net/browse/JDK-8204574
>>

Reply | Threaded
Open this post in threaded view
|

Re: Conceptual feedback on new ECC JEP

Anthony Scarpino
In reply to this post by Adam Petcher
On 09/10/2018 08:50 AM, Adam Petcher wrote:

> See inline below.
>
> It also occurred to me that we could use Provider properties here. We
> have the "ImplementedIn" property, and we can similarly add a standard
> "Branchless" property. I think my preferred solution is still to use
> separate providers, and perhaps use a read-only "Branchless" property to
> aid in provider selection. That is, JCA client code that supports the
> branchless API (that is, no BigInteger) could loop through the providers
> until it finds one with the "Branchless" property set. This same
> mechanism could be used to select a provider that allows branching in an
> environment where the highest-priority provider is branchless.
>
> We may also be able to set the "Branchless" property at runtime to
> influence the behavior of a single provider. But this would introduce a
> lot of complication, and I think it is starting to get away from the
> intended use of these properties.

A provider property would be good route to explore I think.  It would be
nice to cut down on Security properties.

 >

> On 9/7/2018 7:07 PM, Anthony Scarpino wrote:
>
>>> On Sep 7, 2018, at 12:08 PM, Adam Petcher <[hidden email]>
>>> wrote:
>>>
>>> This is a good suggestion. I don't have particularly strong feelings
>>> about using separate providers vs a property in a single provider. I
>>> think the fundamental issues are the same, and this choice mostly
>>> affects API details.
>>>
>>> Do you think this should be a system property, security property, or
>>> something else? Should it be modifiable at any time?
>> I would say a security property
>>
>>> Perhaps it has to be in order to address Mike's desire to put the
>>> provider in "import/export mode". Would the property affect existing
>>> keys? Again, I think it would have to, so you can generate a key,
>>> turn off branchless mode, and then export it.
>> My thought was the property would allow the branchless import/export
>> for that java instance.   Not turning it on and off during
>> operations.  I think the value of the branchless operation is in the
>> usage of the algorithms. If an app wants to use a pure branchless
>> provider the property can be set or never use the APIs with BigInteger
>> in them.
>>
>> One could avoid the property completely by just documenting clearly
>> the interfaces that branched and then leave it to the app developer,
>> but from the email discussion with Mike it sounded like you preferred
>> strong controls on the provider.
>
> The issues related to branching are too subtle, and I don't think we
> should expose any of it to the developer except "use this
> provider/property/algorithm to indicate that branching on secrets is
> unacceptable." Moreover, I'm intimately familiar with all of these
> issue, and yet I still don't have confidence in my own ability to switch
> SunJSSE over to using a branchless ECC implementation, unless I have
> strong enforcement in the provider. It would be too easy for me to
> simply miss an existing call to getS() or a use of ECPrivateKeySpec.
>
> If we only have a single provider, and a security property that has been
> set to indicate that branching is unacceptable in that provider, then I
> think that means that there is no way to change the value of the
> property and use private keys as BigInteger in that JVM process without
> using some other (third party) provider. Though maybe I'm
> misunderstanding something about your proposal.

A single provider with a security property is fine. I think we agree the
property will tell if the API's that use BigInteger will work with the
provider or not.  Internally you can design the algorithm code however
you want.  It's only the import/export parts I've been referring to.

>
>>
>>> What about curves other than P256, P384, and P521? We can't do
>>> branchless operations in those curves, so any attempt to use them
>>> when this property is enabled would result in an exception.
>> I wasn’t going to propose anything further than your existing curves,
>> but it would be nice if branchful curves could be added to eventual
>> replace SunEC.  I know that isn’t the intent of this JEP and depends
>> if you want to expand it.
>
> Sure, but for this JEP, we need to be concerned about how the API can be
> misused, and a branching implementation is obtained when a branchless
> one is expected. The developer shouldn't be expected to know that three
> of the curves have branchless implementations, and using any other curve
> will result in branching. So any global "don't branch" property would
> need to cause the use of any other curve to fail.

Ok.. I had the impression that the other curves could work with the
branchless code.  If they cannot, then I wouldn't worry about including
them.

Tony

12