Truslen fra lækage af adgangsmønstre

Kryptering af data beskytter indholdet mod uautoriserede parter, men kryptering alene skjuler ikke metadata om, hvordan data tilgås. Adgangsmønstre — hvilke poster der læses eller skrives, hvornår og hvor ofte — kan afsløre følsomme oplysninger, selv når selve dataene er fuldstændig krypteret. Denne forskel mellem indholdsfortrolighed og adgangsfortrolighed er den centrale drivkraft bag Oblivious RAM.

Analyse af adgangsmønstre kan afsløre: hvilke databaseposter en bruger slår op (så man kan udlede medicinske tilstande ud fra, hvilke poster brugeren tilgår), kommunikationsmønstre (hvem der kontakter hvem, selv om meddelelsens indhold er krypteret), finansiel aktivitet (så man kan udlede handelsstrategier ud fra, hvilke priser en bruger slår op), og adfærdsmønstre (daglige rutiner ud fra adgangstidspunkter og -hyppigheder). Disse slutninger kan være lige så følsomme som selve dataindholdet.

CryptDB (MIT, 2011) var et indflydelsesrigt system til forespørgsler i krypterede databaser. Efterfølgende forskning udført af Grubbs, McPherson, Naveed, Ristenpart og Spooner (2016) viste, at CryptDB og lignende ordensbevarende krypteringsordninger afslører adgangsmønstre, som muliggør inferensangreb. En angriber med et supplerende datasæt om adgangsfordelinger kan udlede klartekstværdier alene ud fra adgangsfrekvens og rækkefølge, selv uden at bryde krypteringen.

Hvis en krypteret cloudlagertjeneste logfører, hvilke chiffertekstblokke der tilgås, kan en angriber udføre frekvensanalyse. Da brugere typisk tilgår populære filer oftere, afspejler frekvenshistogrammet for chiffertekstblokke fordelingen af adgange til klartekst. Ved at sammenholde det krypterede frekvenshistogram med kendte adgangsmønstre kan man identificere, hvilke krypterede filer der svarer til populære indholdskategorier.

I trusselsmodellen med en ærlig, men nysgerrig (semi-honest) cloududbyder følger cloududbyderen protokollen korrekt, men observerer alle adgangsmønstre til klientdata. Mange cloududbydere logfører legitimt adgangsmønstre til fakturering, fejlfinding og optimering af ydeevne. Selv uden ondsindede hensigter udgør disse logfiler en risiko: En kompromitteret cloududbyder, en illoyal medarbejder eller en stævning fra myndighederne kan afsløre følsomme adgangsmønstre.

Oblivious RAM (ORAM), som blev introduceret af Goldreich og Ostrovsky (1996), er en kryptografisk primitiv, der skjuler adgangsmønstre for serveren. I et ORAM-skema genererer hver adgang (læsning eller skrivning) til en vilkårlig hukommelsesplacering den samme fordeling af server-synlige operationer, uanset hvilken placering der faktisk tilgås. En angriber, der observerer serveren, ser kun ensartet tilfældige adgangsmønstre.

ORAM har en lang række anvendelser overalt, hvor privatliv for adgangsmønstre er påkrævet: sikker cloudlagring (skjule, hvilke filer en bruger tilgår), skjulte databaseforespørgsler (skjule, hvilke rækker en forespørgsel returnerer), SGX-enklaver (forhindre sidekanaler baseret på adgang til enklavens hukommelse), privat informationssøgning (skjule, hvilken databasepost en bruger henter), og sikker flerpartsberegning (skjule adgangsmønstre til den mellemliggende tilstand).

Den enkleste ORAM-løsning er indlysende: For at tilgå én blok læses og omskrives hver blok i hele lageret. Det skjuler, hvilken blok der blev tilgået (hver adgang ser identisk ud), men medfører en kommunikationsoverhead på O(n) pr. logisk adgang, hvilket gør løsningen helt upraktisk for store datasæt. Virkelige ORAM-skemaer forsøger at reducere denne overhead til O(polylog n), samtidig med at de opretholder perfekt eller statistisk obliviousitet.

Goldreich og Ostrovsky beviste en nedre grænse: Enhver ORAM med O(1) lageroverhead på serveren skal have mindst Omega(log n) kommunikationsoverhead pr. adgang. Denne logaritmiske nedre grænse gælder for deterministiske ORAM'er. Praktiske konstruktioner sigter mod en overhead på O(log^2 n) eller O(log n), hvilket er tæt på dette teoretiske minimum. Den nedre grænse viser, at perfekt skjulning af adgangsmønstre har en uundgåelig omkostning.

Søgbar symmetrisk kryptering (SSE) gør det muligt at søge i krypterede data. Grundlæggende SSE-skemaer afslører søgemønstre (hvilke nøgleord der søges efter) og adgangsmønstre (hvilke dokumenter der returneres). Forward-private SSE skjuler søgemønsteret for nye dokumenter, men ORAM er også nødvendig for at skjule, hvilke dokumenter der tilgås. Kombinationen af SSE og ORAM giver den stærkeste privatlivsgaranti, men med en betydelig omkostning for ydeevnen.

ORAM er ikke altid nødvendig. Beslutningen afhænger af trusselsmodellen: Observerer angriberen adgangsmønstrene? Ved lokalt lager med fulddiskkryptering og en ekstern angriber er ORAM muligvis ikke nødvendig. Ved cloudlagring, hvor cloududbyderen ikke er betroet, er ORAM passende. Overheaden (typisk 20-50 gange større båndbreddeforbrug) er umagen værd, når læk af adgangsmønstre udgør en reel trussel, og dataenes følsomhed berettiger omkostningen.

Kryptering af dataindhold skjuler ikke adgangsmønstre, som kan afsløre følsomme oplysninger gennem frekvensanalyse og timing. Cloududbydere i modeller med en ærlig, men nysgerrig udbyder observerer, hvilke chiffertekstblokke klienter tilgår. CryptDB-angreb demonstrerede praktisk inferens ud fra adgangsmønstre i krypterede databaser. ORAM løser dette ved at få alle adgange til at se identiske ud for serveren. Den trivielle løsning (at læse alt ved hver adgang) er upraktisk med O(n); virkelige ORAM-skemaer opnår en overhead på O(log^2 n).