[tor-bugs] #1839 [BridgeDB]: Rotate available bridges over time

[Tor Bug Tracker & Wiki]

#1839: Rotate available bridges over time
-----------------------------+----------------------
     Reporter:  arma         |      Owner:  isis
         Type:  enhancement  |     Status:  assigned
     Priority:  normal       |  Milestone:
    Component:  BridgeDB     |    Version:
   Resolution:               |   Keywords:  easy
Actual Points:               |  Parent ID:
       Points:               |
-----------------------------+----------------------

Comment (by isis):

 Replying to [comment:3 sysrqb]:
 > Also, ideally, the subset of the bridges won't rotate in a predictable
 order, either.

 Actually, we probably shouldn't have to worry about this too much.

 If we implement this with the rotation period as something like either
 `"YEAR || WEEK_NUMBER"` or a rounded-off timestamp, and append it to the
 truncated client IP and then HMACed, then — working in the random oracle
 model — the probability of a collision is negligible, dependent ultimately
 on the key/IV/security parameter size, approximately {{{Pr[HMAC] ≤ 1ᵏ}}}
 where `k` is the security parameter (in our case, 256, which is the
 bitlength of the master HMAC key, `MASTER_KEY` in bridgedb.conf).
 Hopefully I'm remembering the equation correctly... I think I remember it
 being a unary relation to the security parameter. For your concerns on
 predictability, the probability is lower because it needs a second
 preimage for SHA-1.

 And bonus points, that probability is often actually even smaller: the
 security of an HMAC can be proven if [http://cseweb.ucsd.edu/~mihir/papers
 /hmac-new.html only the compression function is modeled as random], the
 digest function doesn't need to be. This is also good news, because digest
 functions are very clearly ''not'' random oracles. For the bad news, there
 are several types of
 [http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.61.7588&rep=rep1&type=pdf
 differential distinguishers for HMAC-SHA-1], though only on reduced-step
 variants. We should make sure we're rotating the `MASTER_KEY` often
 enough, and move to SHA-2/3 when we get around to it (should be simple as
 `'s/\'sha1\'/\'sha256\'/'`)

 > I wonder if weekly rotation will offer enough protection, too.

 It all basically boils down to an adversary using some fancypants tricks
 to brute force the `MASTER_KEY`. If they get that key, and also given that
 some of our adversaries have large IP spaces, it doesn't really matter
 matter how often we rotate. In the end, the problem isn't so much whether
 our adversaries can actually computationally/economically afford to beat
 us and our crypto; it's that no matter what, they've got more resources
 than the people we're trying to help.

--
Ticket URL: <https://trac.torproject.org/projects/tor/ticket/1839#comment:4>
Tor Bug Tracker & Wiki <https://trac.torproject.org/>
The Tor Project: anonymity online