Re: Publishing sanitized bridge pool assignments

[Ian Goldberg <iang@xxxxxxxxxxxxxxx>]

On Wed, Feb 02, 2011 at 04:29:05PM +0100, Karsten Loesing wrote:
> On Wed, Feb 02, 2011 at 09:56:05AM -0500, Ian Goldberg wrote:
> > On Wed, Feb 02, 2011 at 03:50:25PM +0100, Karsten Loesing wrote:
> >> Speaking of sanitizing bridge descriptors, there's a related change to the
> >> current sanitizing process discussed in Trac ticket #2435.  I'd really
> >> like to hear your opinions to that ticket (either here or as comments to
> >> the ticket), because that change is about preserving hashed IP addresses
> >> in sanitized bridge descriptors:
> >> 
> >>   https://trac.torproject.org/projects/tor/ticket/2435
> > 
> > "Never rely on a secret that's expensive to change".
> > 
> > For sure the secret should be long.  20 bytes is probably OK, but why
> > not 256 bits?  As long as the whole thing you're hashing fits in one
> > hash block, it's not more expensive.  (And why SHA1?)
> 
> Pasting the proposed hash function here so that people can follow the
> discussion without opening the Trac ticket:
> 
>   H(IP address + bridge identity + secret)[:3]
> 
> 20 bytes was just a suggestion.  We already have 24 bytes as input to the
> hash function (IP address = 4 bytes, bridge identity = 20 bytes) plus the
> suggested 20 bytes for the secret.  We can as well make the secret 32
> bytes long, or 40.

Actually, to keep it to one SHA block (447 bits, not including padding),
you can have at most 255 bits (31 bytes, if we're byte-aligned) for the
secret.  I wouldn't suggest spanning the secret across SHA blocks.

> SHA1 was just a suggestion, too.  No reason not to use SHA-256, SHA-384,
> or SHA-512 (which are the digests in the Java implementation we use).
> 
> How about using SHA-512 and making the secret 40 bytes long?

SHA-512 seems like overkill if we're only using 3 bytes of the output.
SHA-256 should be fine.  Indeed, there's no _actual_ reason to believe
SHA-1 isn't fine here, except for the general "don't be mandating SHA-1
for anything new at this point" rule.

> > What happens if someone _does_ brute the secret?  How important is it to
> > keep a consistent secret?
> 
> If someone brute forces the secret, they only need the bridge identity to
> further brute force the bridge's past IP addresses.  We usually assume
> that the adversary doesn't have original bridge identities, unless they
> request bridges on their own.  And if they do request bridges, they
> already know current IP addresses.  But when they also have the secret,
> they can use our archives to learn about the bridge's past IP addresses.
> It's unclear whether that's a problem for someone.  Possibly.
> 
> With a changing secret, the adversary could only use the found secret for
> descriptor archives of that month.  And they'll have a much harder time
> brute forcing secrets for past months, for which they cannot set up their
> own bridges (as described in comment #1 in #2435).

A 31-byte secret is far more likely to leak than be brute-forced, of
course.  If it's leaked one month, is it likely to leak again another
month?

   - Ian