Atac în timp

În criptografie , un atac de sincronizare este un atac pe canal lateral în care un atacator încearcă să compromită un sistem criptografic analizând timpul necesar pentru a executa algoritmi criptografici. Fiecare operație logică necesită timp pentru a fi executată pe computer, iar acest timp poate varia în funcție de datele de intrare. Cu măsurători precise ale timpului pentru diferite operațiuni, un atacator poate recupera datele de intrare.

Criptosistemele petrec adesea cantități ușor diferite de timp procesând diferite intrări. Motivele pentru aceasta pot fi optimizări de performanță care ignoră operațiunile inutile, ramificarea , citirea datelor din memoria cache , instrucțiunile procesorului (cum ar fi înmulțirea și împărțirea) care se execută în timp nedeterminist și altele. Caracteristicile de performanță depind de obicei atât de cheia de criptare , cât și de datele de intrare. În același timp, timpul petrecut pentru executarea anumitor solicitări poate deveni o sursă de scurgere de informații despre sistem. Cât de mult pot ajuta astfel de informații un atacator depinde de mulți parametri, cum ar fi: designul criptosistemului, procesorul care servește sistemul, algoritmii utilizați, detaliile relevante de implementare, contramăsurile luate împotriva atacului de sincronizare, acuratețea întârzierii. măsurătorile luate.

Un atac asupra algoritmului de exponențiere rapidă

Algoritmul de exponențiere rapidă utilizat de algoritmii Diffie-Hellman și RSA efectuează următoarea operație pe cheia secretă , unde n face parte din cheia publică (RSA) sau o constantă (Diffie-Hellman) și y poate fi auzit. Scopul atacatorului este de a obține cheia secretă x . Victima calculează pentru mai multe valori y . w este lungimea de biți a cheii x . $R=y^{x}{\bmod {n)}$ $y^{x}{\bmod {n)}$

Să~s_{{0}}~=~1

Pentru~k=0~până la~w-1:

Dacă~(bit~k~of~x)~este~1~atunci

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

Else

Să~R_{{k}}~=~s_{{k}}

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

EndFor

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

Atacul permite, cunoscând biții 0..(b-1) , să se găsească bitul b . Pentru a obține întregul exponent, se poate începe cu b=0 și se poate continua până când se cunoaște întregul exponent.

Cunoscând primii b biți ai lui x , atacatorul poate calcula primele b iterații ale buclei și poate găsi valoarea lui . Următoarea iterație folosește primul bit necunoscut al lui x . Dacă este egal cu 1, calculul va fi efectuat , dacă este 0, atunci operația va fi omisă. $Pentru$ $s_{{b}}$ $R_{b}=(s_{b}\cdot y){\bmod {n}}$

Folosind teorema chineză a restului

Pentru a optimiza operațiunile chei secrete în RSA , este adesea folosită teorema chineză a restului . În primul rând, și sunt calculate , unde y este mesajul. Cel mai simplu atac este să alegeți y aproape de p sau q . Dacă y este mai mic decât p , nu va face nimic, iar dacă , va trebui să scadă p din y cel puțin o dată. De asemenea, dacă y este puțin mai mare decât p , atunci va avea cei mai semnificativi biți egali cu zero, ceea ce poate reduce timpul primei înmulțiri. Timpul specific depinde de implementare. $y{\bmod {p}}$ $y{\bmod {q}}$ $y{\bmod {p}}$ $y>p$ $y{\bmod {p}}$

Exemple de atacuri asupra RSA: atacuri cu timp asupra RSA și atacuri cu timp asupra RSA

Criptanaliza temporală DSS

Algoritmul Digital Signature Standard calculează , unde p și q sunt cunoscute atacatorului și sunt calculate în avans, H(m) este hash-ul mesajului, x este cheia secretă. În practică, mai întâi se calculează și apoi se înmulțește cu . Atacatorul poate calcula H(m) și poate corecta în consecință. Deoarece H(m) are aproximativ aceeași dimensiune cu q , adăugarea are un efect redus asupra operației de reducere în metoda exponențiării Montgomery ( en ). Cei mai înalți biți vor fi cei mai semnificativi . Valoarea lui r este cunoscută. Există o relație între biții mari ai lui x și timpul de execuție al operației de reducere Montgomery. Dacă este calculată în avans, semnătura mesajului necesită doar două înmulțiri modulo, astfel încât cantitatea de zgomot adăugată devine relativ mică. $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}}$

Mascare temporală

Cea mai evidentă modalitate de a preveni atacurile de timp este să vă asigurați că toate operațiunile durează același timp. Cu toate acestea, este dificil de implementat o astfel de soluție, în special una independentă de platformă, deoarece optimizările efectuate de compilator, accesările în cache, timpul de instrucțiuni și alți factori pot introduce abateri de sincronizare neprevăzute. Dacă se folosește un temporizator pentru a întârzia ieșirea rezultatului, capacitatea de răspuns a sistemului rămâne observabilă. De asemenea, unele sisteme de operare oferă niveluri de încărcare a procesorului și consum de energie.

O altă abordare este de a face măsurătorile de timp atât de inexacte încât atacul să devină insuportabil. La timpul de execuție se adaugă întârzieri aleatorii, crescând numărul de texte cifrate necesare unui atacator.

Prevenirea atacurilor

Tehnicile folosite pentru a crea semnături oarbe (vezi și Orbirea ) pot fi adaptate pentru a preveni un atacator să expună intrarea la o operație de exponențiere modulo. Înainte de a calcula exponentul modular, alegem o pereche aleatorie astfel încât . Pentru Diffie-Hellman, este mai ușor să alegeți mai întâi unul aleatoriu și apoi să calculați . Pentru RSA, este mai rapid să alegeți un coprim aleator cu n și apoi să calculați , unde e este parte a cheii publice. Înainte de a efectua modul de exponențiere, mesajul de intrare trebuie înmulțit cu , iar apoi rezultatul trebuie corectat prin înmulțirea cu . Sistemul ar trebui să renunțe la mesaje egale cu . $(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}}$

Calcularea modulo invers este considerată o operație lentă, deci este adesea imposibil să se genereze o nouă pereche pentru fiecare operație de exponențiere. Cu toate acestea, nu pot fi reutilizate, deoarece ei înșiși pot fi atacați de timp. Există o soluție: actualizați și înainte de fiecare operație de exponențiere prin calcul și . $(v_{{i}},v_{{f}})$ $v_{{i}}$ $v_{{f}}$ $v_{{i}}^{{'}}=v_{{i}}^{{2}}$ $v_{{f}}^{{'}}=v_{{f}}^{{2}}$

Link -uri

Paul C. Kocher. Timing atacuri asupra implementărilor Diffie-Hellman, RSA, DSS și alte sisteme . CRYPTO 1996: 104-113.
David Brumley, Dan Boneh. Atacurile de la distanță sunt practice . Simpozionul de securitate USENIX , august 2003.