Door Wouter Tinus

De HyperThreading-'bug' uitgelegd

14-05-2005 • 15:24

37

Multipage-opmaak

Geheime communicatie

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.

Cacheing
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.

Storm in een glas water

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.

Cachespion

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 .

Reacties (37)

37
36
21
3
0
5
Wijzig sortering
Dus als ik het goed begrijp is dit een mogelijke optie tot exploitering van een algoritme dat op een specifieke manier geimplementeerd en uitgevoerd wordt, werkt op een zeer beperkt aantal processoren mits een bepaalde feature aan staat, de processen tegelijk draaien en je zeker weet dat die ander die encryptie doet met die key en diezelfde compile heeft van openssl en RSA gebruikt?

Ik zie niet waarom dit ook maar 1 keer toepasbaar zou zijn.
Hyperthreading processoren komen vrij veel voor en het is meestal makkelijk te achterhalen welke versie van OpenSSL er geïnstalleerd is, want dat is geen geheime informatie. Voor hackers die lokale toegang hebben op een server is het dus al gauw een optie.
Mja, als je een programma kan uitvoeren op een server waarop dus uiterst belangrijke geheime info staat, vind ik dat ook knap; dat mag al helemaal niet kunnen. Als je aan de locale kan het programma uitvoert, kun je net zo goed meteen die keys stelen. Dus tsja.
@bericht: (Sorry, op verkeerde plek gepost, reactie op het bericht hierna)
Om de heisa omtrent deze bug uit te leggen, moet je het volgende snappen:
Het gaat hier om cryptografen.
-Onder cryptografen is het niet erg als men door een brute-force attack de sleutel kan achterhalen, via X stappen.
-ALLE manieren die ervoor zorgen dat je de sleutel in minder dan X stappen kan achterhalen, worden in de cryptografie als een LEK van het schema gezien.
Dus ook al zou je maar 1 bitje van het paswoord te weten komen, dan nog zou je de sleutel 2x zo snel kunnen achterhalen dan bij brute-force, en is het algoritme in de cryptografie dus 'lek'.
Waarom zo'n heisa over deze 'bug'???? Het zal nooi tgebruikt worden om code's te kraken aangezien je er een crypto-analist bij moet hebben, en die hebben de meeste hackers niet in de kast liggen. Verder is het probleem dus al opgelost bij de nieuwste pentium 4. Lekker boeiend dus allemaal....
Zover ik alle berichten op andere sites/freebsd mailinglist heb gelezen is het zeer zeker wel boeiend. Alle bsd's die hyperthreading support hebben (freebsd/netbsd) hebben dit dan nu ook standaard uitstaan.

zie de mails op http://docs.freebsd.org/mail/current/freebsd-security.html
Ik zit op basis van de FreeBSD Security Advisory nogal te twijfelen of ik HTT op mijn Dual Xeon-servers moet uitzetten of niet.
Dat FreeBSD het standaard aanraadt is niet voor niets... maar als ik het bovenstaande moet geloven weegt het performanceverlies niet op tegen dat hele kleine potentiele risico.
Hoe gaan andere FreeBSD'ers hier mee om?
In principe moet je als volgt redeneren: heb je shell dozen waar je klanten toegang toe hebben (ISP's hebben dat soort bakken) of webservers waar klanten scripts op kunnen draaien: dan is het nuttig om HT uit te zetten. (is maar een sysctl)

heb je dozen die performance nodig hebben, maar waarop buiten techneuten om niemand op kan, dan kun je 't redelijk veilig aan laten staan.
al eerder gedemonstreerd op systemen met twee fysieke processors
Zet maar aan dus, je bent toch al de lul met twee procs :Y)
Er is bij mijn inzicht een best wel een groot programma nodig om er misbruik van de maken, niets iets wat toevallig aan een mail vast zit.

Ik denk dan ook dat de kans klein is dat een hacker dit ooit zal gebruiken .
Het is te ingewikkeld en te lastig, tegen de tijd dat er een programma voor is , is de software al aangepast.
in de bron staat een code van maar een paar ASM regeltjes
Dat is dan ook alleen maar het loopje om de latencies te meten.
Ik denk dan ook dat de kans klein is dat een hacker dit ooit zal gebruiken .
Het is te ingewikkeld en te lastig, tegen de tijd dat er een programma voor is , is de software al aangepast.
haal je nu niet twee compleet verschillende groepen door elkaar? Een scriptkiddie zal inderdaad niet aan dit soort meuk beginnen, snapt ie toch niet. Maar een echte cracker/hacker zal wel degelijk deze truuk gebruiken als hij daartoe mogelijkheid ziet. Derhalve zal deze techniek ook getest worden bij security audits in de toekomst.
Misschien snap ik het niet helemaal hoor, maar als je al zo ver bent dat je kan kijken wat er op een processor gebeurt, HEB je al toegang tot de machine en in veel gevallen is dat al meer dan genoeg om leuke dingen te kunnen doen.

Stel: Er wordt op die computer iets met gruwelijke encryptie gedaan om geld over te maken. Ga je dan moeilijk lopen doen om de RSA kraken, of zet je een regeltje in het .txt bestand er bij met je rekeningnummer in Zwitserland?
Je mist het fundamentele punt. Op een normale server zijn processen van gebruikers strict gescheiden: je kunt als gebruiker processen van andere gebruikers niet inzien of wijzigen, dus als jij een lokaal account hebt dan kun je daarmee nog geen bestanden wijzigen. Sterker nog: het besturingssysteem garandeert je dat processen en bestanden die alleen van de ene gebruiker zijn niet door andere gebruikers gelezen kunnen worden.

De ophef ontstaat juist doordat het met de genoemde methode mogelijk is om de restricties die het besturingssysteem oplegt ten dele te omzeilen. Het gaat hierbij dus ook niet om een Windows XP bak waar iedereen als Administrator op inlogt, zodat je als je eenmaal ingelogt bent in willekeurige bestanden bankrekeningnummers kan zetten. ;)
hmmm.... RSA kraken... zien ze niet...
Dus als ik het goed heb, heeft de P4 een L1 cache van 8 KB groot en is 128 bits.
En (zoals in het artikel uitgelegd) heb je voor een woord of wat dan ook van 32 bits 2 KB nodig, en wil je je L1 cache van 8 KB groot dus in 1 keer lezen en schrijven met een 32 bits CPU dit doen in 4 stappen.

Dus al was de L1 cache van de P4, 32 KB groot (om 1 in keer de 512 bit key in de L1 cache op te slaan) dan nog was de kans om een 512 bits RSA key kunnen kraken best klein.
Je hebt dan 16 stappen nodig wat de kans nog kleiner maakt, en CPUŽtjes van Intel met EMT64 draaien intern volgens mij nog gewoon 32 bits.
Dus als ik het goed heb [...]
Je hebt het niet goed. Ik kan nog niet eens beginnen om alle fouten in je reactie aan te wijzen, dus ik zou je aanraden om het artikel gewoon nog eens een keer rustig door te lezen.
Is dit misschien de geheime manier waarop de Amerikanen al onze computerzaken afluisteren, hun backdoor voor onze encryptie? ;)
Is dit misschien de geheime manier waarop de Amerikanen al onze computerzaken afluisteren, hun backdoor voor onze encryptie?
Met een AMD ben je veiliger, geen hyperthreading :+
en onder bepaalde gecontroleerde condities schijnt het zelfs met een enkele single-threaded processor mogelijk te zijn
Ook met een AMD kun je dus potentieel een 'probleem' hebben.
dit is zeker geen backdoor. Een van de twee hoofd kenmerken van een backdoor is dat het makkelijk is.

als je het andere kenmerk niet kent...

de beschreven manier is niet simpel met een progje als een trojan uit te voeren. er moet wat meer intelligentie, feeling en heel veel geluk bij komen kijken. Op het moment dat er maar van 1 thread encryptie gebruikt wordt werkt dit. is het een druk apparaat met veeel threads tegelijkertijd is dit haast onmogelijk.

dit is dus geen backdoor.
Ik vermoed dat het ook niet de gemiddelde hacker is die hier misbruik van gaat maken. Als je bedrijf waardevolle informatie bevat hoeft er dus maar een hoge bieder voor de informatie te zijn, een superslimme nerd die dit programma door de server uit laat voeren, hoopt dat de keys niet veranderen, naar huis gaat, verder analyseerd, ondertussen het programma data uit het cache-geheugen te laten stelen em dit ook mee nemen ter analysatie, later alles wat hij heeft decodeert... en daar heeft hij de wachtwoorden van de gebruikers of andere kostbare informatie...
Goed stuk!
Zet je aan het denken :)

Nooit geweten dat dit soort zaken tot de mogelijkheden behoorde... Valt dus nog veel voor me te leren ;)
Heeft het geen gevolgen voor sommge wedstrijden om de sleutel te kraken?
We hebben vroeger en nu boel koeien laten grazen om sleutel te vinden. Zou met deze ontdekking niet eerder gevonden worden (sommige mensen doen graag alles voor leuke hoofdprijs....) en dat het een roet in wedstrijdverloop kan gooien?

Of hoeven we geen zorgen over te maken? ;)

Op dit item kan niet meer gereageerd worden.