Re: [Cfrg] On the use of Montgomery form curves for key agreement

[Andrey Jivsov <[e-mail]>]

On 09/02/2014 03:59 PM, Nico Williams wrote:
> On Tue, Sep 2, 2014 at 4:58 PM, Andrey Jivsov <[e-mail]> wrote:
>> On 09/02/2014 02:47 PM, Stephen Farrell wrote:
>>> Can you give me an example of such an IETF protocol? Without
>>> having thought much about it, I think there are always different
>>> codepoints allocated for DH and signatures, and I doubt we'd
>>> want the same private values shared anyway, so I'm not sure
>>> if that's a real or a theoretical issue.
> +1.  We generally strive for key hygiene.  We'd not use a key for
> different purposes.
>
> What is the use of using the same key for DH and signatures in the
> same protocol?  I can only think of a round-trip optimization, but
> what I have in mind is very handwavy and not likely to be a win
> (partly because it means losing PFS).
>
>> A few examples of dual-key use and a bit braader question of whether would
>> want to add points as oppose to only do scalar multiplication.
>>
>> Some TLS server side fixed-base optimization will benefit from point
>> addition.
> Can you give some more details of what this would mean protocol-wise?
The format on the wire is not affected, but if there is a penalty for 
point addition, this is a property that didn't exist for, say P-256.

Consider the following example of an optimization a server might have to 
produce a fresh ephemeral key (proof omitted but I think is possible):

Generate n keypairs {ki, kiG}. There are about n^2/2 of the unique 
pairs. The ephemeral key is {ki+kj}G, which is done with a single point 
addition. Thus, sqrt(n) keygens provide n ephemeral keys.

This can be viewed as a special case of fixed-point optimization.


>> While OpenPGP RFC 4880 has a concept of a "bundle of keys" things are easier
>> when the top key can have both encryption and signing capability. There are
>> products that add X.509 certs to PGP keys.
> Yes, I could see this.  Though key bundles have been around for long
> enough (and in widespread enough use) that it doesn't seem likely to
> matter much.

Signatures in OpenPGP "live" on the top key. It's more challenging to 
add X.509 certs to subkeys. X.509 certs on subkeys might go into 
notation packets, but notations are a part of self-signatures are 
therefore signed by the top key, which poses challenges if one wants to 
do management like removal of certificates (by untrusted entity like a 
key server)

>
>> Signing a certificate request for a DH key to prove key possession.
> A self-signed DH cert.  OK, this one makes some sense, but if the
> price is losing PFS or paying extra CPU cycles if you want PFS, then
> it seems not worthwhile.
>
> On the other hand, if using the same key for DH and signatures is
> worthwhile, then it seems likely that point form conversion won't be a
> big deal.  No?

Also CSRs for DH keys, if you want to do ECDSA-like signature with a DH key.

Keys with 10% penalty should be viewed as "optimized" for particular use 
based on the choice of coordinate system.

Compare this with conversion between Montgomery coordinates and Short 
Weierstrass coordinates 
(http://www.ietf.org/mail-archive/web/cfrg/current/msg04996.html): there 
is no such penalty for such a pair.

>> Protocols for applications with space-saving requirements : keys on URLs or
>> e-mail aliases, pre-generate keys "for everybody" to represent identities.
>> Keys that are handled by humans (e.g. typed in base32 encoding), etc
> Yes, this is a clear win.  But again, any point conversion penalty
> seems minor for such a protocol.

Depends on the case. If you think something like SMIME/CMS on outgoing 
e-mails, they will likely get signed+encrypted (to self, when placed 
into the Sent folder) . Not an issue for TLS clients, though.
...