commit 5be420b2ece73fced5ed70d1fabcb81af7bd6ef0 Author: Nick Mathewson nickm@torproject.org Date: Mon Dec 28 17:40:48 2015 -0500

Add proposal 263 (ntru) --- proposals/000-index.txt | 2 + proposals/263-ntru-for-pq-handshake.txt | 300 +++++++++++++++++++++++++++++++ 2 files changed, 302 insertions(+)

diff --git a/proposals/000-index.txt b/proposals/000-index.txt index e098c72..8da27da 100644 --- a/proposals/000-index.txt +++ b/proposals/000-index.txt @@ -183,6 +183,7 @@ Proposals by number: 260 Rendezvous Single Onion Services [DRAFT] 261 AEZ for relay cryptography [OPEN] 262 Re-keying live circuits with new cryptographic material [OPEN] +263 Request to change key exchange protocol for handshake [OPEN]

Proposals by status: @@ -238,6 +239,7 @@ Proposals by status: 258 Denial-of-service resistance for directory authorities 261 AEZ for relay cryptography 262 Re-keying live circuits with new cryptographic material + 263 Request to change key exchange protocol for handshake ACCEPTED: 140 Provide diffs between consensuses 172 GETINFO controller option for circuit information 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) +