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
