Tidsangreb

I kryptografi er et timingangreb et sidekanalangreb , hvor en angriber forsøger at kompromittere et kryptosystem ved at analysere den tid, det tager at udføre kryptografiske algoritmer. Hver logisk handling tager tid at udføre på computeren, og denne tid kan variere afhængigt af inputdataene. Med nøjagtige tidsmålinger for forskellige operationer kan en angriber gendanne inputdataene.

Kryptosystemer bruger ofte lidt forskellig mængde tid på at behandle forskellige input. Årsagerne til dette kan være ydelsesoptimeringer, der springer unødvendige operationer over, forgrening , læsning af data fra cachen , processorinstruktioner (såsom multiplikation og division), der udføres i ikke-deterministisk tid, og andre. Ydeevneegenskaberne afhænger normalt af både krypteringsnøglen og inputdataene. Samtidig kan den tid, der bruges på udførelsen af visse anmodninger, blive en kilde til informationslækage om systemet. Hvor meget sådan information kan hjælpe en angriber afhænger af mange parametre, såsom: designet af kryptosystemet, processoren, de anvendte algoritmer, de relevante implementeringsdetaljer, modforanstaltningerne mod timingangrebet, nøjagtigheden af de forsinkelsesmålinger, der er taget.

Et angreb på den hurtige eksponentieringsalgoritme

Den hurtige eksponentieringsalgoritme brugt af Diffie-Hellman og RSA algoritmerne udfører følgende operation på den hemmelige nøgle , hvor n er en del af den offentlige nøgle (RSA) eller en konstant (Diffie-Hellman), og y kan overhøres. Angriberens mål er at få den hemmelige nøgle x . Offeret beregner flere y- værdier . w er bitlængden af nøglen x . $R=y^{x}{\bmod {n))$ $y^{x}{\bmod {n))$

Lad~s_{{0}}~=~1

For~k=0~op til~w-1:

Hvis~(bit~k~af~x)~er~1~så

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

Else

Lad~R_{{k}}~=~s_{{k}}

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

EndFor

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

Angrebet tillader, at kende bits 0..(b-1) , at finde bit b . For at få hele eksponenten kan man starte med b=0 og fortsætte indtil hele eksponenten er kendt.

Ved at kende de første b bits af x , kan angriberen beregne de første b iterationer af løkken og finde værdien af . Den næste iteration bruger den første ukendte bit af x . Hvis den er lig med 1, udføres beregningen , hvis den er 0, springes operationen over. $Til$ $s_{{b}}$ $R_{b}=(s_{b}\cdot y){\bmod {n}}$

Brug af den kinesiske restsætning

For at optimere hemmelige nøgleoperationer i RSA , bruges den kinesiske restsætning ofte . Først og beregnes , hvor y er beskeden. Det enkleste angreb er at vælge y tæt på p eller q . Hvis y er mindre end p , vil den ikke gøre noget, og hvis , skal den trække p fra y mindst én gang. Også, hvis y er lidt større end p , så vil den have de mest signifikante bit lig med nul, hvilket kan reducere tiden for den første multiplikation. Specifik timing er implementeringsafhængig. $y{\bmod {p}}$ $y{\bmod {q}}$ $y{\bmod {p}}$ $y>s$ $y{\bmod {p}}$

Eksempler på angreb på RSA: Timing angreb på RSA og Timing angreb på RSA

Temporal kryptoanalyse DSS

Digital Signature Standard- algoritmen beregner , hvor p og q er kendt af angriberen og beregnet på forhånd, H(m) er meddelelsens hash, x er den hemmelige nøgle. I praksis bliver det først udregnet og derefter ganget med . Angriberen kan beregne H(m) og rette i overensstemmelse hermed. Da H(m) har omtrent samme størrelse som q , har addition kun ringe effekt på reduktionsoperationen i Montgomery-eksponentieringsmetoden ( en ). De højeste bits vil være de mest signifikante . Værdien af r er kendt. Der er en sammenhæng mellem de høje bits af x og udførelsestiden for Montgomery-reduktionsoperationen. Hvis den beregnes på forhånd, kræver meddelelsessignaturen kun to modulo-multiplikationer, så mængden af tilføjet støj bliver relativt lille. $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}}$

Timing maskering

Den mest oplagte måde at forhindre timing af angreb på er at sikre, at alle operationer tager lige lang tid. Det er dog vanskeligt at implementere en sådan løsning, især en platform-uafhængig, da optimeringer udført af compileren, cache-adgange, instruktionstidspunkter og andre faktorer kan introducere uforudsete tidsafvigelser. Hvis en timer bruges til at forsinke outputtet af resultatet, forbliver systemets reaktionsevne observerbar. Nogle operativsystemer giver også niveauer af processorbelastning og strømforbrug.

En anden tilgang er at gøre tidsmålingerne så unøjagtige, at angrebet bliver uudholdeligt. Tilfældige forsinkelser føjes til eksekveringstiden, hvilket øger antallet af chiffertekster, der kræves for en angriber.

Angrebsforebyggelse

Teknikker, der bruges til at skabe blinde signaturer (se også Blinding ) kan tilpasses for at forhindre en angriber i at udsætte inputtet for en modulo-eksponentieringsoperation. Før vi beregner den modulære eksponent, vælger vi et tilfældigt par , således at . For Diffie-Hellman er det nemmere først at vælge en tilfældig og derefter beregne . For RSA er det hurtigere at vælge en tilfældig coprime med n og derefter beregne , hvor e er en del af den offentlige nøgle. Inden der udføres eksponentieringsmodulo, skal inputmeddelelsen ganges med , og derefter skal resultatet korrigeres ved at gange med . Systemet bør kassere meddelelser svarende til . $(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}}$

Beregning af det inverse modulo betragtes som en langsom operation, så det er ofte upraktisk at generere et nyt par for hver eksponentieringsoperation. De kan dog ikke genbruges, da de selv kan blive angrebet af tiden. Der er en løsning: Opdater og før hver eksponentieringsoperation ved at beregne og . $(v_{{i}},v_{{f}})$ $v_{{i}}$ $v_{{f}}$ $v_{{i}}^{{'}}=v_{{i}}^{{2}}$ $v_{{f}}^{{'}}=v_{{f}}^{{2}}$