Hi all,
At the moment, Tor uses SHA1 for the running digests of circuit cell payloads.
Some of the prop224 code seems to use SHA256 for the digests for client to service rendezvous circuits. But that's not in the spec yet (see #22995 at [0]).
How and when do we plan to move away from using SHA1 in Tor circuits?
For non-onion service circuits, this would mean: * implementing support for SHA256 [1] circuit digests * adding a Relay protocol version 3 * teaching clients to use SHA256 digests with relays with Relay protocol >= 3
For onion service circuits, it's more complicated, because the following circuit types can't use relay versions from the consensus: * client to intro * service to rend * client to service (Using relay versions from the consensus leaks which consensus clients and services have, which reduces the anonymity set.)
Here are the upgrade mechanisms in prop224 at the moment, for both circuit protocol versions and any necessary handshake material:
client to intro: * the protocol version could be in a proto line to each intro point, but this isn't implemented yet * the handshake data can be in the link-specifiers (I think?)
service to rend * the protocol version could be in the EXT_FIELD in the INTRODUCE cell, but this isn't implemented yet * the handshake data can be in the link-specifiers (I think?)
client to service: * the protocol version is in the create2-formats in the descriptor * the handshake data is in HANDSHAKE_INFO in the RENDEZVOUS cells * SHA256 digests are implemented, but not documented in prop224 [0]
I suggest we make the following changes to prop224 to make this happen:
Protocol version information: * add the relevant relay protocol versions to the intro point section of the descriptor * put the relevant relay protocol versions in an EXT_FIELD in the INTRODUCE cell * check create2-formats contains all the version info we will need to change the client to service circuit protocol version
Downgrade resistance: * teach clients and services to use the highest common protocol between client/service and relay, excluding protocols that are below the minimum required protocol versions * work out how we will tell clients to no longer accept an old create2-formats line from a service
[0]: https://trac.torproject.org/projects/tor/ticket/22995 [1]: By SHA256, I mean "a good secure hash at the time"
T
-- Tim Wilson-Brown (teor)
teor2345 at gmail dot com PGP C855 6CED 5D90 A0C5 29F6 4D43 450C BA7F 968F 094B ricochet:ekmygaiu4rzgsk6n xmpp: teor at torproject dot org ------------------------------------------------------------------------
On 22 Jul (00:02:33), teor wrote:
Hi all,
At the moment, Tor uses SHA1 for the running digests of circuit cell payloads.
Some of the prop224 code seems to use SHA256 for the digests for client to service rendezvous circuits. But that's not in the spec yet (see #22995 at [0]).
That is not accurate. It uses SHA3, notice DIGEST_SHA3_256 in circuit_init_cpath_crypto():
if (is_hs_v3) { digest_len = DIGEST256_LEN; cipher_key_len = CIPHER256_KEY_LEN; cpath->f_digest = crypto_digest256_new(DIGEST_SHA3_256); cpath->b_digest = crypto_digest256_new(DIGEST_SHA3_256); } ...
David
On 22 Jul 2017, at 00:07, David Goulet dgoulet@ev0ke.net wrote:
On 22 Jul (00:02:33), teor wrote:
Hi all,
At the moment, Tor uses SHA1 for the running digests of circuit cell payloads.
Some of the prop224 code seems to use SHA256 for the digests for client to service rendezvous circuits. But that's not in the spec yet (see #22995 at [0]).
That is not accurate. It uses SHA3, notice DIGEST_SHA3_256 in circuit_init_cpath_crypto():
if (is_hs_v3) { digest_len = DIGEST256_LEN; cipher_key_len = CIPHER256_KEY_LEN; cpath->f_digest = crypto_digest256_new(DIGEST_SHA3_256); cpath->b_digest = crypto_digest256_new(DIGEST_SHA3_256); } ...
Oops, missed the "3".
We still need to think about how we migrate hashes, because all hashes break eventually: https://valerieaurora.org/hash.html
And I am concerned that we might be hard-coding either SHA1 or SHA3-256 in the v3 hidden service protocol.
The following handshakes depend on version information in the HSv3 protocol: * client to intro, * service to rend, and * client to service. They can't use version information from the consensus.
I've opened a ticket for this:
https://trac.torproject.org/projects/tor/ticket/23010
T
-- Tim Wilson-Brown (teor)
teor2345 at gmail dot com PGP C855 6CED 5D90 A0C5 29F6 4D43 450C BA7F 968F 094B ricochet:ekmygaiu4rzgsk6n xmpp: teor at torproject dot org ------------------------------------------------------------------------
Date: Sun, 23 Jul 2017 12:08:25 +1000 From: teor teor2345@gmail.com
We still need to think about how we migrate hashes, because all hashes break eventually: https://valerieaurora.org/hash.html
As a counterpoint, here is an updated history of collision *and* preimage attacks, and some commentary on them:
https://z.cash/technology/history-of-hash-function-attacks.html
No hash functions widely accepted as preimage-resistant have ever had their preimage resistance broken, with the lone exception of Snefru. (Wikipedia claims a preimage attack on MD5 with complexity 2^123.4, but if you follow the reference, you'll see that's the time estimate; the memory estimate is 2^45, raising the area*time product well above the advertised security level.)
No hash functions widely accepted as collision-resistant have had their collision resistance broken since Panama: not Whirlpool, not SHA-2, not SHA-3, none of the SHA-3 finalists, not BLAKE2. This is not to say it won't happen, but the extrapolation in https://valerieaurora.org/hash.html does not seem as well supported by the (admittedly quite heuristic) evidence as the page suggests.
I don't know how hash functions are used in every case in Tor. Probably not all uses rely on collision resistance at all; perhaps some that do can be adapted to rely instead only on target collision resistance, which even MD5 is still conjectured to exhibit.
And I am concerned that we might be hard-coding either SHA1 or SHA3-256 in the v3 hidden service protocol.
Maybe so, but are you hard-coding it in the v4 hidden serice protocol?
There's a serious complexity cost in implementing fine-grained algorithm agility: a combinatorial explosion of possible compositions and a wider attack surface for decisions by autonomous agents (or, worse, by inexpert users not competent to make crypto decisions).
I'm not saying don't make it easy to swap out SHA-3 if the time comes, just cautioning against wiring complexity into the protocol to have all the agents involved automatically make decisions on the fly about algorithm choices, without a clear benefit that can't be had in some simpler way.
On 23 Jul (12:08:25), teor wrote:
On 22 Jul 2017, at 00:07, David Goulet dgoulet@ev0ke.net wrote:
On 22 Jul (00:02:33), teor wrote:
Hi all,
At the moment, Tor uses SHA1 for the running digests of circuit cell payloads.
Some of the prop224 code seems to use SHA256 for the digests for client to service rendezvous circuits. But that's not in the spec yet (see #22995 at [0]).
That is not accurate. It uses SHA3, notice DIGEST_SHA3_256 in circuit_init_cpath_crypto():
if (is_hs_v3) { digest_len = DIGEST256_LEN; cipher_key_len = CIPHER256_KEY_LEN; cpath->f_digest = crypto_digest256_new(DIGEST_SHA3_256); cpath->b_digest = crypto_digest256_new(DIGEST_SHA3_256); } ...
Oops, missed the "3".
We still need to think about how we migrate hashes, because all hashes break eventually: https://valerieaurora.org/hash.html
And I am concerned that we might be hard-coding either SHA1 or SHA3-256 in the v3 hidden service protocol.
The following handshakes depend on version information in the HSv3 protocol:
- client to intro,
- service to rend, and
- client to service.
They can't use version information from the consensus.
I've opened a ticket for this:
I want to discuss couple of things about this ticket here (discussion on trac are really unpleasant...).
First of all, afaict, the hashing choice is not relevant to IP/RP/HSDir at all. The IP only routes cells between two circuits based on the authentication key it sees in the INTRODUCE1 cell that the client gets from the descriptor. The RP routes cells based on a cookie and the HSDir stores descriptor based on the blinded key it sees in the descriptor. If tomorrow we had to change to SHA9000, they wouldn't care.
That being said, switching the hash algorithm is a problem between the client and service.
The HS protocol version (prop224 introcuces v3) is bound to some crypto choices. It is not designed to be extensible in terms of crypto primitives. All of those are hardcoded and are part of the protocol: ed25519/curve25519 keys, AES-256 is stream encryption, SHAKE-256 our KDF and SHA3 for our hash function.
Negotiating cipher suites is a trap for all sorts of really bad issues (SSL is the prime example). So then we have versionning, different version uses different things (basically HS v2 and v3). And I think it is what you are proposing.
Let's imagine a world where next year SHA3 is broken and thus replaced by SHA4 which means that we need to make changes to the HS protocol. In a nutshell, we'll need to release a tor client and service that can use SHA4 in the HS protocol.
I guess the question you are asking here is: can we do that without bumping the HS protocol to v4? (Because bumping to v4, we hardcode SHA4 and job done). And remember, the version of the service is in the onion address so the client either know how to speak to it or doesn't.
Now back to trying to switch to SHA4 within the v3 protocol. We either put a field in the INTRO cell (for instance an EXTENSION) saying "oh I can speak SHA3 and SHA4". But then you end up with the problem of "which one the client uses in the INTRO cell?". We don't have protocol version negotiation so either the client sends all possibilities (huge cell) or try SHA3 and if fails, re-try with SHA4. Or client picks SHA4, tries the service and service can speak it or not. This is kind of crummy, all sorts of reachability issues, more load on the network and user will get hella confused on why there are failures all of the sudden for this service it was happilly connecting to before.
Second option, the service adds a hint somewhere in the descriptor saying "My hash algorithm is SHA4". I strongly think the service should NOT provide a choice because of the downgrade attack. And we must have a consensus param that provides the minimum required (as you proposed) so malicious service advertising SHA3 (that is broken in our example here) will get rejected by legit clients.
What this approach gives us here versus bumping the protocol version to v4? The only thing I can see is for the service to be able to keep its onion address intact which is kind of a big useful thing :P.
However, we end up with the problem of partition ... where some clients will reach the service that has upgraded and some will fail until they upgrade. Consensus param can help here that is we have a param that tells the service what hash algorithm it must use.
It's not an easy problem to be honest, seems most solutions will bring problems.
To be honest, the version in the address allows a very simple and easy transition because 1) the service can run a v3 and v4 in parallel with two addresses and can decide when to cut off the broken v3. It is actually a good way to transition if you ask me, you put a page on the v3 saying "hey, upgrade Tor and use this v4 address", 2) the client doesn't even touches the network if it can't speak v4 and 3) we avoid the version negotiation problem between client and service. But of course, downside is a new address.
Complexifying the protocol for something that can be fixed with a bump of the hidden service version protocol is something that I'm not comfortable with *unless* it provides an important plus value for the users in terms of security or/and usability.
Cheers! David.
T
-- Tim Wilson-Brown (teor)
teor2345 at gmail dot com PGP C855 6CED 5D90 A0C5 29F6 4D43 450C BA7F 968F 094B ricochet:ekmygaiu4rzgsk6n xmpp: teor at torproject dot org
tor-dev mailing list tor-dev@lists.torproject.org https://lists.torproject.org/cgi-bin/mailman/listinfo/tor-dev
Hi all,
This thread ended up covering a lot of details of Tor crypto. And there are a lot of details! (I'm sorry this email is so long.)
I focused on the circuit digest hash, but I wanted to talk about circuit crypto in general.
So I'm going to focus my reply on how upgrading circuit crypto has worked in the past, using the example of TAP and ntor. And then we can think about how we want it to work in future.
Tor was originally created with TAP as the circuit crypto protocol. But it wasn't very good. So we added ntor circuit crypto to Tor.
From 0.2.4 in 2013 [0], clients used the ntor onion keys in relay descriptors, after checking a consensus parameter. Then in 0.2.9 (3 years later) [0], we required ntor for all relay descriptors and most client circuits.
We wanted to make all client circuits use ntor, but some parts of some hidden service circuits were stuck with TAP (or similar): * client to intro point circuits * service to rendezvous point circuits, and * client to hidden service "circuits".
This happened because the hidden service protocol only uses the relay details from hidden service descriptors, INTRODUCE cells, and RENDEZVOUS cells, and the protocol only had TAP onion keys (or similar).
(Clients can't use the ntor keys from the consensus, because there's no guarantee that the client and service have the same consensus. And they can't optionally use ntor from the consensus, because that can leaks the consensus they have.)
We think it is ok for the final hop on some circuits to use TAP, because the other hops use ntor. (We are more concerned about Tor2web and single onion services, which use single-hop circuits. But there's still an outer TLS layer.)
We will finally stop using TAP when we stop using v2 hidden services. This could happen when we stop supporting 0.2.9 or 0.3.3-ish around 2020 [0] (7 years later). So it took a lot of time to upgrade circuit crypto, because if we had to create a new hidden service protocol to do it.
Now we've seen how hard it was to get rid of TAP, let's talk future upgrades:
On 24 Jul 2017, at 00:00, David Goulet dgoulet@ev0ke.net wrote:
First of all, afaict, the hashing choice is not relevant to IP/RP/HSDir at all. The IP only routes cells between two circuits based on the authentication key it sees in the INTRODUCE1 cell that the client gets from the descriptor. The RP routes cells based on a cookie and the HSDir stores descriptor based on the blinded key it sees in the descriptor. If tomorrow we had to change to SHA9000, they wouldn't care.
But the circuit crypto depends on the onion key in the hidden service descriptor and cells (see above), so we can't just change it tomorrow. Do we want to hard code a particular version of circuit crypto in the hidden service protocol?
(TAP for v2, ntor for v3)
Maybe this is ok, if the underlying hidden service crypto is still secure.
That being said, switching the hash algorithm is a problem between the client and service.
The HS protocol version (prop224 introcuces v3) is bound to some crypto choices. It is not designed to be extensible in terms of crypto primitives. All of those are hardcoded and are part of the protocol: ed25519/curve25519 keys, AES-256 is stream encryption, SHAKE-256 our KDF and SHA3 for our hash function.
The v3 client to service crypto seems like an OK choice to me. (But I am not a cryptographer.)
But we still need to think about the ntor circuit crypto we're using in the other parts of the protocol.
Negotiating cipher suites is a trap for all sorts of really bad issues (SSL is the prime example). So then we have versionning, different version uses different things (basically HS v2 and v3). And I think it is what you are proposing.
The first time we upgraded circuit crypto, it took us 7 years to phase it out, because we hard-coded it in the hidden service protocol. Are we ok with it taking this long next time we upgrade circuit crypto?
If we want circuit crypto upgrades to be faster, are we ok with adding complexity to the hidden service protocol? Are we ok with the risk of downgrade attacks?
If my original proposal is a bad idea, I'm happy to drop it. But let's decide that knowing what happened last time.
Let's imagine a world where next year SHA3 is broken and thus replaced by SHA4 which means that we need to make changes to the HS protocol. In a nutshell, we'll need to release a tor client and service that can use SHA4 in the HS protocol.
Since we support LTS releases for 3 years, it would take us at least 3.5 years to phase out old crypto protocols from the hidden service protocol. Or, we would have to add a major new feature to a LTS release. Or we would have to kill off some LTS features early.
The alternative is adding complex version negotiation to LTS releases in advance, and *hoping* it supports the upgrades we want to make to the crypto. That doesn't seem great, either.
I guess the question you are asking here is: can we do that without bumping the HS protocol to v4? (Because bumping to v4, we hardcode SHA4 and job done). And remember, the version of the service is in the onion address so the client either know how to speak to it or doesn't.
I don't mind: a version bump is ok, but it takes time.
Now back to trying to switch to SHA4 within the v3 protocol. We either put a field in the INTRO cell (for instance an EXTENSION) saying "oh I can speak SHA3 and SHA4". But then you end up with the problem of "which one the client uses in the INTRO cell?". We don't have protocol version negotiation so either the client sends all possibilities (huge cell) or try SHA3 and if fails, re-try with SHA4. Or client picks SHA4, tries the service and service can speak it or not. This is kind of crummy, all sorts of reachability issues, more load on the network and user will get hella confused on why there are failures all of the sudden for this service it was happilly connecting to before.
Yes, this is very complicated. Maybe we shouldn't allow crypto upgrades in v3 hidden services.
Second option, the service adds a hint somewhere in the descriptor saying "My hash algorithm is SHA4". I strongly think the service should NOT provide a choice because of the downgrade attack. And we must have a consensus param that provides the minimum required (as you proposed) so malicious service advertising SHA3 (that is broken in our example here) will get rejected by legit clients.
But it looks like we've left room for some crypto upgrades in the v3 protocol.
v3 hidden service descriptors have "desc-auth-type", "create2-formats", and ONION_KEY_TYPE fields. [1] [2] [3]
They also have "legacy-key", "legacy-key-cert", and AUTH_KEY_TYPE to allow the use of old intro points. [4] [5]
So do we want crypto upgrades, or not?
(We also have extensible link specifiers and other extension fields. I think this is ok, because it means we can add new kinds of addresses and other non-crypto features.)
What this approach gives us here versus bumping the protocol version to v4? The only thing I can see is for the service to be able to keep its onion address intact which is kind of a big useful thing :P.
However, we end up with the problem of partition ... where some clients will reach the service that has upgraded and some will fail until they upgrade. Consensus param can help here that is we have a param that tells the service what hash algorithm it must use.
So an alternative proposal is this:
Let's hard-code all the v3 hidden service protocol crypto, and remove (or hard-code) the following fields: * "desc-auth-type" * "create2-formats" * ONION_KEY_TYPE
That way we don't support version upgrades. But maybe we make writing v4 hidden services easier by changing a few constants.
I'm not sure what to do about: * "legacy-key" * "legacy-key-cert" * AUTH_KEY_TYPE
So do we want crypto upgrades on intro points, or not? If so, how will we eventually phase them out, and prevent downgrade attacks? (Do we need to phase them out?)
[0]: https://trac.torproject.org/projects/tor/wiki/org/teams/NetworkTeam/CoreTorR... [1]: https://gitweb.torproject.org/torspec.git/tree/proposals/224-rend-spec-ng.tx... [2]: https://gitweb.torproject.org/torspec.git/tree/proposals/224-rend-spec-ng.tx... [3]: https://gitweb.torproject.org/torspec.git/tree/proposals/224-rend-spec-ng.tx... [4]: https://gitweb.torproject.org/torspec.git/tree/proposals/224-rend-spec-ng.tx... [5]: https://gitweb.torproject.org/torspec.git/tree/proposals/224-rend-spec-ng.tx... https://gitweb.torproject.org/torspec.git/tree/proposals/224-rend-spec-ng.tx... https://gitweb.torproject.org/torspec.git/tree/proposals/224-rend-spec-ng.tx...
T
-- Tim Wilson-Brown (teor)
teor2345 at gmail dot com PGP C855 6CED 5D90 A0C5 29F6 4D43 450C BA7F 968F 094B ricochet:ekmygaiu4rzgsk6n xmpp: teor at torproject dot org ------------------------------------------------------------------------
-
David Goulet -
Taylor R Campbell -
teor