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

[Tanja Lange <[e-mail]>]

Dear Brian,
 
Most of this is going in circles; the points you raise were discussed 
on the mailing list before and during the Toronto meeting. I would 
appreciate it if instead of starting a new round of this you could 
reply to some earlier emails.

>    1.       Requiring a Montgomery form curve for key agreement and for a
>    particular security level means that implementations of protocols with
>    both key agreement and digital signatures must implement both Montgomery
>    curve arithmetic and additionally curve arithmetic for another curve
>    form.  From an engineering perspective there is thus a clear drawback to
>    requiring different curve forms for key agreement and digital signature at
>    the same security level.
> 
As several people pointed out now and in previous discussions, this
is conflating wire format, implementation, and curve form.

For security and ease of correct implementation I prefer Montgomery-x
for the wire format for DH and a compressed (but uniquely decompressible)
wire format for signatures.

>    2.       Assuming that implementations will implement more than one
>    security level, choosing X25519 for ECDHE at the 128 bit security level
>    will require implementations to use different curve arithmetic for the 128
>    bit security level than other security levels.  Again from an engineering
>    standpoint this is a negative.
> 
This is arguing about one particular suggestion and, again, mixes
wire format, implementation, and curve form.

>    3.       Despite repeated claims to the contrary, there is little evidence
>    that there is a consistent and significant performance benefit to
>    X25519. Indeed, as both the performance numbers in
>    http://eprint.iacr.org/2014/130.pdf as well as the more recent performance
>    numbers posted by Andrey Jivsov demonstrate, the performance of X25519
>    does not significantly differ from that of (twisted) Edwards curves for
>    (non-ephemeral) ECDH at the same size.  For the case of ECDHE,
>    Dan Bernstein has argued for a definition of "ephemeral" that would allow
>    keys to be re-used for some amount of time allowing X25519 implementations
>    to amortize the cost of operations which are particularly expensive for
>    X25519 over multiple uses of the same key.* Such arguments are intended to
>    wrap requirements around specific curves, which is inappropriate for this
>    process. There has been no legitimate argument put forward for repeated
>    use of ephemeral keys in ECDHE.  As a consequence, the adoption of a
>    definition of "ephemeral" that does not allow key re-use (as previously
>    recommended) means that implementations of X25519 would require
>    conversions between curve forms to avoid a significant loss in
>    performance. These conversions are a negative from an engineering
>    perspective.
> 

This is mostly about curve choices, not requirements. As far as the 
requirement of 'ephemeral = once' is concerned we've been through 
this discussion. For a speed comparison one can choose to go for
"KG+DH" or for "KG+nDH" for some value of n or look at several data 
points. However, for the security of the implementation, the system
must not break if the DH key is reused. I already said that after my
talk in Toronto. 

To say it simpler:
Requirement: security MUST not decrease if DH keyis reused
Selection criterion: speed of KG+nDH (incl., maybe exclusively, n=1)

There has been enough ripping into items a0-e) already, 
so I skip that apart from pointing out that you're arguing 
against one particular curve and mixing that with the requirements.
How about my up and coming T255.5? (just kidding).

Regards
	Tanja