Closed Bug 419117 Opened 13 years ago Closed 13 years ago

Add noise to gethash requests

Categories

(Toolkit :: Safe Browsing, defect, P1)

defect

Tracking

()

RESOLVED FIXED
Firefox 3 beta4

People

(Reporter: dcamp, Assigned: dcamp)

References

Details

(Keywords: privacy)

Attachments

(3 files, 1 obsolete file)

We want to add a few randomly-selected hash prefixes to the gethash request to obscure which hash prefix we actually visited.
Flags: blocking-firefox3?
Keywords: privacy
Attached patch v1 (obsolete) — Splinter Review
Attached patch adds 4 randomly-selected partial hashes to the gethash request.

We do this (as suggested by Dr. Hipp) by
a) Ensuring that ids are distributed somewhat evenly across the space by assigning them randomly at insert time.
b) Choosing a row with an id >= random() at lookup time.
c) If that set is empty, select the lowest id (simulate wrapping around the list)
Assignee: nobody → dcamp
Status: NEW → ASSIGNED
Attachment #305618 - Flags: review?(tony)
Attached patch v1, right patchSplinter Review
Attachment #305618 - Attachment is obsolete: true
Attachment #305620 - Flags: review?(tony)
Attachment #305618 - Flags: review?(tony)
Comment on attachment 305620 [details] [diff] [review]
v1, right patch

>   rv = mConnection->CreateStatement
>-    (NS_LITERAL_CSTRING("INSERT OR REPLACE INTO ") + entriesTableName +
>-     NS_LITERAL_CSTRING(" VALUES (?1, ?2, ?3, ?4, ?5, ?6)"),
>+    (NS_LITERAL_CSTRING("INSERT INTO ") + entriesTableName +
>+     NS_LITERAL_CSTRING(" VALUES (abs(random()), ?2, ?3, ?4, ?5, ?6)"),
>      getter_AddRefs(mInsertStatement));
>   NS_ENSURE_SUCCESS(rv, rv);

The REPLACE INTO was removed because we want to error out on collisions of random numbers right?  Does this break any old behavior that expected being able to replace entries?


>   if (newEntry) {
>+    // The insert statement chooses a random ID for the entry, which
>+    // might collide.  This should be exceedingly rare, but we'll try
>+    // a few times, otherwise assume a real error.
>+    nsresult rv;
>+    for (PRUint32 i = 0; i < 10; i++) {
>+      mozStorageStatementScoper scoper(mInsertStatement);
>+

Should 10 be a const in the file?


And a more general question: What type of performance hit does this change have?
Attachment #305620 - Flags: review?(tony) → review+
(In reply to comment #3)

> The REPLACE INTO was removed because we want to error out on collisions of
> random numbers right?  Does this break any old behavior that expected being
> able to replace entries?

Nah, WriteEntry() was updated to use the UPDATE statement in the case of existing entries.

> >   if (newEntry) {
> >+    // The insert statement chooses a random ID for the entry, which
> >+    // might collide.  This should be exceedingly rare, but we'll try
> >+    // a few times, otherwise assume a real error.
> >+    nsresult rv;
> >+    for (PRUint32 i = 0; i < 10; i++) {
> >+      mozStorageStatementScoper scoper(mInsertStatement);
> >+
> 
> Should 10 be a const in the file?

I chose to just keep the magic number in that one place rather than having to spread the documentation explaining what we're doing between that function and the top of the file.  I could change it, but...

> And a more general question: What type of performance hit does this change
> have?

I'd previously been measuring lookup performance.  There's no penalty for a lookup that doesn't match.  A lookup that does match incurs a slight penalty, but insignificant compared to the gethash request that follows.

However, after looking more closely it appears to cause a few other problems.  On my tests it slows down updates by like 50-70%, and increases the file size by 30-40%.  The file size increase is worrisome, it's already an unfortunately large file.

I'm going to put together a patch that tries to solve this a different way.
Flags: blocking-firefox3? → blocking-firefox3+
Priority: -- → P1
This patch takes a different approach.

Rather than selecting 4 random rows, it selects 4 rows adjacent to the row we hit.  How much it selects in each direction is determined randomly.  The general idea should still be the same (we send 5 rows, with no reliable way to determine which I visited), but it's not really as random - the same adjacent rows are generally going to be sent next to each other.

Update performance/disk space usage are not affected, and lookup speed should be a bit faster in most cases than the previous patch.

I couldn't find a decent safe-on-a-thread random number generator, so this code asks sqlite for a random number.  Any suggestions?
Attachment #305791 - Flags: review?(tony)
Comment on attachment 305791 [details] [diff] [review]
different approach

PR_GetRandomNoise isn't thread safe?
Attachment #305791 - Flags: review?(tony) → review+
As I understand it, PR_GetRandomNoise() isn't really intended to give a random number.  It's just meant to seed a decent PRNG.
Actually, nsIRandomGenerator should be ok on a thread (as long as it isn't passed between threads), putting together a new patch now.
Urgh, except it's a Service, not a CreateInstance'ed Object, so that won't work.

Fixing that should be easy enough, but I don't know if we can get that reviewed etc. in time for beta 4.  I think it'd be best to land this patch as-is and file a follow-up to make nsIRandomGenerator threadsafe.
(In reply to comment #9)
> Urgh, except it's a Service, not a CreateInstance'ed Object, so that won't
> work.
> 
> Fixing that should be easy enough, but I don't know if we can get that reviewed
> etc. in time for beta 4.  I think it'd be best to land this patch as-is and
> file a follow-up to make nsIRandomGenerator threadsafe.

Sounds good to me.

Followup patch to use nsIRandomGenerator once bug 419739 has landed.
Attachment #305872 - Flags: review?(tony)
Attachment #305872 - Flags: review?(tony) → review+
I think we want this for beta 4.
Target Milestone: --- → Firefox 3 beta4
Checking in browser/app/profile/firefox.js;
/cvsroot/mozilla/browser/app/profile/firefox.js,v  <--  firefox.js
new revision: 1.288; previous revision: 1.287
done
Checking in toolkit/components/url-classifier/src/nsUrlClassifierDBService.cpp;
/cvsroot/mozilla/toolkit/components/url-classifier/src/nsUrlClassifierDBService.cpp,v  <--  nsUrlClassifierDBService.cpp
new revision: 1.63; previous revision: 1.62
done
Checking in toolkit/components/url-classifier/tests/unit/head_urlclassifier.js;
/cvsroot/mozilla/toolkit/components/url-classifier/tests/unit/head_urlclassifier.js,v  <--  head_urlclassifier.js
new revision: 1.9; previous revision: 1.8
done
Status: ASSIGNED → RESOLVED
Closed: 13 years ago
Resolution: --- → FIXED
Depends on: 423943
Product: Firefox → Toolkit
You need to log in before you can comment on or make changes to this bug.