Kikset kryptering gjorde det nemt at afsløre alle New York-taxaers kørsel

173 millioner taxa-ture i New York kan nu bindes sammen med taxanummer og chauffør, fordi dataene ikke var anonymiseret godt nok. En hash-funktion var alt for nem at knække.

Ideen var ædel – at lægge indsamlede data om taxakørsel i New York ud offentligt, så andre kunne få glæde af disse unikke informationer.

Men et forfejlet forsøg på at anonymisere, hvilke taxaer og chauffører, der har kørt hvilke ture, har gjort at New Yorks bystyre nu er endt med en data-skandale, som kan bruges til at kortlægge chaufførernes præcise færden.

Det skriver udvikleren Vijay Pandurangan i en længere artikel, der er blevet taget op af blandt andet sikkerhedsguruen Bruce Schneier.

Dataene for taxanummer og chaufførnummer blev kørt igennem en MD5-hash-funktion, før de blev offentliggjort, for hvis hashingen var gjort rigtigt, ville det være umuligt at oversætte hash-værdierne tilbage til de oprindelige data.

Problemet var bare, at både taxanumre og chaufførnumre følger bestemte skabeloner, så der var til sammen kun 24 millioner forskellige muligheder for begge værdier. Det tog kun to minutter at beregne hash-værdierne for de 24 millioner muligheder, og med en klynge på 10 computere tog det under en time at parre dem med dataene. Dermed var anonymiseringen helt brudt.

Den rigtige løsning, der ville have beskyttet taxachaufførernes identitet og færden, ville have været at bruge et ’salt’, altså at udvide hvert datasæt med hver sin tilfældige værdi. New York by kunne også have krypteret dataene med AES og bruge en nøgle, som kun de selv kendte.

MD5 er i øvrigt ikke længere en sikker funktion, men det var ikke svaghederne i MD5, som blev brugt til at knække nødden her, men svagheder i måden den blev brugt på.

Tips og korrekturforslag til denne historie sendes til tip@version2.dk
Kommentarer (8)
sortSortér kommentarer
  • Ældste først
  • Nyeste først
  • Bedste først
Nicolai Hansen

Altså hvis man UDVIDER datasættet med saltet, så ville det jo "bare" gøre beregningen 86,5 millioner gange mere ressourcekrævende, men dette er stadig forholdsvis nemt for en kraftig computer at komme igennem.

Den rigtige løsning ville naturligvis være ikke at offentliggøre disse salts, så man ikke kan bruteforce sig frem til de oprindelige data.

  • 0
  • 3
Sune Marcher

Jeg legede på et tidspunkt lidt med sha256 og cpr-numre - for at holde kompleksiteten nede, genererede jeg en mængde numre der er invalide (ingen modulus-konsisten, lod februar have 29 dage hvert år). Det giver 366 millioner hashes.

C++-koden er kun ret trivielt optimeret, men jeg ramte (på en i7-3770) ~1644k hashops/sec per core - at finde det fiktive cpr-nummer 311299-9999 udfra hashen 7c1bb9f1d19393fdbcb04537a679d661180f31166b8ecb21135711c84883914e tager ca. fire minutter, fire tråde ca. 1 minut, og 8 tråde (det er en HyperThreading CPU) rammer ca. 40 sekunder.

Bare for at køre den helt hjem, lavede jeg også en version der gemte hashes i en SQLite database - det tager nogle minutter at bygge de rå database-værdier, og i alt 42min for at generere indexes (databasen smidt på en velociraptor disk, TEMP på en SSD - jeg var for doven til at sætte en ramdisk op, men det er doable; man kan styre hvor meget scratch space SQLite må bruge).

Databasen ender på små 30gb, men derefter tager det under ét sekund at slå værdier op.

Der er naturligvis forskel på CPR og taxa-database - pointen med ovenstående rant er blot at skitsere hvad én person med én standard-computer kan lave på et par aftener... hvis man kaster penge efter et professionelt team og lidt cloud-resourcer, kan man lave ret interessante ting.

Morale: hvis du kun har brug for at verificere en oplysning, og ikke at genskabe den, så er det ikke nok at gemme en hash af oplysningen - GlobalSalt er ikke meget bedre - og selv UnikSalt bliver et issue sometime. PBKDF2, BCrypt eller SCrypt, tak.

  • 0
  • 0
Log ind eller Opret konto for at kommentere