Atacul cu text cifrat ales

Versiunea actuală a paginii nu a fost încă revizuită de colaboratori experimentați și poate diferi semnificativ de versiunea revizuită pe 21 decembrie 2018; verificarea necesită 1 editare .

Chosen - ciphertext attack este un atac criptografic în care un criptoanalist colectează informații despre un cifru ghicind textul cifrat și decriptându-l cu o cheie necunoscută. De obicei, un criptoanalist poate folosi decriptorul o dată sau de mai multe ori pentru a obține textul cifrat decriptat. Folosind datele primite, el poate încerca să recupereze cheia secretă pentru decriptare. Există cifruri pentru care acest tip de atac poate avea succes. Acestea includ: Schema ElGamal ; RSA , utilizat în protocolul SSL ; NTRU . Pentru protecție se folosesc cifrurile RSA-OAEP și Cramer-Showe .

Un atac cu text cifrat poate fi adaptiv sau neadaptativ.

Atacul bazat pe text cifrat dezadaptativ

Într-un atac neadaptativ, criptoanalistul nu folosește rezultatele decriptărilor anterioare, adică textele cifrate sunt selectate în avans. Astfel de atacuri sunt numite atacuri la ora prânzului ( lunchtime sau CCA1 ).

Atacul bazat pe un text cifrat ales adaptativ

În caz contrar, criptoanalistul selectează adaptiv un text cifrat care depinde de rezultatele decriptărilor anterioare ( CCA2 ).

Atacul asupra protocoalelor bazate pe standardul de criptare RSA PKCS#1

O scurtă descriere a standardului RSA PKCS#1

Unul dintre reprezentanții criptosistemelor cu cheie publică ( Public Key Cryptography Standards ), bazat pe algoritmul RSA. Fie k lungimea de octeți a modulului RSA, n. Există multe variante ale standardului PKCS#1. În acest exemplu, versiunea RSAES-PKCS1-v1_5 este considerată fără a utiliza o semnătură digitală, al doilea octet al blocului de mesaje este 00 sau 01. Standardul poate opera cu mesaje cu o lungime maximă egală cu k-11. Blocul standard PKCS#1, EB, este format din k octeți. Forma sa este EB = 00||02||PS||00||D. Primii doi octeți sunt constanți și egali cu 00 și, respectiv, 02. PS este un șir de umplere, un număr pseudo-aleatoriu generat format din octeți diferit de zero. Pentru a crește nivelul de securitate, se recomandă generarea unui nou bloc PS pentru fiecare criptare individuală. Lungimea sa, respectiv, este egală cu k-3-|D|, unde D este blocul de date, |D| este lungimea lui octet. Lungimea blocului PS trebuie să fie de cel puțin 8 octeți. Blocurile PS și D trebuie separate printr-un octet nul. Pentru comoditate, în viitor nu vom specifica standardul RSAES-PKCS1-v1_5, îl vom desemna ca PKCS#1. Fie n, e cheia publică și p, q, d cheia secretă. Potrivit R.S.A. Blocul EB este convertit într-un număr întreg x și criptat cu algoritmul RSA, . Receptorul verifică lungimea textului cifrat, îl decriptează , îl blochează și verifică primii doi octeți corecti care separă octetul nul și lungimea blocului PS. Dacă verificarea eșuează, se afișează o eroare. $n=pq,d=e^{-1}\operatorname {mod} (\phi (n))$ $c=x^{e}\operatorname {mod} (n)$ $c\leqslant n$ $m=c^{d}\operatorname {mod} (n)$

Descrierea atacului

Acest exemplu ilustrează posibilitatea unui atac de succes bazat pe un text cifrat ales adaptiv. Lăsați criptoanalistul să aibă acces la un dispozitiv care, pentru orice text cifrat ales, indică dacă textul simplu corespunzător este în formatul standard PKCS#1 și se confruntă cu sarcina de a decripta textul cifrat C. În acest fel, analistul poate selecta diverse texte cifrate și trimiteți-le la dispozitiv. După ce a primit răspunsul, compune următorul text cifrat, pe baza rezultatelor celor anterioare. Astfel, pe baza răspunsurilor primite de la dispozitiv și a cunoștințelor despre formatul de mesaj deschis conform standardului, criptoanalistul poate calcula . Factorul decisiv în atac sunt primii doi octeți ai mesajului deschis, care sunt constante. În acest exemplu, se consideră un algoritm care minimizează numărul de texte cifrate necesare pentru a primi un mesaj deschis. Atacul poate fi împărțit în 3 etape: $m=c^{d}\operatorname {mod} (n)$

Obținerea textului cifrat care se potrivește cu mesajul $c_{0}$ $m_{0}$
Găsirea numerelor mici pentru care textele cifrate de formă satisfac standardul PKCS. Pentru fiecare găsit cu succes , folosind cunoștințele anterioare , analistul calculează o serie de intervale care ar trebui să conțină . $si}$ $c_{0}\cdot (s_{i})^{e}\operatorname {mod} (n)$ $si}$ $m_{0}$ $m_{0}$
Găsirea unei serii formată dintr-un singur interval. În acest caz, analistul are suficiente informații despre , pentru a selecta doritul , pentru care îndeplinește standardul PKCS. Valoarea crește treptat până când intervalul este redus la un număr posibil. $m_{0}$ $si}$ $c_{0}\cdot (s_{i})^{e}\operatorname {mod} (n)$ $si}$

Descrierea matematică a atacului

Să presupunem că scopul criptoanalistului este să afle . Deoarece k este lungimea octetului lui n, atunci . Analistul alege numărul s, îl calculează și îl trimite la dispozitiv. Dacă dispozitivul primește un mesaj, atunci știm sigur că primii doi octeți sunt 00 și 02. Pentru comoditate, să notăm . Presupunem că s este potrivit, atunci estimarea este adevărată . Culegând acest tip de informații, putem găsi m. De regulă, textele cifrate vor fi suficiente, dar acest număr poate fluctua foarte mult. Să scriem atacul pas cu pas. $m=c^{d}\operatorname {mod} (n)$ $2^{8(k-1)}\leqslant n<2^{8k)$ $c'=c\cdot s^{e}\operatorname {mod} (n)$ $c'$ ${\displaystyle B=2^{8(k-2)))$ $2B\leqslant m\cdot s\operatorname {mod} (n)<3B$ $2^{20}$

Găsind $s_{0)$ . Având în vedere un întreg c, alegem diverse numere întregi aleatoare , apoi verificăm cu dispozitivul dacă expresia îndeplinește standardul PKCS. Pentru primul număr găsit cu succes în acest fel, găsim , , . $s_{0)$ $c\cdot s_{0}^{e}\operatorname {mod} (n)$ $s_{0)$ $c_{0}=c\cdot (s_{0})^{e}\operatorname {mod} (n)$ $M_{0}={[2B,3B-1]}$ $i=1$
Găsirea mesajelor potrivite
1. Începe căutarea. Dacă i=1, atunci căutăm cel mai mic număr pozitiv , pentru care textul cifrat satisface standardul PKCS. $s_{1}\geqslant {\frac {n}{3B)}$ $c_{0}\cdot (s_{1})^{e}\operatorname {mod} (n)$
2. În caz contrar, dacă și numărul de intervale este de cel puțin 2, atunci căutăm cel mai mic număr întreg pentru care textul cifrat satisface standardul PKCS. $i>1$ $M_{{i-1}}$ $s_{i}>s_{i-1}$ $c_{0}\cdot (s_{i})^{e}\operatorname {mod} (n)$
3. În caz contrar, dacă conține exact un interval (adică ), atunci alegeți numere întregi care satisfac expresiile și , până când textul cifrat satisface standardul PKCS. $M_{{i-1}}$ $M_{i-1}={[a,b]}$ $s_{i}r_{i)$ $r_{i}\geqslant 2{\frac {bs_{i-1}-2B}{n)}$ ${\frac {2B+r_{i}n}{b}}\leqslant s_{i}\leqslant {\frac {3B+r_{i}n}{a}}$ $c_{0}\cdot (s_{i})^{e}\operatorname {mod} (n)$
Restrângerea setului de soluții . Odată găsită, se calculează o serie de intervale atât pentru toate , cât și pentru . $si}$ $M_{i}$ $M_{i}=\bigcup _{(a,b,r)}[\operatorname {max} (a,[{\frac {2B+rn}{s_{i}}}]),\operatorname {min} (b,[{\frac {3B-1+rn}{s_{i))}])]$ $[a,b]\in M_{i-1}$ ${\frac {as_{i}-3B+1}{n}}\leqslant r\leqslant {\frac {bs_{i}-2B}{n}}$
Calcularea unei soluții . Dacă conține un singur interval de formă , atunci setați și returnați m ca soluție . În caz contrar , trecem la pasul 2. $M_{i}$ $M_{i}={[a,a]}$ $m=a(s_{0})^{-1}\operatorname {mod} (n)$ $m=c^{d}\operatorname {mod} (n)$ $i=i+1$

Primul pas poate fi omis dacă C este un mesaj criptat conform standardului PKCS. În al doilea pas, potrivirea începe cu , deoarece pentru valori mai mici mesajul nu va fi conform standardului PKCS. Numărul este folosit pentru a împărți intervalul la fiecare iterație la aproximativ jumătate. $s_{1}$ ${\frac {n}{3B)}$ $m_{0}s_{1)$ $r_{i}\geqslant 2{\frac {bs_{i-1}-2B}{n)}$

Analiza atacurilor

Estimarea probabilității ca un mesaj să fie conform standardului PKCS

Fie probabilitatea ca un text cifrat ales aleatoriu să aibă un format de text simplu adecvat și să fie probabilitatea ca pentru orice număr întreg ales aleatoriu primii 2 octeți să fie 00 și 02. Deoarece , rezultă că . Modulul RSA este de obicei ales ca multiplu de 8. Deci, de obicei aproape de . Probabilitatea ca un bloc PS să conțină cel puțin 8 octeți diferit de zero care se termină cu un octet nul este . Presupunând că n este de cel puțin 512 biți (k > 64), avem . Deci . $\Pr(P\cap A)$ $\Pr(A)={\frac {B}{n)}$ $2^{8}B<n<2^{16}B$ $2^{-16}<\Pr(A)<2^{-8}$ $\Pr(A)$ $2^{-16}$ $\Pr(P|A)=({\frac {255}{256)))^{8}\cdot (1-({\frac {255}{256)))^{k-10} )$ $0,18<\Pr(P|A)<0,97$ $0,18\cdot 2^{-16}<\Pr(P\cap A)<0,97\cdot 2^{-8}$

Estimarea intervalelor

M_{i}

Să demonstrăm că . Deoarece respectă standardul PKCS, rezultă că . Să presupunem că . Deci există un interval cu . Deoarece respectă standardul PKCS, există un astfel de r care , prin urmare, , , adică este conținut într-unul dintre intervale. $m_{0}\în M_{i)$ $m_{0}$ $2B\leqslant m_{0}\leqslant 3B-1$ $m_{0}\in M_{0}$ $m_{0}\in M_{i-1}$ $[a,b]\in M_{i-1}$ $a\leqslant m_{0}\leqslant b$ $m_{0}s_{i)$ $2B\leqslant m_{0}s_{i}-rn\leqslant 3B-1$ $as_{i}-(3B-1)\leqslant rn\leqslant bs_{i}-2B$ ${\frac {2B+rn}{s_{i}}}\leqslant m_{0}\leqslant {\frac {3B-1+rn}{s_{i}}}$ $m_{0}$

Estimarea complexității unui atac

Mesajul de la pasul 1 este ales aleatoriu, ceea ce înseamnă că trebuie să trimiteți către dispozitivul din apropierea mesajelor pentru a găsi . În mod similar pentru pașii 2.1 și 2.2 pentru . Fie numărul de intervale în . Apoi pentru . Lungimea intervalului este mărginită de sus de valoarea . Știind că formatul PKCS, obținem intervale de forma . va conține aproximativ intervale. Dacă , atunci fiecare dintre intervale, sau o parte din acesta, este inclus în dacă se suprapune cu unul dintre intervale . Niciunul dintre intervale nu se poate suprapune cu două intervale . Dacă intervalele sunt distribuite aleatoriu, atunci probabilitatea ca unul cu care se intersectează va fi mărginită mai sus de . Astfel, ecuația pentru este obținută în ipoteza că un interval trebuie să conțină valoarea . În cazul nostru, ne așteptăm să ajungem cu aproximativ și să avem . Prin urmare, va lua o singură valoare cu o probabilitate mare. Prin urmare, pasul 2.2 este de așteptat să apară o singură dată. Să analizăm pasul 2.3. Există , prin urmare , prin urmare . Lungimea intervalului . Prin urmare, este posibil să găsim o pereche care satisface inegalitățile din pasul 2.3 pentru fiecare a treia valoare a lui . Probabilitatea ca , este de aproximativ . Prin urmare, putem găsi , care satisface standardul aproximativ cu ajutorul textelor cifrate. Deoarece restul intervalului în este înjumătățit în fiecare pas 2.3, ne așteptăm să găsim folosind texte cifrate aproape. Pentru și va avea nevoie de texte cifrate pentru un atac de succes. Toate probabilitățile indicate mai sus au fost găsite sub ipoteza că toate sunt independente. Să fie și să satisfacă standardul PKCS și să aibă aceeași lungime a blocului PS. Apoi pentru un număr întreg obținem și . Apoi , este foarte probabil să îndeplinească standardul PKCS, deoarece, de asemenea, îndeplinesc adesea standardul. De obicei, n este ales ca multiplu de 8, deoarece probabilitatea este mică pentru acesta. Un modul cu o lungime de biți egală cu , este convenabil pentru analist, deoarece în acest caz sunt necesare texte cifrate pentru un atac de succes. ${\frac {1}{\Pr(P\cap A)))$ $s_{0)$ $i\geqslant 1$ $w_{i}$ $M_{i}$ $w_{i}\leqslant 1+2^{i-1}s_{i}({\frac {B}{n)})^{i)$ $i\geqslant 1$ $M_{i}$ ${\frac {B}{s_{i)}}$ $m_{0}s_{i)$ ${\frac {Bs_{i}}{n}}$ $I_{r}=[[{\frac {2B+rn}{s_{i}}}],[{\frac {3B-1+rn}{s_{i}}}]]$ $M_{1}$ ${\frac {Bs_{i}}{n}}$ $i>1$ $I_r$ $M_{i}$ $I_r$ $M_{{i-1}}$ $I_r$ $M_{{i-1}}$ $I_r$ $M_{{i-1}}$ $({\frac {1}{s_{i}}}+{\frac {1}{s_{i-1}}})w_{i-1}$ $w_{i}$ $m_{0}$ $s_{2}$ ${\frac {2}{\Pr(P\cap A)))$ $2{\frac {({\frac {B}{n)})^{2}}{\Pr(P\cap A)))={\frac {2B}{n\Pr(P| A)))<{\frac {2B}{0.18n}}<{\frac {1}{20}}$ $w_{2)$ $M_{i-1}={[a,b]}$ $a\leqslant m_{0}\leqslant b$ ${\frac {2B+r_{i}n}{b}}\leqslant {\frac {2B+r_{i}n}{m_{0)}}\leqslant s_{i}\leqslant {\ frac {3B-1+r_{i}n}{m_{0}}}\leqslant {\frac {3B-1+r_{i}n}{a}}$ ${\frac {3B-1+r_{i}n}{a}}-{\frac {2B+r_{i}n}{b}}\geqslant {\frac {3B-1+r_{ i}n}{m_{0))}-{\frac {2B+r_{i}n}{m_{0))}\geqslant {\frac {B-1}{m_{0))}\geqslant {\frac {B-1}{3B}}$ $r_{i}s_{i)$ $r_{i}$ $s_{i}\in [{\frac {2B+r_{i}n}{m_{0}}},{\frac {3B-1+r_{i}n}{m_{0}} }]$ ${\frac {1}{2))$ $si}$ ${\frac {2}{\Pr(P|A))}$ $M_{i}$ $m_{0}$ ${\frac {3}{\Pr(P\cap A)))+{\frac {16k}{\Pr(P|A))}$ $\Pr(P\cap A)=0,18\cdot 2^{-16}$ $k=128$ $2^{20}$ $si}$ $m_{0}$ $m_{0}s_{i)$ $j$ $m_{0}=2\cdot 2^{8(k-2)}+2^{8j}PS+D$ $s_{i}m_{0}=2\cdot 2^{8(k-2)}+2^{8j}PS'+D'$ $(2s_{i}-1)m_{0)$ $(2s_{i}-1)m_{0}=2\cdot 2^{8(k-2)}+2^{8j}(2PS'-PS)+2D'-D$ $\Pr(P\cap A)$ $8k-7$ $2^{13}$

Acces la decriptor

Luați în considerare 3 situații în care un analist poate obține acces la un dispozitiv.

Criptare regulată . Alice generează un mesaj, îl criptează folosind standardul PKCS#1 fără a aplica verificări de integritate și îl trimite lui Bob. Bob îl decriptează și dacă formatul mesajului decriptat nu corespunde standardului, atunci aruncă o eroare, altfel acționează conform protocolului. Astfel, analistul poate acționa ca Alice și poate verifica mesajele pentru conformitate cu standardul. Rețineți că atacul analistului funcționează chiar dacă autentificarea este utilizată în pasul următor, deoarece analistul va obține informațiile necesare înainte ca utilizatorul să fie nevoie să fie autentificat.
Mesaje de eroare detaliate . Verificarea integrității este o parte importantă a criptării RSA. O modalitate de a face acest lucru este să semnați mesajul cu cheia privată înainte ca expeditorul să-l cripteze cu cheia publică. Atunci atacatorul nu va putea crea mesajul corect accidental. Cu toate acestea, atacul poate avea succes. În cazul unei validări eșuate, destinatarul trimite un mesaj specificând unde validarea a eșuat. În special, compromite securitatea prin returnarea diferitelor mesaje de eroare pentru un mesaj care nu este conform standardului și pentru un mesaj care are o eroare de verificare a semnăturii.
Atacul în timp . Unele opțiuni de generare a mesajelor includ atât criptarea, cât și semnătura. Luați în considerare succesiunea acțiunilor.
1. Mesajul este decriptat.
2. Dacă nu respectă standardul, atunci este trimis un mesaj de eroare.
3. În caz contrar, semnătura este verificată.
4. Dacă semnătura este incorectă, atunci se aruncă o eroare, în caz contrar acces.

Astfel, prin măsurarea timpului de răspuns al receptorului, este posibil să se determine dacă o eroare de format este prezentă sau nu.

Literatură

Bleichenbacher D. Atacuri cu text cifrat ales împotriva protocoalelor bazate pe standardul de criptare RSA PKCS #1 // Advances in Cryptology — CRYPTO '98 :18- a Conferință Internațională de Criptologie Santa Barbara, California, SUA 23–27 august 1998 Proceedings / H. Krawczyk - Berlin , Heidelberg , New York, NY , Londra [etc.] : Springer Berlin Heidelberg , 1998. - P. 1-12. — 524 p. - ( Note de curs în Informatică ; Vol. 1462) - ISBN 978-3-540-64892-5 - ISSN 0302-9743 ; 1611-3349 - doi:10.1007/BFB0055716

Link -uri

RSA Data Security Inc. PKCS #1: Standard de criptare RSA. — Redwood City, CA, nov. 1993. Versiunea 1.5 - ftp://ftp.rsa.com/pub/pkcs/ascii/pkcs-1.asc
Atacul lui Bleichenbacher // Schimb de chei autentificate (în TLS), Kenny Paterson, 2015, pp. 32-41