[tor-dev] [prop269] [prop270] Ideas from Tor Meeting Discussion on Post-Quantum Crypto

Mon Apr 3 20:42:15 UTC 2017

Nick Mathewson transcribed 2.9K bytes:
> On Fri, Mar 31, 2017 at 10:20 PM, isis agora lovecruft
> <isis at 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%20mathematics/post-quantum%20cryptography/XMSS-T:%20Mitigating%20Multi-target%20Attacks%20in%20Hash-based%20Signatures%20(2016)%20-%20H%C3%BClsing%2C%20Rijneveld%2C%20Song.pdf
[2]: https://github.com/isislovecruft/library--/blob/master/cryptography%20%26%20mathematics/post-quantum%20cryptography/SPHINCS:%20practical%20stateless%20hash-based%20signatures%20(2014)%20-%20Bernstein%2C%20Hopwood%2C%20Lange%2C%20Wilcox-OHearn%2C%20et.%20al.pdf
[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
-------------- next part --------------
A non-text attachment was scrubbed...
Name: signature.asc
Type: application/pgp-signature
Size: 1240 bytes
Desc: Digital signature
URL: <http://lists.torproject.org/pipermail/tor-dev/attachments/20170403/fe30a12e/attachment.sig>