- tor-commits - lists.torproject.org

[torspec/master] prop224: More improvements.
by asn＠torproject.org 12 May '16

12 May '16

commit 316481f4386428f61a436feefa3a4a11a46890bc Author: George Kadianakis <desnacked(a)riseup.net> Date: Tue May 10 14:15:36 2016 -0400 prop224: More improvements. - Specify credential/subcredential format. - Bump up revision-counter to 64-bits. - Specify descriptor encryption padding. --- proposals/224-rend-spec-ng.txt | 30 +++++++++++++++++------------- 1 file changed, 17 insertions(+), 13 deletions(-) diff --git a/proposals/224-rend-spec-ng.txt b/proposals/224-rend-spec-ng.txt index 365f4fd..260036b 100644 --- a/proposals/224-rend-spec-ng.txt +++ b/proposals/224-rend-spec-ng.txt @@ -626,9 +626,17 @@ Table of contents: leaving the hidden service's private key offline. The subcredential for a period is derived as: - H("subcredential" | - credential | - blinded-public-key). + + subcredential = H("subcredential" | credential | blinded-public-key). + + In the above formula, credential corresponds to: + + credential = H(public-identity-key | authorization-key) + + where public-identity-key is the public identity master key of the hidden + service, and authorization-key is an optional secret used for client + authorization. If no client authorization is specified, authorization-key is + left blank. 2.2. Locating, uploading, and downloading hidden service descriptors [HASHRING] @@ -949,7 +957,7 @@ Table of contents: descriptor even if the content of the descriptor hasn't changed. (So that we don't leak whether the intro point list etc. changed) - secret_input = blinded_public_key | subcredential | INT_4(revision_counter) + secret_input = blinded_public_key | subcredential | INT_8(revision_counter) keys = KDF(secret_input, salt, "hsdir-encrypted-data", S_KEY_LEN + S_IV_LEN + MAC_KEY_LEN) @@ -964,14 +972,10 @@ Table of contents: MAC MAC of both above fields [32 bytes] The encryption format is ENCRYPTED = - STREAM(SECRET_IV,SECRET_KEY) xor Plaintext + STREAM(SECRET_IV,SECRET_KEY) XOR Plaintext - Before encryption, the plaintext must be padded to a multiple of ??? - bytes with NUL bytes. The plaintext must not be longer than ??? - bytes. [TODO: how much? Should this be a parameter? What values in - practice are needed to hide how many intro points we have, and how - many might be legacy ones? Note that Single Onion Services add extend - intro points as well. ] + Before encryption, the plaintext must be padded to a multiple of 4096 bytes + with NUL bytes. The plaintext format is: @@ -1007,7 +1011,7 @@ Table of contents: [Exactly once per introduction point] - Base-64 encoded introduction point authentication key that was + Base64 encoded introduction point authentication key that was used to establish introduction point circuit, cross-certifying the blinded public key. This uses the certificate format of proposal 220 with type [09]. The signing-key extension is @@ -1460,7 +1464,7 @@ Table of contents: Hidden services may restrict access only to authorized users. One mechanism to do so is the credential mechanism, where only users who - know the credential for a hidden service may connect at all. For more + know the credentialo for a hidden service may connect at all. For more fine-grained conntrol, a hidden service can be configured with password-based or public-key-based authentication.

1 0

[torspec/master] prop224: Cross-certify all intro keys
by asn＠torproject.org 12 May '16

12 May '16

commit e896dcf2f1e2782c5ba7dc72bdccc39b7f519af1 Author: John Brooks <special(a)torproject.org> Date: Tue May 10 14:24:38 2016 -0400 prop224: Cross-certify all intro keys --- proposals/224-rend-spec-ng.txt | 65 ++++++++++++++++++++++++++---------------- 1 file changed, 40 insertions(+), 25 deletions(-) diff --git a/proposals/224-rend-spec-ng.txt b/proposals/224-rend-spec-ng.txt index 260036b..292ab3f 100644 --- a/proposals/224-rend-spec-ng.txt +++ b/proposals/224-rend-spec-ng.txt @@ -909,14 +909,15 @@ Table of contents: The version-number contains a positive integer indicating the version of the descriptor. Current version is "3". - "descriptor-signing-key-cert" SP certificate NL + "descriptor-signing-key-cert" NL certificate NL [Exactly once.] The 'certificate' field contains a certificate in the format from - proposal 220, with the short-term ed25519 descriptor-signing key - signed by the blinded public key. It must contain a - ed25519-signing-key extension containing the blinded public key. + proposal 220, wrapped with "-----BEGIN ED25519 CERT-----". The + certificate cross-certifies the short-term descriptor signing key with + the blinded public key. The certificate type must be [08], and the + blinded public key must be present as the signing-key extension. "revision-counter" SP Integer NL @@ -944,7 +945,7 @@ Table of contents: [exactly once, at end.] A signature of all previous fields, using the signing key in the - hs-descriptor line. We use a separate key for signing, so that + descriptor-signing-key-cert line. We use a separate key for signing, so that the hidden service host does not need to have its private blinded key online. @@ -1007,37 +1008,49 @@ Table of contents: The link-specifiers is a base64 encoding of a link specifier block in the format described in BUILDING-BLOCKS. - "auth-key" SP "ed25519" SP certificate NL + "auth-key" SP "ed25519" NL certificate NL [Exactly once per introduction point] - Base64 encoded introduction point authentication key that was - used to establish introduction point circuit, cross-certifying - the blinded public key. This uses the certificate format of - proposal 220 with type [09]. The signing-key extension is - mandatory here to tell you what the public key is. + The certificate is a proposal 220 certificate wrapped in + "-----BEGIN ED25519 CERT-----", cross-certifying the descriptor + signing key with the introduction point authentication key, which + is included in the mandatory signing-key extension. The certificate + type must be [09]. - "enc-key" SP "ntor" SP key NL + "enc-key" SP "ntor" SP enc-public-key NL - [At most once per introduction point] + [Exactly one enc-key per introduction point] - Base64-encoded curve25519 key used to encrypt request to - hidden service. - - [TODO: I'd like to have a cross-certification here too.] + The enc-public-key is a base64 encoded curve25519 public key used to + encrypt the introduction request to service. "enc-key" SP "legacy" NL key NL - [At most once per introduction point] + [Exactly one enc-key per introduction point] - Base64-encoded RSA key, wrapped in "----BEGIN RSA PUBLIC + Base64 encoded RSA key, wrapped in "----BEGIN RSA PUBLIC KEY-----" armor, for use with a legacy introduction point as described in [LEGACY_EST_INTRO] and [LEGACY-INTRODUCE1] below. - Exactly one of the "enc-key ntor" and "enc-key legacy" - elements must be present for each introduction point. + "enc-key-certification" NL certificate NL + + [Exactly once per introduction point] + + Cross-certification of the descriptor signing key by the enc-key. + The format of this certificate depends on the type of enc-key. + + For "ntor" keys, certificate is a proposal 220 certificate in + "-----BEGIN ED25519 CERT-----" armor, cross-certifying the descriptor + signing key with the ed25519 equivalent of the curve25519 public key + from "enc-key" derived using the process in proposal 228 appendix A. + The certificate type must be [10], and the signing-key extension is + mandatory. - [TODO: I'd like to have a cross-certification here too.] + For "legacy" keys, certificate is an RSA signature wrapped in + "-----BEGIN SIGNATURE-----" of the digest: + H("legacy introduction point encryption key" | ED25519_KEY) + ED25519_KEY is the 32 byte descriptor signing public key. To remain compatible with future revisions to the descriptor format, clients should ignore unrecognized lines in the descriptor. @@ -1799,10 +1812,12 @@ Appendix E. Reserved numbers We reserve these certificate type values for Ed25519 certificates: - [08] hidden service short-term ed25519 key, signed with blinded + [08] short-term descriptor signing key, signed with blinded public key. (Section 2.4) - [09] intro point authentication key, cross-certifying blinded - public key. (Section 2.5) + [09] intro point authentication key, cross-certifying the descriptor + signing key. (Section 2.5) + [10] ed25519 key derived from the curve25519 intro point encryption key, + cross-certifying the descriptor signing key. (Section 2.5) [XXXX list more]

1 0

[torspec/master] prop224: More trivial fixups.
by asn＠torproject.org 12 May '16

12 May '16

commit f9313163c3f85d7bbb92f90947dfe9021f637c89 Author: John Brooks <special(a)torproject.org> Date: Tue May 10 14:25:21 2016 -0400 prop224: More trivial fixups. - Sectioning fixes --- proposals/224-rend-spec-ng.txt | 12 ++++-------- 1 file changed, 4 insertions(+), 8 deletions(-) diff --git a/proposals/224-rend-spec-ng.txt b/proposals/224-rend-spec-ng.txt index 292ab3f..5db0ae3 100644 --- a/proposals/224-rend-spec-ng.txt +++ b/proposals/224-rend-spec-ng.txt @@ -1165,12 +1165,9 @@ Table of contents: earlier fields. Older versions of Tor always use a 1024-bit RSA key for these introduction - authentication keys. Newer hidden services MAY use RSA keys up 1904 - bits. Any more than that will not fit in a RELAY cell payload. + authentication keys. -[There is no 3.1.3?] - -3.1.4. Acknowledging establishment of introduction point [INTRO_ESTABLISHED] +3.1.3. Acknowledging establishment of introduction point [INTRO_ESTABLISHED] After setting up an introduction circuit, the introduction point reports its status back to the hidden service host with an INTRO_ESTABLISHED cell. @@ -1183,9 +1180,8 @@ Table of contents: EXT_FIELD_LEN [1 byte] EXT_FIELD [EXT_FIELD_LEN bytes] - [Worth mentioning that old-school Tor relays send back an empty - payload here? Or, even better, not mentioning it if we simplify - 3.1.2 to "don't do that". -RD] + Older versions of Tor send back an empty INTRO_ESTABLISHED cell instead. + Services must accept an empty INTRO_ESTABLISHED cell from a legacy relay. 3.2. Sending an INTRODUCE1 cell to the introduction point. [SEND_INTRO1]

1 0

[torspec/master] prop224: Some proposed fixes mostly discussed with asn
by asn＠torproject.org 12 May '16

12 May '16

commit d94b22560b19861b59570a12eff8e68f122ebf31 Author: David Goulet <dgoulet(a)ev0ke.net> Date: Thu May 12 14:17:44 2016 -0400 prop224: Some proposed fixes mostly discussed with asn Signed-off-by: David Goulet <dgoulet(a)ev0ke.net> --- proposals/224-rend-spec-ng.txt | 151 +++++++++++++++++++++-------------------- 1 file changed, 77 insertions(+), 74 deletions(-) diff --git a/proposals/224-rend-spec-ng.txt b/proposals/224-rend-spec-ng.txt index 5db0ae3..0a673a7 100644 --- a/proposals/224-rend-spec-ng.txt +++ b/proposals/224-rend-spec-ng.txt @@ -6,58 +6,58 @@ Status: Draft Table of contents: - 0. Hidden services: overview and preliminaries. - 0.1. Improvements over previous versions. - 0.2. Notation and vocabulary - 0.3. Cryptographic building blocks - 0.4. Protocol building blocks [BUILDING-BLOCKS] - 0.5. Assigned relay cell types - 0.5. Acknowledgments - 1. Protocol overview - 1.1. View from 10,000 feet - 1.2. In more detail: naming hidden services [NAMING] - 1.3. In more detail: Access control [IMD:AC] - 1.4. In more detail: Distributing hidden service descriptors. [IMD:DIST] - 1.5. In more detail: Scaling to multiple hosts - 1.6. In more detail: Backward compatibility with older hidden service - 1.7. In more detail: Keeping crypto keys offline - 1.8. In more detail: Encryption Keys And Replay Resistance - 1.9. In more detail: A menagerie of keys - 2. Generating and publishing hidden service descriptors [HSDIR] - 2.1. Deriving blinded keys and subcredentials [SUBCRED] - 2.2. Locating, uploading, and downloading hidden service descriptors - 2.2.1. Dividing time into periods [TIME-PERIODS] - 2.2.2. Overlapping time periods to avoid thundering herds [TIME-OVERLAP] - 2.2.3. Where to publish a service descriptor - 2.2.4. Using time periods and SRVs to fetch/upload HS descriptors - 2.2.5. URLs for anonymous uploading and downloading - 2.3. Publishing shared random values [PUB-SHAREDRANDOM] - 2.3.1. Client behavior in the absense of shared random values - 2.3.2. Hidden services and changing shared random values - 2.4. Hidden service descriptors: outer wrapper [DESC-OUTER] - 2.5. Hidden service descriptors: encryption format [ENCRYPTED-DATA] - 3. The introduction protocol - 3.1. Registering an introduction point [REG_INTRO_POINT] - 3.1.1. Extensible ESTABLISH_INTRO protocol. [EST_INTRO] - 3.1.2. Registering an introduction point on a legacy Tor node [LEGACY_EST_INTRO] - 3.1.3. Acknowledging establishment of introduction point [INTRO_ESTABLISHED] - 3.2. Sending an INTRODUCE1 cell to the introduction point. [SEND_INTRO1] - 3.2.1. INTRODUCE1 cell format [FMT_INTRO1] - 3.2.2. Legacy formats [LEGACY-INTRODUCE1] - 3.2.3. INTRODUCE_ACK cell format. [INTRO_ACK] - 3.3. Processing an INTRODUCE2 cell at the hidden service. [PROCESS_INTRO2] - 3.3.1. Introduction handshake encryption requirements [INTRO-HANDSHAKE-REQS] - 3.3.2. Example encryption handshake: ntor with extra data [NTOR-WITH-EXTRA-DATA] - 3.4. Authentication during the introduction phase. [INTRO-AUTH] - 3.4.1. Password-based authentication. - 3.4.2. Ed25519-based authentication. - 4. The rendezvous protocol - 4.1. Establishing a rendezvous point [EST_REND_POINT] - 4.2. Joining to a rendezvous point [JOIN_REND] - 4.2.1. Key expansion - 4.3. Using legacy hosts as rendezvous points - 5. Encrypting data between client and host - 6. Open Questions: + 0. Hidden services: overview and preliminaries. + 0.1. Improvements over previous versions. + 0.2. Notation and vocabulary + 0.3. Cryptographic building blocks + 0.4. Protocol building blocks [BUILDING-BLOCKS] + 0.5. Assigned relay cell types + 0.5. Acknowledgments + 1. Protocol overview + 1.1. View from 10,000 feet + 1.2. In more detail: naming hidden services [NAMING] + 1.3. In more detail: Access control [IMD:AC] + 1.4. In more detail: Distributing hidden service descriptors. [IMD:DIST] + 1.5. In more detail: Scaling to multiple hosts + 1.6. In more detail: Backward compatibility with older hidden service + 1.7. In more detail: Keeping crypto keys offline + 1.8. In more detail: Encryption Keys And Replay Resistance + 1.9. In more detail: A menagerie of keys + 2. Generating and publishing hidden service descriptors [HSDIR] + 2.1. Deriving blinded keys and subcredentials [SUBCRED] + 2.2. Locating, uploading, and downloading hidden service descriptors + 2.2.1. Dividing time into periods [TIME-PERIODS] + 2.2.2. Overlapping time periods to avoid thundering herds [TIME-OVERLAP] + 2.2.3. Where to publish a service descriptor + 2.2.4. Using time periods and SRVs to fetch/upload HS descriptors + 2.2.5. URLs for anonymous uploading and downloading + 2.3. Publishing shared random values [PUB-SHAREDRANDOM] + 2.3.1. Client behavior in the absense of shared random values + 2.3.2. Hidden services and changing shared random values + 2.4. Hidden service descriptors: outer wrapper [DESC-OUTER] + 2.5. Hidden service descriptors: encryption format [ENCRYPTED-DATA] + 3. The introduction protocol + 3.1. Registering an introduction point [REG_INTRO_POINT] + 3.1.1. Extensible ESTABLISH_INTRO protocol. [EST_INTRO] + 3.1.2. Registering an introduction point on a legacy Tor node [LEGACY_EST_INTRO] + 3.1.3. Acknowledging establishment of introduction point [INTRO_ESTABLISHED] + 3.2. Sending an INTRODUCE1 cell to the introduction point. [SEND_INTRO1] + 3.2.1. INTRODUCE1 cell format [FMT_INTRO1] + 3.2.2. Legacy formats [LEGACY-INTRODUCE1] + 3.2.3. INTRODUCE_ACK cell format. [INTRO_ACK] + 3.3. Processing an INTRODUCE2 cell at the hidden service. [PROCESS_INTRO2] + 3.3.1. Introduction handshake encryption requirements [INTRO-HANDSHAKE-REQS] + 3.3.2. Example encryption handshake: ntor with extra data [NTOR-WITH-EXTRA-DATA] + 3.4. Authentication during the introduction phase. [INTRO-AUTH] + 3.4.1. Password-based authentication. + 3.4.2. Ed25519-based authentication. + 4. The rendezvous protocol + 4.1. Establishing a rendezvous point [EST_REND_POINT] + 4.2. Joining to a rendezvous point [JOIN_REND] + 4.2.1. Key expansion + 4.3. Using legacy hosts as rendezvous points + 5. Encrypting data between client and host + 6. Open Questions: -1. Draft notes @@ -1018,20 +1018,20 @@ Table of contents: is included in the mandatory signing-key extension. The certificate type must be [09]. - "enc-key" SP "ntor" SP enc-public-key NL + Encryption key is specified as follow: - [Exactly one enc-key per introduction point] + [Exactly once enc-key per introduction point] - The enc-public-key is a base64 encoded curve25519 public key used to - encrypt the introduction request to service. + "enc-key" SP "ntor" SP key NL - "enc-key" SP "legacy" NL key NL + The key is a base64 encoded curve25519 public key used to encrypt + the introduction request to service. - [Exactly one enc-key per introduction point] + "enc-key" SP "legacy" NL key NL - Base64 encoded RSA key, wrapped in "----BEGIN RSA PUBLIC - KEY-----" armor, for use with a legacy introduction point as - described in [LEGACY_EST_INTRO] and [LEGACY-INTRODUCE1] below. + Base64 encoded RSA key, wrapped in "----BEGIN RSA PUBLIC + KEY-----" armor, for use with a legacy introduction point as + described in [LEGACY_EST_INTRO] and [LEGACY-INTRODUCE1] below. "enc-key-certification" NL certificate NL @@ -1041,11 +1041,11 @@ Table of contents: The format of this certificate depends on the type of enc-key. For "ntor" keys, certificate is a proposal 220 certificate in - "-----BEGIN ED25519 CERT-----" armor, cross-certifying the descriptor - signing key with the ed25519 equivalent of the curve25519 public key - from "enc-key" derived using the process in proposal 228 appendix A. - The certificate type must be [10], and the signing-key extension is - mandatory. + "-----BEGIN ED25519 CERT-----" armor, cross-certifying the + descriptor signing key with the ed25519 equivalent of the curve25519 + public key from "enc-key" derived using the process in proposal 228 + appendix A. The certificate type must be [10], and the signing-key + extension is mandatory. For "legacy" keys, certificate is an RSA signature wrapped in "-----BEGIN SIGNATURE-----" of the digest: @@ -1201,9 +1201,13 @@ Table of contents: the client, either informing it that its request has been delivered, or that its request will not succeed. + [TODO: specify what tor should do when receiving a malformed cell. Drop it? + Kill circuit? This goes for all possible cells.] + 3.2.1. INTRODUCE1 cell format [FMT_INTRO1] - An INTRODUCE1 cell has the following contents: + When a client is connecting to an introduction point, INTRODUCE1 cells + should be of the form: LEGACY_KEY_ID [20 bytes] AUTH_KEY_TYPE [1 byte] @@ -1220,7 +1224,7 @@ Table of contents: INTRODUCE1 cells. In new style INTRODUCE1 cells, LEGACY_KEY_ID is 20 zero bytes. Upon receiving an INTRODUCE1 cell, the introduction point checks the LEGACY_KEY_ID field. If LEGACY_KEY_ID is non-zero, the INTRODUCE1 cell - should be handled as specified in rend-spec.txt. + should be handled as specified in [LEGACY-INTRODUCE1]. AUTH_KEY_TYPE is defined as in [EST_INTRO]. Currently, the only value of AUTH_KEY_TYPE for this cell is an Ed25519 public key [02]. @@ -1233,10 +1237,9 @@ Table of contents: 3.2.2. Legacy formats [LEGACY-INTRODUCE1] - When a client is using a legacy introduction point, INTRODUCE1 cells should - be of the form: + For legacy introduction points, INTRODUCE1 cells should be of the form: - LEGACY_KEYID_HASH [20 bytes] + LEGACY_KEY_ID [20 bytes] N_EXTENSIONS [1 byte] N_EXTENSIONS times: EXT_FIELD_TYPE [1 byte] @@ -1244,7 +1247,7 @@ Table of contents: EXT_FIELD [EXT_FIELD_LEN bytes] ENCRYPTED [Up to end of relay payload] - Here, LEGACY_KEYID_HASH is the hash of the introduction point legacy + Here, LEGACY_KEY_ID is the hash of the introduction point legacy encryption key that was included in the hidden service descriptor. Because of limitations in older versions of Tor, the relay payload size for @@ -1271,7 +1274,7 @@ Table of contents: 3.3. Processing an INTRODUCE2 cell at the hidden service. [PROCESS_INTRO2] Upon receiving an INTRODUCE2 cell, the hidden service host checks whether - the AUTH_KEY or LEGACY_KEYID_HASH field matches the keys for this + the AUTH_KEY or LEGACY_KEY_ID field matches the keys for this introduction circuit. The service host then checks whether it has received a cell with @@ -1473,7 +1476,7 @@ Table of contents: Hidden services may restrict access only to authorized users. One mechanism to do so is the credential mechanism, where only users who - know the credentialo for a hidden service may connect at all. For more + know the credential for a hidden service may connect at all. For more fine-grained conntrol, a hidden service can be configured with password-based or public-key-based authentication.

1 0

[torspec/master] prop250: Add the Version field to a commit
by dgoulet＠torproject.org 12 May '16

12 May '16

commit 6945958d997401511fc6dcd36c4e37a6233f2a11 Author: David Goulet <dgoulet(a)ev0ke.net> Date: Thu May 12 13:43:47 2016 -0400 prop250: Add the Version field to a commit Signed-off-by: David Goulet <dgoulet(a)torproject.org> --- proposals/250-commit-reveal-consensus.txt | 17 +++++++++-------- 1 file changed, 9 insertions(+), 8 deletions(-) diff --git a/proposals/250-commit-reveal-consensus.txt b/proposals/250-commit-reveal-consensus.txt index cd19b4c..0e7675e 100644 --- a/proposals/250-commit-reveal-consensus.txt +++ b/proposals/250-commit-reveal-consensus.txt @@ -423,14 +423,15 @@ Supersedes: 225 seen from the other authorities. To do so, it includes the following in its votes: - "shared-rand-commit" SP ALGNAME SP IDENTITY SP COMMIT [SP REVEAL] NL + "shared-rand-commit" SP VERSION SP ALGNAME SP IDENTITY SP COMMIT [SP REVEAL] NL - where IDENTITY is the authority's SHA1 identity fingerprint and COMMIT is the - encoded commit [COMMITREVEAL]. Authorities during the reveal phase can also - optionally include an encoded reveal value REVEAL. There MUST be only one - line per authority else the vote is considered invalid. Finally, the ALGNAME - is the hash algorithm that should be used to compute COMMIT and REVEAL which - is "sha3-256" for version 1. + where VERSION is the version of the protocol the commit was created with. + IDENTITY is the authority's SHA1 identity fingerprint and COMMIT is the + encoded commit [COMMITREVEAL]. Authorities during the reveal phase can + also optionally include an encoded reveal value REVEAL. There MUST be only + one line per authority else the vote is considered invalid. Finally, the + ALGNAME is the hash algorithm that should be used to compute COMMIT and + REVEAL which is "sha3-256" for version 1. 4.1.5. Shared Random Value [SRVOTE] @@ -481,7 +482,7 @@ Supersedes: 225 The following details the commitment and reveal section. They are encoded the same as in the vote. This makes it easier for implementation purposes. - "Commit" SP algname SP identity SP commit [SP reveal] NL + "Commit" SP version SP algname SP identity SP commit [SP reveal] NL [Exactly once per authority]

1 0

[tor/master] Run tor_sscanf test in subprocess, in hopes of coaxing more info from jenkins
by nickm＠torproject.org 12 May '16

12 May '16

commit a7207329a85a156e20f91434347e2741d4d90025 Author: Nick Mathewson <nickm(a)torproject.org> Date: Thu May 12 13:37:05 2016 -0400 Run tor_sscanf test in subprocess, in hopes of coaxing more info from jenkins --- src/test/test_util.c | 2 +- 1 file changed, 1 insertion(+), 1 deletion(-) diff --git a/src/test/test_util.c b/src/test/test_util.c index 21ff757..a880206 100644 --- a/src/test/test_util.c +++ b/src/test/test_util.c @@ -4819,7 +4819,7 @@ struct testcase_t util_tests[] = { UTIL_LEGACY(memarea), UTIL_LEGACY(control_formats), UTIL_LEGACY(mmap), - UTIL_LEGACY(sscanf), + UTIL_TEST(sscanf, TT_FORK), UTIL_LEGACY(format_time_interval), UTIL_LEGACY(path_is_relative), UTIL_LEGACY(strtok),

1 0

[tor/master] Add -ftrapv to gcc-hardening ... mostly!
by nickm＠torproject.org 12 May '16

12 May '16

commit ce854a8d22d5056cc1a47a0d4d4251f93a0c667c Author: Nick Mathewson <nickm(a)torproject.org> Date: Tue Apr 12 18:59:40 2016 -0400 Add -ftrapv to gcc-hardening ... mostly! We know there are overflows in curve25519-donna-c32, so we'll have to have that one be fwrapv. Only apply the asan, ubsan, and trapv options to the code that does not need to run in constant time. Those options introduce branches to the code they instrument. (These introduced branches should never actually be taken, so it might _still_ be constant time after all, but branch predictors are complicated enough that I'm not really confident here. Let's aim for safety.) Closes 17983. --- .gitignore | 3 +++ Makefile.am | 4 ++-- acinclude.m4 | 20 +++++++++++++++----- changes/bug17983 | 11 +++++++++++ configure.ac | 23 ++++++++++++++++++++--- src/common/include.am | 17 ++++++++++++++--- src/ext/include.am | 9 ++++++--- src/or/include.am | 3 ++- src/test/include.am | 6 ++++++ src/tools/include.am | 11 +++++++++-- 10 files changed, 88 insertions(+), 19 deletions(-) diff --git a/.gitignore b/.gitignore index b141e80..7103dbe 100644 --- a/.gitignore +++ b/.gitignore @@ -132,6 +132,9 @@ uptime-*.json /src/common/libor.a /src/common/libor-testing.a /src/common/libor.lib +/src/common/libor-ctime.a +/src/common/libor-ctime-testing.a +/src/common/libor-ctime.lib /src/common/libor-crypto.a /src/common/libor-crypto-testing.a /src/common/libor-crypto.lib diff --git a/Makefile.am b/Makefile.am index 92ba2b8..e9abfc6 100644 --- a/Makefile.am +++ b/Makefile.am @@ -15,8 +15,8 @@ noinst_PROGRAMS= DISTCLEANFILES= bin_SCRIPTS= AM_CPPFLAGS= -AM_CFLAGS = @TOR_SYSTEMD_CFLAGS@ -SHELL = @SHELL@ +AM_CFLAGS=@TOR_SYSTEMD_CFLAGS@ @CFLAGS_BUGTRAP@ +SHELL=@SHELL@ if COVERAGE_ENABLED TESTING_TOR_BINARY="$(top_builddir)/src/or/tor-cov" diff --git a/acinclude.m4 b/acinclude.m4 index 7b1aab2..4b9f095 100644 --- a/acinclude.m4 +++ b/acinclude.m4 @@ -42,10 +42,11 @@ AC_DEFUN([TOR_DEFINE_CODEPATH], AC_SUBST(TOR_LDFLAGS_$2) ]) -dnl 1:flags -dnl 2:also try to link (yes: non-empty string) -dnl will set yes or no in $tor_can_link_$1 (as modified by AS_VAR_PUSHDEF) -AC_DEFUN([TOR_CHECK_CFLAGS], [ +dnl 1: flags +dnl 2: try to link too if this is nonempty. +dnl 3: what to do on success compiling +dnl 4: what to do on failure compiling +AC_DEFUN([TOR_TRY_COMPILE_WITH_CFLAGS], [ AS_VAR_PUSHDEF([VAR],[tor_cv_cflags_$1]) AC_CACHE_CHECK([whether the compiler accepts $1], VAR, [ tor_saved_CFLAGS="$CFLAGS" @@ -63,12 +64,21 @@ AC_DEFUN([TOR_CHECK_CFLAGS], [ CFLAGS="$tor_saved_CFLAGS" ]) if test x$VAR = xyes; then - CFLAGS="$CFLAGS $1" + $3 + else + $4 fi AS_VAR_POPDEF([VAR]) ]) dnl 1:flags +dnl 2:also try to link (yes: non-empty string) +dnl will set yes or no in $tor_can_link_$1 (as modified by AS_VAR_PUSHDEF) +AC_DEFUN([TOR_CHECK_CFLAGS], [ + TOR_TRY_COMPILE_WITH_CFLAGS($1, $2, CFLAGS="$CFLAGS $1", /bin/true) +]) + +dnl 1:flags dnl 2:extra ldflags dnl 3:extra libraries AC_DEFUN([TOR_CHECK_LDFLAGS], [ diff --git a/changes/bug17983 b/changes/bug17983 new file mode 100644 index 0000000..db52a37 --- /dev/null +++ b/changes/bug17983 @@ -0,0 +1,11 @@ + o Minor features (bug-finding): + - Tor now builds with -ftrapv by default on compilers that support it. + This option detects signed integer overflow, and turns it into a + hard-failure. We do not apply this option to code that needs to run + in constant time to avoid side-channels; instead, we use -fwrapv. + Closes ticket 17983. + - When --enable-expensive-hardening is selected, stop applying the clang/gcc + sanitizers to code that needs to run in constant-time to avoid side + channels: although we are aware of no introduced side-channels, we + are not able to prove that this is safe. Related to ticket 17983. + diff --git a/configure.ac b/configure.ac index 4bdd2d3..626be6c 100644 --- a/configure.ac +++ b/configure.ac @@ -755,6 +755,11 @@ dnl use it with a build of a library. all_ldflags_for_check="$TOR_LDFLAGS_zlib $TOR_LDFLAGS_openssl $TOR_LDFLAGS_libevent" all_libs_for_check="$TOR_ZLIB_LIBS $TOR_LIB_MATH $TOR_LIBEVENT_LIBS $TOR_OPENSSL_LIBS $TOR_SYSTEMD_LIBS $TOR_LIB_WS32 $TOR_LIB_GDI $TOR_CAP_LIBS" +CFLAGS_FTRAPV= +CFLAGS_FWRAPV= +CFLAGS_ASAN= +CFLAGS_UBSAN= + AC_COMPILE_IFELSE([AC_LANG_PROGRAM([], [ #if !defined(__clang__) #error @@ -777,20 +782,32 @@ m4_ifdef([AS_VAR_IF],[ AS_VAR_POPDEF([can_link]) AS_VAR_POPDEF([can_compile]) TOR_CHECK_CFLAGS(-Wstack-protector) - TOR_CHECK_CFLAGS(-fwrapv) TOR_CHECK_CFLAGS(--param ssp-buffer-size=1) if test "$bwin32" = "false"; then TOR_CHECK_CFLAGS(-fPIE) TOR_CHECK_LDFLAGS(-pie, "$all_ldflags_for_check", "$all_libs_for_check") fi + TOR_TRY_COMPILE_WITH_CFLAGS(-ftrapv, , CFLAGS_FTRAPV="-ftrapv", /bin/true) + TOR_TRY_COMPILE_WITH_CFLAGS(-fwrapv, , CFLAGS_FWRAPV="-fwrapv", /bin/true) fi if test "x$enable_expensive_hardening" = "xyes"; then - TOR_CHECK_CFLAGS([-fsanitize=address]) - TOR_CHECK_CFLAGS([-fsanitize=undefined]) + TOR_TRY_COMPILE_WITH_CFLAGS([-fsanitize=address], , CFLAGS_ASAN="-fsanitize=address", /bin/true) + TOR_TRY_COMPILE_WITH_CFLAGS([-fsanitize=undefined], , CFLAGS_UBSAN="-fsanitize=undefined", /bin/true) TOR_CHECK_CFLAGS([-fno-omit-frame-pointer]) fi +CFLAGS_BUGTRAP="$CFLAGS_FTRAPV $CFLAGS_ASAN $CFLAGS_UBSAN" +CFLAGS_CONSTTIME="$CFLAGS_FWRAPV" + +dnl These cflags add bunches of branches, and we haven't been able to +dnl persuade ourselves that they're suitable for code that needs to be +dnl constant time. +AC_SUBST(CFLAGS_BUGTRAP) +dnl These cflags are variant ones sutable for code that needs to be +dnl constant-time. +AC_SUBST(CFLAGS_CONSTTIME) + if test "x$enable_linker_hardening" != "xno"; then TOR_CHECK_LDFLAGS(-z relro -z now, "$all_ldflags_for_check", "$all_libs_for_check") fi diff --git a/src/common/include.am b/src/common/include.am index 5afb30d..96fc329 100644 --- a/src/common/include.am +++ b/src/common/include.am @@ -1,12 +1,14 @@ noinst_LIBRARIES += \ src/common/libor.a \ + src/common/libor-ctime.a \ src/common/libor-crypto.a \ src/common/libor-event.a if UNITTESTS_ENABLED noinst_LIBRARIES += \ src/common/libor-testing.a \ + src/common/libor-ctime-testing.a \ src/common/libor-crypto-testing.a \ src/common/libor-event-testing.a endif @@ -27,12 +29,14 @@ src_common_libcurve25519_donna_a_CFLAGS= if BUILD_CURVE25519_DONNA src_common_libcurve25519_donna_a_SOURCES=\ src/ext/curve25519_donna/curve25519-donna.c +# See bug 13538 -- this code is known to have signed overflow issues. src_common_libcurve25519_donna_a_CFLAGS+=\ - @F_OMIT_FRAME_POINTER@ + @F_OMIT_FRAME_POINTER@ @CFLAGS_CONSTTIME@ noinst_LIBRARIES+=src/common/libcurve25519_donna.a LIBDONNA=src/common/libcurve25519_donna.a else if BUILD_CURVE25519_DONNA_C64 +src_common_libcurve25519_donna_a_CFLAGS+=@CFLAGS_CONSTTIME@ src_common_libcurve25519_donna_a_SOURCES=\ src/ext/curve25519_donna/curve25519-donna-c64.c noinst_LIBRARIES+=src/common/libcurve25519_donna.a @@ -58,13 +62,21 @@ else readpassphrase_source= endif +LIBOR_CTIME_A_SOURCES = \ + src/ext/csiphash.c \ + src/common/di_ops.c + +src_common_libor_ctime_a_SOURCES = $(LIBOR_CTIME_A_SOURCES) +src_common_libor_ctime_testing_a_SOURCES = $(LIBOR_CTIME_A_SOURCES) +src_common_libor_ctime_a_CFLAGS = @CFLAGS_CONSTTIME@ +src_common_libor_ctime_testing_a_CFLAGS = @CFLAGS_CONSTTIME@ $(TEST_CFLAGS) + LIBOR_A_SOURCES = \ src/common/address.c \ src/common/backtrace.c \ src/common/compat.c \ src/common/compat_threads.c \ src/common/container.c \ - src/common/di_ops.c \ src/common/log.c \ src/common/memarea.c \ src/common/util.c \ @@ -72,7 +84,6 @@ LIBOR_A_SOURCES = \ src/common/util_process.c \ src/common/sandbox.c \ src/common/workqueue.c \ - src/ext/csiphash.c \ src/ext/trunnel/trunnel.c \ $(libor_extra_source) \ $(threads_impl_source) \ diff --git a/src/ext/include.am b/src/ext/include.am index bf678f2..2a0227a 100644 --- a/src/ext/include.am +++ b/src/ext/include.am @@ -16,7 +16,8 @@ EXTHEADERS = \ noinst_HEADERS+= $(EXTHEADERS) -src_ext_ed25519_ref10_libed25519_ref10_a_CFLAGS= +src_ext_ed25519_ref10_libed25519_ref10_a_CFLAGS=\ + @CFLAGS_CONSTTIME@ src_ext_ed25519_ref10_libed25519_ref10_a_SOURCES= \ src/ext/ed25519/ref10/fe_0.c \ @@ -93,7 +94,8 @@ noinst_HEADERS += $(ED25519_REF10_HDRS) LIBED25519_REF10=src/ext/ed25519/ref10/libed25519_ref10.a noinst_LIBRARIES += $(LIBED25519_REF10) -src_ext_ed25519_donna_libed25519_donna_a_CFLAGS= \ +src_ext_ed25519_donna_libed25519_donna_a_CFLAGS=\ + @CFLAGS_CONSTTIME@ \ -DED25519_CUSTOMRANDOM \ -DED25519_SUFFIX=_donna @@ -135,7 +137,8 @@ noinst_HEADERS += $(ED25519_DONNA_HDRS) LIBED25519_DONNA=src/ext/ed25519/donna/libed25519_donna.a noinst_LIBRARIES += $(LIBED25519_DONNA) -src_ext_keccak_tiny_libkeccak_tiny_a_CFLAGS= +src_ext_keccak_tiny_libkeccak_tiny_a_CFLAGS=\ + @CFLAGS_CONSTTIME@ src_ext_keccak_tiny_libkeccak_tiny_a_SOURCES= \ src/ext/keccak-tiny/keccak-tiny-unrolled.c diff --git a/src/or/include.am b/src/or/include.am index 712ae18..19f1a7f 100644 --- a/src/or/include.am +++ b/src/or/include.am @@ -109,7 +109,7 @@ src_or_libtor_testing_a_CFLAGS = $(AM_CFLAGS) $(TEST_CFLAGS) src_or_tor_LDFLAGS = @TOR_LDFLAGS_zlib@ @TOR_LDFLAGS_openssl@ @TOR_LDFLAGS_libevent@ -src_or_tor_LDADD = src/or/libtor.a src/common/libor.a \ +src_or_tor_LDADD = src/or/libtor.a src/common/libor.a src/common/libor-ctime.a \ src/common/libor-crypto.a $(LIBKECCAK_TINY) $(LIBDONNA) \ src/common/libor-event.a src/trunnel/libor-trunnel.a \ @TOR_ZLIB_LIBS@ @TOR_LIB_MATH@ @TOR_LIBEVENT_LIBS@ @TOR_OPENSSL_LIBS@ \ @@ -121,6 +121,7 @@ src_or_tor_cov_CPPFLAGS = $(AM_CPPFLAGS) $(TEST_CPPFLAGS) src_or_tor_cov_CFLAGS = $(AM_CFLAGS) $(TEST_CFLAGS) src_or_tor_cov_LDFLAGS = @TOR_LDFLAGS_zlib@ @TOR_LDFLAGS_openssl@ @TOR_LDFLAGS_libevent@ src_or_tor_cov_LDADD = src/or/libtor-testing.a src/common/libor-testing.a \ + src/common/libor-ctime-testing.a \ src/common/libor-crypto-testing.a $(LIBKECCAK_TINY) $(LIBDONNA) \ src/common/libor-event-testing.a src/trunnel/libor-trunnel-testing.a \ @TOR_ZLIB_LIBS@ @TOR_LIB_MATH@ @TOR_LIBEVENT_LIBS@ @TOR_OPENSSL_LIBS@ \ diff --git a/src/test/include.am b/src/test/include.am index 7d80fdf..c4ef30f 100644 --- a/src/test/include.am +++ b/src/test/include.am @@ -147,6 +147,7 @@ src_test_test_switch_id_CFLAGS = $(AM_CFLAGS) $(TEST_CFLAGS) src_test_test_switch_id_LDFLAGS = @TOR_LDFLAGS_zlib@ src_test_test_switch_id_LDADD = \ src/common/libor-testing.a \ + src/common/libor-ctime-testing.a \ @TOR_ZLIB_LIBS@ @TOR_LIB_MATH@ src_test_test_LDFLAGS = @TOR_LDFLAGS_zlib@ @TOR_LDFLAGS_openssl@ \ @@ -156,6 +157,7 @@ src_test_test_LDADD = src/or/libtor-testing.a \ $(LIBKECCAK_TINY) \ $(LIBDONNA) \ src/common/libor-testing.a \ + src/common/libor-ctime-testing.a \ src/common/libor-event-testing.a \ src/trunnel/libor-trunnel-testing.a \ @TOR_ZLIB_LIBS@ @TOR_LIB_MATH@ @TOR_LIBEVENT_LIBS@ \ @@ -175,6 +177,7 @@ src_test_test_memwipe_LDFLAGS = $(src_test_test_LDFLAGS) src_test_bench_LDFLAGS = @TOR_LDFLAGS_zlib@ @TOR_LDFLAGS_openssl@ \ @TOR_LDFLAGS_libevent@ src_test_bench_LDADD = src/or/libtor.a src/common/libor.a \ + src/common/libor-ctime.a \ src/common/libor-crypto.a $(LIBKECCAK_TINY) $(LIBDONNA) \ src/common/libor-event.a src/trunnel/libor-trunnel.a \ @TOR_ZLIB_LIBS@ @TOR_LIB_MATH@ @TOR_LIBEVENT_LIBS@ \ @@ -185,6 +188,7 @@ src_test_test_workqueue_LDFLAGS = @TOR_LDFLAGS_zlib@ @TOR_LDFLAGS_openssl@ \ @TOR_LDFLAGS_libevent@ src_test_test_workqueue_LDADD = src/or/libtor-testing.a \ src/common/libor-testing.a \ + src/common/libor-ctime-testing.a \ src/common/libor-crypto-testing.a $(LIBKECCAK_TINY) $(LIBDONNA) \ src/common/libor-event-testing.a \ @TOR_ZLIB_LIBS@ @TOR_LIB_MATH@ @TOR_LIBEVENT_LIBS@ \ @@ -208,6 +212,7 @@ noinst_PROGRAMS+= src/test/test-ntor-cl src_test_test_ntor_cl_SOURCES = src/test/test_ntor_cl.c src_test_test_ntor_cl_LDFLAGS = @TOR_LDFLAGS_zlib@ @TOR_LDFLAGS_openssl@ src_test_test_ntor_cl_LDADD = src/or/libtor.a src/common/libor.a \ + src/common/libor-ctime.a \ src/common/libor-crypto.a $(LIBKECCAK_TINY) $(LIBDONNA) \ @TOR_ZLIB_LIBS@ @TOR_LIB_MATH@ \ @TOR_OPENSSL_LIBS@ @TOR_LIB_WS32@ @TOR_LIB_GDI@ @CURVE25519_LIBS@ @@ -217,6 +222,7 @@ src_test_test_ntor_cl_AM_CPPFLAGS = \ noinst_PROGRAMS += src/test/test-bt-cl src_test_test_bt_cl_SOURCES = src/test/test_bt_cl.c src_test_test_bt_cl_LDADD = src/common/libor-testing.a \ + src/common/libor-ctime-testing.a \ @TOR_LIB_MATH@ \ @TOR_LIB_WS32@ @TOR_LIB_GDI@ src_test_test_bt_cl_CFLAGS = $(AM_CFLAGS) $(TEST_CFLAGS) diff --git a/src/tools/include.am b/src/tools/include.am index 38ed575..b4ea82d 100644 --- a/src/tools/include.am +++ b/src/tools/include.am @@ -7,19 +7,23 @@ endif src_tools_tor_resolve_SOURCES = src/tools/tor-resolve.c src_tools_tor_resolve_LDFLAGS = -src_tools_tor_resolve_LDADD = src/common/libor.a @TOR_LIB_MATH@ @TOR_LIB_WS32@ +src_tools_tor_resolve_LDADD = src/common/libor.a \ + src/common/libor-ctime.a \ + @TOR_LIB_MATH@ @TOR_LIB_WS32@ if COVERAGE_ENABLED src_tools_tor_cov_resolve_SOURCES = src/tools/tor-resolve.c src_tools_tor_cov_resolve_CPPFLAGS = $(AM_CPPFLAGS) $(TEST_CPPFLAGS) src_tools_tor_cov_resolve_CFLAGS = $(AM_CFLAGS) $(TEST_CFLAGS) src_tools_tor_cov_resolve_LDADD = src/common/libor-testing.a \ + src/common/libor-ctime-testing.a \ @TOR_LIB_MATH@ @TOR_LIB_WS32@ endif src_tools_tor_gencert_SOURCES = src/tools/tor-gencert.c src_tools_tor_gencert_LDFLAGS = @TOR_LDFLAGS_zlib@ @TOR_LDFLAGS_openssl@ src_tools_tor_gencert_LDADD = src/common/libor.a src/common/libor-crypto.a \ + src/common/libor-ctime.a \ $(LIBKECCAK_TINY) \ $(LIBDONNA) \ @TOR_LIB_MATH@ @TOR_ZLIB_LIBS@ @TOR_OPENSSL_LIBS@ \ @@ -31,6 +35,7 @@ src_tools_tor_cov_gencert_CPPFLAGS = $(AM_CPPFLAGS) $(TEST_CPPFLAGS) src_tools_tor_cov_gencert_CFLAGS = $(AM_CFLAGS) $(TEST_CFLAGS) src_tools_tor_cov_gencert_LDFLAGS = @TOR_LDFLAGS_zlib@ @TOR_LDFLAGS_openssl@ src_tools_tor_cov_gencert_LDADD = src/common/libor-testing.a \ + src/common/libor-ctime-testing.a \ src/common/libor-crypto-testing.a \ $(LIBKECCAK_TINY) \ $(LIBDONNA) \ @@ -40,7 +45,9 @@ endif src_tools_tor_checkkey_SOURCES = src/tools/tor-checkkey.c src_tools_tor_checkkey_LDFLAGS = @TOR_LDFLAGS_zlib@ @TOR_LDFLAGS_openssl@ -src_tools_tor_checkkey_LDADD = src/common/libor.a src/common/libor-crypto.a \ +src_tools_tor_checkkey_LDADD = src/common/libor.a \ + src/common/libor-ctime.a \ + src/common/libor-crypto.a \ $(LIBKECCAK_TINY) \ $(LIBDONNA) \ @TOR_LIB_MATH@ @TOR_ZLIB_LIBS@ @TOR_OPENSSL_LIBS@ \

1 0

[tor/master] Refactor out u64_dbl_t
by nickm＠torproject.org 12 May '16

12 May '16

commit 20432fc541bf0fb8f136f0d4635b264c624ce3eb Author: Nick Mathewson <nickm(a)torproject.org> Date: Wed Apr 27 10:16:43 2016 -0400 Refactor out u64_dbl_t This type saved a tiny amount of allocation, but not enough to be worth keeping. (This is in preparation for moving choose_array_element_by_weight) --- src/or/routerlist.c | 58 ++++++++++++++++++++++++++++++----------------------- src/or/routerlist.h | 13 +++--------- src/test/test_dir.c | 45 +++++++++++++++++++++-------------------- 3 files changed, 59 insertions(+), 57 deletions(-) diff --git a/src/or/routerlist.c b/src/or/routerlist.c index 80d0197..620b614 100644 --- a/src/or/routerlist.c +++ b/src/or/routerlist.c @@ -67,7 +67,7 @@ typedef struct cert_list_t cert_list_t; /* static function prototypes */ static int compute_weighted_bandwidths(const smartlist_t *sl, bandwidth_weight_rule_t rule, - u64_dbl_t **bandwidths_out); + double **bandwidths_out); static const routerstatus_t *router_pick_trusteddirserver_impl( const smartlist_t *sourcelist, dirinfo_type_t auth, int flags, int *n_busy_out); @@ -1799,20 +1799,23 @@ dirserver_choose_by_weight(const smartlist_t *servers, double authority_weight) { int n = smartlist_len(servers); int i; - u64_dbl_t *weights; + double *weights_dbl; + uint64_t *weights_u64; const dir_server_t *ds; - weights = tor_calloc(n, sizeof(u64_dbl_t)); + weights_dbl = tor_calloc(n, sizeof(double)); + weights_u64 = tor_calloc(n, sizeof(uint64_t)); for (i = 0; i < n; ++i) { ds = smartlist_get(servers, i); - weights[i].dbl = ds->weight; + weights_dbl[i] = ds->weight; if (ds->is_authority) - weights[i].dbl *= authority_weight; + weights_dbl[i] *= authority_weight; } - scale_array_elements_to_u64(weights, n, NULL); - i = choose_array_element_by_weight(weights, n); - tor_free(weights); + scale_array_elements_to_u64(weights_u64, weights_dbl, n, NULL); + i = choose_array_element_by_weight(weights_u64, n); + tor_free(weights_dbl); + tor_free(weights_u64); return (i < 0) ? NULL : smartlist_get(servers, i); } @@ -2075,7 +2078,8 @@ router_get_advertised_bandwidth_capped(const routerinfo_t *router) * much of the range of uint64_t. If total_out is provided, set it to * the sum of all elements in the array _before_ scaling. */ STATIC void -scale_array_elements_to_u64(u64_dbl_t *entries, int n_entries, +scale_array_elements_to_u64(uint64_t *entries_out, const double *entries_in, + int n_entries, uint64_t *total_out) { double total = 0.0; @@ -2085,13 +2089,13 @@ scale_array_elements_to_u64(u64_dbl_t *entries, int n_entries, #define SCALE_TO_U64_MAX ((int64_t) (INT64_MAX / 4)) for (i = 0; i < n_entries; ++i) - total += entries[i].dbl; + total += entries_in[i]; if (total > 0.0) scale_factor = SCALE_TO_U64_MAX / total; for (i = 0; i < n_entries; ++i) - entries[i].u64 = tor_llround(entries[i].dbl * scale_factor); + entries_out[i] = tor_llround(entries_in[i] * scale_factor); if (total_out) *total_out = (uint64_t) total; @@ -2119,7 +2123,7 @@ gt_i64_timei(uint64_t a, uint64_t b) * an index at random. Return -1 on error. */ STATIC int -choose_array_element_by_weight(const u64_dbl_t *entries, int n_entries) +choose_array_element_by_weight(const uint64_t *entries, int n_entries) { int i, i_chosen=-1, n_chosen=0; uint64_t total_so_far = 0; @@ -2127,7 +2131,7 @@ choose_array_element_by_weight(const u64_dbl_t *entries, int n_entries) uint64_t total = 0; for (i = 0; i < n_entries; ++i) - total += entries[i].u64; + total += entries[i]; if (n_entries < 1) return -1; @@ -2140,7 +2144,7 @@ choose_array_element_by_weight(const u64_dbl_t *entries, int n_entries) rand_val = crypto_rand_uint64(total); for (i = 0; i < n_entries; ++i) { - total_so_far += entries[i].u64; + total_so_far += entries[i]; if (gt_i64_timei(total_so_far, rand_val)) { i_chosen = i; n_chosen++; @@ -2206,17 +2210,21 @@ static const node_t * smartlist_choose_node_by_bandwidth_weights(const smartlist_t *sl, bandwidth_weight_rule_t rule) { - u64_dbl_t *bandwidths=NULL; + double *bandwidths_dbl=NULL; + uint64_t *bandwidths_u64=NULL; - if (compute_weighted_bandwidths(sl, rule, &bandwidths) < 0) + if (compute_weighted_bandwidths(sl, rule, &bandwidths_dbl) < 0) return NULL; - scale_array_elements_to_u64(bandwidths, smartlist_len(sl), NULL); + bandwidths_u64 = tor_calloc(smartlist_len(sl), sizeof(uint64_t)); + scale_array_elements_to_u64(bandwidths_u64, bandwidths_dbl, + smartlist_len(sl), NULL); { - int idx = choose_array_element_by_weight(bandwidths, + int idx = choose_array_element_by_weight(bandwidths_u64, smartlist_len(sl)); - tor_free(bandwidths); + tor_free(bandwidths_dbl); + tor_free(bandwidths_u64); return idx < 0 ? NULL : smartlist_get(sl, idx); } } @@ -2229,14 +2237,14 @@ smartlist_choose_node_by_bandwidth_weights(const smartlist_t *sl, static int compute_weighted_bandwidths(const smartlist_t *sl, bandwidth_weight_rule_t rule, - u64_dbl_t **bandwidths_out) + double **bandwidths_out) { int64_t weight_scale; double Wg = -1, Wm = -1, We = -1, Wd = -1; double Wgb = -1, Wmb = -1, Web = -1, Wdb = -1; uint64_t weighted_bw = 0; guardfraction_bandwidth_t guardfraction_bw; - u64_dbl_t *bandwidths; + double *bandwidths; /* Can't choose exit and guard at same time */ tor_assert(rule == NO_WEIGHTING || @@ -2318,7 +2326,7 @@ compute_weighted_bandwidths(const smartlist_t *sl, Web /= weight_scale; Wdb /= weight_scale; - bandwidths = tor_calloc(smartlist_len(sl), sizeof(u64_dbl_t)); + bandwidths = tor_calloc(smartlist_len(sl), sizeof(double)); // Cycle through smartlist and total the bandwidth. static int warned_missing_bw = 0; @@ -2405,7 +2413,7 @@ compute_weighted_bandwidths(const smartlist_t *sl, final_weight = weight*this_bw; } - bandwidths[node_sl_idx].dbl = final_weight + 0.5; + bandwidths[node_sl_idx] = final_weight + 0.5; } SMARTLIST_FOREACH_END(node); log_debug(LD_CIRC, "Generated weighted bandwidths for rule %s based " @@ -2426,7 +2434,7 @@ double frac_nodes_with_descriptors(const smartlist_t *sl, bandwidth_weight_rule_t rule) { - u64_dbl_t *bandwidths = NULL; + double *bandwidths = NULL; double total, present; if (smartlist_len(sl) == 0) @@ -2443,7 +2451,7 @@ frac_nodes_with_descriptors(const smartlist_t *sl, total = present = 0.0; SMARTLIST_FOREACH_BEGIN(sl, const node_t *, node) { - const double bw = bandwidths[node_sl_idx].dbl; + const double bw = bandwidths[node_sl_idx]; total += bw; if (node_has_descriptor(node)) present += bw; diff --git a/src/or/routerlist.h b/src/or/routerlist.h index bc48c20..2166cf5 100644 --- a/src/or/routerlist.h +++ b/src/or/routerlist.h @@ -217,17 +217,10 @@ int hex_digest_nickname_matches(const char *hexdigest, const char *nickname, int is_named); #ifdef ROUTERLIST_PRIVATE -/** Helper type for choosing routers by bandwidth: contains a union of - * double and uint64_t. Before we call scale_array_elements_to_u64, it holds - * a double; after, it holds a uint64_t. */ -typedef union u64_dbl_t { - uint64_t u64; - double dbl; -} u64_dbl_t; - -STATIC int choose_array_element_by_weight(const u64_dbl_t *entries, +STATIC int choose_array_element_by_weight(const uint64_t *entries, int n_entries); -STATIC void scale_array_elements_to_u64(u64_dbl_t *entries, int n_entries, +STATIC void scale_array_elements_to_u64(uint64_t *entries_out, + const double *entries_in, int n_entries, uint64_t *total_out); STATIC const routerstatus_t *router_pick_directory_server_impl( dirinfo_type_t auth, int flags, diff --git a/src/test/test_dir.c b/src/test/test_dir.c index ea179fb..747c4c4 100644 --- a/src/test/test_dir.c +++ b/src/test/test_dir.c @@ -2149,56 +2149,57 @@ test_dir_scale_bw(void *testdata) 1.0/7, 12.0, 24.0 }; - u64_dbl_t vals[8]; + double vals_dbl[8]; + uint64_t vals_u64[8]; uint64_t total; int i; (void) testdata; for (i=0; i<8; ++i) - vals[i].dbl = v[i]; + vals_dbl[i] = v[i]; - scale_array_elements_to_u64(vals, 8, &total); + scale_array_elements_to_u64(vals_u64, vals_dbl, 8, &total); tt_int_op((int)total, OP_EQ, 48); total = 0; for (i=0; i<8; ++i) { - total += vals[i].u64; + total += vals_u64[i]; } tt_assert(total >= (U64_LITERAL(1)<<60)); tt_assert(total <= (U64_LITERAL(1)<<62)); for (i=0; i<8; ++i) { /* vals[2].u64 is the scaled value of 1.0 */ - double ratio = ((double)vals[i].u64) / vals[2].u64; + double ratio = ((double)vals_u64[i]) / vals_u64[2]; tt_double_op(fabs(ratio - v[i]), OP_LT, .00001); } /* test handling of no entries */ total = 1; - scale_array_elements_to_u64(vals, 0, &total); + scale_array_elements_to_u64(vals_u64, vals_dbl, 0, &total); tt_assert(total == 0); /* make sure we don't read the array when we have no entries * may require compiler flags to catch NULL dereferences */ total = 1; - scale_array_elements_to_u64(NULL, 0, &total); + scale_array_elements_to_u64(NULL, NULL, 0, &total); tt_assert(total == 0); - scale_array_elements_to_u64(NULL, 0, NULL); + scale_array_elements_to_u64(NULL, NULL, 0, NULL); /* test handling of zero totals */ total = 1; - vals[0].dbl = 0.0; - scale_array_elements_to_u64(vals, 1, &total); + vals_dbl[0] = 0.0; + scale_array_elements_to_u64(vals_u64, vals_dbl, 1, &total); tt_assert(total == 0); - tt_assert(vals[0].u64 == 0); + tt_assert(vals_u64[0] == 0); - vals[0].dbl = 0.0; - vals[1].dbl = 0.0; - scale_array_elements_to_u64(vals, 2, NULL); - tt_assert(vals[0].u64 == 0); - tt_assert(vals[1].u64 == 0); + vals_dbl[0] = 0.0; + vals_dbl[1] = 0.0; + scale_array_elements_to_u64(vals_u64, vals_dbl, 2, NULL); + tt_assert(vals_u64[0] == 0); + tt_assert(vals_u64[1] == 0); done: ; @@ -2209,7 +2210,7 @@ test_dir_random_weighted(void *testdata) { int histogram[10]; uint64_t vals[10] = {3,1,2,4,6,0,7,5,8,9}, total=0; - u64_dbl_t inp[10]; + uint64_t inp_u64[10]; int i, choice; const int n = 50000; double max_sq_error; @@ -2219,12 +2220,12 @@ test_dir_random_weighted(void *testdata) * in a scrambled order to make sure we don't depend on order. */ memset(histogram,0,sizeof(histogram)); for (i=0; i<10; ++i) { - inp[i].u64 = vals[i]; + inp_u64[i] = vals[i]; total += vals[i]; } tt_u64_op(total, OP_EQ, 45); for (i=0; i<n; ++i) { - choice = choose_array_element_by_weight(inp, 10); + choice = choose_array_element_by_weight(inp_u64, 10); tt_int_op(choice, OP_GE, 0); tt_int_op(choice, OP_LT, 10); histogram[choice]++; @@ -2251,16 +2252,16 @@ test_dir_random_weighted(void *testdata) /* Now try a singleton; do we choose it? */ for (i = 0; i < 100; ++i) { - choice = choose_array_element_by_weight(inp, 1); + choice = choose_array_element_by_weight(inp_u64, 1); tt_int_op(choice, OP_EQ, 0); } /* Now try an array of zeros. We should choose randomly. */ memset(histogram,0,sizeof(histogram)); for (i = 0; i < 5; ++i) - inp[i].u64 = 0; + inp_u64[i] = 0; for (i = 0; i < n; ++i) { - choice = choose_array_element_by_weight(inp, 5); + choice = choose_array_element_by_weight(inp_u64, 5); tt_int_op(choice, OP_GE, 0); tt_int_op(choice, OP_LT, 5); histogram[choice]++;

1 0

[tor/master] Move the ctime part of choose_array_element_by_weight into di_ops
by nickm＠torproject.org 12 May '16

12 May '16

commit e40cfc4425d1e173b5d122e38ab07dd798b11925 Author: Nick Mathewson <nickm(a)torproject.org> Date: Wed Apr 27 10:33:46 2016 -0400 Move the ctime part of choose_array_element_by_weight into di_ops This way it gets the ctime options. --- src/common/di_ops.c | 45 +++++++++++++++++++++++++++++++++++++++++++++ src/common/di_ops.h | 2 ++ src/or/routerlist.c | 35 +++-------------------------------- 3 files changed, 50 insertions(+), 32 deletions(-) diff --git a/src/common/di_ops.c b/src/common/di_ops.c index 5dfe828..e671af6 100644 --- a/src/common/di_ops.c +++ b/src/common/di_ops.c @@ -226,3 +226,48 @@ safe_mem_is_zero(const void *mem, size_t sz) return 1 & ((total - 1) >> 8); } +/** Time-invariant 64-bit greater-than; works on two integers in the range + * (0,INT64_MAX). */ +#if SIZEOF_VOID_P == 8 +#define gt_i64_timei(a,b) ((a) > (b)) +#else +static inline int +gt_i64_timei(uint64_t a, uint64_t b) +{ + int64_t diff = (int64_t) (b - a); + int res = diff >> 63; + return res & 1; +} +#endif + +/** + * Given an array of list of n_entries uint64_t values, whose sum is + * total, find the first i such that the total of all elements 0...i is + * greater than rand_val. + * + * Try to perform this operation in a constant-time way. + */ +int +select_array_member_cumulative_timei(const uint64_t *entries, int n_entries, + uint64_t total, uint64_t rand_val) +{ + int i, i_chosen=-1, n_chosen=0; + uint64_t total_so_far = 0; + + for (i = 0; i < n_entries; ++i) { + total_so_far += entries[i]; + if (gt_i64_timei(total_so_far, rand_val)) { + i_chosen = i; + n_chosen++; + /* Set rand_val to INT64_MAX rather than stopping the loop. This way, + * the time we spend in the loop does not leak which element we chose. */ + rand_val = INT64_MAX; + } + } + tor_assert(total_so_far == total); + tor_assert(n_chosen == 1); + tor_assert(i_chosen >= 0); + tor_assert(i_chosen < n_entries); + + return i_chosen; +} diff --git a/src/common/di_ops.h b/src/common/di_ops.h index 6e77b5c..f1050a0 100644 --- a/src/common/di_ops.h +++ b/src/common/di_ops.h @@ -42,6 +42,8 @@ void dimap_add_entry(di_digest256_map_t **map, const uint8_t *key, void *val); void *dimap_search(const di_digest256_map_t *map, const uint8_t *key, void *dflt_val); +int select_array_member_cumulative_timei(const uint64_t *entries, int n_entries, + uint64_t total, uint64_t rand_val); #endif diff --git a/src/or/routerlist.c b/src/or/routerlist.c index 620b614..b6247a1 100644 --- a/src/or/routerlist.c +++ b/src/or/routerlist.c @@ -2103,20 +2103,6 @@ scale_array_elements_to_u64(uint64_t *entries_out, const double *entries_in, #undef SCALE_TO_U64_MAX } -/** Time-invariant 64-bit greater-than; works on two integers in the range - * (0,INT64_MAX). */ -#if SIZEOF_VOID_P == 8 -#define gt_i64_timei(a,b) ((a) > (b)) -#else -static inline int -gt_i64_timei(uint64_t a, uint64_t b) -{ - int64_t diff = (int64_t) (b - a); - int res = diff >> 63; - return res & 1; -} -#endif - /** Pick a random element of n_entries-element array entries, * choosing each element with a probability proportional to its (uint64_t) * value, and return the index of that element. If all elements are 0, choose @@ -2125,8 +2111,7 @@ gt_i64_timei(uint64_t a, uint64_t b) STATIC int choose_array_element_by_weight(const uint64_t *entries, int n_entries) { - int i, i_chosen=-1, n_chosen=0; - uint64_t total_so_far = 0; + int i; uint64_t rand_val; uint64_t total = 0; @@ -2143,22 +2128,8 @@ choose_array_element_by_weight(const uint64_t *entries, int n_entries) rand_val = crypto_rand_uint64(total); - for (i = 0; i < n_entries; ++i) { - total_so_far += entries[i]; - if (gt_i64_timei(total_so_far, rand_val)) { - i_chosen = i; - n_chosen++; - /* Set rand_val to INT64_MAX rather than stopping the loop. This way, - * the time we spend in the loop does not leak which element we chose. */ - rand_val = INT64_MAX; - } - } - tor_assert(total_so_far == total); - tor_assert(n_chosen == 1); - tor_assert(i_chosen >= 0); - tor_assert(i_chosen < n_entries); - - return i_chosen; + return select_array_member_cumulative_timei( + entries, n_entries, total, rand_val); } /** When weighting bridges, enforce these values as lower and upper

1 0

[tor/master] Rename SOURCES to SRC for things in include.am
by nickm＠torproject.org 12 May '16

12 May '16

commit ef011099327e5547b4786e4c911b7f107aea8306 Author: Nick Mathewson <nickm(a)torproject.org> Date: Thu May 12 11:21:07 2016 -0400 Rename SOURCES to SRC for things in include.am --- src/common/include.am | 24 ++++++++++++------------ 1 file changed, 12 insertions(+), 12 deletions(-) diff --git a/src/common/include.am b/src/common/include.am index 96fc329..33baa12 100644 --- a/src/common/include.am +++ b/src/common/include.am @@ -62,16 +62,16 @@ else readpassphrase_source= endif -LIBOR_CTIME_A_SOURCES = \ +LIBOR_CTIME_A_SRC = \ src/ext/csiphash.c \ src/common/di_ops.c -src_common_libor_ctime_a_SOURCES = $(LIBOR_CTIME_A_SOURCES) -src_common_libor_ctime_testing_a_SOURCES = $(LIBOR_CTIME_A_SOURCES) +src_common_libor_ctime_a_SOURCES = $(LIBOR_CTIME_A_SRC) +src_common_libor_ctime_testing_a_SOURCES = $(LIBOR_CTIME_A_SRC) src_common_libor_ctime_a_CFLAGS = @CFLAGS_CONSTTIME@ src_common_libor_ctime_testing_a_CFLAGS = @CFLAGS_CONSTTIME@ $(TEST_CFLAGS) -LIBOR_A_SOURCES = \ +LIBOR_A_SRC = \ src/common/address.c \ src/common/backtrace.c \ src/common/compat.c \ @@ -92,7 +92,7 @@ LIBOR_A_SOURCES = \ src/common/src_common_libor_testing_a-log.$(OBJEXT) \ src/common/log.$(OBJEXT): micro-revision.i -LIBOR_CRYPTO_A_SOURCES = \ +LIBOR_CRYPTO_A_SRC = \ src/common/aes.c \ src/common/crypto.c \ src/common/crypto_pwbox.c \ @@ -104,17 +104,17 @@ LIBOR_CRYPTO_A_SOURCES = \ src/common/crypto_curve25519.c \ src/common/crypto_ed25519.c -LIBOR_EVENT_A_SOURCES = \ +LIBOR_EVENT_A_SRC = \ src/common/compat_libevent.c \ src/common/procmon.c -src_common_libor_a_SOURCES = $(LIBOR_A_SOURCES) -src_common_libor_crypto_a_SOURCES = $(LIBOR_CRYPTO_A_SOURCES) -src_common_libor_event_a_SOURCES = $(LIBOR_EVENT_A_SOURCES) +src_common_libor_a_SOURCES = $(LIBOR_A_SRC) +src_common_libor_crypto_a_SOURCES = $(LIBOR_CRYPTO_A_SRC) +src_common_libor_event_a_SOURCES = $(LIBOR_EVENT_A_SRC) -src_common_libor_testing_a_SOURCES = $(LIBOR_A_SOURCES) -src_common_libor_crypto_testing_a_SOURCES = $(LIBOR_CRYPTO_A_SOURCES) -src_common_libor_event_testing_a_SOURCES = $(LIBOR_EVENT_A_SOURCES) +src_common_libor_testing_a_SOURCES = $(LIBOR_A_SRC) +src_common_libor_crypto_testing_a_SOURCES = $(LIBOR_CRYPTO_A_SRC) +src_common_libor_event_testing_a_SOURCES = $(LIBOR_EVENT_A_SRC) src_common_libor_testing_a_CPPFLAGS = $(AM_CPPFLAGS) $(TEST_CPPFLAGS) src_common_libor_crypto_testing_a_CPPFLAGS = $(AM_CPPFLAGS) $(TEST_CPPFLAGS)

1 0