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