Tony Arcieri

2017-03-06 19:36:14 UTC

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.

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

Tony Arcieri