Improving DOS protection and preventing channel ID collisions

[afontenot]

This issue was prompted by some discussion on HN: https://news.ycombinator.com/item?id=24514725

Is your feature request related to a problem? Please describe. The shared secrets are generated from a wordlist by default, and the first three characters of the secret is used to define a channel on the relay. The issue is that the wordlist only has ~1600 words, and these words have only ~900 three beginning characters. The birthday problem tells us that only about 35 simultaneous users are needed on the server before someone's connection will randomly fail because they ended up with the same three character prefix as a previously established connection. This seems obviously bad.

Worse still, an attacker could completely DOS a relay by hogging only 900 prefixes, and cause serious problems with much less than that. (I think anyone using uppercase letters or symbols in a custom secret might be okay, so I'm not sure what the "real" limit is, but this is still clearly a problem.)

Describe the solution you'd like Use the Magic Wormhole solution: the client asks the relay to assign a channel, and the lowest natural number currently unassigned is sent to the client to be used (it's prepended to the shared secret). This solves the problem and is better in another way: a three letter prefix is usually enough to entirely disambiguate the first word, so the first word of the shared secret is entirely useless from the point of view of someone who doesn't trust the relay. number-word1-word2-word3 would be much more secure than word1-word2-word3 is currently, for that reason.

Describe alternatives you've considered An interim solution would be to switch to using the entire first word of the secret to define a channel. At least that would almost double the number of channels, and the first word of the shared secret is useless anyway from a security perspective.

If having the relay choose the channel is undesirable, perhaps a mnemonic with a larger wordlist could be used along with the first-word = channel solution. I'd think you'd want at least tens of thousands of channels, ideally. Maybe pick a random integer from 0-99 and add that to the first word, using the current wordlist. That would get you ~160000 channels.

I suggest not using a hash (or other derivative) of the shared secret as a channel identifier. The current space of possible secrets is small enough that creating rainbow tables would be very easy.

[schollz]

The birthday problem tells us that only about 35 simultaneous users are needed on the server before someone's connection will randomly fail. This seems obviously bad.

Can you explain more - this doesn't seem obviously bad? I don't think croc ever has even 2 simultaneous users on the public relay, but more importantly its not a huge problem (except convenience) that it fails. You can simply try again on a failure, security is not compromised.

Worse still, an attacker could completely DOS a relay by hogging only 900 prefixes

This is potentially a problem. But the solution of using the entire word basically just increases the number of channels available to ~1600 and doesn't fix that the relay is getting DOSed. I think a better solution might be to add IP mitigation (rate-restrict, or deny incoming >2 connections from the same IP). But honestly, I think DOS protection might be a bit overzealous at this point. Everyone can run their own relays and they are unlikely to have such problems and the public relay just doesn't have much traffic to require this I think. Let me know what you think.

[afontenot]

I don't think croc ever has even 2 simultaneous users on the public relay, but more importantly its not a huge problem (except convenience) that it fails.

I suppose what I'm thinking is that it makes sense to plan for more users than this. What's the limit, 10, 15 at a time? I regularly see channel IDs higher than that with wormhole. If you get to a point where you have just 15 simultaneous users on average, you should expect ~1/45 users to experience a collision. It just seems really high. Granted, the failure case isn't that bad (just try again), but feels like an ugly workaround.

Wormhole users won't ever experience this issue because of how the channels are allocated. You said on the HN thread that Wormhole was limited to 99 channels, but that appears to be wrong. What the user in https://github.com/warner/magic-wormhole/issues/107 is getting at is that most connections at present have a channel ID < 99, which means you could ruin the experience for users by simply trying to connect to these channels over and over. (There's nothing preventing you - or Wormhole - from choosing a larger channel ID.)

On HN you mentioned that a must-have feature is that croc works over LAN when the relay can't be accessed. That's easy enough, if the request to be assigned a channel times out, fall back to having the client pick one.

Aside: there are really two different DOS attacks to worry about. One attack is a user racing legitimate receivers to be the first to connect, and that's an issue for both croc and wormhole. It's also resource intensive, because you have to constantly be trying all ~900 channels for croc. You're sure to be disruptive but not sure to prevent 100% of connections. Then there's a second attack, where you passively claim (as a sender) all ~900 channels and hold them for as long as possible, restarting them immediately if the server drops you. This attack is easy and low-resource, and is only possible with croc, not wormhole. This latter attack is the one I'm more concerned with. (Note that if you have a botnet, IP banning will still basically prevent the first method because each host will still have to initiate a lot of connections. But it won't work to stop the second method, because you can't tell legitimate senders with one or two channels from illegitimate ones. That's why it's more concerning.)

I'm also worried about there being a difference between real and apparent security with croc. Users might think a three-word shared secret seems pretty good, but as I mentioned above, if you don't trust the relay it's really only a two word secret since the correspondence between three-character prefixes and wordlist words is almost 1:1.

[schollz]

I guess I don't really have a problem with anything your describing to improve croc regarding preventing DOS and preventing user collisions. What you are describing seems to be multiple improvements:

1. Sending clients get assigned channel ID from relay, and on fail create their own channel ID.
2. Increase size of channel ID which can help prevent DOS attacks and also make it even harder for a malicious relay to do a correct guess in one-shot
3. Preventing DOS by adding in IP rate limiting

If you'd like to submit PRs for any of these, I'd happily accept them!

[afontenot]

I'll try to have a look at (1), but it will be contingent on me finding the time.

[emaciasuno]

You can add a numeric password generated algorithm with the already existing world list making the password generated combinations into O(n^2) instead of O(n) making the password generated combination much harder to have a channel ID collection.

[github-actions[bot]]

Stale issue message