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

[Tony Arcieri]

Ed25519 performs the following operations on private scalars immediately
prior to use:

scalar[0] &= 248;
scalar[31] &= 63;
scalar[31] |= 64;


I've heard this referred to as "clamping" although that may not be the best
term.

These operations are not applied to the canonical scalar, i.e. the one
which is serialized and persisted as part of the keypair. Instead Ed25519
implementations generally flip these bits immediately prior to use, either
for signing or deriving the public key.

>From what I've read, this bitflipping is intended to accomplish the
following:

   - Prevent small subgroup attacks: flipping these bits makes the scalar a
   multiple of the cofactor, which I understand is supposed to help prevent
   small subgroup attacks. However, reading about these attacks, they don't
   seem to help the attacker very much.
   - Defense against deficient implementations: I'm not sure I really
   understand the rationale here, but my understanding is there are certain
   classes of implementation defects this helps guard against.

So far, it's been pretty troublesome finding a really good explanation of
what this bitflipping is actually for or anyone who feels particularly
strongly as to its importance. The general reaction I've gotten asking
about them is akin to "djb flipped these bits... he must have his reasons".

Flipping these bits is particularly troublesome for implementing
hierarchical key derivation schemes (e.g. semiprivate keys, BIP-32) which
rely on commutative groups to allow holders of master public keys to derive
child public keys by multiplying by scalar values which can be derived by
both the public and private key holders (a.k.a. "hardened" vs
"non-hardened" derivation in BIP-32 schemes).

In these schemes, it's not possible to "clamp" the derived scalar
immediately prior to signing ("post-clamping" I guess?), as this would
result in a different public key (i.e. the math simply does not work out as
the groups are no longer commutative). Instead, if any clamping is to be
performed it must happen immediately to the parent scalar, and/or to any
scalars derived by both the public and private key holders in such a scheme.

My intuition is that "clamping" more than once is detrimental in that the
clamping operation weakens the key. Not really being sure about the purpose
though, I'm not sure if "pre-clamping" is sufficient to guard against these
attacks.

I'm very curious if "clamping" can simply be omitted, as it seems to
largely be a defense-in-depth measure which guards against a handful of
low-severity theoretical attacks. It complicates HKD schemes and, done
incorrectly in the context of such a scheme, I'm worried it might actually
harm security.

-- 
Tony Arcieri
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://moderncrypto.org/mail-archive/curves/attachments/20170306/a8a94b09/attachment.html>