December 2015 - tor-commits - lists.torproject.org

[tor/master] When allocating a crypto_digest_t, allocate no more bytes than needed
by nickm＠torproject.org 29 Dec '15

29 Dec '15

commit 488cdee5e7e9b23cf7bfee78e47e070489c6ca20 Author: Nick Mathewson <nickm(a)torproject.org> Date: Sun Dec 20 15:15:11 2015 -0500 When allocating a crypto_digest_t, allocate no more bytes than needed Previously we would allocate as many bytes as we'd need for a keccak--even when we were only calculating SHA1. Closes ticket 17796. --- changes/feature17796 | 6 +++++ src/common/crypto.c | 72 ++++++++++++++++++++++++++++++++++++-------------- 2 files changed, 58 insertions(+), 20 deletions(-) diff --git a/changes/feature17796 b/changes/feature17796 new file mode 100644 index 0000000..d96daed --- /dev/null +++ b/changes/feature17796 @@ -0,0 +1,6 @@ + o Minor features (crypto): + - When allocating a digest state object, allocate no more space than we + actually need. Previously, we were allocating as much space as the + state for the largest algorithm would need. This change saves up to + 672 bytes per circuit. Closes ticket 17796. + diff --git a/src/common/crypto.c b/src/common/crypto.c index a11ca79..265d065 100644 --- a/src/common/crypto.c +++ b/src/common/crypto.c @@ -1736,23 +1736,57 @@ crypto_digest_algorithm_get_length(digest_algorithm_t alg) /** Intermediate information about the digest of a stream of data. */ struct crypto_digest_t { + digest_algorithm_t algorithm; /**< Which algorithm is in use? */ + /** State for the digest we're using. Only one member of the + * union is usable, depending on the value of algorithm. Note also + * that space for other members might not even be allocated! + */ union { SHA_CTX sha1; /**< state for SHA1 */ SHA256_CTX sha2; /**< state for SHA256 */ SHA512_CTX sha512; /**< state for SHA512 */ keccak_state sha3; /**< state for SHA3-[256,512] */ - } d; /**< State for the digest we're using. Only one member of the - * union is usable, depending on the value of algorithm. */ - digest_algorithm_bitfield_t algorithm : 8; /**< Which algorithm is in use? */ + } d; }; +/** + * Return the number of bytes we need to malloc in order to get a + * crypto_digest_t for alg, or the number of bytes we need to wipe + * when we free one. + */ +static size_t +crypto_digest_alloc_bytes(digest_algorithm_t alg) +{ + /* Helper: returns the number of bytes in the 'f' field of 'st' */ +#define STRUCT_FIELD_SIZE(st, f) (sizeof( ((st*)0)->f )) + /* Gives the length of crypto_digest_t through the end of the field 'd' */ +#define END_OF_FIELD(f) (STRUCT_OFFSET(crypto_digest_t, f) + \ + STRUCT_FIELD_SIZE(crypto_digest_t, f)) + switch (alg) { + case DIGEST_SHA1: + return END_OF_FIELD(d.sha1); + case DIGEST_SHA256: + return END_OF_FIELD(d.sha2); + case DIGEST_SHA512: + return END_OF_FIELD(d.sha512); + case DIGEST_SHA3_256: + case DIGEST_SHA3_512: + return END_OF_FIELD(d.sha3); + default: + tor_assert(0); + return 0; + } +#undef END_OF_FIELD +#undef STRUCT_FIELD_SIZE +} + /** Allocate and return a new digest object to compute SHA1 digests. */ crypto_digest_t * crypto_digest_new(void) { crypto_digest_t *r; - r = tor_malloc(sizeof(crypto_digest_t)); + r = tor_malloc(crypto_digest_alloc_bytes(DIGEST_SHA1)); SHA1_Init(&r->d.sha1); r->algorithm = DIGEST_SHA1; return r; @@ -1765,7 +1799,7 @@ crypto_digest256_new(digest_algorithm_t algorithm) { crypto_digest_t *r; tor_assert(algorithm == DIGEST_SHA256 || algorithm == DIGEST_SHA3_256); - r = tor_malloc(sizeof(crypto_digest_t)); + r = tor_malloc(crypto_digest_alloc_bytes(algorithm)); if (algorithm == DIGEST_SHA256) SHA256_Init(&r->d.sha2); else @@ -1781,7 +1815,7 @@ crypto_digest512_new(digest_algorithm_t algorithm) { crypto_digest_t *r; tor_assert(algorithm == DIGEST_SHA512 || algorithm == DIGEST_SHA3_512); - r = tor_malloc(sizeof(crypto_digest_t)); + r = tor_malloc(crypto_digest_alloc_bytes(algorithm)); if (algorithm == DIGEST_SHA512) SHA512_Init(&r->d.sha512); else @@ -1797,7 +1831,8 @@ crypto_digest_free(crypto_digest_t *digest) { if (!digest) return; - memwipe(digest, 0, sizeof(crypto_digest_t)); + size_t bytes = crypto_digest_alloc_bytes(digest->algorithm); + memwipe(digest, 0, bytes); tor_free(digest); } @@ -1856,8 +1891,9 @@ crypto_digest_get_digest(crypto_digest_t *digest, return; } + const size_t alloc_bytes = crypto_digest_alloc_bytes(digest->algorithm); /* memcpy into a temporary ctx, since SHA*_Final clears the context */ - memcpy(&tmpenv, digest, sizeof(crypto_digest_t)); + memcpy(&tmpenv, digest, alloc_bytes); switch (digest->algorithm) { case DIGEST_SHA1: SHA1_Final(r, &tmpenv.d.sha1); @@ -1873,12 +1909,7 @@ crypto_digest_get_digest(crypto_digest_t *digest, log_warn(LD_BUG, "Handling unexpected algorithm %d", digest->algorithm); tor_assert(0); /* This is fatal, because it should never happen. */ default: - log_warn(LD_BUG, "Called with unknown algorithm %d", digest->algorithm); - /* If fragile_assert is not enabled, then we should at least not - * leak anything. */ - memwipe(r, 0xff, sizeof(r)); - memwipe(&tmpenv, 0, sizeof(crypto_digest_t)); - tor_fragile_assert(); + tor_assert(0); /* Unreachable. */ break; } memcpy(out, r, out_len); @@ -1891,15 +1922,14 @@ crypto_digest_get_digest(crypto_digest_t *digest, crypto_digest_t * crypto_digest_dup(const crypto_digest_t *digest) { - crypto_digest_t *r; tor_assert(digest); - r = tor_malloc(sizeof(crypto_digest_t)); - memcpy(r,digest,sizeof(crypto_digest_t)); - return r; + const size_t alloc_bytes = crypto_digest_alloc_bytes(digest->algorithm); + return tor_memdup(digest, alloc_bytes); } /** Replace the state of the digest object into with the state - * of the digest object from. + * of the digest object from. Requires that 'into' and 'from' + * have the same digest type. */ void crypto_digest_assign(crypto_digest_t *into, @@ -1907,7 +1937,9 @@ crypto_digest_assign(crypto_digest_t *into, { tor_assert(into); tor_assert(from); - memcpy(into,from,sizeof(crypto_digest_t)); + tor_assert(into->algorithm == from->algorithm); + const size_t alloc_bytes = crypto_digest_alloc_bytes(from->algorithm); + memcpy(into,from,alloc_bytes); } /** Given a list of strings in lst, set the len_out-byte digest

1 0

[tor/master] Remove the (now-unused) digest_algorithm_bitfield_t
by nickm＠torproject.org 29 Dec '15

29 Dec '15

commit a12c5f462f99e7e8f0dcd4b91baac1d35b2ff88a Author: Nick Mathewson <nickm(a)torproject.org> Date: Sun Dec 20 15:18:22 2015 -0500 Remove the (now-unused) digest_algorithm_bitfield_t --- src/common/crypto.h | 1 - 1 file changed, 1 deletion(-) diff --git a/src/common/crypto.h b/src/common/crypto.h index cf7b9ee..d0bbf7b 100644 --- a/src/common/crypto.h +++ b/src/common/crypto.h @@ -100,7 +100,6 @@ typedef enum { DIGEST_SHA3_512 = 4, } digest_algorithm_t; #define N_DIGEST_ALGORITHMS (DIGEST_SHA3_512+1) -#define digest_algorithm_bitfield_t ENUM_BF(digest_algorithm_t) /** A set of all the digests we know how to compute, taken on a single * string. Any digests that are shorter than 512 bits are right-padded

1 0

[tor/master] Merge branch 'feature17796_squashed'
by nickm＠torproject.org 29 Dec '15

29 Dec '15

commit 603110aa1db69ef0506ee94c3be80c59a664ee03 Merge: bc2cd0f a12c5f4 Author: Nick Mathewson <nickm(a)torproject.org> Date: Tue Dec 29 09:48:39 2015 -0500 Merge branch 'feature17796_squashed' changes/feature17796 | 6 +++++ src/common/crypto.c | 72 ++++++++++++++++++++++++++++++++++++-------------- src/common/crypto.h | 1 - 3 files changed, 58 insertions(+), 21 deletions(-)

1 0

[tor/master] Use timingsafe_memcmp() where available.
by nickm＠torproject.org 29 Dec '15

29 Dec '15

commit bc2cd0ff2bfc70916efe6b6a7fe0a4aae481df3b Author: Nick Mathewson <nickm(a)torproject.org> Date: Tue Dec 29 09:43:01 2015 -0500 Use timingsafe_memcmp() where available. See ticket 17944; patch from "logan". --- changes/17944 | 3 +++ configure.ac | 1 + src/common/di_ops.c | 4 ++++ 3 files changed, 8 insertions(+) diff --git a/changes/17944 b/changes/17944 new file mode 100644 index 0000000..b279506 --- /dev/null +++ b/changes/17944 @@ -0,0 +1,3 @@ + o Minor features (portability): + - Use timingsafe_memcmp() where available. Closes ticket 17944; + patch from "logan". diff --git a/configure.ac b/configure.ac index ad86f76..a47cee6 100644 --- a/configure.ac +++ b/configure.ac @@ -381,6 +381,7 @@ AC_CHECK_FUNCS( backtrace_symbols_fd \ clock_gettime \ eventfd \ + timingsafe_memcmp \ flock \ ftime \ getaddrinfo \ diff --git a/src/common/di_ops.c b/src/common/di_ops.c index c9d1350..70f2da7 100644 --- a/src/common/di_ops.c +++ b/src/common/di_ops.c @@ -25,6 +25,9 @@ int tor_memcmp(const void *a, const void *b, size_t len) { +#ifdef HAVE_TIMINGSAFE_MEMCMP + return timingsafe_memcmp(a, b, len); +#else const uint8_t *x = a; const uint8_t *y = b; size_t i = len; @@ -83,6 +86,7 @@ tor_memcmp(const void *a, const void *b, size_t len) } return retval; +#endif /* timingsafe_memcmp */ } /**

1 0

[webwml/master] Do we actually need these empty files?
by mikeperry＠torproject.org 29 Dec '15

29 Dec '15

commit 34df5fc9c92821b77ba8421e7fc375be60b44bea Author: Mike Perry <mikeperry-git(a)torproject.org> Date: Tue Dec 29 03:34:27 2015 -0800 Do we actually need these empty files? --- 0 files changed diff --git a/donate/en/donate-chaos.wml b/donate/en/donate-chaos.wml new file mode 100644 index 0000000..e69de29

1 0

[webwml/master] CCC Donations link.
by mikeperry＠torproject.org 29 Dec '15

29 Dec '15

commit ff3ad8e4e6096b51c5ec8c38e8c765e07b98f7aa Author: Mike Perry <mikeperry-git(a)torproject.org> Date: Tue Dec 29 03:30:50 2015 -0800 CCC Donations link. --- .htaccess | 1 + 1 file changed, 1 insertion(+) diff --git a/.htaccess b/.htaccess index 930e802..fb59b90 100644 --- a/.htaccess +++ b/.htaccess @@ -67,6 +67,7 @@ RewriteRule ^donate/donate-hpbanner(.*) /donate/donate$1 [R=302,L] RewriteRule ^donate/donate-blog-benw(.*) /donate/donate$1 [R=302,L] RewriteRule ^donate/donate-blog-ellsberg(.*) /donate/donate$1 [R=302,L] RewriteRule ^donate/donate-blog-alison(.*) /donate/donate$1 [R=302,L] +RewriteRule ^donate/donate-chaos(.*) /donate/donate$1 [R=302,L] #keep prefixes of other entries down here... RewriteRule ^donate/donate-hp(.*) /donate/donate$1 [R=302,L]

1 0

[torspec/master] Add proposal 263 (ntru)
by nickm＠torproject.org 29 Dec '15

29 Dec '15

commit 5be420b2ece73fced5ed70d1fabcb81af7bd6ef0 Author: Nick Mathewson <nickm(a)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) +

1 0

[torspec/master] Add proposal 261 and 262, for AEZ and rekeying
by nickm＠torproject.org 29 Dec '15

29 Dec '15

commit bd6da728510d4fe3bf79d59905a599661c5d7e1f Author: Nick Mathewson <nickm(a)torproject.org> Date: Mon Dec 28 17:37:18 2015 -0500 Add proposal 261 and 262, for AEZ and rekeying --- proposals/000-index.txt | 4 + proposals/261-aez-crypto.txt | 282 ++++++++++++++++++++++++++++++++++++++ proposals/262-rekey-circuits.txt | 130 ++++++++++++++++++ 3 files changed, 416 insertions(+) diff --git a/proposals/000-index.txt b/proposals/000-index.txt index 8dcbe26..e098c72 100644 --- a/proposals/000-index.txt +++ b/proposals/000-index.txt @@ -181,6 +181,8 @@ Proposals by number: 258 Denial-of-service resistance for directory authorities [OPEN] 259 New Guard Selection Behaviour [DRAFT] 260 Rendezvous Single Onion Services [DRAFT] +261 AEZ for relay cryptography [OPEN] +262 Re-keying live circuits with new cryptographic material [OPEN] Proposals by status: @@ -234,6 +236,8 @@ Proposals by status: 246 Merging Hidden Service Directories and Introduction Points 256 Key revocation for relays and authorities 258 Denial-of-service resistance for directory authorities + 261 AEZ for relay cryptography + 262 Re-keying live circuits with new cryptographic material ACCEPTED: 140 Provide diffs between consensuses 172 GETINFO controller option for circuit information diff --git a/proposals/261-aez-crypto.txt b/proposals/261-aez-crypto.txt new file mode 100644 index 0000000..14435e7 --- /dev/null +++ b/proposals/261-aez-crypto.txt @@ -0,0 +1,282 @@ +Filename: 261-aez-crypto.txt +Title: AEZ for relay cryptography +Author: Nick Mathewson +Created: 28 Oct 2015 +Status: Open + +0. History + + I wrote the first draft of this around October. This draft takes a + more concrete approach to the open questions from last time around. + +1. Summary and preliminaries + + This proposal describes an improved algorithm for circuit + encryption, based on the wide-block SPRP AEZ. I also describe the + attendant bookkeeping, including CREATE cells, and several + variants of the proposal. + + For more information about AEZ, see + http://web.cs.ucdavis.edu/~rogaway/aez/ + + For motivations, see proposal 202. + +2. Specifications + +2.1. New CREATE cell types. + + We add a new CREATE cell type that behaves as an ntor cell but which + specifies that the circuit will be created to use this mode of + encryption. + + [TODO: Can/should we make this unobservable?] + + The ntor handshake is performed as usual, but a different PROTOID is + used: + "ntor-curve25519-sha256-aez-1" + + To derive keys under this handshake, we use SHAKE256 to derive the + following output: + + struct shake_output { + u8 aez_key[48]; + u8 chain_key[32]; + u8 chain_val_forward[16]; + u8 chain_val_backward[16]; + }; + + The first two two fields are constant for the lifetime of the + circuit. + +2.2. New relay cell payload + + We specify the following relay cell payload format, to be used when + the exit node circuit hop was created with the CREATE format in 2.1 + above: + + struct relay_cell_payload { + u32 zero_1; + u16 zero_2; + u16 stream_id; + u16 length IN [0..498]; + u8 command; + u8 data[498]; // payload_len - 11 + }; + + Note that the payload length is unchanged. The fields are now + rearranged to be aligned. The 'recognized' and 'length' fields are + replaced with zero_1, zero_2, and the high 7 bits of length, for a + minimum of 55 bits of unambigious verification. (Additional + verification can be done by checking the other fields for + correctness; AEZ users can exploit plaintext redundancy for + additional cryptographic checking.) + + When encrypting a cell for a hop that was created using one of these + circuits, clients and relays encrypt them using the AEZ algorithm + with the following parameters: + + Let Chain denote chain_val_forward if this is a forward cell + or chain_val_backward otherwise. + + tau = 0 + + # We set tau=0 because want no per-hop ciphertext expansion. Instead + # we use redundancy in the plaintext to authenticate the data. + + Nonce = + struct { + u64 cell_number; + u8 is_forward; + u8 is_early; + } + + # The cell number is the number of relay cells that have + # traveled in this direction on this circuit before this cell. + # ie, it's zero for the first cell, two for the second, etc. + # + # is_forward is 1 for outbound cells, 0 for inbound cells. + # is_early is 1 for cells packaged as RELAY_EARLY, 0 for + # cells packaged as RELAY. + # + # Technically these two values would be more at home in AD + # than in Nonce; but AEZ doesn't actually distinguish N and AD + # internally. + + Define CELL_CHAIN_BYTES = 32 + + AD = [ XOR(prev_plaintext[:CELL_CHAIN_BYTES], + prev_ciphertext[:CELL_CHAIN_BYTES]), + Chain ] + + # Using the previous cell's plaintext/ciphertext as additional data + # guarantees that any corrupt ciphertext received will corrupt the + # plaintext, which will corrupt all future plaintexts. + + Set Chain = AES(chain_key, Chain) xor Chain. + + # This 'chain' construction is meant to provide forward + # secrecy. Each chain value is replaced after each cell with a + # (hopefully!) hard-to-reverse construction. + + This instantiates a wide-block cipher, tweaked based on the cell + index and direction. It authenticates part of the previous cell's + plaintext, thereby ensuring that if the previous cell was corrupted, + this cell will be unrecoverable. + +3. Design considerations + +3.1. Wide-block pros and cons? + + See proposal 202, section 4. + +3.2. Given wide-block, why AEZ? + + It's a reasonably fast probably secure wide-block cipher. In + particular, it's performance-competitive with AES_CTR, and far better + than what we're doing now. See performance appendix. + + It seems secure-ish too. Several cryptographers I know seem to + think it's likely secure enough, and almost surely at least as + good as AES. + + [There are many other competing wide-block SPRP constructions if + you like. Many require blocks be an integer number of blocks, or + aren't tweakable. Some are slow. Do you know a good one?] + +3.3. Why _not_ AEZ? + + There are also some reasons to consider avoiding AEZ, even if we do + decide to use a wide-block cipher. + + FIRST it is complicated to implement. As the specification says, + "The easiness claim for AEZ is with respect to ease and versatility + of use, not implementation." + + SECOND, it's still more complicated to implement well (fast, + side-channel-free) on systems without AES acceleration. We'll need + to pull the round functions out of fast assembly AES, which is + everybody's favorite hobby. + + THIRD, it's really horrible to try to do it in hardware. + + FOURTH, it is comparatively new. Although several cryptographers + like it, and it is closely related to a system with a security proof, + you never know. + + FIFTH, something better may come along. + + +4. Alternative designs + +4.1. Two keys. + + We could have a separate AEZ key for forward and backward encryption. + This would use more space, however. + +4.2. Authenticating things differently + + In computing the AD, we could replace xor with concat. + + In computing the AD, we could replace CELL_CHAIN_BYTES with 16, or + 509. + + (Another thing we might dislike about the current proposal is + that it appears to requires us to remember 32 bytes of plaintext + until we get another cell. But that part is fixable: note that + in the structure of AEZ, the AD is processed in the AEZ-hash() + function, and then no longer used. We can compute the AEZ-hash() + to be used for the next cell after each cell is en/de crypted.) + +4.3. Other hashes. + + We could update the ntor definition used in this to use a better hash + than SHA256 inside. + +4.4. Less predictable plaintext. + + A positively silly option would be to reserve the last X bytes of + each relay cell's plaintext for random bytes, if they are not used + for payload. This might help a little, in a really doofy way. + + +A.1. Performance notes: memory requirements + + Let's ignore Tor overhead here, but not openssl overhead. + + IN THE CURRENT PROTOCOL, the total memory required at each relay is: 2 + sha1 states, 2 aes states. + + Each sha1 state uses 96 bytes. Each aes state uses 244 bytes. (Plus + 32 bytes counter-mode overhead.) This works out to 704 bytes at each + hop. + + IN THE PROTOCOL ABOVE, using an optimized AEZ implementation, we'll + need 128 bytes for the expanded AEZ key schedule. We'll need another + 244 bytes for the AES key schedule for the chain key. And there's 32 + bytes of chaining values. This gives us 404 bytes at each hop, for a + savings of 42%. + + If we used separate AES and AEZ keys in each direction, we would be + looking at 776 bytes, for a space increase of 10%. + +A.2. Performance notes: CPU requirements on AESNI hosts + + The cell_ops benchmark in bench.c purports to tell us how long it + takes to encrypt a tor cell. But it wasn't really telling the truth, + since it only did one SHA1 operation every 2^16 cells, when + entries and exits really do one SHA1 operation every end-to-end cell. + + I expanded it to consider the slow (SHA1) case as well. I ran this on + my friendly OSX laptop (2.9 GHz Intel Core i5) with AESNI support: + + Inbound cells: 169.72 ns per cell. + Outbound cells: 175.74 ns per cell. + Inbound cells, slow case: 934.42 ns per cell. + Outbound cells, slow case: 928.23 ns per cell. + + + Note that So for an n-hop circuit, each cell does the slow case and + (n-1) fast cases at the entry; the slow case at the exit, and the fast + case at each middle relay. + + So for 3 hop circuits, the total current load on the network is + roughly 425 ns per hop, concentrated at the exit. + + Then I started messing around with AEZ benchmarks, using the + aesni-optimized version of AEZ on the AEZ website. (Further + optimizations are probably possible.) For the AES256, I + used the usual aesni-based aes construction. + + Assuming xor is free in comparison to other operations, and + CELL_CHAIN_BYTES=32, I get roughly 270 ns per cell for the entire + operation. + + If we were to pick CELL_CHAIN_BYTES=509, we'd be looking at around 303 + ns per cell. + + If we were to pick CELL_CHAIN_BYTES=509 and replace XOR with CONCAT, + it would be around 355 ns per cell. + + If we were to keep CELL_CHAIN_BYTES=32, and remove the + AES256-chaining, I see values around 260 ns per cell. + + (This is all very spotty measurements, with some xors left off, and + not much effort done at optimization beyond what the default + optimized AEZ does today.) + +A.3. Performance notes: what if we don't have AESNI? + + Here I'll test on a host with sse2 and ssse3, but no aesni instructions. + From Tor's benchmarks I see: + + Inbound cells: 1218.96 ns per cell. + Outbound cells: 1230.12 ns per cell. + Inbound cells, slow case: 2099.97 ns per cell. + Outbound cells, slow case: 2107.45 ns per cell. + + For a 3-hop circuit, that gives on average 1520 ns per cell. + + [XXXX Do a real benchmark with a fast AEZ backend. First, write one. + Preliminary results are a bit disappointing, though, so I'll + need to invetigate alternatives as well.] + diff --git a/proposals/262-rekey-circuits.txt b/proposals/262-rekey-circuits.txt new file mode 100644 index 0000000..ca8ad01 --- /dev/null +++ b/proposals/262-rekey-circuits.txt @@ -0,0 +1,130 @@ +Filename: 262-rekey-circuits.txt +Title: Re-keying live circuits with new cryptographic material +Author: Nick Mathewson +Created: 28 Dec 2015 +Status: Open + +1. Summary and Motivation + + Cryptographic primitives have an upper limit of how much data should + be encrypted with the same key. But currently Tor circuits have no + upper limit of how much data they will deliver. + + While the upper limits of our AES-CTR crypto is ridiculously high + (on the order of hundreds of exabytes), the AEZ crypto we're + considering suggests we should rekey after the equivalent in cells + after around 280 TB. 280 TB is still high, but not ridiculously + high. + + So in this proposal I explain a general mechanism for rekeying a + circuit. We shouldn't actually build this unless we settle on + +2. RELAY_REKEY cell operation + + To rekey, the circuit initiator ("client") can send a new RELAY_REKEY cell + type: + + struct relay_rekey { + u16 rekey_method IN [0, 1]; + u8 rekey_data[]; + } + + const REKEY_METHOD_ACK = 0; + const REKEY_METHOD_SHAKE128_CLIENT = 1; + + This cell means "I am changing the key." The new key material will be + derived from SHAKE128 of the aez_key concatenated with the rekey_data + field, to fill a new shake_output structure. The client should set + rekey_data at random. + + After sending one of these RELAY_REKEY cells, the client uses the new + aez_key to encrypt all of its data to this hop, but retains the old + aez_key for decrypting the data coming back from the relay. + + When the relay receives a RELAY_REKEY cell, it sends a RELAY_REKEY + cell back towards the client, with empty rekey_data, and + relay_method==0, and then updates its own key material for all + additional data it sends and receives to the client. + + When the client receives this reply, it can discard the old AEZ key, and + begin decrypting subsequent inbound cells with the new key. + + + So in summary: the client sends a series of cells encrypted with the + old key, and then sends a REKEY cell, followed by relay cells + encrypted with the new key: + + OldKey[data data data ... data rekey] NewKey[data data data...] + + And after the server receives the REKEY cell, it stops sending relay + cells encrypted with the old keys, sends its own REKEY cell with the + ACK method, and starts sending cells encrypted with the new key. + + REKEY arrives somewhere in here + I + V + OldKey[data data data data rekey-ack] NewKey[data data data ...] + +2.1. Supporting other cryptography types + + Each relay cipher must specify its own behavior in the presence of a + REKEY cell of each type that it supports. In general, the behavior + of method 1 ("shake128-client") is "regenerate keys as if we were + calling the original KDF after a CREATE handshake, using SHAKE128 on + our current static key material and on a 32-byte random input." + + The behavior of any unsupported REKEY method must be to close the + circuit with an error. + + The AES-CTR relay cell crypto doesn't support rekeying. See 3.2 below + if you disagree. + +2.2. How often to re-key? + + Clients should follow a deterministic algorithm in deciding when to + re-key, so as not to leak client differences. This algorithm should + be type-specific. For AEZ, I recommend that clients conservatively + rekey every 2**32 cells (about 2 TB). And to make sure that this + code actually works, the schedule should be after 2**15 cells, and + then every 2**32 cells thereafter. + + It may be beneficial to randomize these numbers. If so, let's try + subtracting between 0 and 25% at random. + +2.3. How often to allow re-keying? + + We could define a lower bound to prevent too-frequent rekeying. I'm + not sure I see the point here; the process described above is not + that costly. + +3. Alternative designs + +3.1. Should we add some public key cryptography here? + + We could change the body of a REKEY cell and its ack to be more like + CREATE/CREATED. Then we'd have to add a third step from the client + to the server to acknowledge receipt of the 'CREATED' cell and + changing of the key. + + So, what would this added complexity and computational load buy us? + It would defend against the case where an adversary had compromised + the shared key material for a circuit, but was not able to compromise + the rekey process. I'm not sure that this is reasonable; the + likeliest cases I can think of here seem to be "get compromised, stay + compromised" for a circuit. + +3.2. Hey, could we use this for forward secrecy with AES-CTR? + + We could, but the best solution to AES-CTR's limitations right now is + to stop using our AES-CTR setup. Anything that supports REKEY will + also presumably support AEZ or something better. + +3.3. We could upgrade ciphers with this! + + Yes we could. We could define this not only to change the key, but + to upgrade to a better ciphersuite. For example, we could start by + negotiating AES-CTR, and then "secretly" upgrade to AEZ. I'm not + sure that's worth the complexity, or that it would really be secret + in the presence of traffic analysis. + +

1 0

[webwml/master] landing page for alison
by nickm＠torproject.org 28 Dec '15

28 Dec '15

commit aad289abd330e4d24367a81b4b8b5be0bb5700b0 Author: Nick Mathewson <nickm(a)torproject.org> Date: Mon Dec 28 13:00:14 2015 -0500 landing page for alison --- .htaccess | 1 + 1 file changed, 1 insertion(+) diff --git a/.htaccess b/.htaccess index 135805b..930e802 100644 --- a/.htaccess +++ b/.htaccess @@ -66,6 +66,7 @@ RewriteRule ^donate/donate-blog-cory(.*) /donate/donate$1 [R=302,L] RewriteRule ^donate/donate-hpbanner(.*) /donate/donate$1 [R=302,L] RewriteRule ^donate/donate-blog-benw(.*) /donate/donate$1 [R=302,L] RewriteRule ^donate/donate-blog-ellsberg(.*) /donate/donate$1 [R=302,L] +RewriteRule ^donate/donate-blog-alison(.*) /donate/donate$1 [R=302,L] #keep prefixes of other entries down here... RewriteRule ^donate/donate-hp(.*) /donate/donate$1 [R=302,L] diff --git a/donate/en/donate-blog-alison.wml b/donate/en/donate-blog-alison.wml new file mode 100644 index 0000000..e69de29

1 0

[webwml/master] that was silly
by sebastian＠torproject.org 28 Dec '15

28 Dec '15

commit f28a4d059d9c365cf1b57ce5130c8ed157eb6707 Author: Sebastian Hahn <sebastian(a)torproject.org> Date: Mon Dec 28 10:22:29 2015 +0100 that was silly --- about/en/contact.wml | 2 +- 1 file changed, 1 insertion(+), 1 deletion(-) diff --git a/about/en/contact.wml b/about/en/contact.wml index 13e7c83..7f0bfe7 100644 --- a/about/en/contact.wml +++ b/about/en/contact.wml @@ -53,7 +53,7 @@ docs/documentation>#MailingLists">mailing lists</a>, you must subscribe before you can post.</li> <li>donations(a)torproject.org is for questions and comments about <a - href="<page donate/donate-1>">getting money to the developers</a>. More + href="<page donate/donate>">getting money to the developers</a>. More donations means <a href="<page docs/faq>#Funding">more Tor</a>. We're happy to help think about creative ways for you to contribute.</li>

1 0