782106 - Remove the per-client randomization in the url-classifier

Status: RESOLVED FIXED

(Toolkit :: Safe Browsing, defect)

Description

[Gian-Carlo Pascutto [:gcp]]

In bug 669407, it was pointed out that moving to 32-bit prefixes (from 32-bit prefixes + 32-bit hostkeys) would mean websites that are unlucky and collide with a malware site would get loading penalty in Firefox. Even worse, if the collision was at a popular site that could cause flood of requests to the SafeBrowsing completion server.

We currently protect against this via rehashing the prefixes with a per-client key and Murmurhash3.

There are several reasons why we now think this was not needed:

1) There are cryptographic attacks that collide Murmurhash3 independent of the per-user key.
2) It is computationally very feasible to collide the *original* 32-bit SHA-256 prefixes, and with some EC2 instances or a small botnet, (2 x 32bit =) 64-bit SHA-256 prefixes. (e.g. g00gle7074559436.org/ collides google.com/, http://www.sjeng.org/4806321590.html collides known malware)
3) As far as I can tell Chrome only stores 32-bit prefixes and does not use any per-client randomization.

(2) and (3) seem to be a very strong indication that Google in fact does not care about potential floods to the completion server, and has enough (dynamic) resources to deal with it.

We asked confirmation through email. If so, we should remove the complication of our per-client rehashing. Because of (1), it currently might generating intentional collisions even easier.

There is some slight concern that if malware/phishing sites would collectively start doing (2), it would make the current client-side databases in SafeBrowsing mostly useless.

Comment 1

[Andrew McCreight [:mccr8]]

Does this really need to be a security sensitive bug?  If so, what sort of security rating would you give it?  Maybe sec-audit or something?

Comment 2

[Gian-Carlo Pascutto [:gcp]]

sec-other & sec-low or thereabouts? The vulnerability has always existed, but it requires knowing Firefox & Chrome's SafeBrowsing implementation in detail to see there's a really easy way to collide (i.e. 32-bit collisions instead of 64-bit ones).

Turning this into a real attack would require some sort of agreement among everyone posting malware/phishing sites to only do so at colliding URLs, and the result would then be a sort of DDoS against the relevant Google servers (one wonders if that concept can actually exist ;-), or slowed loading of another target site.

I don't have anything against unhiding, particularly as Chrome has the same behavior[1] and Google seemingly doesn't care. Just wanted to allow the other parties to weigh in here first.

[1] Presuming I read the code correctly. I haven't seen any reply to my email from the Chrome/SafeBrowsing guys.

Comment 3

[Andrew McCreight [:mccr8]]

Thanks for the explanation. It sounds like the main problem here is sending traffic to Google, so leaving it as security sensitive sounds reasonable.  I'll make it sec-other because it isn't really affecting Mozilla per se.

Comment 4

[Sid Stamm [:geekboy or :sstamm]]

FWIW, I filed bug 783047 to change safebrowsing to use HTTPS instead of MACing.

Comment 5

[Gian-Carlo Pascutto [:gcp]]

This exists independent of HTTP or HTTPS, the problem is in the actual database.

FWIW, Google never replied to my inquiries. 

Changing this would require resetting the database of all our users, which puts a lot of traffic on Google's server - should be avoided as possible. We will already do so in Firefox 17 because it has the new backend. I think it's too late/risky now to put this change still into the 17 betas. So I'm going to postpone removal of the randomization to whenever we need some database-related changes anyway.

Comment 6

[Gian-Carlo Pascutto [:gcp]]

Unfortunately, per-client randomization completely breaks our noise system.

If we do a gethash request, we add noise to mask the URL being queried, by making several other Completion requests for other Prefixes in our database. But those prefixes don't correspond to anything in Google's DB, because we've hashed them with our per-client key. This makes it trivial to undo the noise: every request from Firefox will contain 4 requests, 1 of which will hit in the database, and 3 that will miss. The one that hits was the real one the user requested :-(

I know it's late in the 17 cycle, but it we don't remove this misfeature now, we're painting ourselves in a corner we can only get out of by having all users re-download their databases, again.

Bug 768871 introduced a pref that controls this feature. I think we can just toggle the pref, but I'll also have to update the database identifiers so current beta users will have their databases reset.

Comment 7

[:Gavin Sharp [email: [e-mail]]]

(In reply to Gian-Carlo Pascutto (:gcp) from comment #6)
> Unfortunately, per-client randomization completely breaks our noise system.

That's pretty serious. :(

Comment 8

[Gian-Carlo Pascutto [:gcp]]

Attachment: Patch 1. Disable per-client randomization. Force DB reset.

Comment 9

[Gian-Carlo Pascutto [:gcp]]

Attachment: Patch 2. Initialize key on a reset.

While testing the upgrade procedure for the DB, I found a bug. The per-client key is not initialized/written on a reset. It has no effect or importance when we disable per-client keys, as the previous patch does, and in fact we're better off without it because that's one useless file less.

But if we ever *go back* for whatever reason, this patch should be applied to ensure correct recovery. 

i.e. apply this patch if backing out the previous one

Comment 10

[Gian-Carlo Pascutto [:gcp]]

https://tbpl.mozilla.org/?tree=Try&rev=caa492f7913b

https://hg.mozilla.org/mozilla-central/rev/89e780d81ef0

Comment 11

[Gian-Carlo Pascutto [:gcp]]

Comment on attachment 677718 [details] [diff] [review]
Patch 1. Disable per-client randomization. Force DB reset.

[Approval Request Comment]
Bug caused by (feature/regressing bug #): bug 673470
User impact if declined: We will be unable to fix privacy issues with SafeBrowsing (now and in the future) without re-downloading the complete database again.
Testing completed (on m-c, etc.): Landed on m-c yesterday. All Nightlies should have taken the resulting upgrade/reset codepath by now. Seems to have worked fine on all my machines.
Risk to taking this patch (and alternatives if risky): Worst case is likely some kind of corruption during the upgrade that renders SafeBrowsing broken (and if we're very unlucky, perhaps the recovery codepath has a bug and we get a startup crash - but this should be visible in Nightly numbers by the time you read this). Alternative is to delay this patch and redo the database download in a future version.

If this patch is rejected, taking the second patch in this bug is recommended.

Comment 12

[Gian-Carlo Pascutto [:gcp]]

Comment on attachment 677722 [details] [diff] [review]
Patch 2. Initialize key on a reset.

[Approval Request Comment]
Bug caused by (feature/regressing bug #): bug 673470
User impact if declined: If the first patch in this bug is *NOT* taken, users who start Firefox with a corrupted profile risk having their SafeBrowsing database start to get filled with junk until they restart Firefox again. This junk will then prevent proper entries from entering the database after the restart, thereby diminishing the effectiveness of SafeBrowsing for them. This could take several weeks to recover automatically.
Testing completed (on m-c, etc.): Local testing for the exact scenario the patch protects against.
Risk to taking this patch (and alternatives if risky): Very low. Only triggers if the user hoses (part of) his/her profile. The extra code that will run already runs each startup.

Comment 13

[Alex Keybl [:akeybl]]

Comment on attachment 677718 [details] [diff] [review]
Patch 1. Disable per-client randomization. Force DB reset.

[Triage Comment]
In support of unbreaking safe browsing and preventing another DB download. As mentioned in email, if we don't hit beta 5 with this fix or we find major regressions during b5, we'll likely wontfix for FF17.

Comment 14

[Gian-Carlo Pascutto [:gcp]]

https://hg.mozilla.org/releases/mozilla-beta/rev/1fe8fd75e5d5
https://hg.mozilla.org/releases/mozilla-aurora/rev/3584ecc80e5d