Re: [Cfrg] Elliptic Curves - curve form and coordinate systems

[Rene Struik <[e-mail]>]

Hi Viktor:

You are correct: I have no idea where Dan Bernstein got that from. I *did* comment on the DH function, which, with Montgomery-style specification as in the "Curve25519" draft, is completely insecure, if one does not check the output to be nonzero. This is a form of the small subgroup attack and has been known for over 15 years.

BTW - I don't think this is properly captured in draft-irtf-cfrg-curves-01 and sent an offline note to suggest remedying this by replacing the last para prior to Section 8.1 of that draft to the following:

"Note that the (co-factor) Diffie-Hellman protocol presented here results in the all-zero key if it operates on an input corresponding to a point with order dividing the co-factor h of the curve. Failure to check the output for this condition leads to a trivial (and well-known) small subgroup confinement attack. The output of this protocol SHALL therefore be checked and, if this value is found to be zero, the protocol SHALL fail."

  

===
One quick question.  I did not think that Rene was saying that the
Montgomery ladder computes multiples of 0 incorrectly.  Rather,
the concern is I believe that when one of the parties to an ECDH
agreement sends zero as their public key, the output is then zero
regardless of the public key of the other party.

On 3/16/2015 12:49 AM, Viktor Dukhovni wrote:
> On Mon, Mar 16, 2015 at 12:22:55AM -0000, D. J. Bernstein wrote:
>
>> In particular, input 0 is handled correctly without any special tests,
>> contrary to Rene's comments and earlier comments from Microsoft. See
>> https://www.ietf.org/mail-archive/web/cfrg/current/msg05004.html.
> Dan, thanks for the detailed comments.  I support the emphasis on
> implementation simplicity they represent (including potentially
> taking away choices, when such choices are more prone to mistakes
> than "the right way").  That is, I suport removing inessential
> degrees of freedom.
>
> One quick question.  I did not think that Rene was saying that the
> Montgomery ladder computes multiples of 0 incorrectly.  Rather,
> the concern is I believe that when one of the parties to an ECDH
> agreement sends zero as their public key, the output is then zero
> regardless of the public key of the other party.
>
> This may allow an attacker to force a given session key, depending
> on how the ECDH output is used to construct session keys (whether
> additional nonces are used.  Can you comment on situations (in
> higher level protocols) under which participants in ECDH might want
> to explicitly reject 0 as the peer's public key?  (I don't know
> whether any protocols in wide use that employ ECDH are potentially
> exposed to this issue, if it is an issue.)
>
> If I recall correctly, with X25519, such a key will never arise if
> both peers choose their secret keys per the specification (the
> private "exponent" is never 0, and I think it is always smaller
> than the order of the group).
>


-- 
email: [e-mail] | Skype: rstruik
cell: [phone] | US: [phone]