JCA design for RFC 7748

Michael StJohns mstjohns at comcast.net
Fri Aug 18 20:52:01 UTC 2017


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 (cfrg at 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







More information about the security-dev mailing list