Criptanaliza liniară

Criptanaliza liniară este o formă generală de criptanaliză bazată pe căutarea unor aproximări similare cu comportamentul unui cifru . Atacurile au fost dezvoltate pentru cifrele bloc și cifrele flux . Criptanaliza liniară este una dintre cele două tehnici de atac cele mai utilizate împotriva cifrelor bloc: cealaltă este criptanaliza diferențială .

Descoperirea criptanalizei liniare este atribuită lui Mitsuru Matsui , care a aplicat-o pentru prima dată la cifrul FEAL în 1992 . Matsui a publicat ulterior un atac asupra DES , probabil primul experiment de criptanaliză cifrat raportat de un academic. Cu toate acestea, atacul nu este în general practicabil, deoarece necesită 2 ⁴³ text clar cunoscut .

S-au sugerat o varietate de îmbunătățiri ale atacului, inclusiv utilizarea unor aproximări liniare multiple sau încorporarea expresiilor neliniare.

Noile cifre se așteaptă, în general, să își publice nivelul de securitate și împotriva criptanalizei liniare.

Analize

Există două părți distincte ale criptanalizei liniare. Prima este construirea de ecuații liniare care leagă textul clar, textul cifrat și biții cheie care au o valoare de distorsiune ridicată, adică cei a căror probabilitate de estimare (în spațiul tuturor valorilor posibile ale variabilelor lor) este la fel de apropiată de 0 sau 1 posibil. Al doilea este să utilizați aceste ecuații liniare împreună cu perechile cunoscute de text cifrat și text simplu pentru a obține biții cheie.

Construirea ecuațiilor liniare

O ecuație liniară, în scopul criptanalizei liniare, exprimă egalitatea a două expresii care constau în valori binare combinate cu o operație OR exclusivă (XOR). De exemplu, următoarea ecuație indică faptul că suma XOR a primului și celui de-al treilea biți ai textului simplu (conținută în blocul unui cifru bloc) și a primului bit al textului cifrat este egală cu al doilea bit al cheii:

$P_{1}\oplus P_{3}\oplus C_{1}=K_{2}.$ ${\ displaystyle P_ {1} \ oplus P_ {3} \ oplus C_ {1} = K_ {2}.}$ ${\ displaystyle P_ {1} \ oplus P_ {3} \ oplus C_ {1} = K_ {2}.}$

Într-un cifru real, nu ar trebui să fie posibil să se creeze astfel de ecuații care sunt valabile tot timpul. Într-un cifru ideal, orice ecuație liniară care leagă textul clar, textul cifrat și biții cheie ar trebui să fie valabilă cu o probabilitate de 1/2. Deoarece ecuațiile acoperite în criptanaliza liniară sunt de așteptat să nu fie valabile tot timpul, ele sunt adesea mai corect denumite aproximări liniare.

Procedura de construire a aproximărilor diferă de la cifru la cifru. În tipul mai clasic de cifrare bloc, o rețea de substituție și permutare , analiza se concentrează în principal pe casetele S , singura parte neliniară a cifrului (adică operația efectuată de o casetă S nu poate fi codificată cu o ecuație liniară). Pentru S-box-uri destul de mici, este posibil să se numere fiecare ecuație liniară posibilă care leagă intrarea S-box de biții de ieșire, să se calculeze distorsiunile lor și să se aleagă cele mai bune. Aproximările liniare ale casetelor S trebuie apoi combinate cu celelalte operații ale cifrului, cum ar fi permutarea și amestecarea cheilor, pentru a ajunge la aproximările liniare ale întregului cifru. Teorema stivuirii este un instrument util pentru acest proces de combinație. Există, de asemenea, alte tehnici de îmbunătățire iterativă a aproximărilor liniare (Matsui, 1994 ).

Derivarea biților cheie

Odată ce se obține o aproximare liniară în formă:

$P_{i_{1}}\oplus P_{i_{2}}\oplus \cdots \oplus C_{j_{1}}\oplus C_{j_{2}}\oplus \cdots =K_{k_{1}}\oplus K_{k_{2}}\oplus \cdots$ ${\ displaystyle P_ {i_ {1}} \ oplus P_ {i_ {2}} \ oplus \ cdots \ oplus C_ {j_ {1}} \ oplus C_ {j_ {2}} \ oplus \ cdots = K_ {k_ { 1}} \ oplus K_ {k_ {2}} \ oplus \ cdots}$ ${\ displaystyle P_ {i_ {1}} \ oplus P_ {i_ {2}} \ oplus \ cdots \ oplus C_ {j_ {1}} \ oplus C_ {j_ {2}} \ oplus \ cdots = K_ {k_ { 1}} \ oplus K_ {k_ {2}} \ oplus \ cdots}$

Este posibil să se aplice un algoritm simplu (Matsui's Algorithm 2) folosind perechi de note de text simplu și text cifrat pentru a prezice valorile biților cheie implicați în aproximare.

Pentru fiecare serie de valori ale biților cheii plasate pe partea dreaptă, indicate ca cheie parțială , este necesar să se numere de câte ori este adevărată aproximarea pentru toate perechile cunoscute de text clar și text cifrat: acest număr este numit T. Cheia parțială a cărei T are diferența absolută față de jumătate din numărul celor mai mari perechi de text simplu și text cifrat este denumită cel mai probabil set de valori pentru acei biți ai cheii. Acest lucru se realizează deoarece se presupune că cheia parțială corectă va face aproximația adevărată cu părtinire mare. Este important de reținut că valoarea prejudecății este aici, spre deosebire de valoarea probabilității în sine, semnificativă.

Această procedură poate fi repetată cu alte aproximări liniare, obținându-se valori finale pentru biții cheie, până când numărul de biți cheie necunoscuți este suficient de redus pentru a fi recuperat cu un atac cu forță brută .

Elemente conexe

Referințe

Mitsuru Matsui, A. Yamagishi: O nouă metodă pentru atacul cunoscut în text clar al cifrului FEAL - EUROCRYPT 1992
M. Matsui: Metoda de criptanaliză liniară pentru cifrul DES - EUROCRYPT 1993
M. Matsui: Prima criptanaliză experimentală a standardului de criptare a datelor - CRYPTO 1994

linkuri externe

Un ghid pentru criptanaliza liniară (și diferențială) a cifrelor bloc , la engr.mun.ca.

Portal de criptografie

Portal de securitate IT