HMAC het my outovoltooiing opgevreet: vooruit-tik-soektog oor geënkripteerde e-posse

Ons enkripteer gebruikers se PII in rus met sleutels per huurder, sodat 'n uitgelekte databasis-aflaai niks bruikbaars blootstel nie. Die e-poskolom is syferteks. Telefoonnommers, name, pasgemaakte attribute: syferteks. Ons is trots hierop. Dit is 'n verkoopspunt.

En die dag toe dit regstreeks gegaan het, het die admin-soekkassie stilweg opgehou outovoltooi.

Geen fout nie. Geen loglyn nie. Tik ali in die gebruikersoektog, en die huurder-admin wat gewoond was om [email protected] na drie toetsaanslae te sien opduik, het nou... niks gesien nie, tensy hulle die volledige e-posadres presies ingetik het. Die soektog het nie gebreek nie; dit het stilweg gedegradeer van "begin met" na "is gelyk aan", en niks in die stelsel het dit die moeite werd geag om te noem nie.

Dit is die storie van hoe ons vooruit-tik teruggekry het oor data wat ons weier om in skoonteks te stoor, en die drie strikke wat ons in die proses getref het. Die kriptografie was uiteindelik die maklike deel.

Waarom enkripsie outovoltooiing opvreet

Met skoonteks is voorvoegsel-soektog presies waarvoor databasisse bestaan. Hou 'n indeks gesorteer volgens e-pos, en starts with "ali" is 'n reeksskandering: alles >= "ali" en < "alj". Goedkoop, voor die hand liggend, klaar.

Enkripteer die kolom, en die gesorteerde indeks is weg. Die standaardvervanging is 'n blind index ('n blinde indeks): stoor langs die syferteks 'n gesleutelde HMAC van die waarde, en soek gebruikers op deur die HMAC van die soekterm te herbereken. HMAC(key, "[email protected]") is deterministies, so presiese-passing-opsoek werk perfek, en die indeks lek niks leesbaars nie, want sonder die sleutel per huurder kan jy nie 'n hutswaarde bereken om mee te vergelyk nie.

Maar let op waarvoor HMAC bedoel is. Sy hele ontwerpsdoel is dat soortgelyke insette onverwante uitsette lewer: draai een bis om, en jy kry 'n heeltemal ander hutswaarde. HMAC("ali") en HMAC("alistair") het niks met mekaar te doen nie. Die eienskap wat die blind index veilig maak om te lek, is presies die eienskap wat dit onmoontlik maak om "begin met" te beantwoord. Ordening is lekkasie. 'n Blind index breek nie voorvoegsel-soektog per ongeluk nie; dit breek dit uit beginsel.

Die soekkassie het dus stilweg na presiese passing gedegradeer, omdat presiese passing die enigste vraag was wat die indeks nog kon beantwoord.

Die ontwerp: indekseer elke voorvoegsel as sy eie waarde

As die indeks slegs "is gelyk aan" kan beantwoord, verander dan "begin met" in "is gelyk aan".

Elke voorvoegsel van die genormaliseerde e-pos se lokale deel (die stukkie voor die @) kry sy eie blind-index-ry. Vir [email protected] is dit rye vir al, ali, alis, alist, en so aan: PartitionKey = HMAC(prefix), RowKey = die gebruiker-id. Nou is "begin met ali" 'n presiese-passing-opsoek op HMAC("ali"): een puntnavraag, geen ordening nodig nie. Ons naamsoektog het reeds om dieselfde rede so gewerk; e-pos het net daarby aangesluit.

Twee konstantes hou dit gesond. Voorvoegsels begin by 2 karakters (een-karakter-opsoeke was nooit nuttig nie en verdubbel die rye) en stop by 16 (dit begrens die uitwaaiering per e-pos; 'n langer navraag pas net op sy eerste 16 karakters, en die handvol kandidate word ná dekripsie gefiltreer). Elke e-pos kos dus hoogstens 15 indeksrye: geskryf met skep, geskuif met e-posverandering, verwyder met uitvee.

Dit is die ruil in een sin: jy koop die ordening terug wat jy geweier het om te lek, en jy betaal daarvoor in skryf-uitwaaiering. Stoorplek en skryfbewerkings is goedkoop; gelekte struktuur is nie. Dit is 'n goeie ruil.

Een subtiliteit in die skuif-met-verandering-pad het sy eie kommentaar in die kode verdien: die voorvoegselrye word gesleutel op die lokale deel, so die herskryf moet afgaan wanneer die lokale deel verander, onafhanklik van die domein. 'n Hernoeming binne dieselfde domein, [email protected] → [email protected], lyk vir 'n wag wat met die domeinindeks in gedagte geskryf is soos "domein onveranderd, slaan die indekswerk oor", en sou die ou voorvoegselrye vir ewig na die hernoemde gebruiker laat wys.

En om eerlik te wees oor wat ons gebou het: hierdie indeks lek doelbewus voorvoegsel-gelykheid. 'n Aanvaller met die tabel kan sien dat twee gebruikers 'n 3-karakter-e-posvoorvoegsel deel, maar nie wat dit is nie. Deursoekbare enkripsie skakel lekkasie nooit uit nie; dit laat jou toe om dit bewustelik te kies, per navraagvorm. Gelykheid en voorvoegsel-gelykheid is die lekkasie wat ons gekies het. Daardie raamwerk (kies jou lekkasie, en ontwerp dan alles anders daarom) is die hele dissipline.

Die ontwerp het gewerk. Toe begin die stelselprobleme.

Strik een: die sleutel wat nie geskep kon word nie

Blind indexes benodig 'n HMAC-sleutel per huurder, voorsien in Vault se transit-enjin soos ons enkripsiesleutels. Om een te skep het 'n 500 teruggegee: invalid key size for HMAC key.

Vault vereis 'n eksplisiete key_size vir sleutels van die hmac-tipe (32 tot 512 grepe), terwyl die vaste-grootte-tipes (aes256-gcm96, ecdsa-p256) dit verbied. Ons sleutelskeppingsoproep het slegs {"type":"hmac"} gestuur. Een ontbrekende veld.

Hier is hoekom dit 'n strik was en nie 'n foutverslag nie: elke tokenize-bewerking het 'n uitsondering gegooi, en die aanmeldpad tokeniseer, want om 'n gebruiker by aanmelding via e-pos te vind, gaan deur dieselfde blind index as die admin-soektog. Om enkripsie aan te skakel het nie soektog gebreek nie. Dit het aanmelding gebreek. Die kenmerk waarvan die verkoopspraatjie "jou gebruikers is veiliger" is, het aanmelding platgetrek met die eerste aanskakeling in dev. Die oplossing is key_size=32 (HMAC-SHA256) vir hmac-sleutels, weggelaat vir die vaste-grootte-tipes, en 'n staande reël: rooktoets die tokenize-pad teen 'n regte Vault voordat jy enkripsie enige plek aanskakel. Mocks valideer nie sleutelskepping-payloads nie.

Strik twee: die opdatering wat 'n gebruiker kon laat strand

Om 'n e-pos te verander beteken indeksonderhoud: verwyder die ou rye, skryf die nuwes. Ons eerste implementering het dit in daardie volgorde gedoen: skrap, dan skryf. Natuurlik, netjies, verkeerd.

Elke skryf van 'n nuwe ry betrek nou Vault (die berekening van die HMAC-PartitionKeys). Skrap eers die ou rye, en 'n Vault-hakkel tydens die skryf laat die gebruiker met nóg die ou opsoekrye nóg die nuwes. Hulle bestaan, geënkripteer, in die tabel, en niks kan hulle vind nie. Insluitend aanmelding. Dit is nie 'n gedegradeerde soektog nie; dit is 'n uitgesluite gebruiker, totdat een of ander toekomstige herindeksering verbykom.

Die oplossing is volgorde, nie fouthantering nie: skryf voor skrap, oral waar die indeks onderhou word. 'n Ineenstorting tussen die twee stappe laat nou 'n ekstra verouderde ry agter (skadeloos, lui skoongemaak) in plaas van 'n ontbrekende een. Die faalmodus het verskuif van "gebruiker onbereikbaar" na "een oortollige ry", verniet. Wanneer 'n skryfpad 'n afgeleë afhanklikheid betrek, kies die stapvolgorde waarvan jy met die halfklaar toestand kan saamleef.

Strik drie: die partisie wat 'n invoer opgevreet het

Ons hou ook 'n domein-blind-index (HMAC(domain) → lede), sodat "almal by acme.com" een opsoek is. Deterministiese hashing het 'n gevolg wat niemand inprys voordat 'n invoer plaasvind nie: elke gebruiker van een domein beland in een partisie. 'n Azure Table-partisie hanteer ongeveer 2 000 bewerkings per sekonde. 'n Invoer van 50 000 gebruikers uit een domein vanaf Auth0 het elke domeinindeks-skryf presies in daardie bottelnek ingetregter.

Die oplossing is emmerverdeling: lede word oor 16 partisies versprei volgens 'n hash van die gebruiker-id, en domeinlesings waaier uit oor die emmers, begrens, en skaars genoeg om nie saak te maak nie. Twee besonderhede het die les gedra. Die emmer-hash is 'n handgeskrewe FNV-1a, want .NET se string.GetHashCode is doelbewus onstabiel oor prosesse heen: verdeel daarvolgens, en môre se proses bereken 'n ander emmer vir dieselfde gebruiker en kan nie die ry vind wat dit veronderstel is om te skrap nie. En die leespad vee steeds die verouderde onverdeelde partisies deur, sodat bestaande rye vindbaar gebly het met geen gedwonge terugvul nie: nuwe skryfbewerkings versprei onmiddellik, ou rye migreer wanneer die gebruiker volgende aangeraak word.

Die les

Niks in hierdie storie is nuwe kriptografie nie. HMAC is dekades oud; "hash die waarde, indekseer die hash" pas in een sin. Alles wat ons werklik gekos het, was stelselwerk: watter navraagvorms die produk werklik nodig het (gelykheid, voorvoegsel, domein; elkeen het sy eie indeks gekry, want 'n blind index beantwoord presies een vraag); hoe sleutels voorsien word en wat op die aanmeldpad gebeur wanneer dit nie gebeur nie; in watter volgorde indeksskryfbewerkings plaasvind wanneer 'n afgeleë KMS in die middel sit; en waar deterministiese hashing las konsentreer wat skoonteks nooit gedoen het nie.

Deursoekbare enkripsie word as 'n kripto-kenmerk verkoop. Bou dit en jy sal ontdek dis 'n verspreide-stelsels-kenmerk in 'n kripto-kostuum. Die soekkassie voltooi weer outomaties (ali vind Alistair na drie toetsaanslae), en 'n gesteelde aflaai van dieselfde tabel wys HMAC-hutswaardes uitgewaaier oor sestien emmers, met ander woorde: niks. Albei tegelyk was nog altyd die punt.