Útok v otevřeném textu

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é 3. ledna 2020; ověření vyžaduje 1 úpravu .

Útok na známý holý text je typ kryptoanalýzy , ve které jsou v šifrovém textu přítomny standardní pasáže , jejichž význam je analytikovi předem znám. Během druhé světové války angličtí kryptoanalytici nazývali takové pasáže "tipy" ( anglicky crib - hint, cheat sheet) [pozn. 1] .

Šifry z různých zemí často obsahovaly konkrétní výrazy: Heil Hitler! , Banzai! , Proletáři všech zemí, spojte se! atd.

Dalším příkladem použití metody je kryptografický útok na jednoduchý gama algoritmus . Pokud je znám alespoň jeden otevřený text a délka šifrového textu, který mu odpovídá, je větší nebo rovna délce gama (klíče), pak je gama jednoznačně nalezen.

Popis

Podle Kerckhoffsova principu má kryptoanalytik všechny informace o kryptosystému kromě určité sady parametrů nazývaných klíč . Úkolem kryptoanalytika je najít společný šifrovací klíč nebo dešifrovací algoritmus, aby bylo možné dešifrovat další šifrované texty stejným klíčem.

Vzhledem k tomu:

P 1 , P 2 , …, P i — prosté texty
C 1 =E k (P 1 ), C 2 =E k (P 2 ), …, C i =E k (P i ) — jejich odpovídající šifrové texty

Potřebujete najít:

k je šifrovací klíč, popř
D(C) - funkce dešifrování (ne jako funkce klíče, ale pouze šifrovaného textu)

Rozdíly od jiných metod kryptoanalýzy

Útok pouze pomocí šifrovaného textu

Útok pouze na šifrovaný text je primární kryptoanalytická technika, při které kryptoanalytik zná pouze šifrované texty. Útok v otevřeném textu je jeho vylepšením, protože známe i zdrojové texty. Například metoda frekvenční kryptoanalýzy často používaná pro kryptoanalýzu založenou na šifrovaném textu v případě kryptoanalýzy založené na prostém textu otevírá více možností, protože frekvenční odezva šifrované zprávy musí být srovnávána nikoli s frekvenční odezvou jazyka, ale s frekvenční odezva původní zprávy (ve zvláštních případech frekvenční odezva otevřeného textu).text a frekvenční odezva jazyka se mohou značně lišit).

Zvolený útok v otevřeném textu

Zvolený útok v otevřeném textu – Tento typ útoku je vylepšením metody založené na otevřeném textu. Zde má kryptoanalytik také řadu předem známých párů holého textu/šifrovaného textu. Může ale také přijímat šifrové texty odpovídající textům, které si předem vybral. Způsob, jak takové šifrové texty získat, je například napsat dopis s prostým textem a přitom se vydávat za osobu, od které se očekává zašifrovaná zpráva, a za určitých podmínek můžete dostat odpověď s citací z tohoto textu, ale již v zašifrované podobě. Rozdíl mezi touto metodou a útokem na prostý text je v tom, že u této metody si kryptoanalytik může vybrat, který text chce zašifrovat. A v metodě pouze prostý text jsou všechny dvojice prostého textu/šifrovaného textu předem známy.

Adaptivní útok na prostý text

Adaptivně zvolený útok s otevřeným textem je rozšířením zvoleného útoku s otevřeným textem. Rozdíl spočívá v tom, že po obdržení šifrovaného textu odpovídajícímu danému otevřenému textu se kryptoanalytik sám rozhodne, který text chce dále šifrovat, což jakoby přidává zpětnou vazbu k metodě hackování. Tato metoda vyžaduje přímý přístup k šifrovacímu zařízení.

Příklad aplikace v historii

V případě Enigmy bylo německé vrchní velení při zabezpečení systému velmi pečlivé, protože si bylo vědomo možného problému prolomení na základě otevřených textů. Tým, který na hacku pracoval, mohl uhodnout obsah textů podle toho, kdy byly zprávy odeslány. Předpověď počasí byla například přenášena každý den ve stejnou dobu. Podle předpisů vojenských zpráv obsahovala každá zpráva na stejném místě slovo „Weather“ (Wetter) a znalost počasí v dané oblasti byla velmi nápomocná při tipování obsahu zbytku zprávy. Velmi užitečné byly také zprávy od důstojníka, který pokaždé posílal „Nic k hlášení“ a poskytoval materiál pro kryptoanalýzu. Ostatní velitelé také zasílali standardní odpovědi nebo jejich odpovědi obsahovaly standardní části.

Poté, co se zajatý Němec při výslechu přiznal, že operátoři dostali příkaz šifrovat čísla psaním každé číslice písmeny, Alan Turing zprávy zkontroloval a zjistil, že slovo „eins“ se vyskytuje v 90 % zpráv. Na základě toho vznikl katalog Eins, který obsahoval všechny možné polohy rotorů, výchozí polohy a sady klíčů Enigma.

Nyní

Moderní šifry jsou špatně přístupné této metodě kryptoanalýzy. Například prolomení DES vyžaduje přibližně páry prostého textu/šifrovaného textu. $2^{{47}}$

Zároveň jsou vůči této formě útoku zranitelné různé šifrované archivy, jako je ZIP . V tomto případě útočník, který chce otevřít skupinu zašifrovaných souborů ZIP, potřebuje znát pouze jeden nezašifrovaný soubor z archivu nebo jeho části, který bude v tomto případě fungovat jako čistý text. Dále pomocí programů, které jsou volně dostupné, je klíč potřebný k dešifrování celého archivu rychle nalezen. Cracker se může pokusit najít nezašifrovaný soubor na internetu nebo v jiných archivech, nebo se může pokusit obnovit prostý text tím, že zná název ze zašifrovaného archivu.

Základní metody

Lineární metoda kryptoanalýzy

V otevřeném tisku byla lineární metoda kryptoanalýzy poprvé navržena japonským matematikem Matsui. Metoda předpokládá, že kryptoanalytik zná otevřený text a odpovídající šifrové texty. Nejčastěji se při šifrování používá modulo 2 přidávání textu pomocí klíče, operace míchání a rozptylu. Úkolem kryptoanalytika je takovou lineární aproximaci najít

$x_{i_{1}}+\ldots +x_{i_{r}}+y_{j_{1}}+y_{j_{s}}=z_{k_{1}}+\ldots +z_ {k_{t}}$ , (jeden)

která bude nejlepší. Nechť je pravděpodobnost, že (1) je splněna. Je jasné, že potřebujeme , a také že hodnota je maximální. Pokud je tato hodnota dostatečně velká a kryptoanalytik zná dostatek párů otevřeného textu a odpovídajícího šifrovaného textu, pak modulo 2 součet bitů klíče na odpovídající pozici na pravé straně rovnosti (1) je roven nejpravděpodobnějšímu hodnota součtu modulo 2 odpovídajících bitů v otevřeném a šifrovém textu na levé straně. V případě kde je součet na pravé straně (1) nula, když součet bitů na levé straně je nula ve více než polovině párů šifrových textů. Součet bitů na pravé straně je roven jedné, pokud je součet bitů na levé straně roven jedné ve více než polovině případů textů. Jestliže , pak naopak: součet bitů na pravé straně je roven jedné, je-li součet bitů na levé straně roven nule pro více než polovinu textů. A součet bitů na pravé straně je nula, pokud je součet bitů na levé straně o jedničku více než poloviční. Pro nalezení každého bitu klíče je nyní nutné vyřešit systém lineárních rovnic pro odpovídající známé kombinace těchto bitů. To není obtížné, protože složitost tohoto systému je vyjádřena polynomem, který nepřesahuje třetí stupeň délky klíče. Počet požadovaných dvojic holého textu/šifrovaného textu k prolomení šifry se odhaduje podle vzorce . K prolomení šifry DES tímto způsobem se ukázalo, že je potřeba přibližně 247 otevřených/šifrovaných párů bloků. $p$ $p\cca 0,5$ $|p-0,5|$ $p>0,5$ $p<0,5$ $N=|p-1/2|2^{{-2}}$

Diferenciální metoda kryptoanalýzy.

Diferenciální metodu kryptoanalýzy (DCA) navrhli v roce 1990 E. Biham a A. Shamir. Diferenciální kryptoanalýza je pokusem prolomit tajný klíč blokových šifer, které jsou založeny na opakované aplikaci kryptograficky slabých šifrovacích operací r krát. Cryptanalysis předpokládá, že každý cyklus šifrování používá svůj vlastní šifrovací podklíč. DFA může používat vybrané i známé otevřené texty. Hlavní podmínkou úspěchu pokusů o otevření r-cyklické šifry je existence diferenciálů (r-1)-tého cyklu, které mají vysokou pravděpodobnost. Diferenciál i-tého cyklu je definován jako pár čísel , takže pár různých otevřených textů x a x* s rozdílem může po i-tém cyklu dát pár y a y* s rozdílem . Pravděpodobnost diferenciálu i-cyklu je podmíněná pravděpodobnost , že rozdíl mezi y a y* po i-tém cyklu je roven , za předpokladu, že původně existovaly x a x* s rozdílem . Otevřený text x a podklíče až 1 , až 2 , …, až i jsou považovány za nezávislé a náhodné. Postup DFA pro r-cyklickou šifru s vybranými otevřenými texty může být následující: $(\alpha ,\beta )_{i},$ $\alpha$ $\beta$ $P(\Delta y(i)=\beta |\Delta x=\alpha )$ $\beta$ $\alpha$

Tato fáze je fází předběžných výpočtů. Na něm hledáme množinu (r-1)-cyklových diferenciálů . Danou množinu seřadíme podle hodnoty jejich pravděpodobností. $(\alpha _{1},\beta _{1})_{r-1},(\alpha _{2},\beta _{2})_{r-1},... .(\alpha _{s},\beta _{s})_{r-1}$
Tato fáze vyžaduje, abychom zvolili x a x* tak, aby jejich rozdíl byl roven , pro ně máme dvojici šifrových textů y(r), y*(r). Domníváme se, že na výstupu z předposledního cyklu je rozdíl roven nejpravděpodobnějšímu . Pro trojnásobek najdeme všechny možné hodnoty podklíče k (r) . Zvyšujeme počítadlo výskytu každé takové hodnoty je spojeno s (r) . $\alpha_{1}$ $\Delta y(r-1)=\beta _{1}$ $(\Delta y(r-1),y(r),y^{*}(r))$
V této fázi opakujeme předchozí odstavec, dokud se jeden nebo více podklíčů nezačne objevovat častěji než ostatní. Daný klíč (nebo sadu klíčů) bereme jako řešení (r) .
V této fázi opakujeme kroky 1-3 pro (r-1)-tý cyklus, přičemž hodnoty y(r-1) se vypočítají dešifrováním y(r) pomocí klíče k (r) nalezeného v předchozí krok. A tyto akce opakujeme, dokud nenajdeme klíče všech cyklů.

Tato metoda byla původně navržena pro řešení jedné šifry, ale poté se ukázala jako úspěšná v kryptoanalýze mnoha Markovových šifer. Šifra se nazývá markovská, pokud její rovnice na jednom cyklu splňuje podmínku, že pravděpodobnost diferenciálu nezávisí na volbě otevřených textů. Pokud jsou klíče cyklů nezávislé, pak sekvence rozdílů každého cyklu tvoří Markovův řetězec, ve kterém každý následující prvek závisí pouze na předchozím. Příklady Markovových šifer jsou DES a FEAL. Ukažme, že Markovova r-cyklická šifra s nezávislými podklíči je zranitelná vůči DFA právě tehdy, když pro jeden cyklus lze klíč snadno vypočítat ze známého triple . Existuje také (r-1) diferenciál a jeho pravděpodobnost splňuje výraz , kde n je počet bitů v bloku šifrovaného textu. Složitost nalezení klíče r-cyklické šifry Q(r) je definována jako počet použitých šifrování, po kterém následuje nalezení klíče: kde Zejména pokud , pak takový útok nebude úspěšný. Vzhledem k tomu, že operace hledání podklíče je pracnější než operace šifrování, jednotkou složitosti je složitost nalezení možných podklíčů pro jeden cyklus nad známými trojkami. Charakteristickým rysem diferenciální kryptoanalýzy je, že téměř nepoužívá algebraické vlastnosti šifry (např. linearita, jiné.) Je založena pouze na nestejnoměrnosti rozdělení pravděpodobnosti diferenciálů. $(y,y^{*},\Delta x)$ ${\displaystyle (\alpha ,\beta )_{r-1))$ $P(\Delta y(r-1)=\beta |\Delta x=\alpha )\gg 2^{-n},$ $Q(r)\geqslant 2/(P_{\mathrm {max} }-1/(2^{n}-1)),$ $P_{\mathrm {max} }=\jméno operátora {max} (\alpha )\jméno operátora {max} (\beta )(P(\Delta y(r-1)=\beta |\Delta x=\ alfa)).$ $P_{\mathrm {max} }\cca 1/(2^{n}-1)$ $(\Delta y(r-1),y(r),y^{*}(r)).$

Poznámky

↑ Slovo betlém (podstatné jméno i sloveso) má v angličtině desítky významů, včetně slangových . Zejména ve školním slangu znamená jeslička nápovědu, podvodný list atd. nezákonné metody pro složení zkoušek

Literatura

Bruce Schneier. Aplikovaná kryptografie . Archivováno 28. února 2014 na Wayback Machine }
David Kahn. Lamači kódů.

Welchman, Gordon (1982), The Hut Six Story: Breaking the Enigma Codes , Harmondsworth: Allen Lane, ISBN 0713912944