Adaptív egyszerű szöveges támadás

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

Az adaptív módon megválasztott egyszerű szöveges támadás a támadások olyan típusa a kriptográfiai elemzésben , amely azt feltételezi, hogy a kriptoanalizátor többször is kiválaszthatja a nyílt szöveget , és közvetlenül a támadás során megszerezheti a megfelelő titkosított szöveget . A kriptoanalizátor célja, hogy a rendszer elfogott rejtjelezett szövegeiből információt tudjon kinyerni, és ideális esetben a kulcsot a nyílt szöveg és a fogadott rejtjelezett szöveg összehasonlításával tudja kivenni . Ez egy speciális esete a megfelelő szöveges támadásnak [1] .

Alkalmazás

Egy adaptívan megválasztott egyszerű szöveges támadás alkalmazható olyan esetekben, amikor a kriptoanalizátor hozzáfér egy titkosító eszközhöz , például egy intelligens kártyához , amely valamilyen titkosítási algoritmuson fut, olyan kulccsal , amelyet a felhasználó nem olvashat [2] .

Ezenkívül ezt a támadást széles körben használják nyilvános kulcsú kriptográfiai rendszerek feltörésére . Mivel a titkosítási szolgáltatások egy ilyen titkosítási rendszerben mindenki számára elérhetőek, minden olyan támadást, amely nem használ visszafejtési blokkot, adaptívan választott nyílt szövegen alapuló támadásnak nevezhetjük. Ezért a nyilvános kulcsú kriptorendszer megfelelő működéséhez meg kell követelni a rendszer stabilitását az ilyen támadásokkal szemben [3] .

Történelem

A második világháború alatt a kriptaelemzők széles körben alkalmazták az (adaptív) választott sima szövegen, nyílt szövegeken és ezek kombinációján alapuló támadásokat [4] .

Így a Bletchley Park kriptaelemzői meg tudták határozni az üzenetek egyszerű szövegét attól függően, hogy mikor küldték el az üzeneteket. Például a napi időjárás-jelentést a német jeladók egy időben küldték el. Tekintettel arra, hogy a katonai jelentéseknek van egy bizonyos szerkezete, a kriptaelemzők képesek voltak megfejteni a többi információt az adott területen lévő időjárási adatok segítségével. [5]

Szintén a Bletchley Parkban találták ki a következő módszert, hogy bizonyos üzenetek küldésére kényszerítsék a németeket. A kriptoanalitikusok kérésére a Nagy-Britannia Királyi Légiereje az Északi-tenger bizonyos szakaszait bányászta , ezt a folyamatot "Gardening"-nak (angolul "kertészet" ) nevezték el. Majdnem azonnal ezután a németek titkosított üzeneteket küldtek az aknák ledobásának helyeinek nevével. [5]

Egy másik példa a Midway-i csatából származik. Az amerikai haditengerészet szakemberei elfogtak egy japán titkosított üzenetet, amelyet sikerült részben visszafejteni. Kiderült, hogy a japánok támadást terveztek az AF ellen, ahol az AF része volt annak a rejtjelezett szövegnek, amelyet az amerikai szakértők nem tudtak megfejteni. Aztán a kriptoanalitikusok megparancsolták a szigeten tartózkodó amerikai hadseregnek, hogy küldjenek hamis üzenetet a friss víz hiányáról. A japánok elfogták ezt az üzenetet, és továbbították feletteseiknek. Így a haditengerészet kriptaelemzői tudomást szereztek a tervezett támadásról [4]

Összehasonlítás más típusú támadásokkal

Bruce Schneier szerint , feltételezve , hogy a kriptoanalitikus ismeri a titkosítási algoritmust , a kriptoanalízisnek 4 fő típusa van [1] :

Rejtjeles támadás
Támadás nyílt szövegek és a megfelelő titkosított szövegek alapján
Választott egyszerű szöveges támadás (lehetőség a titkosítandó szövegek kiválasztására, de csak egyszer, a támadás előtt)
Adaptív egyszerű szöveges támadás

Egyértelmű szövegeken és a megfelelő rejtjelezett szövegeken alapuló támadás esetén a kriptoanalizátor hozzáfér néhány szöveg-titkosszöveg párhoz [1] .

Kényelmesebb lehetőség a választott egyszerű szöveges támadás , amelyben a kriptoanalizátor először kiválaszthat bizonyos számú nyílt szöveget, majd beszerezheti a megfelelő titkosított szövegeket [1] .

Az adaptív-választott-plaintext támadás a választott egyszerű szöveges támadás módosított változata. Ennek a támadástípusnak az az előnye, hogy a kriptoanalizátor a kapott eredmények alapján új nyílt szöveget tud kiválasztani, míg egy illesztett egyszerű szöveges támadás esetén az összes szöveget a támadás megkezdése előtt kiválasztja [1] .

Támadási algoritmus

Az adaptív egyszerű szöveges támadások gyakran alkalmaznak differenciális kriptográfiai módszereket, amelyeket Adi Shamir munkái ír le , és lineáris kriptoanalízist . Az ilyen támadások általános módszerei a következők:

Differenciális kriptoanalízis

Először is kiválasztunk egy pár egyszerű szöveget illesztett különbséggel. A rendszer elküldi őket a titkosító eszközre. Rejtjelezett szövegeknek felelnek meg , amelyekben szintén van némi különbség. Így a statisztikákat a plaintext - titkosított szöveg alakpárokból gyűjtik össze . Ezt követően a nyílt szövegek közötti különbséget összehasonlítjuk a rejtjelezett szövegek közötti különbséggel , és az összegyűjtött adatok alapján feltételezzük a rendszer kulcsát [6]

Lineáris kriptoanalízis

Ebben az esetben valószínűségi lineáris kapcsolatot keresünk a nyílt szöveg, a rejtjelezett szöveg és a kulcs között. Először olyan arányszámokat állítunk össze, amelyek nagy valószínűséggel érvényesek, majd ezeket az arányokat a kiválasztott nyílt szövegek párjaival és a hozzájuk tartozó rejtjelezett szövegekkel használjuk [7] .

Példák támadásokra

Támadás az RSA algoritmus ellen

Tekintsük az RSA [8] titkosítási algoritmust .

Hagyja, hogy a kriptoanalitikus elkapjon valamilyen üzenetet , amelyet vissza akar fejteni, és ismeri a nyilvános kulcsot . $C=M^{e}\operátornév {mod} N$ $e$

Ezután kiválaszt egy véletlen számot , kiszámítja az üzenetet , és elküldi a felhasználónak. $r\in \mathbb {Z} ^{*}$ $C_{2}=C\cdot r^{e}\operátornév {mod} N$

A visszafejtés után a felhasználó a következőket kapja:

$M_{2}=C_{2}^{d}\operátornév {mod} N=((M\cdot r)^{e})^{d}\operátornév {mod} N=M\cdot r$

A kapott szám teljesen véletlenszerűnek tűnhet a felhasználó számára, mivel a számmal való szorzás egy csoport permutációja . Ha az üzenetet véletlenszerű számkészletként ismeri fel, akkor ez a készlet visszakerül a feladóhoz, vagyis a felhasználó egy számot küld a támadónak . Egy ilyen munkaalgoritmust abból a feltevésből adódóan használnak, hogy a dekódolt szöveg, amelynek szerkezete véletlenszerű számhalmaz, nem használható hasznos információk megszerzésére [8] . $M_{{2}}$ $r$ $Z^{{*}}$ $M_{{2}}$

Így a kriptoanalitikus rendelkezésére állnak a számok, majd ezeket modulo elosztva a támadó megtudhatja az értéket [8] . $r$ $M\cdot r$ $N$ $M$

Támadás differenciális kriptográfiai módszerekkel

Vegyük például a titkosítást a DES algoritmussal [6] .

Tegyük fel, hogy hozzáférünk valamilyen programhoz, amely ezen algoritmus szerint működik, és minden paramétere ismert, kivéve a kulcsot .

Legyen és legyen párosított egyszerű szövegek különbséggel . $x$ $X'$ $\Delta X$

Ezek a titkosított szövegeknek felelnek meg, és eltéréssel - . $Y$ $Y'$ $\Delta Y$

Mivel a -blokk kiterjesztésű permutációk ismertek, így ismertek . $P$ $\Delta A$ $\Delta C$

A és értékei ismeretlenek, de megtaláljuk a különbséget. $B$ $B'$

Szóval . $\Delta B=BB'=A\operátornév {xor} KA'\operátornév {xor} K=\Delta A$

Az utolsó kifejezés helyes, mivel a és az egyező bitek érvénytelenítik, míg a különböző bitek különbséget adnak annak ellenére, hogy . $A$ $A'$ $\operátornév {xor}$

A kulcs kiválasztásának folyamata azon alapul, hogy egy adott kulcsnál különböző valószínűséggel különbözőek fognak előfordulni. $\Delta A$ $\Delta C$

Így a és kombinációi lehetővé teszik a és értékeinek bizonyos valószínűséggel való kitalálását . Ami ismert és , lehetővé teszi számunkra, hogy megtaláljuk a kulcsot . $\Delta A$ $\Delta C$ $A\operatorname {xor} K$ $A'\operátornév {xor} K$ $A$ $A'$ $K$

Így a nyílt szövegek közötti eltérések kellően nagy valószínűséggel bizonyos eltéréseket okoznak a fogadott rejtjelezett szövegekben. Ezeket a különbségeket jellemzőknek nevezzük. A karakterisztikákat a következőképpen felépített táblázatok segítségével találjuk meg: lehetséges sorok , oszlopok - . Adott sor és oszlop metszéspontjában rögzítésre kerül, hogy a bemeneten, a kimeneten hányszor érkezett adat . Mivel az iterációk mindegyike független, a különböző jellemzők a valószínűségek szorzásával kombinálhatók. A valószínűségi eloszlás ismeretében nagy pontossággal lehet kulcsot választani [6] . $\Delta X$ $\Delta Y$ $\Delta X$ $\Delta Y$

Támadás lineáris kriptográfiai módszerekkel

Vegyünk például egy titkosítást a DES algoritmussal [7] .

Legyen P a nyílt szöveg, C a titkosított szöveg, K a kulcs, F a titkosítási függvény, A, B, D a maszkok, amelyek maximalizálják a lineáris relációk követésének valószínűségét:

$F(X_{1})\cdot A=X_{1}\cdot D$

$F(X_{3})\cdot B=X_{3}\cdot D$

$F(X_{1})\cdot D=X_{2}\cdot (A\bigoplus B)$ , ahol , a függvény bemenete az i-edik körben. $F(X_{i})=F(X_{i},K_{i})$ $X_{i}$

Ekkor a 16 körös DES egyenlete a következő [7] :

$(P^{L}\cdot A)\bigoplus (F(P^{R},K_{1}^{*})\cdot A)\bigoplus (C^{L}\cdot D)\ bigoplus (F(C^{R},K_{16}^{*})\cdot D)\bigoplus (C^{R}\cdot B)=0$ $(egy)$

Ennek az egyenletnek a valószínűsége:

$P_{L}^{15}={\frac {1}{2}}+2^{14-1}\prod _{i=2}^{15}(p_{i}-{\ frac {1}{2}})$ helyes feltevésekkel , hol $K_{1}^{*},K_{16}^{*}$

$p_{i}=1,i\in$ {2, 6, 10, 14}

$p_{i}=42/64,i\in$ {3, 9, 11}

$p_{i}=30/64,i\in$ {4, 8, 12}

$p_{i}=12/64,i\in$ {5, 7, 13, 15}

Más kulcsok esetében ez az egyenlet véletlenszerű lesz.

Az aktív S-boxban első körben hat bemeneti bitet rögzítünk. Ekkor ennek a függvénynek bármely kimeneti maszkja konstans 0 vagy 1 eltolással . Ezután tekintsük a következő [7] egyenletet : ${\frac {1}{2))$

$(P^{L}\cdot A)\bigoplus (C^{L}\cdot D)\bigoplus (F(C^{R},K_{n}^{*})\cdot D)\ bigoplus (C^{R}\cdot B)=0$

A támadás során a titkos kulcs minden értékéhez egy számlálót vezetnek, amely nyomon követi, hogy az egyenlet bal oldala hányszor 0. N -pár esetén a T számlálóérték legtávolabbi kulcsot veszik a kulcsnak . helyes kulcsérték [7] . ${\megjelenítési stílus (P,C)}$ ${\frac {N}{2))$

Lásd még

Jegyzetek

↑ 1 2 3 4 5 Schneier B. Kriptanalízis // Alkalmazott kriptográfia. Protokollok, algoritmusok, forráskód C nyelven = Applied Cryptography. Protokollok, algoritmusok és forráskód in C. - M. : Triumf, 2002. - S. 20. - 816 p. - 3000 példányban. - ISBN 5-89392-055-4 .
↑ Skalyarov D.V. Az információk védelmének és feltörésének művészete . - Szentpétervár. : BHV-Petersburg, 2004. - S. 56 . — 288 p. — ISBN 5-94157-331-6 .
↑ Mao Wenbo. Modern kriptográfia: elmélet és gyakorlat / ford. angolról. D. A. Klyushina. - M . : "Williams" kiadó, 2005. - S. 307. - 768 p. — ISBN 5-8459-0847-7 .
↑ 1 2 Jonathan Katz. Bevezetés a modern kriptográfiába . - Boca Raton: CRC, 2016. - 85 p. - ISBN 978-1-4822-5414-3 .
↑ 1 2 Tony Sale "A Bletchley Park rejtélye" . Letöltve: 2011. november 30. Az eredetiből archiválva : 2011. augusztus 5.. (határozatlan)
↑ 1 2 3 Heys HM Oktatóanyag a lineáris és differenciális kriptoanalízisről (19-27) // Taylor és Francis. - 2002. - ISSN 0161-1194 .
↑ 1 2 3 4 5 Knudsen LR, Mathiassen JE Választott egyszerű szövegű lineáris támadás a DES ellen // Nemzetközi műhely a gyors szoftvertitkosításról. - 2000. - április 10. ( 7. köt. ). — P. 262-272 . — ISSN 978-3-540-41728-6 .
↑ 1 2 3 Y. Desmedt, A. M. Odlyzko. Egy kiválasztott szöveges támadás az RSA titkosítási rendszer ellen és néhány diszkrét logaritmusséma // Előadásjegyzetek a számítástechnikából. - 2000. - január 1. — ISSN 1611-3349 .

Irodalom

Mao V. Modern kriptográfia : Elmélet és gyakorlat / ford. D. A. Klyushina - M .: Williams , 2005. - 768 p. — ISBN 978-5-8459-0847-6
Sklyarov D. V. Az információvédelem és a hackelés művészete.
Bruce Schneier. Alkalmazott kriptográfia. Protokollok, algoritmusok, forrásszövegek C nyelven.
Panasenko Szergej. „Modern technikák 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
Panasenko Szergej. „Modern módszerek a titkosítási algoritmusok feltörésére, 4. rész” . Információs igazgató - 2006 . Archiválva : 2009. május 21. a Wayback Machine -nél