JCA design for RFC 7748

Michael StJohns mstjohns at comcast.net
Thu Aug 17 17:44:30 UTC 2017


See inline.

On 8/17/2017 11:19 AM, Adam Petcher wrote:
> On 8/16/2017 3:17 PM, Michael StJohns wrote:
>
>> On 8/16/2017 11:18 AM, Adam Petcher wrote:
>>>
>>> My intention with this ByteArrayValue is to only use it for 
>>> information that has a clear semantics when represented as a byte 
>>> array, and a byte array is a convenient and appropriate 
>>> representation for the algorithms involved (so there isn't a lot of 
>>> unnecessary conversion). This is the case for public/private keys in 
>>> RFC 7748/8032:
>>>
>>> 1) RFC 8032: "An EdDSA private key is a b-bit string k." "The EdDSA 
>>> public key is ENC(A)." (ENC is a function from integers to 
>>> little-endian bit strings.
>
> Oops, minor correction. Here A is a point, so ENC is a function from 
> points to little-endian bit strings.
>
>>> 2) RFC 7748: "Alice generates 32 random bytes in a[0] to a[31] and 
>>> transmits K_A =X25519(a, 9) to Bob..." The X25519 and X448 
>>> functions, as described in the RFC, take bit strings as input and 
>>> produce bit strings as output.
>>
>> Thanks for making my point for me.  The internal representation of 
>> the public point is an integer.  It's only when encoding or decoding 
>> that it gets externally represented as an array of bytes.  (And yes, 
>> I understand that the RFC defines an algorithm using little endian 
>> byte array representations of the integers - but that's the 
>> implementation's call, not the API).
>>
>> With respect to the output of the KeyAgreement algorithm - your (2) 
>> above, the transmission representation (e.g. the encoded public key) 
>> is little endian byte array representation of an integer.  The 
>> internal representation is - wait for it - integer.
>>
>> I have no problems at all with any given implementation using little 
>> endian math internally.  For the purposes of using JCA, stick with 
>> BigInteger to represent your integers.  Use your provider encoding 
>> methods to translate between what the math is internally and what the 
>> bits are externally if necessary. Implement the conversion methods 
>> for the factory and for dealing with the existing EC classes.   Maybe 
>> get BigInteger to be extended to handle (natively) littleEndian 
>> representation (as well as fixed length outputs necessary for things 
>> like ECDH).
>>
>
> All good points, and I think BigInteger may be a reasonable 
> representation to use for public/private key values. I'm just not sure 
> that it is better than byte arrays. I'll share some relevant 
> information that affects this decision.
>
> First off, one of the goals of RFC 7748 and 8032 is to address some of 
> the implementation challenges related to ECC. These algorithms are 
> designed to eliminate the need for checks at various stages, and to 
> generally make implementation bugs less likely. These improvements are 
> motivated by all the ECC implementation bugs that have emerged in the 
> last ~20 years. I mention this because I think it is important that we 
> choose an API and implementation that allows us to benefit from these 
> improvements in the standards. That means we shouldn't necessarily 
> follow all the existing ECC patterns in the API and implementation.

No - it means that the authors of the RFCs have a bias to have their 
code be the only code.  As I note below I don't actually think they got 
everything right.   The underlying math is really what matters, and the 
API should be able to handle any implementation that gets the math correct.

>
> Specifically, these standards have properties related to byte arrays 
> like: "The Curve25519 function was carefully designed to allow all 
> 32-byte strings as Diffie-Hellman public keys."[1]

This statement is actually a problem.  Valid keys are in the range of 1 
to p-1 for the field (with some additional pruning).   32 byte strings 
(or 256 bit integers) do not map 1-1 into that space.  E.g. there are 
some actual canonical keys where multiple (at least 2) 32 byte strings 
map to them.  (See the pruning and clamping algorithms).  The NIST 
private key generation for EC private keys mitigates this bias by either 
(a) repeatedly generating random keys until you get one in the range or 
(b) generating a key stream with extra (64) bits and reducing that mod p 
of the curve.


> If we use representations other than byte strings in the API, then we 
> should ensure that our representations have the same properties (e.g. 
> every BigInteger is a valid public key).
>
> It's best to talk about each type on its own. Of course, one of the 
> benefits of using bit strings is that we may have the option of using 
> the same class/interface in the API to hold all of these.
>
> RFC 7748 public keys: I think we can reasonably use BigInteger to hold 
> public key values. One minor issue is that we need to specify how 
> implementations should handle non-canonical values (numbers that are 
> less than 0 or greater than p-1). This does not seem like a huge 
> issue, though, and the existing ECC API has the same issue. Another 
> minor issue is that modeling this as a BigInteger may encourage 
> implementations to use BigInteger in the RFC 7748 Montgomery ladder. 
> This would be unfortunate because it would leak sensitive information 
> through timing channels.

When you do the conversion from a key spec to a key you do what you're 
supposed to do - e.g. I think its mod p to reduce it.  Either that or 
you throw an error.  That's implementation side so not a big problem 
except that the documentation should explain what is supposed to happen.

>
> RFC 7748 private keys: This one is a bit more difficult. RFC 7748 
> defines a "clamping" operation that ensures that the integers 
> corresponding to bit strings have certain properties (e.g. they are a 
> multiple of the cofactor). So if we use BigInteger for private keys in 
> the API, we need to specify whether the value is clamped or unclamped. 
> If an unclamped value is treated as clamped, then this can result in 
> security and correctness issues. Also, the RFC treats private keys as 
> bit strings---they are not used in any integer operations. So modeling 
> them with byte arrays seems just as valid as modeling them with 
> BigInteger.

Nope.  The private keys are actually integers - the first thing that is 
done to the bit string is to "decodeLittleEndian".  Any programmer worth 
their salary is going to do this once on input. The implementation stuff 
described in the RFC then does big integer math on the bytes.

I assume that the PKCS8 conventions will use the bit string - but 
internally, this is going to be an integer of some sort.  It would be 
nice if BigInteger had support for input/output of little endian values 
- but it doesn't.  I expect that anyone who implements this set of 
curves will probably extend BigInteger to make little endian support 
just work.  Externally, the BigInteger in/out stuff  (e.g. key spec's) 
would then be completely backwards compatible.

In any event - please don't confuse the suggested implementation of the 
various RFCs  and the various external representations with the actual 
underlying math.


>
> RFC 8042 public keys: The analysis here is similar to RFC 7748 public 
> keys, except we also need to store the (probably compressed) x 
> coordinate. So if we don't use byte arrays, we would need to use 
> something like ECPoint.
Yup - see my previous email on how to handle this.
>
> RFC 8032 private keys: These are definitely bit strings, and modeling 
> them as integers doesn't make much sense. The only thing that is ever 
> done with these private keys is that they are used as input to a hash 
> function.

Again - no.   The actual private key is what you get after stage 3 of 
section 5.1.5.  E.g. generate a random string of 32 bytes.  Hash it to 
help with the bad random generators (*sheesh*),  Interpret the hash 
after pruning as a little endian integer.   Any programmer worth their 
salary is going to do steps 1-3 once at generation and store the private 
key as that pruned value.   An equivalent  (and possibly stronger) 
generation function would be to randomly generate 320 bits as an 
integer, take that mod p of the curve and then do any additional 
pruning.  That reduces the bias introduced by generating only  256 bits 
from the hash and immediately throwing away the last bit (MSBit of the 
MSByte in little endian terms).


Bernstein et al hide a lot under the covers in the RFCs, but this is 
integer and point math and there's nothing special about it. Forcing the 
transmission formats to be little endian when every other public key 
system uses big endian (and trying to hide that by calling them byte and 
bit strings) seems to be short sighted, but its what we got.   But you 
shouldn't confuse the RFC defined external encodings to be the API you 
need for JCA.  Especially if yet another edwards RFC comes along 
specifying Big Endian encoding for a different curve type. (Or 
interleaved bytes or something that makes sense for a highly parallel 
processing regime but translates poorly to an on the wire representation).

These are Integers  (private scalars) and ECPoints.  The curve parameter 
set needs mapping to the JCA API - but the curves are not anything special.

Mike



>
> [1] https://cr.yp.to/ecdh.html
>




More information about the security-dev mailing list