Add proposal 263 (ntru)

1 files changed, 300 insertions, 0 deletions

diff --git a/proposals/263-ntru-for-pq-handshake.txt b/proposals/263-ntru-for-pq-handshake.txt
new file mode 100644
index 0000000..0216658
--- /dev/null
+++ b/proposals/263-ntru-for-pq-handshake.txt
@@ -0,0 +1,300 @@
+Filename: 263-ntru-for-pq-handshake.txt
+Title: Request to change key exchange protocol for handshake
+Author: John SCHANCK, William WHYTE and Zhenfei ZHANG
+Created: 29 Aug 2015
+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+sha256 handshake
+                            and a quantum-safe key encapsulation mechanism
+
+  where
+    0X0101  ntor+qsh    --  refers this modular design, no specific KEM is
+                            assigned.
+
+    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
+
+	DEPENDENCY:
+	  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 future.
+
+  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 algorithm.
+
+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
+    approach.
+
+    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"
+
+      curve25519
+        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.
+    http://link.springer.com/chapter/10.1007%2F978-3-540-30576-7_11
+    (conference version) or http://cs.nyu.edu/~dodis/ps/2enc.pdf (preprint)
+