Tidsattack

Inom kryptografi är en timingattack en sidokanalsattack där en angripare försöker äventyra ett kryptosystem genom att analysera den tid det tar att exekvera kryptografiska algoritmer. Varje logisk operation tar tid att utföra på datorn, och denna tid kan variera beroende på indata. Med exakta tidsmätningar för olika operationer kan en angripare återställa indata.

Kryptosystem lägger ofta lite olika lång tid på att bearbeta olika indata. Orsakerna till detta kan vara prestandaoptimeringar som hoppar över onödiga operationer, förgrening , läsning av data från cachen , processorinstruktioner (som multiplikation och division) som körs i icke-deterministisk tid och annat. Prestandaegenskaperna beror vanligtvis på både krypteringsnyckeln och indata. Samtidigt kan tiden som läggs på att utföra vissa förfrågningar bli en källa till informationsläckage om systemet. Hur mycket sådan information kan hjälpa en angripare beror på många parametrar, såsom: utformningen av kryptosystemet, processorn som betjänar systemet, de algoritmer som används, de relevanta implementeringsdetaljerna, de motåtgärder som vidtagits mot tajmingsattacken, fördröjningens noggrannhet gjorda mätningar.

En attack på den snabba exponentieringsalgoritmen

Den snabba exponentieringsalgoritmen som används av Diffie-Hellman och RSA-algoritmerna utför följande operation på den hemliga nyckeln , där n är en del av den publika nyckeln (RSA) eller en konstant (Diffie-Hellman) och y kan höras. Angriparens mål är att få den hemliga nyckeln x . Offret beräknar för flera y -värden . w är bitlängden för nyckeln x . $R=y^{x}{\bmod {n))$ $y^{x}{\bmod {n))$

Låt~s_{{0}}~=~1

För~k=0~upp till~w-1:

Om~(bit~k~av~x)~är~1~då

LetR_{k}=(s_{k}\cdot y){\bmod {n))

Else

Låt~R_{{k}}~=~s_{{k}}

Let~s_{k+1}=R_{k}^{2}{\bmod {n))

EndFor

Retur~(R_{{w-1}})

Attacken tillåter, att känna till bitarna 0..(b-1) , att hitta biten b . För att få hela exponenten kan man börja med b=0 och fortsätta tills hela exponenten är känd.

Genom att känna till de första b bitarna av x , kan angriparen beräkna de första b iterationerna i slingan och hitta värdet på . Nästa iteration använder den första okända biten av x . Om det är lika med 1 kommer beräkningen att utföras , om det är 0 kommer operationen att hoppas över. $För$ $s_{{b}}$ $R_{b}=(s_{b}\cdot y){\bmod {n))$

Använda den kinesiska restsatsen

För att optimera hemliga nyckeloperationer i RSA används ofta den kinesiska restsatsen . Först och beräknas , där y är meddelandet. Den enklaste attacken är att välja y nära p eller q . Om y är mindre än p , kommer den att göra ingenting, och om , måste den subtrahera p från y minst en gång. Dessutom, om y är något större än p , kommer den att ha de mest signifikanta bitarna lika med noll, vilket kan minska tiden för den första multiplikationen. Specifik tidpunkt är implementeringsberoende. $y{\bmod {p}}$ $y{\bmod {q}}$ $y{\bmod {p}}$ $y> sid$ $y{\bmod {p}}$

Exempel på attacker mot RSA: Tajming av attacker mot RSA och Timing av attacker mot RSA

Temporal kryptoanalys DSS

Algoritmen för digital signaturstandard beräknar , där p och q är kända för angriparen och beräknade i förväg, H(m) är meddelandehash, x är den hemliga nyckeln. I praktiken beräknas det först och multipliceras sedan med . Angriparen kan beräkna H(m) och korrigera därefter. Eftersom H(m) är ungefär lika stor som q , har addition liten effekt på reduktionsoperationen i Montgomery-exponentieringsmetoden ( en ). De högsta bitarna kommer att vara de mest signifikanta . Värdet på r är känt. Det finns ett samband mellan de höga bitarna av x och exekveringstiden för Montgomery-reduktionsoperationen. Om den beräknas i förväg kräver meddelandesignaturen endast två modulo-multiplikationer, så mängden extra brus blir relativt liten. $s=(k^{-1}(H(m)+x\cdot r)){\bmod {q))$ $k^{{-1}}$ $(H(m)+x\cdot r){\bmod {q))$ $k^{-1}{\bmod {q))$ $x\cdot r$ $k^{{-1}}$

Tidsmaskering

Det mest uppenbara sättet att förhindra timingattacker är att se till att alla operationer tar lika lång tid. Det är dock svårt att implementera en sådan lösning, särskilt en plattformsoberoende, eftersom optimeringar som utförs av kompilatorn, cache-åtkomster, instruktionstidningar och andra faktorer kan introducera oförutsedda tidsavvikelser. Om en timer används för att fördröja utmatningen av resultatet, förblir systemets reaktionsförmåga observerbar. Vissa operativsystem ger också ut nivåer av processorbelastning och strömförbrukning.

Ett annat tillvägagångssätt är att göra tidsmätningarna så inexakta att attacken blir outhärdlig. Slumpmässiga förseningar läggs till avrättningstiden, vilket ökar antalet chiffertexter som krävs för en angripare.

Attackförebyggande

Tekniker som används för att skapa blinda signaturer (se även Blindning ) kan anpassas för att förhindra en angripare från att exponera indata för en modulo-exponentieringsoperation. Innan vi beräknar den modulära exponenten väljer vi ett slumpmässigt par så att . För Diffie-Hellman är det lättare att först välja en slumpmässig och sedan beräkna . För RSA är det snabbare att välja en slumpmässig coprime med n och sedan beräkna , där e är en del av den publika nyckeln. Innan exponentieringsmodulo utförs måste ingångsmeddelandet multipliceras med , och sedan måste resultatet korrigeras genom att multipliceras med . Systemet bör kassera meddelanden som är lika med . $(v_{{i}},v_{{f}})$ $v_{f}^{-1}=v_{i}^{x}{\bmod {n))$ $v_{{i}}$ $v_{f}={(v_{i}^{-1})^{x}}{\bmod {n}}$ $v_{{f}}$ $v_{i}={(v_{f}^{-1})}^{e}{\bmod {n))$ $v_{i}{\pmod {n))$ $v_{f}{\pmod {n))$ $0{\pmod {n}}$

Att beräkna invers modulo anses vara en långsam operation, så det är ofta opraktiskt att generera ett nytt par för varje exponentieringsoperation. De kan dock inte återanvändas, eftersom de själva kan attackeras av tiden. Det finns en lösning: uppdatera och före varje exponentieringsoperation genom att beräkna och . $(v_{{i}},v_{{f}})$ $v_{{i}}$ $v_{{f}}$ $v_{{i}}^{{'}}=v_{{i}}^{{2}}$ $v_{{f}}^{{'}}=v_{{f}}^{{2}}$

Länkar

Paul C. Kocher. Tajming av attacker på implementeringar av Diffie-Hellman, RSA, DSS och andra system . CRYPTO 1996: 104-113.
David Brumley, Dan Boneh. Timingattacker på distans är praktiska . USENIX Security Symposium, augusti 2003.