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. 

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). 

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

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".

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.

Thanks for your time, and happy holidays!

Zhenfei Zhang

Security Innovation.