Integrální kryptoanalýza

Aktuální verze stránky ještě nebyla zkontrolována zkušenými přispěvateli a může se výrazně lišit od verze recenzované 15. června 2014; kontroly vyžadují 14 úprav .

Integrální kryptoanalýza je metoda kryptoanalýzy , která kombinuje řadu útoků na symetrické blokové kryptografické algoritmy. Na rozdíl od diferenciální kryptoanalýzy , která zvažuje účinek algoritmu na pár holých textů, integrální dešifrování zahrnuje studium mapování souboru holých textů do ciphertextu . Poprvé ji použil v roce 1997 Lars Knudsen .

Historie

Ve vědeckých článcích byl termín „ integrální kryptoanalýza “ navržen v roce 1999 v publikaci Integral cryptanalysis of SAFER + (anglicky) . Samotný koncept poprvé vyslovil Lars Knudsen při analýze čtvercové šifry v roce 1997. Z tohoto důvodu se v literatuře často používá termín „útoky podobné čtverci“ nebo jednoduše „útok čtvercový“. Pro rok 2011 nedošlo k žádnému převratnému pokroku ohledně útoku Square na poli integrální kryptoanalýzy.

Teoretický základ metody

Nechť je konečná abelovská grupa . Poté, když vezmeme 1. blok jako množinu možných šifrových textů (obecně je určen zvolenou abecedou a velikostí bloku), můžeme uvažovat skupinu následujícího tvaru se stejnou skupinovou operací: . Takto vytvořená množina n-rozměrného prostoru je množinou všech možných šifrových textů. V souladu s tím je prostorovým prvkem určitý šifrový text, složky tohoto vektoru jsou hodnotou bloků šifrového textu. Předpokládáme, že součet vektorů je vektor, jehož složky se rovnají součtům odpovídajících složek členů. Množinový integrál je součtem všech vektorů obsažených v : . $(G,+)$ $G$ $G$ $G^{n}=G\times ...\times G$ $v=(v_{1},...,v_{n}),v\in G$ $S\subseteq G$ $S$ $\int S=\sum _{v\in S}v$

Úspěšná integrální kryptoanalýza by měla snížit počet iterací odhadu klíče . Abychom toho dosáhli, snažíme se seskupit vektory otevřeného textu tak, aby na základě seskupení bylo možné najít jakékoli vzory. Je vhodné studovat algoritmy založené na následujícím oddílu:

$v_{i}=c,\forall v\in S$
$\{v_{i}:v\in S\}=G$
$\sum _{v\in S}=c'$ ,

kde je pevné číslo, (vektor) $i$ $c,c'=const\in G$

Klíčovou roli hraje následující věta [1] :

Nechť je konečná abelovská grupa . Označte a řád g se rovná 1 nebo 2. Definujte . Pak . dále $(G,+)$ $H=\{g\in G:g+g=0\}$ $s(G)=\sum _{g\in G}g$ $s(G)=\součet _{h\in H}h$ $s(G)+s(G)=0$

Za zmínku stojí důležitý výsledek věty: if ), then , since ${\displaystyle G=GF(2^{s))$ $s(G)=0$ $H=\{0\}$

Všimli jsme si řady notací, které se často používají v publikacích o útocích založených na integrální kryptoanalýze:

Pokud je i -tá složka integrálu označena , znamená to, že ve všech termínech integrálního součtu je i -tá složka stejná ${\mathcal {C}}$
Podobně ukazuje, že odpovídající složka se liší ve všech termínech. $\mathcal{A}$
$\mathcal{S}$ ukazuje, že danou složku integrálu lze předpovědět.
? ukazuje, že je nemožné předpovědět složku integrálu.

Obecný princip hledání zranitelností na příkladu sítě Feistel

Zvažte, jak se změní integrály přes S , pokud jsou všechny prvky této množiny přivedeny na vstup Feistelovy sítě. Nechť S je množina šifrových textů, ve kterých jsou všechny odpovídající bloky kromě jednoho stejné (mohou se od sebe lišit). V příkladu je šifrový text 16 bloků uspořádaných do 2 řádků. U šifer, jako je AES , je také důležité vzít v úvahu, že šifrový text je dán maticí, protože používají různé operace pro řádky a sloupce. Zvažte účinek Feistelových buněk ve fázích:

Za předpokladu, že Feistelovy buňky produkují bijektivní mapování , je zřejmé, že stejné bloky mezi šifrovými texty přejdou do stejných bloků mezi převedenými šifrovými texty (je však téměř jisté, že staré a nové hodnoty se budou lišit). Můžeme tedy napsat, že 1. buňka mapovala množinu z třídy množin s komponentami shodnými v množině s množinou ze stejné třídy.
Protože hodnota všech bloků na výstupu Feistelovy buňky závisí na hodnotě každého bloku na vstupu, dopad jednoho bloku změní každý blok šifrovaného textu na výstupu. Hodnoty složek integrálu se tak stávají pouze předvídatelnými [2] . $\mathcal{A}$
Protože na vstupu pro každý blok patřící do vstupního šifrového textu se množina hodnot neshoduje s množinou možných hodnot bloku, jejich součet nemusí být při bijektivní transformaci zachován, takže na výstupu lze získat cokoliv z buňka.

I v případě popsaného příkladu je možné výrazně snížit počet iterací pro výběr nebo poskytnout další informace pro různé typy kryptoanalýz.

Srovnání s diferenciální kryptoanalýzou

Stejně jako u diferenciální kryptoanalýzy lze integrální útoky klasifikovat jako typ útoku založený na adaptivně zvoleném otevřeném textu .

Lars Knudsen si také všiml podobnosti s zkráceným diferenciálním útokem , který má myšlenku zvažovat chování ne celého rozdílu, jako v diferenciální kryptoanalýze, ale jeho částí. Integrální kryptoanalýza má navíc převahu ve své schopnosti zohlednit třetí stav výsledku - , zatímco útok zkrácených diferenciálů rozlišuje pouze dva. $\mathcal{S}$

Pro útok na diferenciály vyšších řádů můžete vidět, že v Galoisově poli je výraz pro diferenciál s -tého řádu podobný integrálu [3] . Lze se tedy pokusit zobecnit některé metody diferenciální kryptoanalýzy na integrální. $GF(2^{s})$

Je pozoruhodné, že útoky zkrácených diferenciálů a diferenciálů vyšších řádů také poprvé publikoval Lars Knudsen v roce 1994, rovněž na konferenci FSE [4].

Pozoruhodné útoky

Útoky na šifry podobné AES ( Rijndael , SQUARE , CRYPTON ) lze zobecnit prvním krokem - zvážením integrálů po 3. kole šifrování Dalšími kroky jsou pokusy o vylepšení útoku zvýšením počtu kol za použití různých předpokladů, které nevyhnutelně zvýšit počet iterací hledání, a tím i složitost prolomení .

AES

Útok na 4kolovou šifru

Klíčovými body šifrování bajtové matice jsou nelineární transformace, posun řádků, transformace sloupců, přidání textu (střední bajtová matice) s maticí kulatého klíče.

Zvažte šestnáctibajtový prostý text . Nechť má kryptoanalytik k dispozici 256 šifrových textů s následující vlastností: získávají se z bajtových matic, ve kterých jsou všechny bajty kromě jednoho stejné v množině těchto šifrových textů. Vzhledem k jejich počtu můžeme říci, že „nerovný“ bajt nabude všech možných hodnot na dané množině. Můžeme tedy přejít k výše uvedené notaci:

Počáteční stav:

$\mathcal{A}$	${\mathcal {C}}$	${\mathcal {C}}$	${\mathcal {C}}$
${\mathcal {C}}$	${\mathcal {C}}$	${\mathcal {C}}$	${\mathcal {C}}$
${\mathcal {C}}$	${\mathcal {C}}$	${\mathcal {C}}$	${\mathcal {C}}$
${\mathcal {C}}$	${\mathcal {C}}$	${\mathcal {C}}$	${\mathcal {C}}$

Zvažte stav textu po každém kole:

Nelineární převod díky bijektivitě nemění typ bajtu, pouze hodnoty pro jednotlivé texty.
Posun řádku nemá vliv na 1. řádek, zbytek se posune bez změny integrálu.
Při převodu sloupců je každý výsledný bajt závislý na všech 4 bytech původního sloupce, ale opět díky bijektivitě operace dostaneme, že každý bajt sloupce nabude každou ze svých hodnot pouze jednou.
Přidání klíče nezmění typy bajtů.

Takže po prvním kole:

Po 1. kole:

$\mathcal{A}$	${\mathcal {C}}$	${\mathcal {C}}$	${\mathcal {C}}$
$\mathcal{A}$	${\mathcal {C}}$	${\mathcal {C}}$	${\mathcal {C}}$
$\mathcal{A}$	${\mathcal {C}}$	${\mathcal {C}}$	${\mathcal {C}}$
$\mathcal{A}$	${\mathcal {C}}$	${\mathcal {C}}$	${\mathcal {C}}$

Posun řádků distribuuje 1 bajt v každém sloupci s typem . $\mathcal{A}$
Stejně jako v 1. kole, pokud je ve sloupci jeden bajt a zbytek je , pak se všechny bajty ve sloupci převedou na . Tímto způsobem jsou převedeny všechny 4 sloupce. $\mathcal{A}$ ${\mathcal {C}}$ $\mathcal{A}$

Po druhém kole:

Po 2. kole:

$\mathcal{A}$	$\mathcal{A}$	$\mathcal{A}$	$\mathcal{A}$
$\mathcal{A}$	$\mathcal{A}$	$\mathcal{A}$	$\mathcal{A}$
$\mathcal{A}$	$\mathcal{A}$	$\mathcal{A}$	$\mathcal{A}$
$\mathcal{A}$	$\mathcal{A}$	$\mathcal{A}$	$\mathcal{A}$

Pomocí výsledku věty popsané v části teorie získáme hodnoty integrálů v každém bajtu ${\mathcal {S}}=0$

Po třetím kole :

{\mathcal {S}}=0

$\mathcal{S}$	$\mathcal{S}$	$\mathcal{S}$	$\mathcal{S}$
$\mathcal{S}$	$\mathcal{S}$	$\mathcal{S}$	$\mathcal{S}$
$\mathcal{S}$	$\mathcal{S}$	$\mathcal{S}$	$\mathcal{S}$
$\mathcal{S}$	$\mathcal{S}$	$\mathcal{S}$	$\mathcal{S}$

Protože v posledním kole nedochází k transformaci sloupců (podle specifikace AES) a zbývající transformace jsou převedeny na , pak se pro čtyřkolové schéma v důsledku posledního kola hodnota integrálu nezmění až do fáze binárního sčítání kulatým klíčem. V tomto případě zbývá pouze, aby každý bajt převzal hodnotu odpovídajícího bajtu kruhového klíče, získal odhadovaný text 3. kola a zkontroloval, zda je integrál odpovídajícího bloku roven nule. Pokud je rovno, pak lze bajt kulatého klíče považovat za nalezený. $\mathcal{A}$ $\mathcal{A}$

Rozšíření podle počtu kol

Schéma lze rozšířit na sedmikolové schéma tím, že zvážíme, jaká transformace integrálu závisí na konkrétním bytu. Avšak i v případě 7 kol je počet požadovaných iterací vysoký, v tomto případě se vazby mezi okrouhlými klíči hledají analýzou schématu generování kódu. [5]

Vylepšení zdrojů kryptografů

Výrazně zkrátit dobu hledání klíčů, díky speciální organizaci vyhledávacích podmínek, pomocí tříbajtových vektorů, umožňuje zavedení tzv. částečného součtu. Taková úprava pro šestikolovou šifru snižuje výkon výčtu z na . Jiný přístup je využít toho, že integrál nad množinami s různými po kýženém třetím kole také zaniká. Tato metoda vyžaduje obrovské množství paměťových zdrojů a vlastnictví velmi rozsáhlé základny otevřeného textu – šifrovaného textu. [6] $2^{{72}}$ $2^{{44}}$ ${\mathcal {C}}$

Pomocí dílčích součtů je možné implementovat hack osmikolového systému, ale složitost tohoto hacku je ještě větší než u vyčerpávajícího výčtu .

Čtverec

Základní útok na čtvercovou šifru je prakticky stejný jako čtyřkolový útok na AES, navíc umožňuje rozšířit počet kol. Snad jediným podstatným rozdílem je přítomnost prvního kola šifrování a ve výsledku dva způsoby rozšíření (jeden směrem k poslednímu kolu, druhý směrem k prvnímu). Vývojáři šifry, když ji zkoumali, dokázali postavit útok na šestikolové šifrování .

Byly zveřejněny následující výsledky [7] :

Útoky na náměstí:

Záchvat	Počet otevřených textů	Čas	Náklady na paměť
Na 4 kola	$2^{{9}}$	$2^{{9}}$	Málo
Na 5 kol 1. způsobem	$2^{11}$	$2^{40}$	málo
Na 5 kol 2. způsobem	$2^{32}$	$2^{40}$	$2^{32}$
Na 6 kol	$2^{32}$	$2^{{72}}$	$2^{32}$

Poznámky

↑ Herstein, Témata algebry, 2. vyd., 1975, strana 116
↑ Dolgov, Golovashich, Ruzhentsev. „Analýza kryptografické síly šifry Tornado“ (2003), str. 7
↑ Lars Knudsen (2001). "Integrální kryptoanalýza (rozšířený abstrakt), str. 118"
↑ Lars Knudsen (1994). "Zkrácené diferenciály a diferenciály vyššího řádu"
↑ Niels Ferguson, John Kelsey, Stefan Lucks, Bruce Schneier, Mike Stay, David Wagner a Doug Whiting. "Vylepšená kryptoanalýza Rijndaela" (2001), s. 2-3
↑ Niels Ferguson, John Kelsey, Stefan Lucks, Bruce Schneier, Mike Stay, David Wagner a Doug Whiting. "Vylepšená kryptoanalýza Rijndaela" (2001), s. 4-7
↑ Joan Daemen, Lars Knudsen, Vincent Rijmen. "The Block Cipher Square" (1997), str. 15

Odkazy

Lars Knudsen a David Wagner. Integrální kryptoanalýza (rozšířený abstrakt) (neopr.) . — 2003.
Niels Ferguson, John Kelsey, Stefan Lucks, Bruce Schneier, Mike Stay, David Wagner a Doug Whiting. Vylepšená kryptoanalýza Rijndael (neopr.) . - 2001. Archivováno 8. ledna 2009. Archivováno 8. ledna 2009 na Wayback Machine
Joan Daemen, Lars Knudsen, Vincent Rijmen (leden 1997). Čtverec blokové šifry (PDF) . 4th International Workshop on Fast Software Encryption (FSE '97), Volume 1267 of Lecture Notes in Computer Science. Haifa: Springer-Verlag. str. 149-165.