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

Zhenfei Zhang zzhang at securityinnovation.com
Mon Dec 28 22:34:26 UTC 2015

Hi list,

This is a proposal to use quantum-safe hybrid handshake for Tor
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
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$,
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
the existing ntor protocol. An adversary needs to be able to break the
encryption algorithm to learn q. On the other hand, if the quantum-safe
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
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
large key and/or ciphertext size that exceeds the cell size ~500. So this
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
protocol. We believe that authentication can wait, as future (quantum)
cannot come back to present time and break authentication. Hence, we use
authentication to keep the proposal compact and simple. It will be a future
after this proposal.

Thanks for your time, and happy holidays!

Zhenfei Zhang
Security Innovation.
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.torproject.org/pipermail/tor-dev/attachments/20151228/53241496/attachment.html>
-------------- next part --------------
Title: Request to change key exchange protocol for handshake
Author: John SCHANCK, William WHYTE and Zhenfei ZHANG
Created: 29 Aug 2015

1. Introduction

  Recognized handshake types are:
    0x0000  TAP         --  the original Tor handshake;
    0x0001  reserved
    0x0002  ntor        --  the ntor+curve25519+sha256 handshake;

  Request for a new (set of) handshake type:
    0x010X  ntor+qsh    --  the hybrid of ntor+curve25519+sha256 handshake
                            and a quantum-safe key encapsulation mechanism

    0X0101  ntor+qsh    --  refers this modular design, no specific KEM is

    0X0101  ntor+ntru   --  the quantum safe KEM is based on NTRUEncrypt, with
                            parameter ntrueess439ep1

    0X0102  ntor+ntru   --  the quantum safe KEM is based on NTRUEncrypt, with
                            parameter ntrueess743ep1

    0X0103  ntor+rlwe   --  the quantum safe KEM is based on ring learning with
                            error encryption scheme; parameter not specified

	  Proposal 249: Allow CREATE cells with >505 bytes of handshake data

  1.1 Motivation: Quantum resistant key agreement

    We are trying to add quantum resistance to the key agreement in Tor
    handshake. Current approaches for handling key agreement, for instance,
    ntor, are not quantum resistant. ECC will be broken when quantum computers
    become available. This allows an adversary with significant storage
    capabilities to harvest Tor handshakes now and decrypt them in the

  1.2 Motivation: Disaster resilience

    We are really trying to protect against the disastrous situation of one key
    being entirely compromised. By introducing a second cryptographic primitive,
    namely, NTRUEncrypt, we ensure that the system remains secure in those
    extreme scenarios.

  1.3 Motivation: Allowing plug & play for quantum-safe encryption algorithms

    We would like to be conservative on the selection of quantum-safe encryption
    algorithm. For this purpose, we propose a modular design that allows any
    quantum-safe encryption algorithm to be included in this handshake
    framework. We will illustrate the proposal with NTRUEncrypt encryption

2. Proposal

  2.1 Overview

    In Tor, authentication is one-way in the authenticated key-exchange
    protocol. This proposed new handshake protocol is consistent with that

    We aim to provide quantum resistance and disaster resilience to the Tor
    network, with the minimum impact on the current version. We aim to use
    as many existing mechanisms as possible.

    For purposes of comparison, proposed modifications are indicated with * at
    the beginning of the corresponding line, the original approaches in ntor
    are marked with # when applicable.

    In order to enable variant quantum-safe algorithms for Tor handshake, we
    propose a modular approach that allows any quantum-safe encryption algorithm
    to be adopted in this framework. Our approach is a hybridization of ntor
    protocol and a KEM. We instantiate this framework with NTRUEncrypt, a
    lattice-based encryption scheme that is believed to be quantum resistant.
    This framework is expandable to other quantum-safe encrypt schemes such as
    Ring Learning with Error (R-LWE) based schemes.

    2.1.1 Achieved Property:

      1)  The proposed key exchange method is quantum resistant: The forward secrecy 
      of the scheme assumes future adversaries are equipped with quantum computers.

      2)  The proposed key exchange method is disaster resilient: The protocol
      depends on two cryptographic primitives. Compromising one does not break
      the security of the whole system.

      3)  The proposed key exchange method provides one-way authentication: The
      server is authenticated, while the client remains anonymous.

      4)  The protocol is almost backward compatible with its previous
      version: ntor. By omitting a single field, one obtains the exact ntor
      protocol. That is, the protocol is at least as secure as ntor.

      5)  The protocol provides perfect forward secrecy: two secrets are
      exchanged, one protected by ECC, one protected by NTRUEncrypt, and then
      put through the native Tor Key Derivation Function (KDF) to derive the
      encryption and authentication keys. Both secrets are protected with
      one-time keys for their respective public key algorithms.

    2.1.2 General idea:

      When a client wishes to establish a one-way authenticated key K with a
      server, through following steps a session key is established:
      1)  Establish a common secret E (classical cryptography, i.e., ECC) using
      a one-way authenticated key exchange protocol.
      #ntor currently uses this approach#;
      2)  Establish a common "parallel" secret P using a key encapsulation
      mechanism similar to TLS_RSA. In this feature request we use NTRUEncrypt
      as an example.
      3)  Establish a new session key k = KDF(E|P, info, i), where KDF is a Key
      Derivation Function.

    2.1.3 Building Blocks

      1)  ntor: ECDH-type key agreement protocol with one-way authentication;
      ##existing approach: See 5.1.4 tor-spec.txt##

      2)  A quantum-safe encryption algorithm: we use QSE to refer to the
      quantum-safe encryption algorithm, and use NTRUEncrypt as our example;
      **new approach**

      3)  HMAC-based Extract-and-Expand Key Derivation Function - KDF-RFC5869;
      ##existing approach: See 5.2.2 tor-spec.txt##

  2.2 The protocol

    2.2.1 Initialization

      H(x,t) as HMAC_SHA256 with message x and key t.
      H_LENGTH      = 32
      ID_LENGTH     = 20
      G_LENGTH      = 32

*     QSPK_LENGTH   = XXX           length of QSE public key
*     QSC_LENGTH    = XXX           length of QSE cipher

*     PROTOID       = "ntor-curve25519-sha256-1-[qseid]"
#pre  PORTOID       = "ntor-curve25519-sha256-1"

      t_mac         = PROTOID | ":mac"
      t_key         = PROTOID | ":key_extract"
      t_verify      = PROTOID | ":verify"

      These three variables define three different cryptographic hash functions:
      hash1         = HMAC(*, t_mac);
      hash2         = HMAC(*, t_key);
      hash3         = HMAC(*, t_verify);

      MULT(A,b)     = the multiplication of the curve25519 point 'A' by the
                      scalar 'b'.
      G             = The preferred base point for curve25519
      KEYGEN()      = The curve25519 key generation algorithm,
                      returning a private/public keypair.
      m_expand      = PROTOID | ":key_expand"

        b, B        = KEYGEN();

*     QSH
*       QSSK,QSPK   = QSKEYGEN();
*       cipher      = QSENCRYPT (*, PK);
*       message     = QSDECRYPT (*, SK);

    2.2.2 Handshake

      To perform the handshake, the client needs to know an identity key digest
      for the server, and an ntor onion key (a curve25519 public key) for that
      server. Call the ntor onion key "B".

      The client generates a temporary key pair:
        x, X        = KEYGEN();

      an NTRU temporary key pair:
*       QSSK, QSPK  = QSKEYGEN();

      and generates a client-side handshake with contents:
        NODEID      Server identity digest  [ID_LENGTH   bytes]
        KEYID       KEYID(B)                [H_LENGTH    bytes]
        CLIENT_PK   X                       [G_LENGTH    bytes]
*       QSPK        QSPK                    [QSPK_LENGTH bytes]

      The server generates an ephemeral curve25519 keypair:
        y, Y        = KEYGEN();

      a ephemeral "parallel" secret for encryption with NTRU:
*       PAR_SEC     P                       [H_LENGTH    bytes]

      and computes:
*       C           = ENCRYPT( P | B, QSPK);

      Then it uses its ntor private key 'b' to compute an ECC secret
        E           = EXP(X,y) | EXP(X,b) | B | X | Y

      and computes:

*       secret_input    = E | P | QSPK | ID | PROTOID
#pre    secret_input    = E | ID | PROTOID

        KEY_SEED        = H(secret_input, t_key)
        verify          = H(secret_input, t_verify)
*       auth_input      = verify | B | Y | X | C | QSPK
                          | ID | PROTOID | "Server"
#pre    auth_input      = verify | B | Y | X | ID | PROTOID | "Server"

      The server's handshake reply is:
        SERVER_PK       Y                       [G_LENGTH     bytes]
        AUTH            H(auth_input, t_mac)    [H_LENGTH     bytes]
*       QSCIPHER        C                       [QSPK_LENGTH  bytes]
      The client then checks Y is in G^*, and computes

        E               = EXP(Y,x) | EXP(B,x) | B | X | Y
*       P'              = DECRYPT(C, QSSK)

      extract P,B from P' (P' = P|B), verifies B, and computes

*       secret_input    = E | P | QSPK | ID | PROTOID
#pre    secret_input    = E | ID | PROTOID

        KEY_SEED        = H(secret_input, t_key)
        verify          = H(secret_input, t_verify)
*       auth_input      = verify | B | Y | X | C | ID | PROTOID | "Server"
#pre    auth_input      = verify | B | Y | X | ID | PROTOID | "Server"

      The client verifies that AUTH == H(auth_input, t_mac).

      Both parties now have a shared value for KEY_SEED. This value will be used
      during Key Derivation Function - KDF-RFC5869 (see 5.2.2 tor-spec.txt)

  2.3 Instantiation with NTRUEncrypt

    The example uses the NTRU parameter set NTRU_EESS439EP1. This has keys
    and ciphertexts of length 604 bytes. This parameter set delivers 128 bits
    classical security. For 128 bits quantum security, use NTRU_EESS743EP1.

    We adjust the following parameters:

    handshake type:
    0X0101  ntor+ntru       the quantum safe KEM is based on NTRUEncrypt, with
                            parameter ntrueess439ep1
    PROTOID       = "ntor-curve25519-sha256-1-ntrueess439ep1"
    QSPK_LENGTH   = 609     length of NTRU_EESS439EP1 public key
    QSC_LENGTH    = 604     length of NTRU_EESS439EP1 cipher

    NTRUEncrypt can be adopted in our framework without further modification.

3. Security Concerns

  The proof of security can be found at https://eprint.iacr.org/2015/287
  We highlight some desired features.

  3.1 One-way Authentication
    The one-way authentication feature is inherent from the ntor protocol.

  3.2 Multiple Encryption
    The technique to combine two encryption schemes used in 2.2.4 is named
    Multiple Encryption. Discussion of appropriate security models can be
    found in [DK05]. Proof that the proposed handshake is secure under this
    model can be found at https://eprint.iacr.org/2015/287.

  3.3 Cryptographic hash function
    The default hash function HMAC_SHA256 from Tor suffice all requirements of
    our proposal.

  3.4 Key Encapsulation Mechanism
    The KEM in our protocol can be proved to be KEM-CCA-2 secure.

  3.5 Forward Secrecy
    The forward secrecy is achieved.

  Note that although this protocol meets the indicated goals, it is secure
  only until a quantum computer is developed that is capable of breaking the
  onion keys in real time. Such a computer can compromise the authentication
  of ntor online; the security of this approach depends on the authentication
  being secure at the time the handshake is executed. This approach is
  intended to provide security against the harvest-then-decrypt attack while
  an acceptable quantum-safe approach with security against an active
  attacker is developed.

4. Bibliography

[DK05] Y. Dodis, J. Katz, "Chosen-Ciphertext Security of Mulitple Encryption",
    Theory of Cryptography Conference, 2005.
    (conference version) or http://cs.nyu.edu/~dodis/ps/2enc.pdf (preprint)

More information about the tor-dev mailing list