[tor-dev] Propsal 263 Quantum-safe Hybrid handshake for Tor, updated feature request v1.2

Zhenfei Zhang zzhang at securityinnovation.com
Mon Feb 8 15:56:08 UTC 2016

Hello list,

We had a very constructive discussion on this proposal last Thursday.
I have updated the feature request based on the feedback from the
We also like to thank Roger for grammar fixes on the proposal.

The diff file is available at:

Major tech updates are:
1. Use SHA3 and SHAKE instead of HMAC_SHA3

2. In previous proposal, when server sends back the message, it sends a
C = ENCRYPT( P | B, QSPK), and its one-time ECC public key Y = e^y;
where P is the secret that server chose, B is servers long term public key.

In this new version, we also include servers short term public key in the
plaintext, i.e.,
and Y is no longer send to the client separately. The client will need to
C first and retrieve Y from the message. Y is not revealed to any one other
than the

This is proposed by Nick. It was also suggested to us by Aniket Kate. We
thank Nick
and Aniket for the suggestion. This modification will save 32 bytes of
traffic as Y is no
longer transmitted. Also since Y is now encrypted it will be a little
harder for the attacker
to attack the 25519 keys.

3. Choosing algorithms and parameters for the protocol.
We have identified NTRUEncrypt and R-LWE as two candidates for this
We have agreed to use NTRUEncrypt for now, in the meantime, keep the option
for "newesthope" version of R-LWE type key exchange when it becomes
available. Also,
for NTRUEncrypt we will be using parameters sets with SHA3, to align with
Tor specs.
I have modified the feature request to reflect this change.

Also in the discussion we were talking about the possibility of using
non-product form
polynomial version of NTRUEncrypt, as this version will become patent free
by Aug 2017,
while the patent for product form will last for another 4 years. The main
concern is that
Debian will not allow patented software in the package.  However, through
our discussion,
it turns out that we may be able to include this proposal in the next one
of two release of
Tor. From this point of view, both patent (basic NTRU patent, till 2017 and
product form
patent, till 2021) are going to be an issue if Debian does not agree with
SI's patent statement.
So does it make sense to keep the product form polynomials as they enables
roughly 3
times faster operations on both client side and server side?

Thanks for your time, and please let us know if you have any further

Best regards,
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.torproject.org/pipermail/tor-dev/attachments/20160208/4a54fc5c/attachment-0001.html>
-------------- next part --------------
Filename: 263-ntru-for-pq-handshake.txt
Title: Request to change key exchange protocol for handshake v1.2
Author: John SCHANCK, William WHYTE and Zhenfei ZHANG
Created: 29 Aug 2015
Updated: 4 Feb 2016
Status: Open

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+sha3 handshake
                            and a quantum-safe key encapsulation mechanism

    0X0101  ntor+qsh    --  refers to this modular design; no specific Key
                            Encapsulation Mechanism (KEM) is assigned.

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

    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-safe forward-secure key agreement

    We are trying to add Quantum-safe forward-secrecy to the key agreement in
    tor handshake. (Classical) forward-secrecy means that if the long-term key
    is compromised, the communication prior to this compromise still stays
    secure. Similarly, Quantum-safe forward-secrecy implies if the long-term
    key is compromised due to attackers with quantum-computing capabilities, the
    prior communication still remains secure.

    Current approaches for handling key agreement, for instance the ntor
    handshake protocol, do not have this feature. ntor uses ECC, which will be
    broken when quantum computers become available. This allows the simple yet
    very effective harvest-then-decrypt attack, where an adversary with
    significant storage capabilities harvests Tor handshakes now and decrypts
    them in the future.

    The proposed handshake protocol achieves quantum-safe forward-secrecy and
    stops those attacks by introducing a secondary short-term pre-master secret
    that is transported via a quantum-safe method. In the case where the long-term
    key is compromised via quantum algorithm, the attacker still needs to recover
    the second pre-master secret to be able to decrypt the communication.

  1.2 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-safe forward-secrecy and modular design to the Tor
    handshake, 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 encryptions such as Ring
    Learning with Error (R-LWE) based schemes.

    2.1.1 Achieved Property:

      1)  The proposed key exchange method is quantum-safe forward-secure: 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)  The proposed key exchange method provides one-way authentication: The
      server is authenticated, while the client remains anonymous.

      3)  The protocol is at least as secure as ntor. In the case where the
      quantum-safe encryption algorithm fails, the protocol is indentical to 
      ntor protocol.

    2.1.2 General idea:

      When a client wishes to establish a one-way authenticated key K with a
      server, a session key is established through the following steps:
      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)  SHA3-256 hash function (see FIPS 202), and SHAKE256 KDF;
      ##previous approach: HMAC-based Extract-and-Expand KDF-RFC5869##

  2.2 The protocol

    2.2.1 Initialization

      H(x,t) as SHA3-256 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-sha3-1-[qseid]"
#pre  PROTOID       = "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         = H(*, t_mac);
      hash2         = H(*, t_key);
      hash3         = H(*, 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();

      and a QSE 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();

      and an ephemeral "parallel" secret for encryption with QSE:
*       PAR_SEC     P                       [H_LENGTH    bytes]

      and computes:
*       C           = ENCRYPT( P | B | Y, 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:
        AUTH            H(auth_input, t_mac)    [H_LENGTH     bytes]
*       QSCIPHER        C                       [QSPK_LENGTH  bytes]

      Note: in previous ntor protocol the server also needs to send
#pre    SERVER_PK       Y                       [G_LENGTH     bytes]
      This value is now encrypted in C, so the server does not need to send Y.
      The client decrypts C, 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.

  2.3 Instantiation with NTRUEncrypt

    The example uses the NTRU parameter set NTRU_EESS443EP2. This has keys
    and ciphertexts of length 610 bytes. This parameter set delivers 128 bits
    classical security and quantum security. This parameter set uses product
    form NTRU polynomials. For 256 bits classical and quantum security, use 

    We adjust the following parameters:

    handshake type:
    0X0102  ntor+ntru       the quantum safe KEM is based on NTRUEncrypt, with
                            parameter ntrueess443ep2
    PROTOID       = "ntor-curve25519-sha3-1-ntrueess443ep2"
    QSPK_LENGTH   = 610     length of NTRU_EESS443EP2 public key
    QSC_LENGTH    = 610     length of NTRU_EESS443EP2 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 suffices to provide
    desired security for the present day. However, to be more future proof, we
    propose to use SHA3 when Tor starts to migrate to SHA3.

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

  3.5 Quantum-safe Forward Secrecy
    Quantum-safe forward secrecy is achieved.

  3.6 Quantum-safe authentication
    The proposed protocol 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. Candidate quantum-safe encryption algorithms

  Two candidate quantum-safe encryption algorithms are under consideration.
  NTRUEncrypt, with parameter set ntrueess443ep2 provides 128 bits classcial and
  quantum security. The parameter sets is available for use now. 

  LWE-based key exchange, based on Peikert's idea [Pei14]. Parameter sets 
  suitable for this framework (the newerhop vairant) is still under development. 

5. 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)
[Pei14] C. Peikert, "Lattice Cryptography for the Internet", PQCrypto 2014.   


More information about the tor-dev mailing list