On 8/18/2017 3:26 PM, Adam Petcher wrote:
On 8/17/2017 1:44 PM, Michael StJohns wrote:
See inline.
On 8/17/2017 11:19 AM, Adam Petcher wrote:
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 you are concerned about the distribution of private keys in these
standards, then you may want to raise your concerns on the CFRG
mailing list (c...@irtf.org). I don't have this concern, so I think we
should implement the RFC as written.
Basically, the RFC describes the form of the private key. It also
gives you an implementation for how to generate one. BUT - any method
that gives you an equivalent key and that has the same or better
security guarantees is equally valid. WRT to the RFC, I missed this
at the time it went through but noticed it after having to deal with
generation of normal EC keys and a FIPS evaluation. The bias is small,
but it exists. The method of the RFC does not reduce the bias. The
NIST method does. I know which one I would choose.
Regardless - this has no bearing on the fact that the output of the key
generation process is an integer.
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.
I'm not sure I understand what you are suggesting. For Ed25519, the
initial 32-byte secret is hashed to produce 64 bytes. The first 32
bytes are pruned, interpreted as an integer, and used to produce the
public key. The second 32 bytes are also used in the signing operation
and contribute to a deterministic nonce. See RFC 8032, section 5.1.6,
step 1. Are you suggesting that we should represent all 64 bytes as an
integer?
Sorry - I did miss this. Unfortunately, it screws up making this work
cleanly. There are two ways of doing this - I'd prefer (1) but could
live with (2):
1) The private key is a BigInteger (and that's how it gets in and out of
the ECPrivateKeySpec as 's') derived as up to step 3. The nonce is the
leftmost 32 bytes of the SHA512 of the private key expressed as a
little endian integer). The key thing about the deterministic nonce is
that it's the same for the key for its signature lifetime (which I'm
really not sure is a good thing - but its what we have). The way the
nonce is derived in the RFC shows one way. Hashing the private key
shows another way. I'd prefer this because you can use the same
input/output from the 'spec method for the ed25519 key as the curve25519
key. (do you really want two different spec classes for edxx and
curvexxx keys???)
2) The private key is the 32byte secret array of step 1 stored in the
concrete class. The input and output ECPrivateKeySpec defines a
transform from that array to/from a BigInteger to that array. The
private key concrete class includes storage for both the internal 's'
little endian integer value and the internal 'prefix' value. This isn't
as clean because the scalar secret 's' isn't the same as the
ECPrivateKeySpec.getS(), but allows for impedance matching between the
existing classes and the strangeness of an ed25519 private key. It
would definitely divorce keys from the two curve uses by doing it this way.
*sigh* The private key is an integer and that's really what needs to be
represented.
Mike
