Indistinguirea textului cifrat

Indistinguirea textului cifrat este o proprietate a multor sisteme de criptare . Intuitiv, dacă un sistem are proprietatea de indistingere, atunci un atacator nu va putea distinge perechile de texte cifrate pe baza textelor clare pe care le criptează. Proprietatea de indistinguire pentru atacurile bazate pe textul simplu ales este considerată o cerință de bază pentru cele mai sigure criptosisteme cu cheie publică , deși unele sisteme de criptare au, de asemenea, o proprietate de indistinguire pentru atacurile bazate pe textul simplu ales și pentru atacurile adaptive bazate pe textul cifru ales. Indistinguirea pentru atacurile cu text simplu este echivalentul pentru securitatea semantică a unui sistem, astfel încât aceste definiții sunt considerate interschimbabile în multe dovezi criptografice.

Un criptosistem este considerat sigur din punct de vedere al indistinguirii [1] dacă niciun atacator, după ce a primit un text cifrat selectat aleatoriu dintr-un spațiu de mesaj cu două elemente definit de adversar, nu poate identifica textul simplu corespunzător acestui text cifrat cu o probabilitate semnificativ mai bună . decât cu ghicirea aleatorie (1⁄2 ). Dacă orice atacator poate reuși să discerne textul cifrat ales cu o probabilitate semnificativ mai mare de 1⁄2, atunci se spune că acel atacator are un „avantaj” în discernerea textului cifrat, iar sistemul nu este considerat sigur din punct de vedere al indistinguirii. . Această definiție include ideea că, într-un sistem securizat, un atacator nu ar trebui să obțină nicio informație prin vizualizarea textului cifrat . Prin urmare, un atacator ar trebui să poată distinge textele cifrate nu mai bine decât dacă ar ghici aleatoriu.

Definiții formale

Securitatea în ceea ce privește indistingubilitatea are multe definiții, în funcție de ipotezele despre capacitățile atacatorului. Următoarea analogie este de obicei folosită. Un criptosistem este un fel de joc . Mai mult, un criptosistem este considerat sigur dacă niciun participant nu poate câștiga jocul cu o probabilitate semnificativ mai mare decât un participant care va acționa aleatoriu. Cele mai frecvente concepte utilizate în criptografie sunt indistingubilitatea pentru atacurile cu text simplu ales (abreviat ca IND-CPA), indistingubilitatea pentru atacurile cu text cifr ales (neadaptativ) (IND-CCA1) și indistingubilitatea pentru atacurile cu text cifrat ales adaptiv (IND-). CPA). CCA2). Securitatea în sensul fiecăreia dintre definițiile de mai sus implică securitate în sensul fiecărei definiții anterioare: un criptosistem care este securizat IND-CCA1 este, de asemenea, securizat IND-CPA și, în consecință, un sistem care este securizat IND-CCA2 este atât IND-CCA1. și IND-CPA securizat. Astfel, securitatea în sensul IND-CCA2 este cea mai puternică dintre cele trei definiții.

Indiscernibility for Chosen Plaintext Attacks (IND-CPA)

Pentru un algoritm probabilistic pentru criptarea cheii asimetrice, indistingubilitatea în sensul IND-CPA [2] este determinată de următorul joc între atacator și tester. Pentru sistemele bazate pe securitate computațională, atacatorul este modelat de o mașină Turing polinomială probabilistică , ceea ce înseamnă că trebuie să finalizeze jocul și să dea o ghicire într-un număr polinom de pași de timp. În această definiție, E(PK, M ) reprezintă textul cifrat al mesajului M , obținut folosind cheia PK :

Testerul generează o pereche de chei PK , SK pe baza unui parametru de securitate k (de exemplu dimensiunea cheii în biți) și publică PK atacatorului. Testerul salvează SK .
Un atacator poate efectua un număr limitat polinomial de criptări sau alte operațiuni.
În cele din urmă, atacatorul prezintă două texte clare separate testatorului. $\scriptstyle M_{0},M_{1)$
Testerul alege bitul b {0, 1} aleatoriu și trimite textul cifrat testat C = E(PK, ) înapoi atacatorului. $\scriptstyle \in$ $\scriptstyle M_{b)$
Un atacator poate efectua orice număr de calcule sau criptări suplimentare. În cele din urmă, imprimă doar valoarea lui b .

Un criptosistem este sigur în sensul IND-CPA dacă orice atacator credibil în timp polinomial are doar un mic „avantaj” în a distinge textele cifrate față de ghicitul aleatoriu. Atacatorul are un „avantaj” neglijabil dacă câștigă jocul de mai sus cu probabilitate , unde este o funcție neglijabilă pentru parametrul de securitate k , adică pentru orice funcție polinomială (diferită de zero) , care are , astfel încât pentru toate . $\scriptstyle \left({\frac {1}{2}}\right)\,+\,\epsilon (k)$ $\scriptstyle \epsilon (k)$ $\scriptstyle poly()$ $\scriptstyle k_{0)$ $\scriptstyle |\epsilon (k)|\;<\;\left|{\frac {1}{poly(k)))\right|$ $\scriptstyle k\;>\;k_{0)$

Chiar dacă atacatorul știe și PK , natura probabilistică a lui E înseamnă că textul cifrat va fi doar unul dintre multele texte cifrate valide și, prin urmare , criptarea și compararea textelor cifrate primite cu textul cifrat al testerului nu oferă atacatorului niciun avantaj semnificativ. $\scriptstyle M_{0)$ $\scriptstyle M_{1}$ $\scriptstyle M_{b)$ $\scriptstyle M_{0)$ $\scriptstyle M_{1}$

Deși definiția de mai sus este specifică criptosistemelor cu cheie asimetrică , ea poate fi adaptată la cazul simetric prin înlocuirea funcției de criptare a cheii publice cu criptare Oracle , care stochează cheia secretă de criptare și criptează textele arbitrare la cererea atacatorului.

Indistincte pentru atacurile de text cifrat alese/atacurile de text cifrat adaptiv (IND-CCA1, IND-CCA2)

Securitatea în sensul IND-CCA1 și IND-CCA2 [1] este definită similar fiabilității sistemului în sensul IND-CPA. Cu toate acestea, în plus față de cheia publică (sau criptarea oracle , în cazul simetric ), atacatorului i se oferă acces la decriptarea oracle , care decriptează texte cifrate arbitrare la cererea atacatorului, returnând textul simplu . În definiția IND-CCA1, unui atacator îi este permis să interogheze oracolul până când a primit textul cifrat testat. În definiția IND-CCA2, atacatorul poate continua să interogheze oracolul după ce primește textul cifrat testat, cu avertismentul că nu îl poate trimite pentru decriptare (altfel definiția ar fi banală).

Testerul generează o pereche de chei PK , SK pe baza unui parametru de securitate k (de exemplu dimensiunea cheii în biți) și publică PK atacatorului. Testerul salvează SK .
Un atacator poate efectua orice număr de criptări , apeluri de decriptare cu un oracol bazat pe texte cifrate arbitrare sau alte operațiuni.
În cele din urmă, atacatorul prezintă două texte clare separate testatorului. $\scriptstyle M_{0},\,M_{1}$
Testerul alege bitul b {0, 1} aleatoriu și trimite textul cifrat testat C = E(PK, ) înapoi atacatorului. $\scriptstyle \in$ $\scriptstyle M_{b)$
Un atacator poate efectua orice număr de calcule sau criptări suplimentare.
1. În definiția IND-CCA1, atacatorul nu poate efectua nicio decriptare suplimentară cu oracle .
2. În definiția IND-CCA2, atacatorul poate efectua apeluri oracol suplimentare , dar nu poate folosi textul cifrat C pentru a face acest lucru .
În cele din urmă, atacatorul face o ghicire despre valoarea lui b .

Un criptosistem este sigur în sensul IND-CCA1 sau IND-CCA2 dacă niciun adversar nu are un avantaj semnificativ în jocul dat.

Nu se distinge de zgomotul aleatoriu

Uneori sunt necesare sisteme de criptare în care un șir de text cifrat nu poate fi distins pentru un atacator de un șir aleatoriu. [3]

Dacă atacatorul nici măcar nu poate spune dacă mesajul există, acest lucru oferă persoanei care a scris mesajul o negație plauzibilă .

Unii oameni care creează canale de comunicare criptate preferă să facă conținutul fiecărui text cifrat să nu se distingă de datele aleatorii, pentru a face analiza traficului mai dificilă. [patru]

Unii oameni care construiesc sisteme pentru stocarea datelor criptate preferă ca datele să nu fie distinse de datele aleatorii pentru a le facilita ascunderea . De exemplu, unele tipuri de criptare de disc , cum ar fi TrueCrypt , încearcă să ascundă datele din datele aleatorii rămase de la anumite tipuri de distrugere a datelor . Ca un alt exemplu, unele tipuri de steganografie încearcă să ascundă datele făcându-le să se potrivească cu caracteristicile statistice ale zgomotului „aleatoriu” al imaginii din fotografiile digitale .

În prezent, există algoritmi criptografici special concepuți pentru sistemele de criptare refuzată , în care textele cifrate nu se pot distinge de șirurile de biți aleatorii. [5] [6] [7]

Dacă algoritmul de criptare E poate fi construit în așa fel încât un atacator (definit în general ca un observator în timp polinomial) care cunoaște textul simplu al mesajului m nu poate face distincția între E(m) și un șir de biți aleatoriu proaspăt generat de aceeași lungime, ca și E(m), atunci rezultă că, dacă E(m1) are aceeași lungime cu E(m2), aceste două texte cifrate nu vor fi distinse unul de celălalt pentru un atacator, chiar dacă el cunoaște textul simplu m1 și m2. (IND -CPA). [opt]

Majoritatea aplicațiilor nu necesită un algoritm de criptare pentru a crea texte cifrate care nu pot fi distinse de biții aleatori. Cu toate acestea, unii autori consideră că astfel de algoritmi de criptare sunt conceptual mai simpli și mai ușor de lucrat și mai versatili în practică - și majoritatea algoritmilor de criptare IND-CPA par să producă mesaje criptate care nu se pot distinge de biții aleatori. [9]

Echivalente și semnificația lor

Indiscernibilitatea este o proprietate importantă pentru menținerea confidențialității mesajelor criptate. Cu toate acestea, s-a constatat că, în unele cazuri, proprietatea de indistinguire implică alte proprietăți care nu au legătură în mod explicit cu securitatea. Uneori, astfel de definiții echivalente au semnificații complet diferite. De exemplu, proprietatea de indistinguire în sensul IND-CPA este cunoscută a fi echivalentă cu proprietatea de inflexibilitate pentru atacuri de scenarii similare (NM-CCA2). Această echivalență nu este imediat evidentă, deoarece inflexibilitatea este o proprietate legată de integritatea mesajului, nu de confidențialitate. De asemenea, s-a demonstrat că indistingebilitatea poate rezulta dintr-o altă definiție sau invers. Următoarea listă enumeră câteva consecințe cunoscute, deși sunt departe de a fi complete:

Securitate semantică IND-CPA pentru CPA. [zece] $\scriptstyle \Leftrightarrow$
NM-CPA (Inflexibilitatea pentru atacurile alese în text simplu ) IND-CPA. [unu] $\scriptstyle \Rightarrow$
NM-CPA (Inflexibilitatea pentru atacurile alese în text simplu ) IND-CCA2 . [unu] $\scriptstyle \nu \Rightarrow$
NM-CCA2 (Inflexibilitate pentru atacurile Adaptive Ciphertext-Based) IND-CCA2. [unu] $\scriptstyle \Leftrightarrow$

Note

↑ 1 2 3 4 5 Krohn, Maxwell. Despre definițiile securității criptografice : atacul cu text criptat ales revizuit . — 1999.
↑ Katz, Jonathan; Lindell, Yehuda. Introducere în criptografia modernă : principii și protocoale . — Chapman și Hall/CRC, 2007.
↑ Chakraborty, Debrup; Rodriguez-Henriquez., Francisco. Inginerie criptografică (neopr.) / Çetin Kaya Koç. - 2008. - S. 340. - ISBN 9780387718170 .
↑ iang. Nu se distinge de aleatoriu (20 mai 2006). Preluat la 6 august 2014. Arhivat din original la 15 august 2014. (nedefinit)
↑ Bernstein, Daniel J.; Hamburg, Mike; Krasnova, Anna; Lange, Tanja Elligator: puncte de curbă eliptică care nu se pot distinge de șirurile aleatoare uniforme (28 august 2013). Consultat la 23 ianuarie 2015. Arhivat din original la 5 noiembrie 2014. (nedefinit)
↑ Möller, Bodo. O schemă de criptare cu cheie publică cu texte cifrate pseudo-aleatorie // Computer Security - ESORICS 2004 (neopr.) . - 2004. - T. 3193. - S. 335-351. — (Note de curs în Informatică). — ISBN 978-3-540-22987-2 . - doi : 10.1007/978-3-540-30108-0_21 .
↑ Moore, Christopher; Mertens, Stephan. Natura calculului (neopr.) . - 2011. - ISBN 9780191620805 .
↑ Reingold, Omar Pseudo-Random Synthesizers, Functions and Permutations 4 (noiembrie 1998). Preluat la 7 august 2014. Arhivat din original pe 19 februarie 2014. (nedefinit)
↑ Rogaway, Phillip Nonce-Based Symmetric Encryption 5–6 (1 februarie 2004). Preluat la 7 august 2014. Arhivat din original la 10 mai 2013. (nedefinit)
↑ Silvio Micali, Shafi Goldwasser Probabilistic encryption (1984). (nedefinit)

Literatură

Katz, Jonathan; Lindell, Yehuda. Introducere în criptografia modernă : principii și protocoale . - Chapman & Hall / CRC Press , 2007. - ISBN 978-1584885511 .