Refactoring and improvements

[piegamesde]

See commit log. Generally speaking, this changes nothing on the protocol itself. Just the documentation.

[piegamesde]

Thanks for the review. Ideally, none of the important information should be lost in the rewrite, so I'll go and add the missing bits

[piegamesde]

I added a commit that deprecates the current_cli_version field in the welcome message from the server. Of course the server will continue to provide it anyways, but it has no value to any other client other than the Python implementation. Should it be desirable we can create a new replacement for the other clients in the future.

[meejah]

I don't actually see anywhere in the current mailbox code where it sends a current_cli_version (all I did is searched for that string but don't find anything). Anyway, fine to mention it here as "deprecated" (as you point out it's not going to work as-is for multiple kinds of clients anyway).

edit: github search was apparently broken, or I was, when I did that search -- it does send it.

[piegamesde]

Unless anybody has strong objections, I'm inclined to merge this now. As this is about documentation and does not make any substantial changes to the protocol, I don't think this requires doing an FCP and stuff.

[meejah]

I haven't re-reviewed since the force-push, and I think at least the 65536 number should be changed right? (to 32k or 45k depending on how you word it?)

[piegamesde]

The force-push only added " at least once" as a clarification, see https://github.com/magic-wormhole/magic-wormhole-protocols/compare/95a1e65b510c88ebf552cd057ed27de26011456e..1286cb4159a048918bd2cfdff54708162da7d0ca.

The 65536 should be correct, because it is an average/expected value. (Okay actually it should be 65535, but that's not your point.) After 32768 attempts you'd expect 0.5 successes on average, which is not the same as a 50% probability for a single success.

[meejah]

The force-push only added " at least once" as a clarification, see https://github.com/magic-wormhole/magic-wormhole-protocols/compare/95a1e65b510c88ebf552cd057ed27de26011456e..1286cb4159a048918bd2cfdff54708162da7d0ca.

It would be a lot easier to see this without force-pushes ...

The 65536 should be correct, because it is an average/expected value. (Okay actually it should be 65535, but that's not your point.) After 32768 attempts you'd expect 0.5 successes on average, which is not the same as a 50% probability for a single success.

I'm more confused then, because the text says "any successful attack implies 65536 failed attempts on average, which will quickly be noticed" but the discussion justifies 32k or 45k. Surely on average there are less failures than that? (Or, please explain in the text).

[piegamesde]

How about "From a perspective of the service, it will see on average one success and 65535 failures for every 2^16 attempts. Therefore, brute force attacks are inherently very disruptive of the service, and thus easy to detect."

Surely on average there are less failures than that?

No, the chance of guessing a password with 16 bits strength in a single attempt is precisely 2^-16.

[wuan]

We could simply say that an attacker would need to do more than 300k attempts to be at least 99% sure to have one successful attempt (Or more than 196k for at least 95%).

2^16 attempts would only lead to 63% probability, which is not really high.

[maralorn]

We could simply say that an attacker would need to do more than 300k attempts to be at least 99% sure to have one successful attempt (Or more than 196k for at least 95%).

I wouldn’t recommend that. This looks like we are putting the bar too high. Like, “Yeah, they might hack the connection. But they can’t be sure to definitely hack the connection, so we are fine …”

[wuan]

I wouldn’t recommend that. This looks like we are putting the bar too high. Like, “Yeah, they might hack the connection. But they can’t be sure to definitely hack the connection, so we are fine …”

An attacker who wants to have an acceptable probability (> 95%) to succeed will need to do that many attempts, that is just the math. On the other hand we can calculate the number of malicious attempts that we need to detect in order to keep the probability low, e. g. < 3000 to be smaller than 5 %. But then we will also need to have an idea about how to detect those attacks.

There is an extremely small probability to guess the password already on the initial attempt. This could be overcome by adding a verification message from the receiver back to the sender which can be used to identify the receiver before the data is transmitted.

[meejah]

There is an extremely small probability to guess the password already on the initial attempt. This could be overcome by adding a verification message from the receiver back to the sender which can be used to identify the receiver before the data is transmitted.

This feature already exists.

[meejah]

The chance of rolling a "1" on a d6 is 1/6 .. but we don't say that "in order to roll a 3 there will be on average 5 failures". (Or at least, this framing isn't familiar to me ... but statistics classes were a long time ago ;).

Put another way: the attacker will not keep guessing once they have succeeded, so on average they will only need to try half that number of times. Only the least-lucky attacker will have 65535 failures first (well, a strictly least lucky attacker will have an infinite number of failures if we channel H2G2 I suppose because they're so unlucky they will never succeed ;) ).

Anyway, your last suggestion sounds more clear (at least it highlights that the service should see a lot of failures if someone is doing a lot of guessing). I still feel like it's giving an incorrect impression that an attacker will definitely steal one connection after 65k tries (or that they need to on average try 65k times to get one, which they don't). That is, by your own reasoning from the "failure" side it should be 45425 (i.e. the first time the chance of failure goes below 50%) so why are you now using 65k here? If you have different reasoning, please respond in the thread about that.

(But, if you wanted to look from the failure way, after 65536 guesses there's still a decent chance of not getting any correct: if we insist on the attacker being unsuccessful every time, they have a (65535/65536) ^ 65536 = 0.37 chance of continuing to be unsuccessful after 65k guesses).

No matter what, I think the text should include some math at least as a footnote to justify whatever number is put here, and why. The important takeaway is that an attacker would have to do "a lot" of guesses.

[piegamesde]

but we don't say that "in order to roll a 3 there will be on average 5 failures"

the correct phrase here would be "for every 3 roll there will be on average 5 failures". Which indeed is not a very useful statement in the context of most dice games.

Anyways, I've reworked the paragraph again. I removed the 45000 number, because it doesn't help that it's correct (AFAICT) if it's not intuitive to interpret what it represents; and the new version still gets the relevant point across IMO.