De HyperThreading-'bug' uitgelegd

HyperThreading aankondiging De onafhankelijk werkende BSD-programmeur Colin Percival waarschuwde afgelopen vrijdag dat het gebruik van HyperThreading-technologie op servers met meerdere gebruikers een beveiligingsrisico kon vormen. Er zou namelijk een methode bestaan om deze techniek - die al lange tijd standaard in een groot deel van de desktop- en serverchips van Intel zit - te misbruiken voor het achterhalen van encryptiesleutels van anderen. Nu de complete technische details met betrekking tot deze ontdekking bekend zijn gemaakt is het tijd om te bekijken wat er precies aan de hand is. Van te voren kunnen we al melden dat het allemaal niet zo spectaculair is als het in eerste instantie werd gebracht: Het is niet nodig voor Intel om al zijn HyperThreading Xeons terug te roepen, en waarschijnlijk zullen alleen de écht paranoïde systeembeheerders het de moeite waard vinden om er een oplossing voor te zoeken. Toch is het een interessante en vooral slimme truc, dus vandaar dat we er graag nog even aandacht aan willen besteden.

Geheime kanalen

Om een beter idee te krijgen van wat er mogelijk kan gebeuren is het handig om eerst het concept van een 'secret channel' uit te leggen. Dit is een manier voor twee threads om met elkaar te communiceren zonder dat het operating systeem dat kan voorkomen of zelfs maar in de gaten heeft. Beide processen moeten hier bewust aan meewerken, maar een hacker kan op deze manier dus wel alle restricties omzeilen die het operating systeem heeft om gebruikers van elkaar gescheiden te houden. De eerste methode die we zullen bekijken gaat er wel vanuit dat er een bestand is waar beide processen van kunnen lezen, maar verderop zullen we zien dat zelfs dat niet nodig is.

De communicatie werkt op de volgende manier: Het 'verzendende' proces leest een paar delen van het bestand uit. Door het lezen van deze gegevens komen ze automatisch in het geheugen te staan. Het 'ontvangende' proces leest vervolgens het complete bestand uit. Het (virtuele) geheugen van een computer werkt altijd met brokken data van vaste grootte, de zogenaamde pagina's. Door te meten hoe lang het duurt voor iedere pagina van het bestand is opgehaald kan herkend worden welke delen ervan al een keer eerder zijn gelezen. Als een bepaald deel al in het RAM staat zal het immers veel eerder toegankelijk zijn dan wanneer het nog van de harde schijf gehaald moet worden. Door een simpele afspraak te maken (pagina lezen: 1, pagina niet lezen: 0) kunnen op deze manier gegevens in binaire vorm worden overgestuurd.

Wie nu denkt dat dit een gigantisch onhandige methode is met meer nadelen dat wat anders heeft helemaal gelijk. Toch is er een variant die wel degelijk (redelijk) goed werkt. Deze is gebaseerd op het cache van de processor en doet eigenlijk precies het tegenovergestelde van de eerste methode: In plaats van dingen te lezen zodat voor de ander merkbaar is dat ze sneller zijn, duwt deze juist data uit het cache om het voor de ander trager te maken. Het voordeel daarvan ten opzichte van de andere methode is dat de twee threads op deze manier geen toegang hoeven hebben tot een of ander gedeeld bestand, maar behalve het draaien op dezelfde processor geen enkele andere connectie nodig hebben.

Van traag en groot naar klein en snel: harde schijf, systeemgeheugen, L2-cache, L1-cache.

Het equivalent van een geheugenpagina in termen van processorcache is een lijn. Hoewel het operating systeem zelf kan bepalen hoe groot pagina's zijn, liggen cachelijnen vastgelegd in de hardware. Het L1-cache van de Pentium 4-architectuur is bijvoorbeeld opgebouwd uit 128 lijnen van 64 bytes groot. Voor iedere bit die de 'verzender' wil versturen moet het een stuk geheugen reserveren ter grootte van één cachelijn. Om een 32-bits woord te versturen is dus een array van 2048 bytes nodig. De ontvanger reserveert ondertussen een array dat precies even groot is als de capaciteit van het cache (voor het L1 van de Pentium 4 is dat 8KB) en leest dat direct helemaal in. Op dat moment staan er dus alleen nog maar gegevens van de ontvanger in het cache.

Vervolgens is de verzender aan de beurt om bepaalde delen van zijn 2KB-array lezen. Omdat het L1-cache al helemaal volstaat zal iedere keer dat de verzender iets leest een stuk data van de ontvanger weggegooid moeten worden. Als de ontvanger vervolgens weer aan de beurt is kan deze zijn eigen 8KB-array weer een keer nalopen, en meten of (en zo ja ook welke) lijnen door de verzender terug naar het L2-cache zijn geschopt. Er kunnen natuurlijk altijd andere threads tussendoor komen die roet in het eten gooien, maar gegeven dat er gunstige omstandigheden zijn en er een goed foutcorrectie-algoritme in het protocol zit kan op een 2,8GHz Pentium 4 toch een kanaal van 400KB/s worden gerealiseerd.

Ook het L2-cache kan gebruikt worden om een geheim kanaal aan te leggen, maar dat is om verschillende redenen al een stuk lastiger. Ten eerste bevat het L2-cache in tegenstelling tot het L1-cache een mix van instructies en data, waardoor de reden waarom een lijn uit het cache is geschopt minder zeker is. Ook is de extra latency bij ontbrekende gegevens minder consequent, omdat dankzij de TLB (translation lookaside buffer) de helft van de lijnen sneller in het geheugen kan worden gevonden dan de andere helft. Ook kan het hardwarematige prefetch-mechanisme roet in het eten gooien als er in een (te) voorspelbaar patroon uit het cache wordt gelezen. Toch is het mogelijk om deze problemen te omzeilen en een kanaal met een bandbreedte van ongeveer 100KB/s aan te leggen.

Tot nu toe hebben we gezien dat het mogelijk is voor twee threads om op een zeer vernuftige manier met elkaar te communiceren door op een van te voren afgesproken manier samen te werken. Is het dan ook mogelijk om gegevens uit een andere thread te krijgen zónder dat deze daaraan meewerkt? Het antwoord daarop is nee. Er zit geen bug in de hardware, dus als het operating systeem aangeeft dat iets niet gelezen mag worden, dan kan dat ook niet gelezen worden. Waarom dan toch de ophef? Omdat iemand met zeer specifieke kennis over de implementatie van een encryptie-algoritme én informatie over het moment waarop dit wordt uitgevoerd een idee kan krijgen van wat er achter gesloten deuren gebeurt. Dit gaat op een manier die veel lijkt op de geheime kanalen. In dit geval is er echter geen 'verzender' die expliciet gegevens aan het versturen is, maar wordt er simpelweg geluisterd naar de ruis veroorzaakt door het encryptieproces. Zometeen zullen we zien hoe het uitvoeren van 1024-bit RSA-encryptie met OpenSSL eruit ziet voor een cache-spion.

In het onderstaande plaatje zijn op de x-as alle cachelijnen die in de gaten worden gehouden uiteengezet. De y-as is het verloop van de tijd gemeten in klokcycles, waaraan te zien is dat het plaatje slechts gegevens verzameld over een zeer korte periode representeert (500.000 cycles worden er door een 2,8GHz-processor binnen 0,2 milliseconde doorheen gejaagd). De kleur van de blokjes geeft aan hoe kort of lang het steeds duurde voor iedere cachelijn beschikbaar was. Hieruit is met een redelijk grote mate van nauwkeurigheid af te leiden of ze wel of niet uit het cache werden gegooid door het encryptieproces. De schaal loopt van een wit blok (120 cycles) tot een zwart blok (170+ cycles). Omcirkeld zijn de patronen die interessant zijn voor iemand die wil proberen om de key te achterhalen.

De reden waarom de omcirkelde lijntjes informatie bevatten over de gebruikte sleutel is de manier waarop het RSA-algoritme door de makers van OpenSSL is geïmplementeerd. Omdat deze vorm van encryptie rekenkundig behoorlijk zwaar is wordt de berekening zo ver mogelijk geoptimaliseerd, onder andere door de wiskundige handeling x := a^d mod p om te schrijven naar een hele serie kwadrateringen en een vermenigvuldiging. Een andere optimalisatie is dat de getallen waarmee vermenigvuldigd moet worden van te voren worden uitgerekend en in een tabel worden gezet, zodat ze herbruikt kunnen worden in plaats van keer op keer opnieuw uitgerekend moeten worden. Hierdoor kan de afluisterthread makkelijk herkennen wanneer vermeningvuldigd wordt, want zodra er een waarde uit die tabel gehaald wordt moet er iets van hem uit het cache verwijderd worden om er plaats voor te maken. Uit iedere vermeningvuldiging (en het aantal kwadrateringen dat eraan vooraf ging) kan een bit van de sleutel worden afgeleid. Op deze manier kunnen er in goede omstandigheden zo'n 200 bits van beide 512-bit exponenten worden blootgelegd. De rest gaat verloren in de ruis die wordt veroorzaakt door andere threads.

Op dat moment is er nog steeds niet genoeg informatie beschikbaar om de complete sleutel te achterhalen, maar door goed te kijken naar de volgorde waarin de verschillende multipliers gebruikt worden kunnen meer gegevens afgeleid worden. Hier komt een hoop onzekerheid bij kijken (onder andere omdat het niet zeker is dat dezelfde waarde steeds op dezelfde plek in het cache komt te staan), maar geschat wordt dat voor de helft van de vermenigvuldigingen het aantal mogelijke multipliers teruggebracht kan worden tot twee. Statistisch gezien zou dat genoeg data moeten zijn om van beide delen nog eens 110 extra bits te bepalen, waarna in totaal dus ongeveer 310 van de 512 bits van beide exponenten beschikbaar zijn. Dit is voor crypto-analisten wèl genoeg informatie om de sleutel in relatief korte tijd te kunnen breken.

Oplossingen

HyperThreading Er worden door de ontdekker van het (potentiële) probleem een aantal verschillende oplossingen aangedragen om computers tegen dit soort aanvallen te kunnen verdedigen. De processor zou bijvoorbeeld aangepast kunnen worden om te voorkomen dat threads elkaars gegevens continu uit het cache kunnen wippen. In latere steppings van de Pentium 4 is dat overigens al zo, dus wat dat betreft hoeft men zich sowieso al geen zorgen meer te maken. Verder zou de hardware het zo vaak en nauwkeurig opmeten van alle latencies kunnen tegenhouden, maar dit kan natuurlijk compatibiliteitsproblemen opleveren en is dus geen realistische optie. Volgens de auteur kan daarom beter een oplossing gezocht worden aan de kant van de software. Een vrij complexe maar effectieve oplossing zou zijn dat de scheduler geen twee threads met verschillende rechten tegelijk laat draaien op dezelfde processor. Simpeler is echter een soort "secure mode" in het leven roepen voor threads, waarin iedere keer standaard het hele cache geflushed wordt, zodat er geen enkel herkenbaar patroon wordt achtergelaten.

Conclusie: Storm in een glas water

Hoewel de 'exploit' van HyperThreading zeker interessant en slim genoemd kan worden, is het concept van dit soort zogenaamde timing-aanvallen bij lange na niet nieuw te noemen. Andere onderzoekers hadden soortgelijken technieken om informatie over geheime sleutels te achterhalen al eerder gedemonstreerd op systemen met twee fysieke processors, en onder bepaalde gecontroleerde condities schijnt het zelfs met een enkele single-threaded processor mogelijk te zijn. HyperThreading kan het misschien dan wel makkelijker maken om het te doen, maar het blijft een zeer ingewikkelde methode waar een diepgaand begrip van de hardware, het gebruikte algoritme en de implementatie daarvan nodig is. Verder is timing cruciaal en zijn bijna onrealistisch gunstige omstandigheden nodig om een 'schoon signaal' af te kunnen tappen. Al met al hoeft het gemiddelde bedrijf zich weinig zorgen te maken over de veiligheid van zijn servers met HyperThreading. Voor de echte securityfreaks is het echter wel leuk hersenvoer .