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

[zaki at manian.org]

This clamping question also impacts how Tor's Next Generation Onion
services will blind keys from the Onion Services Directory authorities.

On Mon, Mar 6, 2017 at 2:36 PM Tony Arcieri <bascule at gmail.com> wrote:

> 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
> _______________________________________________
> Curves mailing list
> Curves at moderncrypto.org
> https://moderncrypto.org/mailman/listinfo/curves
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://moderncrypto.org/mail-archive/curves/attachments/20170306/178983cd/attachment.html>