Closed Bug 782106 Opened 8 years ago Closed 7 years ago

Remove the per-client randomization in the url-classifier

Categories

(Toolkit :: Safe Browsing, defect)

defect
Not set

Tracking

()

RESOLVED FIXED
Firefox 19
Tracking Status
firefox17 + fixed
firefox18 + fixed
firefox-esr10 --- wontfix

People

(Reporter: gcp, Unassigned)

References

Details

(Keywords: sec-other, Whiteboard: [adv-track-main17-])

Attachments

(2 files)

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.
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?
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.
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.
Keywords: sec-other
FWIW, I filed bug 783047 to change safebrowsing to use HTTPS instead of MACing.
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.
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.
(In reply to Gian-Carlo Pascutto (:gcp) from comment #6)
> Unfortunately, per-client randomization completely breaks our noise system.

That's pretty serious. :(
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
Attachment #677722 - Flags: review?(dcamp)
Depends on: 807847
Attachment #677718 - Flags: review?(dcamp) → review+
Attachment #677722 - Flags: review?(dcamp) → review+
Status: NEW → RESOLVED
Closed: 7 years ago
Resolution: --- → FIXED
Target Milestone: --- → Firefox 19
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.
Attachment #677718 - Flags: approval-mozilla-beta?
Attachment #677718 - Flags: approval-mozilla-aurora?
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.
Attachment #677722 - Flags: approval-mozilla-beta?
Attachment #677722 - Flags: approval-mozilla-aurora?
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.
Attachment #677718 - Flags: approval-mozilla-beta?
Attachment #677718 - Flags: approval-mozilla-beta+
Attachment #677718 - Flags: approval-mozilla-aurora?
Attachment #677718 - Flags: approval-mozilla-aurora+
Attachment #677722 - Flags: approval-mozilla-beta?
Attachment #677722 - Flags: approval-mozilla-beta+
Attachment #677722 - Flags: approval-mozilla-aurora?
Attachment #677722 - Flags: approval-mozilla-aurora+
Whiteboard: [adv-track-main17-]
Group: core-security
Product: Firefox → Toolkit
You need to log in before you can comment on or make changes to this bug.