[tor-dev] Propsal 263 Quantum-safe Hybrid handshake for Tor, updated feature request
Zhenfei Zhang
zzhang at securityinnovation.com
Mon Jan 11 14:16:01 UTC 2016
Hi list,
Thanks for all your valuable comments.
We have updated the feature request following your comments.
Please see the attachment for the updated feature request, and see
https://github.com/zhenfeizhang/ntru-tor/commit/0354fe1d61b2b79615301ff387e8c03230235f12
for the modification over last version.
Thanks for your time, and please let us know if you have any further
comments/suggestions.
Cheers,
Zhenfei
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.torproject.org/pipermail/tor-dev/attachments/20160111/73d18a72/attachment.html>
-------------- next part --------------
Title: Request to change key exchange protocol for handshake v1.1
Author: John SCHANCK, William WHYTE and Zhenfei ZHANG
Created: 9 Jan 2016
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
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 ntrueess443ep1
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-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 decrypt
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 long-term
key is compromised via quantum algorithm, the attacker still need 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
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-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 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.
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##
Note: a new hash function, SHA3 as in FIPS 202, will be used, rather than
SHA256 as in ntor.
2.2 The protocol
2.2.1 Initialization
H(x,t) as HMAC_SHA3 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 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 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();
a ephemeral "parallel" secret for encryption with QSE:
* 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_EESS443EP1. This has keys
and ciphertexts of length 610 bytes. This parameter set delivers 128 bits
classical security and quantum security. For 256 bits classcial and 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 ntrueess443ep1
PROTOID = "ntor-curve25519-sha3-1-ntrueess443ep1"
QSPK_LENGTH = 610 length of NTRU_EESS439EP1 public key
QSC_LENGTH = 610 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. This is suffice to provide
desired security for the present day. However, to be more future proof, we
propose to use HMAC_SHA3 when Tor starts to migrant 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
The 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
We do not propose any quantum-safe encryption algorithms in this proposal.
This documents focus on the hybrid design. The implementer should modularize
the protocol with appropriate interfaces that allows any quantum-safe
encryption algorithms to be used in this setting.
Candidate quantum-safe encryption algorithms will be included in another
proposal. This document will refer to the proposal when both proposals are
mature.
5. 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)
More information about the tor-dev
mailing list