[tor-dev] prop224: Deprecating SHA1 circuit digests

Mon Jul 24 13:07:19 UTC 2017

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 at 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/CoreTorReleases
[1]: https://gitweb.torproject.org/torspec.git/tree/proposals/224-rend-spec-ng.txt#n1041
[2]: https://gitweb.torproject.org/torspec.git/tree/proposals/224-rend-spec-ng.txt#n1175
[3]: https://gitweb.torproject.org/torspec.git/tree/proposals/224-rend-spec-ng.txt#n1573
[4]: https://gitweb.torproject.org/torspec.git/tree/proposals/224-rend-spec-ng.txt#n1249
[5]: https://gitweb.torproject.org/torspec.git/tree/proposals/224-rend-spec-ng.txt#n1349
     https://gitweb.torproject.org/torspec.git/tree/proposals/224-rend-spec-ng.txt#n1476
     https://gitweb.torproject.org/torspec.git/tree/proposals/224-rend-spec-ng.txt#n1675

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
------------------------------------------------------------------------

-------------- next part --------------
A non-text attachment was scrubbed...
Name: signature.asc
Type: application/pgp-signature
Size: 801 bytes
Desc: Message signed with OpenPGP
URL: <http://lists.torproject.org/pipermail/tor-dev/attachments/20170724/59d79387/attachment.sig>