Zhenfei Zhang transcribed 22K bytes: > Hi list, > > This is a proposal to use quantum-safe hybrid handshake for Tor > communications. Given NSA's recent announcement on moving towards > quantum-safe cryptography, it would be nice to have a quantum-safe feature > for Tor. Hello Zhenfei, We're also very interested in having post-quantum security for Tor, and it's super exciting and helpful to have researchers helping us come up with a designs. > The idea of the quantum-safe hybrid handshake is to combine both classical > key exchange and a key encapsulation mechanism (KEM) instantiated by a > quantum safe encryption algorithm, so that the combination gives both > (classical) authentication and quantum safety. In a bit more details, the > client and the server agrees on a classic pre-master secret, $c$, using the > ntor protocol. In parallel, client generates a public/private key pair of > the quantum-safe encryption algorithm, and send the public key to the > server. The server picks a random string, $q$, encrypts it with the public > key and send the ciphertext back to the client. The final secret is the > output of KDF(c|q). Assuming an adversary who possesses a quantum computer capable of performing Shor's algorithm to break ECDLP in some reasonable amount of time, sending client's "quantum-safe" key through the ntor channel still doesn't provide post-quantum security, since this portion of the KEX isn't authenticated with a PQ-secure scheme. (Upon reading further, I realised this is mentioned in the last paragraph of your proposal.) I feel like there needs to be some new terminology here. It's certainly not post-quantum secure, but "quantum-safe" doesn't seem right either, because it's exactly the point at which the adversary gains appropriate quantum computational capabilities that it become *unsafe*. If I may, I suggest calling it "pre-quantum secure". :) > This proposal defeats the harvest-then-decrypt attack with a minimum impact > to the existing ntor protocol. An adversary needs to be able to break the > quantum-safe encryption algorithm to learn q. On the other hand, if the > quantum-safe encryption algorithm turns out to be not secure, the protocol > is still as secure as ntor protocol. In other words, it will at least do no > harm to the current security. > > In addition, this is a modular design that allows us to use any quantum-safe > cryptographic primitives. As a proof of concept, we instantiated the > protocol with NTRUEncrypt lattice-based crypto. We implemented the the > protocol with NTRU parameters that gives 128 bits security. The code is > available at https://github.com/NTRUOpenSourceProject/ntru-tor Thanks! This is great! Having an implementation to go along with the proposal makes it easier to evaluate. I've already actually looked at your code a couple months ago, but I'll take a second look after the new year and see what (if anything) changed. However, if we were to go the route of using NTRU, we'd likely want to instead use Dan Bernstein's NTRU Prime parameters, in order to eliminate some of the inherent algebraic structure of the ideal lattice which might possibly be exploited. [0] [1] Also, what is the current state of patents on NTRU? My understanding is that NTRU is dual-licenced as GPLv2+ and commercial, [2] however, Tor is currently BSD licenced. Would it be necessary to relicense Tor as GPLv2+? Will the GPL exceptions continue to be applied to further patents on optimisations and improvements/protections for NTRU? > Please find the attachment for the request to change the feature. The proof > of the protocol can be found at: https://eprint.iacr.org/2015/287.pdf > > Some known issue: > 1. cell size. As far as we know, all quantum-safe encryption algorithms have > large key and/or ciphertext size that exceeds the cell size ~500. So this > protocol needs to transmit multiple cells, no matter which quantum-safe > encryption algorithm we chose. This is addressed by "Proposal 249: Allow > CREATE cells with >505 bytes of handshake data". Nick created proposal #249 [2] to address this issue. (It'd be great to have additional review on the proposal to ensure that it does meet the needs of designers of candidate post-quantum schemes!) > 2. quantum-safe authentication: there is no quantum-safe authentication in > this protocol. We believe that authentication can wait, as future > (quantum) adversary cannot come back to present time and break > authentication. Hence, we use ntor authentication to keep the proposal > compact and simple. It will be a future work after this proposal. Not to delay progress on making Tor post-quantum secure, but if we tackled both encryption and authentication in parallel, we'd better able to compare the advantages and disadvantages of schemes, given that we can take overhead fully into account, e.g. total added keysize(s). For example, if we were to add something like a McEliese CFS signature (code-based) or an XMSS signature (hash-based) to add authentication, on top of already using some lattice-based cryptosystem like NTRU, we would have two quite large keys, with one or both needing to be distributed, for each relay. > Thanks for your time, and happy holidays! Many thanks for the proposal, research, and code! Have a great new year! [0]: http://blog.cr.yp.to/20140213-ideal.html [1]: http://cr.yp.to/talks/2015.04.22/slides-djb-20150422-a4.pdf [2]: https://github.com/NTRUOpenSourceProject/ntru-crypto/blob/master/PATENTS.md [3]: https://gitweb.torproject.org/torspec.git/tree/proposals/249-large-create-cells.txt -- ââ isis agora lovecruft _________________________________________________________ OpenPGP: 4096R/0A6A58A14B5946ABDE18E207A3ADB67A2CDB8B35 Current Keys: https://blog.patternsinthevoid.net/isis.txt
Attachment:
signature.asc
Description: Digital signature
_______________________________________________ tor-dev mailing list tor-dev@xxxxxxxxxxxxxxxxxxxx https://lists.torproject.org/cgi-bin/mailman/listinfo/tor-dev