Differenciális kriptoanalízis

Az oldal jelenlegi verzióját még nem ellenőrizték tapasztalt közreműködők, és jelentősen eltérhet a 2020. január 3-án felülvizsgált verziótól ; az ellenőrzések 5 szerkesztést igényelnek .

A differenciális kriptoanalízis a szimmetrikus blokkrejtjelek ( és más kriptográfiai primitívek , különösen a hash függvények és az adatfolyam-rejtjelek ) kriptográfiai elemzésének módszere.

A differenciális kriptoanalízis a titkosított értékek közötti különbségek transzformációjának tanulmányozásán alapul a különböző titkosítási körökben . Különbségként általában a bitenkénti összegzés modulo 2 műveletét használják , bár vannak támadások a modulo különbség kiszámításával . Ez egy statisztikai támadás. Alkalmazható a DES , FEAL és néhány más titkosítás feltörésére, amelyeket általában a 90-es évek eleje előtt fejlesztettek ki. A modern titkosítások ( AES , Camellia stb.) köreinek számát a biztonság figyelembevételével számították ki , beleértve a differenciális kriptoanalízist is. $2^{32}$

Történelem

A differenciális kriptoanalízist 1990 -ben Eli Biham és Adi Shamir izraeli szakértők javasolták az olyan kriptorendszerek feltörésére, mint a DES. Munkájuk során kimutatták, hogy a DES algoritmus meglehetősen ellenállónak bizonyult ezzel a kriptográfiai módszerrel szemben, és az algoritmus szerkezetének legkisebb változása sebezhetőbbé teszi.

1994-ben az IBM Don Coppersmith cikke [1] közölt arról, hogy a differenciális kriptoanalízis módszerét az IBM már 1974-ben ismerte, és a DES fejlesztésének egyik célja az volt, hogy védekezzenek ezzel a módszerrel szemben. Az IBM-nek megvoltak a titkai. Coppersmith elmagyarázta:

A tervezés során kihasználtak bizonyos kriptoanalitikai módszereket, különösen a "differenciális kriptoanalízis" módszert, amely a nyílt szakirodalomban nem jelent meg. Az NSA - val folytatott megbeszélések után úgy döntöttek, hogy a tervezési folyamat feltárása egy differenciális kriptoanalízis módszerét is feltárja, amelynek ereje számos rejtjel ellen használható. Ez viszont csökkentené az USA előnyét más országokkal szemben a kriptográfia területén.

A DES kriptográfiailag ellenállónak bizonyult a differenciális kriptoanalízissel szemben, ellentétben néhány más rejtjellel. Így például a FEAL titkosítás sebezhetőnek bizonyult . Egy 4 körös FEAL-4 akár 8 kiválasztott sima szöveggel is feltörhető , és még a 31 körös FEAL is sebezhető a támadásokkal szemben.

DES Hacking Scheme

1990-ben Eli Biham és Adi Shamir differenciális kriptoanalízis segítségével olyan módszert talált a DES megtörésére , amely hatékonyabb volt, mint a nyers erő. Olyan rejtjelezett szövegpárokkal dolgozva, amelyek nyílt szövegei bizonyos különbségeket mutatnak, a tudósok elemezték ezeknek a különbségeknek az alakulását, ahogy a nyílt szövegek áthaladnak a DES szakaszain .

Egykörös elemzés

A differenciális kriptográfiai elemzés alapvető módszere az adaptívan választott sima szöveges támadás , bár van egy kiterjesztése a nyílt szöveges támadásra is . A támadás végrehajtásához egyértelmű szövegpárokat használnak, amelyeket egy bizonyos különbség köt össze. A DES és a DES-szerű rendszerek esetében kizárólagos VAGY (XOR) ként van definiálva . A visszafejtéshez csak a megfelelő rejtjelezett szövegpárok értékére van szükség.

A diagram a Feistel függvényt mutatja . Legyen és egy olyan bemenetpár, amelyek különböznek egymástól . A hozzájuk tartozó kimenetek ismertek és egyenlők a és -vel , a különbség köztük . A kiterjesztéssel és -blokkkal való permutáció is ismert tehát, és szintén ismert . és ismeretlenek, de tudjuk, hogy különbségük , mert különbségek c és semlegesítik. Az áramkör egyetlen nemlineáris eleme a -blokkok. Minden -blokkhoz tárolhat egy táblázatot, melynek sorai a -blokk bemenetén lévő különbségek , az oszlopok a kimeneti különbségek, a metszéspontban pedig a bemeneti és kimeneti párok száma. különbségeket, és hol tárolják ezeket a párokat. $x$ $X'$ $\Delta X$ $Y$ $Y'$ $\Delta Y$ $P$ $\Delta A$ $\Delta C$ $B$ $B'$ $\Delta A$ $XOR\ K_{{i}}$ $A$ $A'$ $S$ $S$ $S$

A kerek kulcs megnyitása azon alapul, hogy egy adott értéknél nem minden érték egyformán valószínű, de a és kombinációja lehetővé teszi számunkra, hogy a és az értékeket feltételezzük . Az ismert és ez lehetővé teszi számunkra, hogy meghatározzuk . Az utolsó fordulóhoz szükséges összes információ kivételével az utolsó titkosított szövegpár tartalmazza. $\Delta A$ $\Delta C$ $\Delta A$ $\Delta C$ $A\ XOR\ K_{{i}}$ $A'\ XOR\ K_{{i}}$ $A$ $A'$ $K_{{i}}$ $\Delta C$

Az utolsó ciklus kerek kulcsának meghatározása után lehetővé válik a rejtjelezett szövegek részleges visszafejtése, majd a fenti módszerrel az összes kerek kulcs megtalálásához.

Jellemzők

Az i-edik körben kapott rejtjelezett szövegek lehetséges eltéréseinek meghatározásához körkarakterisztikákat használunk .

Az N-fordulós karakterisztika egy sor , amely egyszerű szöveges különbségekből, rejtjelezett szövegbeli különbségekből és az egyes elmúlt körök közbenső titkosítási eredményeiben mutatkozó különbségekből áll. $\Omega \ =\ (\Omega _{{P)),\Omega _({\Lambda )),\Omega _{{T)))$ $\Omega _{{P}}$ $\Omega _{{T}}$ $\Omega _{{\Lambda }}\ =\ (\Lambda _{{1}},\Lambda _{{2}},\ ...\ ,\Lambda _{{n}})$

A karakterisztikához egy olyan valószínűséget rendelünk, amely megegyezik annak valószínűségével, hogy egy véletlenszerű kulcsú titkosítás eredményeként eltérő nyílt szövegpárnak kerek különbségei és titkosított szövegbeli eltérései vannak, amelyek megegyeznek a jellemzőben megadottakkal. A jellemzőnek megfelelő nyitott szövegpárt "helyesnek" nevezzük . Azokat a nyitott szövegpárokat, amelyek nem felelnek meg a jellemzőnek, "helytelennek" nevezik . $\Omega _{{P}}$

Vegyük az utolsó előtti ciklus kimenetén lévő szövegek különbségének értékét, amelyet az utolsó kör lehetséges alkulcsának meghatározásához használunk . Ilyen esetben a "helyes" szövegpár határozza meg a helyes kulcsot, míg a "rossz" pár egy véletlenszerű kulcsot. $\Delta A=\Omega _{{T}}$

Egy támadás során általában több jellemzőt használnak egyszerre. A struktúrákat általában a memória megőrzésére használják.

A kvartett négy szövegből álló szerkezet, amely egyidejűleg két szövegpárt tartalmaz két különböző tulajdonságra. Lehetővé teszi a memória 1/2-ének megtakarítását egyszerű szövegek számára.
Oktett - 16 szövegből álló szerkezet, amely 8 párból áll, mindegyik jellemzőhöz 4-et. Lehetővé teszi a memória 2/3-ának megtakarítását egyszerű szövegek számára.

Jel-zaj arány

Minden kulcsopcióhoz létrehozhat számlálókat, és ha valamelyik pár ezt az opciót javasolja érvényes kulcsnak, akkor növeljük a megfelelő számlálót. A legnagyobb számlálónak megfelelő kulcs nagy valószínűséggel helyes.

Számítási sémánk szerint a helyes S párok számának az N számláló átlagos értékéhez viszonyított arányát jel-zaj viszonynak nevezzük , és jelöljük . $S/N$

A megfelelő kulcs megtalálásához és annak biztosításához, hogy a megfelelő párok jelen vannak, a következőket kell tennie:

jellemző kellő valószínűséggel;
elég pár.

A szükséges párok számát a következők határozzák meg:

a jellemző valószínűsége;
a kulcsbitek száma (a bitek, amelyeket definiálni akarunk);
a hibás párok azonosításának szintje (a párok nem járulnak hozzá a számlálókhoz, mivel korábban eldobják).

Legyen a kulcsméret k bit, akkor számlálók kellenek. Ha egy: $2^k$

m a használt párok száma;
$\alpha$ - a számlálók átlagos kiegészítése egy pár esetén;
$\beta$ a számlálókhoz hozzájáruló párok aránya az összes párhoz (beleértve az eldobottakat is),

akkor az N számláló átlagos értéke :

N={\frac {m\cdot \alpha \cdot \beta }{2^{{k))))

Ha a jellemző valószínűsége, akkor a helyes S párok száma egyenlő: $p$

S=m\cdot p.

Ekkor a jel/zaj arány :

S/N={\frac {m\cdot p}{m\cdot \alpha \cdot \beta /2^{{k))))={\frac {2^{{k))\cdot p}{ \alpha \cdot \beta }}.

Vegye figyelembe, hogy tervezési sémánk esetében a jel-zaj arány nem függ a párok teljes számától. A szükséges érvényes párok száma általában a jel-zaj arány függvénye . Kísérletileg megállapítottam, hogy ha S/N=1-2 , akkor 20-40 helyes pár előfordulása szükséges. Ha jóval nagyobb az arány, akkor akár 3-4 helyes pár is elég lehet. Végül, amikor ez sokkal alacsonyabb, a szükséges párok száma óriási.

S/N	Szükséges párok száma
kevesebb mint 1	Veliko
1-2	20-40
több mint 2	3-4

Hack hatékonyság

A körök számának növekedésével a kriptoanalízis bonyolultsága növekszik, de kisebb marad, mint a kimerítő keresés bonyolultsága, ha a ciklusok száma kevesebb, mint 16.

Függőség a körök számától
A körök száma	A támadás összetettsége
$négy$	$2^{{4}}$
$6$	$2^{{8}}$
$nyolc$	$2^{16}$
$9$	$2^{26}$
$tíz$	$2^{{35}}$
$tizenegy$	$2^{{36}}$
$12$	$2^{43}$
$13$	$2^{{44}}$
$tizennégy$	$2^{{51}}$
$tizenöt$	$2^{{52}}$
$16$	$2^{{58}}$

Az S-boxok kialakítása is jelentősen befolyásolja a differenciális kriptoanalízis hatékonyságát. A DES S-boxok különösen a támadásokkal szembeni ellenállásra vannak optimalizálva.

Összehasonlítás más módszerekkel

Lásd: Ismert támadások a DES ellen

Differenciális kriptoanalízis és DES-szerű rendszerek

Míg a teljes 16 körös DES-t eredetileg úgy tervezték, hogy ellenálljon a differenciális kriptoanalízisnek, a támadás sikeresnek bizonyult a DES-szerű rejtjelek széles csoportja ellen [2] .

A nyolc körre rövidített Lucifer kevesebb mint 60 titkosított szöveget használ.
A FEAL -8-at kevesebb mint 2000 titkosított szöveg használatával törik fel.
A FEAL-4 feltörése 8 titkosított szöveg és egy egyszerű szöveg felhasználásával történik .
A FEAL-N és a FEAL-NX feltörhető a -val . $N\leq 31$

A differenciális kriptoanalízis a hash függvények ellen is alkalmazható .

Miután az 1990-es évek elején megjelentek a differenciális kriptoanalízisről szóló munkák, a későbbi titkosításokat úgy tervezték, hogy ellenálljanak ennek a támadásnak.

A módszer hátrányai

A differenciális kriptoanalízis módszere nagyrészt elméleti vívmány. Gyakorlati alkalmazását a magas idő- és adatmennyiségigények korlátozzák.

Mivel a differenciális kriptográfiai elemzés elsősorban választott egyszerű szöveges támadási módszer, a gyakorlatban nehezen kivitelezhető. Használható ismert sima szöveggel történő támadásra, de egy teljes 16 körös DES esetén ez még kevésbé hatékony, mint egy brute-force támadás.

A módszer nagy mennyiségű memóriát igényel a jelölt kulcsok tárolásához. A módszer hatékonysága erősen függ a feltört algoritmus S-boxainak szerkezetétől is.

Lásd még

Jegyzetek

↑ Coppersmith, Don. Az adattitkosítási szabvány (DES) és erőssége a támadásokkal szemben // IBM Journal of Research and Development : folyóirat. - 1994. - május ( 38. köt. , 3. sz.). - 243. o . - doi : 10.1147/rd.383.0243 . (előfizetés szükséges)
↑ Biham E. , Shamir A. DES - szerű kriptorendszerek differenciális kriptoanalízise . - 1990. - 7. o .

Irodalom

Bruce Schneier. Alkalmazott kriptográfia. Protokollok, algoritmusok, forrásszövegek C nyelven.
Panasenko, S. „Modern módszerek a titkosítási algoritmusok feltörésére, 3. rész” . Információs igazgató - 2006 . Archiválva : 2010. január 15. a Wayback Machine -nél
Biham E. , Shamir A. Az adattitkosítási szabvány differenciális kriptoanalízise.
Biham E. , Shamir A. DES-szerű kriptorendszerek differenciális kriptoanalízise (angol) . – 1990.