Closed Bug 1343416 Opened 5 years ago Closed 5 years ago

Use a deterministic algorithm when generating noise entries for Safe Browsing completions

Categories

(Toolkit :: Safe Browsing, enhancement, P2)

enhancement

Tracking

()

RESOLVED FIXED
mozilla55
Tracking Status
firefox55 --- fixed

People

(Reporter: tnguyen, Assigned: tnguyen)

References

Details

Attachments

(1 file)

Following bug 1297962 comment20, comment 23 we have to use a deterministic algorithm rather than rand() in term of privacy
Summary: Removing rand() deterministic algorithm when generating noise → Removing rand() and use a deterministic algorithm when generating noise
Summary: Removing rand() and use a deterministic algorithm when generating noise → Remove rand() and use a deterministic algorithm when generating noise
(copying my comments from https://bugzilla.mozilla.org/show_bug.cgi?id=1297962#c24)

GCP, do you think we could simply seed the random number generator with the prefix before calling rand()?

The previous code was getting harder to understand and I feared it would be hard to spot a regression (ironically, my suggestions introduced a different regression).
Assignee: nobody → tnguyen
Flags: needinfo?(gpascutto)
Priority: -- → P2
Summary: Remove rand() and use a deterministic algorithm when generating noise → Use a deterministic algorithm when generating noise
Summary: Use a deterministic algorithm when generating noise → Use a deterministic algorithm when generating noise entries for Safe Browsing completions
What I would fear is that it's case of "what random number generator?" rand() isn't thread-safe. Reseeding a random number generator deterministically might break some other part of the code that expects real randomness (Don't want to reseed any of the CPRG's!)

I think Thomas' suggestion was OK (linear congruent generator), but it does need a comment right before explaining what it does and why it's doing that, and why it works.
Flags: needinfo?(gpascutto)
Comment on attachment 8844825 [details]
Bug 1343416 - Use LCG when generating noise entries for Safe Browsing completions

https://reviewboard.mozilla.org/r/118146/#review119980

::: toolkit/components/url-classifier/Classifier.cpp:1430
(Diff revision 1)
>  
> +  // Pick some random prefix indexs from 0 to prefixes.Length() - 1;
> +  // We may not want to use rand() which is not thread-safe and uses a global
> +  // state (therefore may break some other parts that expect randomness).
> +  // Also rand() is often predictable and easy to filter out popular prefixes
> +  // which may cause a privacy consideration.

I would reword this a little. It's not very clear that the problem actually *is* that rand() is random (that it's predictable *isn't* as much of a problem for us).

"We do not want to simply pick random prefixes, because this would allow averaging out the noise by analysing the traffic from Firefox users. Instead, we ensure the 'noise' is the same for the same prefix by seeding the random number generator with the prefix. We prefer not to use rand() which isn't thread safe, and the reseeding of which could trip up other parts othe code that expect actual random numbers."

::: toolkit/components/url-classifier/Classifier.cpp:1432
(Diff revision 1)
> +  // We may not want to use rand() which is not thread-safe and uses a global
> +  // state (therefore may break some other parts that expect randomness).
> +  // Also rand() is often predictable and easy to filter out popular prefixes
> +  // which may cause a privacy consideration.
> +  // Here we use a simple LCG (Linear Congruential Generator) to generate
> +  // random numbers. Due to generating the same noise for the same seed, that

Replace the second sentence by: "We seed the LCG with the prefix we are generating noise for".
Attachment #8844825 - Flags: review?(gpascutto) → review+
Thanks gcp for rewording the comment
Keywords: checkin-needed
Pushed by cbook@mozilla.com:
https://hg.mozilla.org/integration/autoland/rev/fae378413e34
Use LCG when generating noise entries for Safe Browsing completions r=gcp
Keywords: checkin-needed
https://hg.mozilla.org/mozilla-central/rev/fae378413e34
Status: NEW → RESOLVED
Closed: 5 years ago
Resolution: --- → FIXED
Target Milestone: --- → mozilla55
You need to log in before you can comment on or make changes to this bug.