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

[Mike Hamburg]

> On Mar 6, 2017, at 12:23 PM, Gregory Maxwell <gmaxwell at gmail.com> wrote:
> 
> On Mon, Mar 6, 2017 at 7:36 PM, Tony Arcieri <bascule at gmail.com> wrote:
>> Ed25519 performs the following operations on private scalars immediately
>> prior to use:
> 
> I assume the bytes of the scalar here is written least significant
> first; otherwise I can't make sense of your message.

Yes.  DJB crypto is generally little-endian.

>> scalar[0] &= 248;
> 
> This is making the number a multiple of 8, presumably due to the
> cofactor. You can simply make your derivation scheme multiply its
> scalar by the cofactor for this... Then everything is compatible.
> Hurray.

Right.  And this step doesn’t matter for security in x25519, unless you’re checking for contributory behavior.  This is because an attacker who sent points with a torsion component could recover the low bits of your key.  You’ve stymied that attacker by setting those bits to 0… which is basically the same result.

However, for hierarchical key derivation you should probably multiply by the cofactor as Gregory suggests.  Otherwise you might have an attack based on the hidden number problem or something (eg, Bleichenbacher).

> 
>> scalar[31] &= 63;
>> scalar[31] |= 64;
> 
> This is clamping to ~the order and making the most significant bit 1.
> Your application should already be assuring that the scalar is in
> range for the group size.
> 
> Setting the most significant bit is a (IMO mildly offensive)
> performance hack so that the exponentiation ladder does not need to
> correctly handle the point at infinity.  To deal with this the point
> arithmetic likely needs to have a conditional move to handle
> propagating through a point at infinity when the scalar's most
> significant bits are a run of zeros. The only real solution to this
> one is "don't do that optimization" (or do it and use an extra
> addition and a conditional swap).
> 
> Good luck with mysterious failures when someone combines your
> application which relaxes this restriction with found-on-the-internets
> ed25519 code which expects it to be upheld.

I believe it turns out that for most implementations of the Montgomery ladder found on the internet, the leading bit doesn’t have to be 1 for correctness, and you don’t need any extra CMOVs or anything.

Setting the leading bit to 1 and the low bits to 0 does ensure that the scalar is not a multiple of q, and that you don’t pass through any multiples of q on the way.  I’m not sure that restriction matters in practice, though, because the scalar should be random and therefore almost certainly not a multiple of q anyway.  But in principle this could cause an incorrect result… it just happens with negligible probability that an attacker can’t really amplify.

Cheers,
— Mike
-------------- next part --------------
A non-text attachment was scrubbed...
Name: smime.p7s
Type: application/pkcs7-signature
Size: 3571 bytes
Desc: not available
URL: <http://moderncrypto.org/mail-archive/curves/attachments/20170306/23357102/attachment.bin>