Proposal: DHT Announcements

[zugz]

This is a proposal for replacing the onion. Based on an original proposal by
@GrayHatter. Comments and suggestions welcome!

https://github.com/zugz/tox-DHTAnnouncements/

[hugbubby]

404'd URL? Think you meant: https://github.com/zugz/tox-DHTAnnouncements/

[zugz]

* Monday, 2018-11-05 at 09:57 -0800 - hugbubby <notifications@github.com>:

404 url?

Oops... will fix, thanks!

[sudden6]

The Ping ID is generated as in the onion: it is the SHA256 hash of some per-node secret bytes, the current time rounded to 20s, the searched key in the request, and the requester's DHT public key and sender IP/Port.

Wouldn't it be better to use a proper HMAC instead of just concatenating with the secret bytes? I recently learned concatenating SHA256 with secrets can lead to "length extension" attacks, but I'm not sure this applies here.

[sudden6]

a DHT node should accept any Store Announcement Request and store the announcement indexed by the announcement public key with a lifetime of 300 seconds

Is this 300s storage duration set in stone or some optimal value? Because in regards to mobile this should probably be as long as possible to keep devices in deep sleep as long as possible. Personally I would double or triple this value.

[sudden6]

Regarding https://github.com/zugz/tox-DHTAnnouncements/blob/master/DHTAnnouncements.md#shared-announcements

As far as I understand, this is to reduce the announce traffic on the DHT and the storage requirements in the DHT at some cost of privacy (friends can with some effort get IPs of our other friends), right?

This example is based on my own contact list, with total 50 contacts and about ~15 that are regularly online, the rest probably abandoned.

If I understand the proposal correctly, the shared announcement key is changed on every delete of friend. So as I regularly create test ToxIDs and add them it is continuously changing, but since a lot of my contacts don't come online I have to do an individual announcement to them.

I could not find any sentences describing any privacy improvements with shared announcements.

I argue, that it may not be worth the complexity and possible security implications to use shared announcements for user clients over individual announcements for a reduction of 50 to 35 announcement locations. I think this could be useful for bots since they probably need to purge offline friends more aggressively anyway.

We send Data Search requests once every 3 seconds to nodes on our list which we are not announced to, and once every 120 seconds to those we are announced to.

Again, are these fixed or optimal values? Because 3 seconds sounds like a no-go for ever trying to use the DHT on mobile directly. Is there a reason we need to announce this often?

Migration

I prefer the smooth road here. I think it will be really hard to convince users to switch "all at once". Would it be possible to gather statistics at e.g. some popular bots about the distribution of "old" vs "new" lookup traffic? If so, we could use this as a metric when to turn of the old system once enough people have migrated, but I guess this will be in the range of 1-2 years :/

[zugz]

* Monday, 2018-11-05 at 20:13 +0000 - sudden6 <notifications@github.com>:

Wouldn't it be better to use a proper HMAC instead of just concatenating with the secret bytes? I recently learned concatenating SHA256 with secrets can lead to "length extension" attacks, but I'm not sure this applies here.

It does apply, but it isn't a problem here because the input is of fixed length - at least as long as you understand IP/Port to mean the full 19 byte IP/Port even if it's IPv4 (which is how it's done in the current code in the onion). But probably you're right that it would be better to use HMAC-SHA256 here and everywhere, just so we don't have to think about the effects of length extension (though I did).

[zugz]

* Monday, 2018-11-05 at 12:18 -0800 - sudden6 <notifications@github.com>:

Is this 300s storage duration set in stone or some optimal value?

I made it up, and it isn't set in stone at all. The problem with having it too large is just that our announcements will stay for longer after we leave the network, causing our friends to produce some wasted traffic trying to contact us. Possibly it would be better to have the announce request include a requested timeout, which will be honoured up to some reasonable maximum (say 900s), so we'll have room when we come to think about letting mobile users sleep.

[zugz]

* Monday, 2018-11-05 at 12:56 -0800 - sudden6 <notifications@github.com>:

Regarding https://github.com/zugz/tox-DHTAnnouncements/blob/master/DHTAnnouncements.md#shared-announcements As far as I understand, this is to reduce the announce traffic on the DHT and the storage requirements in the DHT at some cost of privacy (friends can with some effort get IPs of our other friends), right?

Yes. Getting IPs of friends of friends is possible anyway, though. Easiest alternative way, assuming you're on the DHT: attacker positions themself near your DHT key and listens for searches for your DHT key, which friends make in the process of connecting to you.

since a lot of my contacts don't come online I have to do an individual announcement to them.

Yes, that is a problem. I don't have a nice solution. One not nice solution would be to try to communicate to the user that there are bandwidth costs associated to their inactive friends, so they can choose to delete them if this worries them. Another would be to automatically stop announcing to / searching for them after a period of inactivity (a year?), again communicating this to the user somehow and letting them override it. Another, not really a solution at all, would be to not automatically regenerate the shared key on deleting a friend, but rather give the user the option to do so, and communicate to them why they might want to do so (which is because if they don't, the ex-friend could still determine their IP address at any future time) and why they might not (bandwidth). For example, rather than actually delete friends you could first "block" them (no change in shared key) then as a separate step "purge" blocked friends (meaning regenerating the shared key), with the explanations being associated with this purge option. I don't much like the idea of encouraging less than maximally privacy-preserving behaviour this way, though. Another partial solution would be to just announce less vigorously for long-inactive friends, on the basis that it's possibly not so much of a problem if they don't reliably find you quickly. Maybe just by reducing the number of nodes announced to. In theory, you could even announce just at a single node and still be found. What do you think of that?

I could not find any sentences describing any privacy improvements with shared announcements.

There are none, it's purely for efficiency.

I argue, that it may not be worth the complexity and possible security implications to use shared announcements

I don't think there are security implications, properly understood. Tox can not protect the information of which IP addresses are friends with which. It does involve some complexity, but I think it's worth it.

I think this could be useful for bots since they probably need to purge offline friends more aggressively anyway.

Why useful? Anyway, bots would probably want to use the public announcements system rather than shared announcements.

> We send Data Search requests once every 3 seconds to nodes on our > list which we are not announced to, and once every 120 seconds to > those we are announced to. Again, are these fixed or optimal values? Because 3 seconds sounds like a no-go for ever trying to use the DHT on mobile directly. Is there a reason we need to announce this often?

This is copied directly from the onion. The idea is that you search rapidly like this until you get close enough to the target key that you find nodes who will accept your announcements. The only problem is if one of the 8 closest nodes refuses the announcement, because it's full or uncooperative. I guess there should be a backoff system to handle that case - say linear backoff as with searches, up to a max of 120s?

> Migration I prefer the smooth road here. I think it will be really hard to convince users to switch "all at once". Would it be possible to gather statistics at e.g. some popular bots about the distribution of "old" vs "new" lookup traffic?

Yeah, that should be straightforward.

If so, we could use this as a metric when to turn of the old system once enough people have migrated, but I guess this will be in the range of 1-2 years :/

Yeah. I guess one question to ask is: since we know the onion doesn't serve its purpose (#1121), would we really be doing right by users if we encouraged them to keep using it?

[sudden6]

Possibly it would be better to have the announce request include a requested timeout, which will be honoured up to some reasonable maximum (say 900s), so we'll have room when we come to think about letting mobile users sleep.

I think that would be even better I think. But on a second thought we can probably introduce this later and get the first version running faster.

Another partial solution would be to just announce less vigorously for long-inactive friends, on the basis that it's possibly not so much of a problem if they don't reliably find you quickly. Maybe just by reducing the number of nodes announced to. In theory, you could even announce just at a single node and still be found. What do you think of that?

I think this would be a quite good solution, maybe for long offline friends half the announcement nodes will do.

Will answer the rest once I have time to properly read your answers.

[sudden6]

Why useful? Anyway, bots would probably want to use the public announcements system rather than shared announcements.

Scratch that, I misunderstood how public announcements work.

Yes, that is a problem. I don't have a nice solution.

I agree, the shared announcement approach seems preferable to all the approaches which require user interaction. IMO the user shouldn't have to deal with that.

What do you think about implementing this in a two step approach? step 1: only individual announcements, probably faster to implement and then we can already test bandwidth requirements. step 2: implement shared announcements if needed, AFAICT this would be transparent to clients, so we can implement it whenever we like

would we really be doing right by users if we encouraged them to keep using it?

As far as I understand, removing the onion and implementing this would result in a protocol break that leaves old users unable to connect. One of Toxs major problems is already that nobody uses a messenger where they can't talk to anyone, so splitting up the already small user base is making that worse. I think we should however inform the users about this problem as much as possible, to get them to update to the new (better) system as quickly as possible.

[zugz]

* Wednesday, 2018-11-07 at 05:09 -0800 - sudden6 <notifications@github.com>:

What do you think about implementing this in a two step approach?

Yes, that makes sense.

As far as I understand, removing the onion and implementing this would result in a protocol break that leaves old users unable to connect.

Yes.

I think we should however inform the users about this problem as much as possible, to get them to update to the new (better) system as quickly as possible.

The thing is, even if we just have one friend left over who we don't know isn't still using only the onion (which I guess will often be the case forever, since it's enough to have a friend who never connects at all), then we have to keep searching on the onion for them, and that's enough to compromise our privacy. Since we don't announce the easiest attacks won't work, but still a sybil attacker could connect our DHT key to our long term key. Maybe it's possible to communicate this in clients - have it only search on the onion in "legacy mode", and have clients warn prominently when they're running in legacy mode, and explain the consequences of disabling. Just chopping off the onion entirely would definitely be simpler. But I can ceratinly see it making people unhappy, and probably someone would maintaing an onion-preserving fork... (They might do that anyway - surely not everyone will be happy to give up friend requests?).

[sudden6]

Just chopping off the onion entirely would definitely be simpler. But I can ceratinly see it making people unhappy, and probably someone would maintaing an onion-preserving fork... (They might do that anyway - surely not everyone will be happy to give up friend requests?).

I'm pretty convinced just removing the onion will not fly well. I think to replace friend requests we could add something on top of public announcements, to get the same feature we have with the current NoSpam. Communicating the drawbacks of this to the users will probably be fun though.

[GrayHatter]

I'd like to break this down to the simplest form.

The onion, doesn't provide the feature that it was created for. It's a large block of code that requires work to maintain, and is the partial source of a number of the current bugs in Tox (battery usage, and data required). So it should just be removed now, like a bandage.

So, do we keep the complicated, and expensive code base that doesn't do what it's supposed to be doing? Thus creating the illusion of it doing something good, and delaying iteration on a feature that we actually need, like meaningful and usable friend finding?

Context:
Because The onion, can't really even be used to obscure the source IP in friend requests past the first connection. We should drop the onion, and just make friend requests public the same way meeting requests are. People who need IP obscurity can still tunnel tox through tor as they should be doing already.

Users who don't want friend requests, can use one time use IDs they can give to friends, or make "public", and their "real long term key" if they don't care about friend requests being public.

In the meantime, friend requests are CURRENTLY complicated, and IMO out of scope for this issue. The topic at hand, is only the continued existence of the onion.

[GrayHatter]

We don't need to notify users... People who are using tox, generally, are technologically adept. If something stops working, one of the first things you do is check for updates. What Toxcore should make sure it does, is try to work with as many clients as possible to make sure all clients are able to release the new version at the same time. Speaking for uTox, New versions display a changelog to the user. Clients can then inform the user of the new change, and that friends might not appear online until they update.

Responsible clients will pre-release an update about a month before the next update to make sure everyone is warned.

Keeping users up to date is the responsibility of the clients, not the library. Toxcore needs to make sure it's doing it's job, which is not to stop others from bad decisions, but to not make any itself. The onion is problematic.