search

cloudflare / boringtun

Userspace WireGuard® Implementation in Rust
BSD 3-Clause "New" or "Revised" License
5.92k stars 397 forks source link

Use non-sequential peer indices #308

Closed cbranch closed 1 year ago

cbranch commented 1 year ago

Resolves #55 about as much as is possible given the design constraints of boringtun peer handling.

boringtun is not intended to provide unlinkable sessions, particularly given that source addresses remain constant across sessions. We can at least obscure the details of the number of peers registered with a server.

Noah-Kennedy commented 1 year ago

Could you add more comments explaining what you are doing? I can follow what is going on here, but its a bit dense with the bit twiddling.

cbranch commented 1 year ago

Added some exposition in the code itself. We're using xorshift to generate a random-looking sequence with period (2^24-1) so that it's not completely obvious how many peers are configured in the server.

jeff-hiner commented 1 year ago

I realize this has already been merged, but is there a reason we don't just generate a random u32 using something like OsRng::next_u32 and then just mask off the upper bits? Why the custom PRNG?

cbranch commented 1 year ago

Generating indices randomly makes adding a new peer an exponential time operation, or requires us to implement an algorithm to find the closest free index to the randomly generated one.

jeff-hiner commented 1 year ago

Why would it be exponential time? Generating a random u32 (or using a hash of a salted counter) is O(1), and if you have a collision you simply advance the counter and retry. Collision chance within a 24-bit space for a should be very small.