On Thu, Mar 9, 2017 at 10:54 AM, Tony Arcieri <basc...@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 _______________________________________________ Curves mailing list Curves@moderncrypto.org https://moderncrypto.org/mailman/listinfo/curves