Programma Les 53 van 156 · Meet privacy, eerlijk.
Meet privacy, eerlijk.

Anonimiteitssets en entropie

Waarom dit ertoe doetKoppen zeggen dingen zoals "je browser is uniek" of "dit kenmerk geeft 10 bits". Deze les laat zien hoe zulke getallen worden gemeten, en de twee valkuilen die velen groter maken dan de waarheid. Dan kun je privacyclaims beoordelen, inclusief je eigen.

Hudden in een menigte

Stel je een station voor vol met reizigers in identieke zwarte jassen. Als jij ook een zwarte jas draagt, verberg je je tussen honderden mensen. Als je een felgele jas draagt, is de menigte waarin je je verbergt gewoon jij.

Anonymity set: de groep mensen die voor een waarnemer precies op jou lijken. Hoe groter deze is, hoe beter je je verstopt. Een set van grootte 1 betekent dat je uniek bent.

In les 50 heb je gemeten hoe opvallend één persoon, Sam, opviel in een menigte. Hier meet je de hele menigte van 5.000 synthetische browsers (gemaakt door synthetic_browsers, geen echte mensen), om te zien hoe goed everyone zich verbergt.

Group, dan tel

Kies wat kenmerken, bijvoorbeeld ["timezone", "language"]. De fingerprint van elke browser is de tuple van die waarden, bijvoorbeeld ("Europe/London", "en-GB"). Een tuple werkt als een dict key, dus collections.Counter kan tellen hoeveel browsers elk ervan delen:

from collections import Counter
Counter([("A", "x"), ("A", "x"), ("B", "x")])
# Counter({('A', 'x'): 2, ('B', 'x'): 1})

Elke telling is een anonimiteitsset. Een telling van 1 is een unieke browser. Met alle 13 kenmerken blijken de meeste van de 5.000 browsers uniek te zijn.

Entropy: één getal voor de hele groep

In les 48 heb je Shannon entropy gebruikt om te meten hoe door elkaar gemengd de tekens van een tekst zijn. Dezelfde formule werkt op een menigte: neem voor elke anonimiteitsset zijn aandeel p van iedereen, en tel -p * log2(p).

bij elkaar op.

Entropy (van een vingerafdruk): het gemiddelde aantal bits dat een tracker leert over een willekeurige bezoeker vanuit deze kenmerken. 0 bits: iedereen ziet er hetzelfde uit. log2(N) bits: iedereen in een menigte van N is uniek.

Voorbeeld: vier browsers met tijdzones A, A, B, C. Aandelen zijn 1/2, 1/4 en 1/4, dus entropie is 0.5 x 1 + 0.25 x 2 + 0.25 x 2 = 1.5 bits.

Valkuil 1: het plafond

Een menigte van 5.000 kan nooit meer dan log2(5000), ongeveer 12,3 bits laten zien, omdat op dat punt iedereen al uniek is. Een studie van 5.000 browsers die "12 bits" vindt, raakt dan misschien het plafond en meet niet de eigenschap. En uniek onder 5.000 is niet uniek onder miljarden. Grotere steekproeven geven grotere, eerlijkere getallen.

Valkuil 2: eigenschappen optellen

Tijdzone en taal reizen samen: de meeste Asia/Tokyo browsers zeggen ja-JP. De videokaart en het systeem doen dat ook. Het toevoegen van de entropie van elke eigenschap apart telt dezelfde informatie meerdere keren. Je sum_of_parts zal veel hoger uitkomen dan joint, de entropie van alle eigenschappen samen gemeten, en veel boven het plafond van 12.3 bits. Het gezamenlijke getal is het eerlijke getal.

A veelvoorkomende misvatting

"Hoge entropie betekent dat iedereen traceerbaar is." Entropie is een gemiddelde. Een menigte kan een hoge entropie hebben terwijl een grote groep mensen met zeer veelvoorkomende setups nog steeds goed verborgen blijft. Kijk naar zowel het gemiddelde als naar hoeveel mensen in kleine sets zitten.

Probeer het Als je klaar bent, print dan entropy_bits(crowd, [t]) voor elke eigenschap (de oplossing doet dit). Welke drie eigenschappen bevatten de meeste bits? Vergelijk daarna de eigen waarden van je browser voor die eigenschappen met een fingerprint test site zoals EFF's Cover Your Tracks.

In andere talen

JavaScript:

function entropyBits(rows, traits) {
  const counts = new Map();
  for (const r of rows) {
    const key = JSON.stringify(traits.map(t => r[t]));
    counts.set(key, (counts.get(key) || 0) + 1);
  }
  let bits = 0;
  for (const c of counts.values()) {
    const p = c / rows.length;
    bits -= p * Math.log2(p);
  }
  return bits;
}

Go:

func entropyBits(keys []string) float64 {
    counts := map[string]int{}
    for _, k := range keys {
        counts[k]++
    }
    bits := 0.0
    for _, c := range counts {
        p := float64(c) / float64(len(keys))
        bits -= p * math.Log2(p)
    }
    return bits
}

Samenvatting

  • Een anonimiteitsset is iedereen die er precies zo uitziet als jij; grootte 1 betekent uniek.
  • Entropy is het gemiddelde aantal bits dat over een bezoeker is geleerd: groep, telling, dan som -p log2(p).
  • Geen sample van N kan meer dan log2(N) bits laten zien; kleine samples onderschatten de menigte.
  • Meet eigenschappen samen: het één voor één toevoegen telt gekoppelde eigenschappen dubbel.
Jij bent aan de beurt

Schrijf fingerprint(row, traits) (een tuple van de waarden), anonymity_sets(rows, traits) (een dictionary van fingerprint naar count), fraction_unique(rows, traits) (aandeel van rijen in een set van grootte 1), entropy_bits(rows, traits) (Shannon entropie over de anonimiteitsets) en max_bits(n) (log2(n)). Stel daarna joint in op de entropie van crowd over alle TRAIT_NAMES, en sum_of_parts op de som van de entropie van elke individuele eigenschap.

Een probleem ontdekt in deze les? Meld het · Vraag naar deze les

Deze oefening opent binnenkort

Maak de les ervoor af voordat deze wordt ontgrendeld. De hele cursus is gratis, geen account nodig, en je kunt deze les nu lezen.