Re: [tor-dev] Interest in collaborating on a standard Ed25519 key blinding scheme?
On Wed, Apr 12, 2017 at 05:57:00PM +0300, George Kadianakis wrote: > An update: > > After lots of discussions in the Amsterdam Tor meeting, the following > approach was suggested for cleansing keys of their torsion components > that is more friendly towards hierarchical key-derivation schemes: > https://moderncrypto.org/mail-archive/curves/2017/000866.html > > However, my current intuition is to just not do this for hidden service > ed25519 blinded keys. Those keys are only used for signing descriptors > which should be safe to do, and we don't plan to use them for D-H any > time soon. If we or some crazy app EVER decides to use those ephemeral > keys for key exchange, we would need to use a special DH function that > kills the tensor component of keys before using them, as suggested by > Trevor here: https://moderncrypto.org/mail-archive/curves/2017/000874.html > > Please let me know if you think this is not a good idea! You're correct that you don't need to do anything special for signatures, since you created the key yourself. For DH, the torsion-safe representative method was meant to be a replacement for the "special DH function" you point to at the end of your message. The win of TSR is that, if no one's doing anything dastardly, you get the *same answer* as a regular unmodified DH, but any attempt at a malicious component to a received DH value is silently zeroed out, at basically no extra cost. The method you cite above also has basically no extra cost, but produces a *different* answer, so everyone has to upgrade at once if you've got an already-deployed system. (Which we don't, to be sure.) The method of "explicitly check for a torsion component and fail if there is one" does produce the same answer as plain DH, but has about double the cost of plain DH (though there are some tricks to cut that down a bit). - Ian ___ tor-dev mailing list tor-dev@lists.torproject.org https://lists.torproject.org/cgi-bin/mailman/listinfo/tor-dev
Re: [tor-dev] Interest in collaborating on a standard Ed25519 key blinding scheme?
Note that the torsion-safe method explicitly *does* result in the low 3 bits being "000". It does not explicity preserve the top bits being "10", because in discussion, we could not determine an actual reason for them to be fixed in that way. Another thing to keep an eye on is how one produces subsequent blinded values after the first. If you use additive blinding, and you produce the next blinded value by re-blinding the last blinded value with the *same* blinding factor (i.e. P -> P + b*G -> P + (2b)*G -> P + (3b)*G, etc.), then all of the pubkeys on that chain are linkable together as coming from the same chain. If you use multiplicative blinding, or derive new blinding factors each time, and/or reblind the original P (i.e. P -> b_1 * P -> b_2 * P -> b_3 * P where the b_i are either independent or even b_i = b^i (multiplicatively blind by b in a chain)), the values are not linkable. [Independently multiplicatively reblinding the original value is what the Tor proposal does.] - Ian ___ tor-dev mailing list tor-dev@lists.torproject.org https://lists.torproject.org/cgi-bin/mailman/listinfo/tor-dev
Re: [tor-dev] Interest in collaborating on a standard Ed25519 key blinding scheme?
> From: George Kadianakis > Date: Wed, Apr 12, 2017 at 7:57 AM > > An update: > > After lots of discussions in the Amsterdam Tor meeting, the following > approach was suggested for cleansing keys of their torsion components > that is more friendly towards hierarchical key-derivation schemes: > https://moderncrypto.org/mail-archive/curves/2017/000866.html > > However, my current intuition is to just not do this for hidden service > ed25519 blinded keys. Those keys are only used for signing descriptors > which should be safe to do, and we don't plan to use them for D-H any > time soon. If we or some crazy app EVER decides to use those ephemeral > keys for key exchange, we would need to use a special DH function that > kills the tensor component of keys before using them, as suggested by > Trevor here: https://moderncrypto.org/mail-archive/curves/2017/000874.html > > Please let me know if you think this is not a good idea! Thanks for the update, George. TL;DR: your scheme seems to be just fine for signatures, and even torsion-safety issues are not huge issues IMHO. For wide applicability reasons, I am trying to make our scheme ChainKD [1] to fit as many use cases as possible and therefore very interested in Tor's requirements and rationale regarding Tor's key blinding proposal. L;R: After studying the situation with key derivation schemes for Ed25519, my impression is that the central issue is not even safety, but compatibility with existing Ed25519 implementations. People who have to integrate a key derivation scheme in their protocol are often not the same people who write the underlying primitives such as scalar multiplication. This means, that it's safer to be conservative and keep the derivation scheme as compatible with EdDSA as possible so that assumptions that implementors may take by just reading the EdDSA spec without knowing about key derivation schemes, do not cause compatibility problems. Since it's not a trivial task to even learn the landscape of problems around Ed25519 compatibility- and safety-wise, it'd help if we can figure all of that once, implement and reuse the result w/o having to go through this again and again. Hence, our interest in standardizing the scheme that satisfies as many requirements as possible. https://xkcd.com/927/ Following the feedback in BIP32-Ed25519 paper [2], I've updated our ChainKD [1] scheme to make it safely "compatible" with DH use cases (among those is asymmetric encryption such as ECIES). In the Design Rationale section [3] I try to describe the issues with low/high bits and torsion-safe representative and why we choose to keep those bits as defined in Curve25519 instead of "torsion-safe representative" and why we use BIP32-style blinding-by-addition instead of blinding-by-multiplication. One piece of feedback affecting our proposal is missing, though: I'd like to ask Tor developers what is the rationale and requirements for their key blinding proposal. Specifically, why do you choose to blind via multiplication instead of addition: s' = b*s; P' = b*P (Tor's proposal) vs s' = s + b; P' = P + b*G (BIP32, ChainKD) (G -- base point, P -- pubkey, s -- secret scalar, P = s*G, b -- blinding scalar) I know of a few reasons to use addition over multiplication (e.g. performance and bit-compatibility with EdDSA), but would love to learn if that hurts some protocols. PS. I've just joined the list and replying to a forwarded message. I apologize if I break the thread. [1] ChainKD, revised: https://github.com/chain/chain/blob/chainkd-dh/docs/protocol/specifications/chainkd.md [2] BIP32-Ed25519: https://drive.google.com/open?id=0ByMtMw2hul0EMFJuNnZORDR2NDA [3] ChainKD rationale: https://github.com/chain/chain/blob/chainkd-dh/docs/protocol/specifications/chainkd.md#design-rationale ___ tor-dev mailing list tor-dev@lists.torproject.org https://lists.torproject.org/cgi-bin/mailman/listinfo/tor-dev
Re: [tor-dev] Interest in collaborating on a standard Ed25519 key blinding scheme?
Tony Arcieri writes: > I'm trying to gauge interest on the IRTF's CFRG mailing list regarding > collaborating on a draft for a standard Ed25519 hierarchical derivation / > key blinding scheme: > > https://mailarchive.ietf.org/arch/msg/cfrg/lM1ix9R-0tVzhZorQhQlKvi4wpA > > The post makes several mentions of Tor's work in the space in regard to the > next-generation hidden services design. > > I think it'd be great if Tor were to collaborate on the design of such a > scheme and adopt it for the new hidden services design. I see a lot of > convergent evolution in this space and think it would be great if there > were a single standard everyone could implement. > > Even if you don't, I think there are some ideas from similar schemes Tor > should fold back into its own design, particularly in regard to how certain > bits of the private scalar are "clamped". Some discussion of that here: > > https://moderncrypto.org/mail-archive/curves/2017/000862.html > > tl;dr: clamp the third highest bit of the root scalar to zero (in addition > to the bits normally clamped in the non-canonical Ed25519 private scalar), > and use 224-bit child scalars. > An update: After lots of discussions in the Amsterdam Tor meeting, the following approach was suggested for cleansing keys of their torsion components that is more friendly towards hierarchical key-derivation schemes: https://moderncrypto.org/mail-archive/curves/2017/000866.html However, my current intuition is to just not do this for hidden service ed25519 blinded keys. Those keys are only used for signing descriptors which should be safe to do, and we don't plan to use them for D-H any time soon. If we or some crazy app EVER decides to use those ephemeral keys for key exchange, we would need to use a special DH function that kills the tensor component of keys before using them, as suggested by Trevor here: https://moderncrypto.org/mail-archive/curves/2017/000874.html Please let me know if you think this is not a good idea! ___ tor-dev mailing list tor-dev@lists.torproject.org https://lists.torproject.org/cgi-bin/mailman/listinfo/tor-dev
Re: [tor-dev] Interest in collaborating on a standard Ed25519 key blinding scheme?
On Wed, Mar 22, 2017 at 12:07 PM, Tony Arcieri wrote: > On Wed, Mar 22, 2017 at 6:15 AM, Nick Mathewson > wrote: >> >> Hi! I guess we could keep an eye on the process, though I don't know that >> I'd have much to contribute myself: I'm more of a crypto consumer than a >> crypto generator. Maybe one of the developers who knows crypto better can >> join in here? > > > The main notable points of discussion so far have all been around preserving > Ed25519's original "clamping" invariants. I didn't see any discussion of > this in the current Tor spec. > >> >> As for adoption: we're on track to deploy next generation hidden services >> some time this year, ideally in the next 4 or 5 months, so the window to >> converge on a common system is small by standards-body standards. > > > Yeah, that's a blink of an eye in the IETF timescale. However, I think if > you incorporate some feedback into your current design and do end up > shipping it before a draft standard undergoes the requisite bikeshedding, > the "running code" aspect of Tor using it in the wild will probably help the > standard converge around whatever you ship. Worked out for Ed25519 itself, > anyway. Fair enough. My understanding right now is that a bunch of us think this solution looks promising, and will probably be what we build, unless it turns out to be bad or someone comes up with something even better. https://moderncrypto.org/mail-archive/curves/2017/000866.html Henry, Isis, Ian, George: Would one of you like to join in on the the CFRG thread about this? I'm not sure I'm enough of a cryptographer to be a good advocate here. -- Nick ___ tor-dev mailing list tor-dev@lists.torproject.org https://lists.torproject.org/cgi-bin/mailman/listinfo/tor-dev
Re: [tor-dev] Interest in collaborating on a standard Ed25519 key blinding scheme?
On Wed, Mar 22, 2017 at 6:15 AM, Nick Mathewson wrote: > Hi! I guess we could keep an eye on the process, though I don't know that > I'd have much to contribute myself: I'm more of a crypto consumer than a > crypto generator. Maybe one of the developers who knows crypto better can > join in here? > The main notable points of discussion so far have all been around preserving Ed25519's original "clamping" invariants. I didn't see any discussion of this in the current Tor spec. > As for adoption: we're on track to deploy next generation hidden services > some time this year, ideally in the next 4 or 5 months, so the window to > converge on a common system is small by standards-body standards. > Yeah, that's a blink of an eye in the IETF timescale. However, I think if you incorporate some feedback into your current design and do end up shipping it before a draft standard undergoes the requisite bikeshedding, the "running code" aspect of Tor using it in the wild will probably help the standard converge around whatever you ship. Worked out for Ed25519 itself, anyway. -- Tony Arcieri ___ tor-dev mailing list tor-dev@lists.torproject.org https://lists.torproject.org/cgi-bin/mailman/listinfo/tor-dev
Re: [tor-dev] Interest in collaborating on a standard Ed25519 key blinding scheme?
On Mar 21, 2017 9:47 PM, "Tony Arcieri" wrote: I'm trying to gauge interest on the IRTF's CFRG mailing list regarding collaborating on a draft for a standard Ed25519 hierarchical derivation / key blinding scheme: https://mailarchive.ietf.org/arch/msg/cfrg/lM1ix9R-0tVzhZorQhQlKvi4wpA The post makes several mentions of Tor's work in the space in regard to the next-generation hidden services design. I think it'd be great if Tor were to collaborate on the design of such a scheme and adopt it for the new hidden services design. I see a lot of convergent evolution in this space and think it would be great if there were a single standard everyone could implement. Even if you don't, I think there are some ideas from similar schemes Tor should fold back into its own design, particularly in regard to how certain bits of the private scalar are "clamped". Some discussion of that here: https://moderncrypto.org/mail-archive/curves/2017/000862.html tl;dr: clamp the third highest bit of the root scalar to zero (in addition to the bits normally clamped in the non-canonical Ed25519 private scalar), and use 224-bit child scalars. -- Tony Arcieri Hi! I guess we could keep an eye on the process, though I don't know that I'd have much to contribute myself: I'm more of a crypto consumer than a crypto generator. Maybe one of the developers who knows crypto better can join in here? As for adoption: we're on track to deploy next generation hidden services some time this year, ideally in the next 4 or 5 months, so the window to converge on a common system is small by standards-body standards. Of course, I'd rather we adopt a standard scheme than not, but I think we are instead likeliest to adopt whatever scheme we have available to us on our timescale. George, David: any thoughts on the moderncrypto post? I think nicoo maybe mentioned it to me a couple of weeks back? -- Nick ___ tor-dev mailing list tor-dev@lists.torproject.org https://lists.torproject.org/cgi-bin/mailman/listinfo/tor-dev
