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

[Trevor Perrin]

On Thu, Mar 9, 2017 at 10:54 AM, Tony Arcieri <bascule at gmail.com> wrote:
>
> I'd be curious what you think about a paper describing an
> adaptation of BIP32 to Ed25519 I've recently been pointed at (shortly after
> posting this thread):
>
> https://github.com/WebOfTrustInfo/rebooting-the-web-of-trust-fall2016/blob/master/topics-and-advance-readings/HDKeys-Ed25519.pdf


That Evernym paper is similar to Greg's suggestion [1] ("make your
derivation scheme multiply its scalar by the cofactor"), but also
arranges things so the high scalar bits are "clamped".

Mike pointed out that making your scalar a multiple of cofactor isn't
that important for traditional X25519 DH, since a small-subgroup
attack would only leak a few low bits of the scalar.  But if
hierarchically-derived keys were used for DH then a few low bits from
related-but-different scalars might be leaked, which could be a
problem [2].

In addition to "clamping" the low bits to deal with small-subgroup
attacks, the other part of clamping is setting the high bits so (a)
the scalar is smaller than the subgroup order, and (b) so the highest
set bit is constant in case the scalar is used with a
non-constant-time scalarmult algorithm that leaks based on the highest
set bit [3].

For hierarchical key derivation it's easy to keep the scalar modulo
the subgroup order, so (a) is easy to deal with.  I think (b) isn't
that important, since people aren't (or at least shouldn't be) writing
non-const-time scalarmult.  Anyone disagree?

Anyways, Henry suggested another way of dealing with the
small-subgroup risk: Convert the scalar to a representative equivalent
to the original scalar (mod subgroup order), but zero (mod cofactor).
I could imagine that being useful in some protocols.  But for
hierarchical key derivation, where you're deriving a new scalar
anyways, I'm not sure this has advantages versus multiplying by the
cofactor?

The Tor approach seems simplest [4]:  ignore the clamping!  As long as
the hierarchically-derived keys are used for signatures (not DH) then
Mike's concern is avoided.

If you wanted to use hierarchically-derived keys for DH later you
could define a cofactor-DH operation that multiplies by cofactor.  In
the olden days, this is how NIST specified ECDH (see Cofactor DH in
SP800-56A [5]).  DJB chose to include cofactors into the private keys
instead, presumably because bit-flipping was easier than multiplying,
for a freshly-generated scalar.

So maybe the question is how much you care about spending a little
extra effort in key derivation to make the keys a little safer with
existing DH software?  I.e., do you multiply by the scalar as part of
derivation, or leave that for a future DH operation?


Trevor

[1] https://moderncrypto.org/mail-archive/curves/2017/000860.html
[2] https://moderncrypto.org/mail-archive/curves/2017/000861.html
[3] https://www.ietf.org/mail-archive/web/cfrg/current/msg05004.html
[4] https://moderncrypto.org/mail-archive/curves/2017/000866.html
[5] https://gitweb.torproject.org/torspec.git/tree/proposals/224-rend-spec-ng.txt#n1979
[6] http://nvlpubs.nist.gov/nistpubs/SpecialPublications/NIST.SP.800-56Ar2.pdf