[tor-dev] Quantum-safe Hybrid handshake for Tor

[isis]

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
-------------- 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/20151231/b65bc3e9/attachment.sig>