[curves] Ed25519 "clamping" and its effect on hierarchical key derivation

[Gregory Maxwell]

On Fri, Apr 7, 2017 at 11:40 PM, Oleg Andreev <oleganza at gmail.com> wrote:
> My conjecture is: if there is no implementation that accepts 64-byte expanded key
> and sets bits in its left half, then arguments that bit-twiddling is good
> for compatibility become irrelevant -- because no one except NaCl can possibly be compatible with any HKD scheme.

I think that people should really consider curves with cofactor 1.
Outside of the DH context where very efficient X-only has some nice
payoffs (though moderately efficient X-only is also possible for other
curves) the expected benefits seem to be more fiction than reality.
The cofactor needlessly complicates many usages, as we see in this
discussion; and failures to handle it well can result in invisible
failures and vulnerabilities..

With suitable use of constant moves (which can't be avoided completely
in ed25519 once you must handle arbitrary keys) other formulations can
be soundly constant time.

Irresponsibly written software is going to be busted regardless of the
curve used.

I like to use an example this implementation of 'ed25519' signatures,
which is widely linked all over the internet in 'lists of ed25519
software' pages, as though it were something you should use,
https://github.com/vbuterin/ed25519/blob/master/ed25519.py#L242

... It leaks the private key on the second signature and uses a
gratuitously timing-side-channel exposed double and add. Two of the
issues the construction is supposed to have designed out.

(As a more on-topic point, that implementation hashes the incoming
secret; adding to the body of 25519 software which isn't compatible
with hierarchical keys)

You cannot reliably engineer around raw carelessness or indifference.

I think the best we can do is pack all worst of the complexity as deep
inside as possible, to that it's all handled in the parts that _must_
be done with care and competence and extensive review. I think that
optimizing addition formula at the expense of cofactor (whos
complexity is not hidden behind a point_add function deep in the
software) does not accomplish this, at least for applications other
than pure DH.