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