[curves] Checking for all-zeros ECDH output

[Trevor Perrin]

The IETF is specifying ECDH for the 25519 and 448 curves [1].

Their draft largely follows the existing spec for 25519 ECDH [2], and
extends it to 448.

But there's a surprising added check for the ECDH output (K):
Implementations "MUST check, without leaking extra information about
the value of K, whether K is the all-zero value and abort if so".

The effect is that the ECDH function rejects small-order inputs.  This
is surprising because the function is otherwise lax:
 * it accepts inputs which are not in the field (e.g. >= 2^255-19)
 * it accepts inputs which are not on the curve (twist points)
 * it accepts inputs which are not in the curve's main prime-order subgroup

There's some downsides to this check:
 * It adds complexity, since the function now has an error return.
 * It isn't present in existing 25519 software, so is likely to cause
confusion and "implementation fingerprinting" differences between
implementations with and without it.
 * It adds a side-channel risk: if this check isn't executed in
constant-time but with memcmp [3], it might leak information about K.

The draft doesn't provide a rationale, but there's some explanation
from a previous draft before the check was added [4]:

"""
Note that this Diffie-Hellman protocol is not contributory, e.g. if
the u-coordinate is zero then the output will always be zero.  A
contributory Diffie-Hellman function would ensure that the output was
unpredictable no matter what the peer's input.  This is not a problem
for the vast majority of cases but, if a contributory function is
specifically required, then "curve25519" should not be used.
"""

There was light discussion when the check was added, with Watson,
CodesInChaos, Nick Mathewson, and DJB skeptical [5].

I share the skepticism.  First, the goal isn't well-defined: terms
like "contributiveness" and "contributory" appear in the Group Key
Agreement literature, but without a precise definition or rationale
[6].  The explanation in above text doesn't make sense: DH is always
predictable given the peer's input and your own private key, you just
calculate the DH.

I suspect this is fallout from the "Triple Handshake" TLS paper and
the notion of "channel binding":  you might want an inner protocol to
send some message which is "bound" to the outer session, e.g. in weird
compound protocols like TLS renegotiation or ChannelID.

If the inner protocol uses the outer protocol's session key as the
channel-binding value, and an attacker can negotiate the same session
key with two different honest parties, then the attacker could relay a
"channel-bound" message from one session to another.  So Alice might
think she's saying "I'm renegotiating with client-auth as Alice inside
a session where I previously said innocuous things" but someone else
sees "Someone is renegotiating with client-auth as Alice inside a
session where they previously said bad things".

It seems like the right way to do channel binding with ECDH is to
include ephemeral public keys from the outer protocol in the
channel-binding value, e.g. hashing them into the session key, as TLS
is being modified to do, and as the draft already recommends, and
which provides a strong argument in the ROM.

Instead, this check is apparently trying to make it hard for an
adversary to synchronize session keys with two honest parties, by
making this problem hard:
 - given g^a and g^b, find C, D, such that C^a == D^b

Is there a standard name, or reduction, for this?

Am I missing some more rationale here, or is this just about
mitigating the risk from flawed channel binding?

Trevor


[1] https://tools.ietf.org/html/draft-irtf-cfrg-curves-09
[2] http://cr.yp.to/ecdh/curve25519-20060209.pdf
[3] http://rdist.root.org/2010/08/05/optimized-memcmp-leaks-useful-timing-differences/
[4] https://tools.ietf.org/html/draft-irtf-cfrg-curves-01
[5] https://mailarchive.ietf.org/arch/msg/cfrg/idCfKikSdhvh2JPibLzoi5-3WQU
[6] https://conspicuouschatter.wordpress.com/2014/06/28/should-group-key-agreement-be-symmetric-and-contributory/