De HyperThreading-'bug' uitgelegd

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

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 .