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