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

[Nick Mathewson]

On Mon, Dec 28, 2015 at 5:34 PM, Zhenfei Zhang
<zzhang at securityinnovation.com> wrote:
> 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.
>
> 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
> https://github.com/NTRUOpenSourceProject/ntru-tor
>
> 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!

Thank you!  This is now proposal 263.

peace,
-- 
Nick