[prop269] [prop270] Ideas from Tor Meeting Discussion on Post-Quantum Crypto
Hey hey, In summary of the breakaway group we had last Saturday on post-quantum cryptography in Tor, there were a few potentially good ideas I wrote down, just in case they didn't make it into the meeting notes: * A client should be able to configure "I require my entire circuit to have PQ handshakes" and "I require at least one handshake in my circuits to be PQ". (Previously, we had only considered having consensus parameters, in order to turn the feature on e.g. once 20% of relays supported the new handshake method.) * Using stateful hash-based signatures to sign descriptors and/or consensus documents, and (later) if state has been lost or compromised, then request the last such document submitted to regain state (probably skipping over all the leaves of the last used node in the tree, or the equivalent, to be safe). (This requires more concrete design analysis, including the effects of the large size of hash-based signatures on the directory bandwidth usage, probably in a proposal or longer write up, should someone awesome decides to research this idea further. :) Thanks to everyone involved in the breakaway group, and I apologise, but I don't actually remember all the attendants off the top of my head. If either of these were your idea, please message me off-list and I'll ensure you're credited in the eventual proposal(s)/documentation. Best regards, -- ♥Ⓐ isis agora lovecruft _________________________________________________________ OpenPGP: 4096R/0A6A58A14B5946ABDE18E207A3ADB67A2CDB8B35 Current Keys: https://fyb.patternsinthevoid.net/isis.txt
On Fri, Mar 31, 2017 at 10:20 PM, isis agora lovecruft <isis@torproject.org> wrote:
Hey hey,
In summary of the breakaway group we had last Saturday on post-quantum cryptography in Tor, there were a few potentially good ideas I wrote down, just in case they didn't make it into the meeting notes:
* A client should be able to configure "I require my entire circuit to have PQ handshakes" and "I require at least one handshake in my circuits to be PQ". (Previously, we had only considered having consensus parameters, in order to turn the feature on e.g. once 20% of relays supported the new handshake method.)
+1 on having something like this happen in some way, -0 on having client configuration be the recommended way for any purpose other than testing (Having clients behave differently is best avoided.) Our usual approach for this kind of thing a consensus parameter that can be overridden with a local option.
* Using stateful hash-based signatures to sign descriptors and/or consensus documents, and (later) if state has been lost or compromised, then request the last such document submitted to regain state (probably skipping over all the leaves of the last used node in the tree, or the equivalent, to be safe). (This requires more concrete design analysis, including the effects of the large size of hash-based signatures on the directory bandwidth usage, probably in a proposal or longer write up, should someone awesome decides to research this idea further. :)
Interesting! I'd hope we do this as a separate proposal. Also my hope is that in our timeline, we prioritize PQ encryption over authentication, since PQ encryption provides us forward secrecy against future quantum computers, whereas PQ authentication is only useful once a sufficient quantum computer exists. (That's no reason not to think about PQ authentication, but with any luck, we can wait a few years for the PQ crypto world to invent some even better algorithms.) peace, -- Nick
Nick Mathewson transcribed 2.9K bytes:
On Fri, Mar 31, 2017 at 10:20 PM, isis agora lovecruft <isis@torproject.org> wrote:
Hey hey,
In summary of the breakaway group we had last Saturday on post-quantum cryptography in Tor, there were a few potentially good ideas I wrote down, just in case they didn't make it into the meeting notes:
* A client should be able to configure "I require my entire circuit to have PQ handshakes" and "I require at least one handshake in my circuits to be PQ". (Previously, we had only considered having consensus parameters, in order to turn the feature on e.g. once 20% of relays supported the new handshake method.)
+1 on having something like this happen in some way, -0 on having client configuration be the recommended way for any purpose other than testing (Having clients behave differently is best avoided.)
Our usual approach for this kind of thing a consensus parameter that can be overridden with a local option.
So it sounds like we want one consensus parameter that is a preference-ordered list of handshake types to use, e.g. "RecommendedHandshakes 3 2", to turn on/off usage of a particular handshake. And we also want a consensus parameter particular to PQ handshakes, something like "PQHandshakesPerCircuit {none,one,all}" which only has an effect if "RecommendedHandshakes" includes a PQ one. Does that sound like it would give the desired configurability?
* Using stateful hash-based signatures to sign descriptors and/or consensus documents, and (later) if state has been lost or compromised, then request the last such document submitted to regain state (probably skipping over all the leaves of the last used node in the tree, or the equivalent, to be safe). (This requires more concrete design analysis, including the effects of the large size of hash-based signatures on the directory bandwidth usage, probably in a proposal or longer write up, should someone awesome decides to research this idea further. :)
Interesting! I'd hope we do this as a separate proposal.
Yes, as I recall (avoiding naming names so as not to volunteer anyone) others were interested in looking into this. A good start would be to come up with some napkin numbers on the impacts of signature and key sizes. For anyone interested in exploring this idea, good starting resources for hash-based signatures: * For a light introduction to hash-based signatures, Adam Langley has a good blog post. [0] * For stateful: "XMSS-T: Mitigating Multi-target Attacks in Hash-based Signatures" (2016), by Hülsing, Rijneveld, and Song. [1] * For stateless: "SPHINCS: practical stateless hash-based signatures" (2014) by Bernstein, Hopwood, Hüsling, Lange, Niederhagen, Papachristodoulou, Schwabe, and Zooko. [2] * For background/history: Andy Hülsing keeps up-to-date lists of papers and recommendations. [3]
Also my hope is that in our timeline, we prioritize PQ encryption over authentication, since PQ encryption provides us forward secrecy against future quantum computers, whereas PQ authentication is only useful once a sufficient quantum computer exists.
(That's no reason not to think about PQ authentication, but with any luck, we can wait a few years for the PQ crypto world to invent some even better algorithms.)
Yes, I agree. (Personally, I'm not inclined to work on this, at least not any time in the next few years.) If other people want to do it as a fun research project, though, I think that's fine, since it wouldn't hurt to have a decent proposal on the table if/when the "quantum computers we care about are for real" day comes. Also, for what it's worth, I know Andy is always looking for specific applications/design constraints for hash-based sigs, since constructions can often be hand-tailored/optimised. And, obviously, from an academic-incentives perspective, this is both a fun problem to solve and a paper. [0]: https://www.imperialviolet.org/2013/07/18/hashsig.html [1]: https://github.com/isislovecruft/library--/blob/master/cryptography%20%26%20... [2]: https://github.com/isislovecruft/library--/blob/master/cryptography%20%26%20... [3]: https://huelsing.wordpress.com/hash-based-signature-schemes/literature/ Best, -- ♥Ⓐ isis agora lovecruft _________________________________________________________ OpenPGP: 4096R/0A6A58A14B5946ABDE18E207A3ADB67A2CDB8B35 Current Keys: https://fyb.patternsinthevoid.net/isis.txt
participants (2)
-
isis agora lovecruft -
Nick Mathewson