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/ _______________________________________________ Curves mailing list [email protected] https://moderncrypto.org/mailman/listinfo/curves
