Útok předpokládaný klíčem

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é 21. března 2015; kontroly vyžadují 24 úprav .

Útok zvoleným klíčem je jednou z metod kryptoanalytického útoku , která sleduje činnost šifrovacího algoritmu využívajícího několik tajných klíčů . Kryptanalytik má zpočátku pouze informace o určitém matematickém vztahu, který spojuje klíče dohromady.

Popis

Podle Kerckhoffsova principu má kryptoanalytik všechny potřebné informace o použitém šifrovacím systému, kromě určité sady tajných parametrů nazývaných klíč. Kryptanalytik zná pouze vztah mezi párem klíčů. K uhodnutí obou klíčů používá šifrový text a daný poměr. Jsou známy dva typy útoků na vybraný klíč: útok pomocí zvoleného klíče a známého otevřeného textu, při kterém kryptoanalytik specifikuje pouze vztah mezi párem klíčů, a útok pomocí zvoleného klíče a otevřeného textu, při kterém kryptoanalytik nastaví vztah mezi klíčový pár a a samotný prostý text, který má být zašifrován. [jeden]

Útok na základě zvoleného klíče se provádí stejným způsobem na všechny kryptosystémy, včetně tzv. „černé skříňky“, ve které jsou neznámé všechny vlastnosti. Tato "černá skříňka" využívá funkci šifrování , která se volí stejným způsobem pro náhodné permutace zpráv. Bity klíče jsou vybírány náhodně, takže znalost šifrového textu nám nemůže říci nic o šifrovém textu klíče . ${\displaystyle E_{k))$ $k$ $E_{k}(m)$ $E_{h}(m')$ $h\neq k$

Algoritmus útoku založený na zvoleném klíči na „černé skříňce“ může kromě standardních operací kdykoli během výpočtu vyžadovat:

šifrovat nebo dešifrovat pomocí tajného klíče a odpovídající zprávy a inverzního vektoru , $E_{k\oplus l}(m)$ $E_{k\oplus l}^{-1}(m)$ $k$ $m$ $l$
použijte "černou skříňku" pro výpočet nebo pomocí klíče (což není funkce ) vyzvednutím zprávy . $E_{h}(m)$ $E_{h}^{-1}(m)$ $h$ $k$ $m$

Algoritmus může mít také přístup k generátoru náhodných bitů. Na konci výpočtu je výstupem odhadovaný klíč . [2] $k$

Pokud tedy uživatel používá tajný klíč a veřejný kryptosystém ( kryptosystém veřejného klíče ), může si kryptoanalytik kdykoli vybrat zprávu a inverzní vektor a provést šifrování nebo dešifrování . Hlavní aplikací útoku na uhádnutý klíč je ověřování systémů, ale za určitých okolností lze tento útok aplikovat v praxi. Pokud se k přenosu klíče relace od uživatele k uživateli použije proudová šifra a kryptoanalytik získá kontrolu nad přenosovou linkou, může změnit libovolné bity klíče podle svých představ a obdrží změněný klíč místo . Poté, když zahájí přenos pomocí nesprávného klíče, obdrží zkomolenou zprávu a zahájí proceduru obnovy. Mezitím kryptoanalytik obdrží text zašifrovaný klíčem. (Dobrá krypto ochrana může takové útoky odvrátit použitím nových nezávislých klíčů relace nebo přidáním nelineárních bitů detekce chyb do klíče relace, kdykoli je potřeba procedura obnovy. Historie však ukazuje, že dobrá krypto ochrana to vždy nedodržuje. je žádoucí mít systém, který při takovém útoku nepadá) [3] . $k$ $E$ $m$ $l$ $E_{{k\oplus l}}$ $E_{{k\oplus l}}^{{-1}}$ $k$ $A$ $B$ $B$ $k\oplus l$ $k$ $B$ $A$ $k\oplus l$

Hlavní typ útoku založený na zvoleném klíči

V této části se budeme zabývat útokem, který nezávisí na konkrétní slabosti ve funkci šifrování. Jedná se o útok typu man-in-the-middle ( MITM ). Tento typ útoku umožňuje zkrátit dobu pokročilého vyhledávání v závislosti na počtu povolených inverzí klíče [4] .

Teorém. Nechť je bloková šifra s n-bitovým klíčem. Předpokládejme, že kryptoanalytik může provádět inverze a má slova paměti. Poté bude schopen rozluštit šifru v dalších krocích [4] . $E$ $2^{p}$ $2^{p}$ $E$ $2^{{np}}$

Důkaz:

Analytik všemi možnými způsoby nahrazuje poslední bity v klíči . Například šifruje hodnoty $p$ $2^{p}$

E_{k}(m),E_{{k\oplus (00\tečky 01)}}(m),\tečky ,E_{{k\oplus j}}(m),\ldots ,E_{{k\ oplus (00\tečky 011\tečky 1)}} (m)

kde je soukromý klíč uživatele a jakákoli vhodná zpráva. Z hodnot [4] vytvoří hashovací tabulku . $k$ $m$ $2^{p}$ $(E_{{k\oplus j}},j)$

Poté provede šifrování změnou prvních bitů klíče a resetováním posledních bitů: $2^{{np}}$ $np$ $p$

E_{{(00\dots 0)}}(m),E_{{(00\tečky 10\dots)}}(m),\tečky ,E_{{(11\tečky 10\ldots 0)}}( m)

Po všech výpočtech je každá hodnota porovnána s hashovací tabulkou [4] .

Pokud je původní klíč prolomen přes , kde se skládá z posledních bitů, bude záznam odpovídat výsledku pomocí šifrování ve druhé fázi. Když je nalezena shoda, bude to kandidátský klíč. Několik falešných poplachů je možné, pokud se zprávou shoduje více klíčů , ale stejně jako v případě útoku s odpovídajícím textem je jeden nebo dva další bloky známého otevřeného textu téměř jistě vyloučí, s malým dopadem na dobu běhu [4] . $k$ $(a,b)$ $b$ $p$ $(E_{{k\oplus b}},b)$ $a^{{th}}$ $(a,b)$ $m$

Závěr: Pomocí neomezeného počtu útoků se zvoleným klíčem lze prolomit jakoukoli blokovou šifru s n-bitovým klíčem pouze pomocí výpočtů v paměti [4] . $O(2^{{n{/2}})$

Důkaz: Pojďme si vybrat . $p=n/2$

Poznámka: Pro velké množství příkladů a velké množství dostupné paměti bude mnohem efektivnější obě fáze v důkazu věty prohodit. Vypočítat a uložit šifrování do paměti. U každého úkolu proveďte inverze a zkontrolujte, zda tabulka vyhovuje. Iterace tedy budou vynaloženy na každý další úkol [4] . $2^{{np}}$ $2^{p}$ $2^{p}$

Zranitelnost blokového kódu vůči útoku na základě zvoleného klíče

Schopnosti tohoto typu útoku si ukážeme na kryptosystému, který se ukázal jako extrémně odolný proti útokům se shodným textem [3] .

Nechť je tajná bloková šifra s klíčem o velikosti bitů. Pojďme definovat novou blokovou šifru . $E$ $n$ $F$

F_{k}(m)=E_{k}(m)

pokud je první bit 0

k

F_{k}(m)=E_{{k'}}(m)\oplus k

v ostatních případech, kdy výsledkem inverze prvního bitu je například .

k'

k

k'=k\oplus(1,0,\ldots ,0)

F

legitimní bloková šifra:

F_{k}^{{-1}}(m)=E_{k}^{{-1}}(m)

pokud je první bit klíče 0

k

F_{k}^{{-1}}(m)=E_{{k'}}^{{-1}}(m\plus k)

, v ostatních případech

Pokud má hlavní šifra dobrou n-bitovou ochranu, pak prolomení šifry útokem na analýzu textu vyžaduje pokročilé vyhledávání v klíčovém bitovém prostoru. Jinými slovy, pokud analytik nemá informace o šifře , může potřebné informace získat, pokud šifruje nebo dešifruje pomocí klíčů nebo [3] . $E$ $F$ $n-1$ $E$ $k$ $k'$

I když je šifra obtížně prolomitelná vybraným textovým útokem, je velmi snadné ji prolomit útokem zvoleného klíče. Analytik potřebuje dvě šifry: a pro nějakou vhodnou zprávu . Pokud je první bit nula, pak $F$ $F_{k}(m)$ $F_{{k'}}(m)$ $m$ $k$

F_{k}(m)\oplus F_{{k'}}(m)=E_{k}(m)\oplus (E_{{k''}}(m)\oplus k')=k'

V ostatních případech

F_{k}(m)\oplus F_{{k'}}(m)=(E_{{k'}}(m)\oplus k)\oplus (E_{{k'}}(m)=k

[3] .

Analytik tedy okamžitě obdrží všechny bity klíče , kromě prvního, a může dokončit operaci, protože zná otevřený text [4] . $k$

Příklady útoků

Útok na LOKI89

V šifře LOKI89 má každá volba ze dvou podklíčů , jeden ze sudého cyklu a jeden z lichého cyklu, odpovídající 64bitový klíč. Protože všechny algoritmy pro získání dvou podklíčů z předchozích dvou jsou stejné, umístění cyklů, ve kterých jsou umístěny dva aktuální podklíče, neovlivní výstup následujících podklíčů. Pokud opravíme dva podklíče a klíče a definujeme druhý klíč výběrem a , budou hodnoty podklíčů klíče stejné jako následující podklíče klíče . V tom případě, . Tento vztah je zachován pro libovolné dva klíče zvolené tímto způsobem: pokud jsou informace před druhým šifrovacím cyklem s klíčem stejné jako informace před prvním šifrováním pomocí klíče , pak jsou informace a vstupní data funkce stejné . v obou operacích posunuto o jeden cyklus. V tomto případě, pokud je otevřený text zašifrován klíčem , bude šifrovaný text před druhým cyklem . Přijatá data jsou stejná jako ta nalezená před prvním šifrovacím cyklem s klíčem , jehož hodnota bude , a tedy v tomto páru $K2$ $K3$ $K$ $K^{*}$ $K1^{*}=K2$ $K2^{*}=K3$ $Ki^{*}$ $K^{*}$ $K(i+1)$ $K$ $K^{*}=(K2,K3)=(K_{R},ROL12(K_{L}))$ $K$ $K^{*}$ $F$ $P$ $K$ $(P_{R}\oplus K_{R},P_{L}\oplus K_{L}\oplus F(P_{R}\oplus K_{R},K_{L}))$ $K^{*}$ $P^{*}\oplus K^{*}=(P_{R}^{*}\oplus K_{L},P_{R}^{*}\oplus ROL12(K_{L}))$

P ∗ = ( P R , P L ⊕ K L ⊕ R Ó L 12 ( K L ) ⊕ F ( P R ⊕ K R , K L ) ) {\displaystyle P^{*}=(P_{R},P_{L}\oplus K_{L}\oplus ROL12(K_{L})\oplus F(P_{R}\oplus K_{R},K_ {L}))}

P^{*}=(P_{R},P_{L}\oplus K_{L}\oplus ROL12(K_{L})\oplus F(P_{R}\oplus K_{R},K_ {L}))

Můžete vidět, že pravá strana výrazu je stejná jako levá strana výrazu a poměr ostatních dvou částí závisí na klíči. V takovém páru existuje podobný vztah mezi šifrovými texty:

P

P^{{*}}

C ∗ = ( C R ⊕ K L ⊕ R Ó L 12 ( K L ) ⊕ F ( C L ⊕ K R , K L ) , C L ) . {\displaystyle C^{*}=(C_{R}\oplus K_{L}\oplus ROL12(K_{L})\oplus F(C_{L}\oplus K_{R},K_{L}), C_{L}).}

C^{*}=(C_{R}\oplus K_{L}\oplus ROL12(K_{L})\oplus F(C_{L}\oplus K_{R},K_{L}), C_{L}).

Grafy popisují vztah mezi podklíči dvou klíčů a vztah mezi hodnotami během procesu šifrování.

SYSTÉM

Útok s holým textem se shodným klíčem, který spoléhá na tyto vlastnosti, vybere 32bitovou hodnotu , otevřené texty , jejichž pravé strany jsou , a jejichž 32bitové levé poloviny jsou náhodně vybrány, a prosté texty , jejichž levé strany jsou , a jejichž pravé strany jsou vybrány náhodně. Dva neznámé přidružené klíče se používají k šifrování dat v otevřeném textu ve zkoumaném systému: klíč se používá k šifrování prvních otevřených textů a klíč se používá k šifrování zbývajících otevřených textů. Pro každý pár otevřených textů je zaručeno, že as vysokou pravděpodobností existují dva otevřené texty takové, že . U takové dvojice zůstávají data stejná, pokud se obě provedení posunou o jeden cyklus. Takovou dvojici lze snadno vybrat, pokud existuje, kontrolou rovnosti Pravděpodobnost, že tento test náhodně projde, je tedy schopno projít jím jen několik párů. $P_{R}$ $2^{16}$ $P_{0},...,P_{65535}$ $P_{R}$ $2^{16}$ $P_{0}^{*},...,P_{65535}^{*}$ $P_{R}$ $K$ $2^{16}$ $K^{*}=(K_{R},ROL12(K_{L}))$ $2^{16}$ $P_{{i}}$ $P_{j}^{*}$ ${\displaystyle P_{jL}^{*}=P_{iR))$ $P_{jR}^{*}=P_{iL}\oplus K_{L}\oplus ROL12(K_{L})\oplus F(P_{iR}\oplus K_{R},K_{L} )$ $C_{R}^{*}=C_{L}.$ $2^{-32}$

Páry, které mají tyto vlastnosti prostého a šifrového textu, splňují klíčové požadavky (1) a (2). Pro tuto dvojici je tedy splněn vztah , ve kterém je hodnota jedinou neznámou . Ze všech možných hodnot tuto rovnici splňuje pouze několik. Pomocí diferenciální kryptoanalýzy a optimalizačních technik lze najít hodnotu pomocí několika operací. Jakmile je hodnota nalezena , je snadné vypočítat pomocí vzorců (1) a (2) a získat a . $F(P_{R}\oplus K_{R},K_{L})\oplus F(C_{L}\oplus K_{R},K_{L})=P_{R}^{*} \oplus P_{L}\oplus C_{L}^{*}\oplus C_{R}$ $K_{L}\oplus K_{R}$ $2^{32}$ $K_{L}\oplus K_{R}$ $K_{L}\oplus K_{R}$ $K_{L}\oplus K_{R}$ $K_{L}\oplus ROL12(K_{L})$ $K$ $K^{*}$

Podobný útok typu selected-key-known-plaintext používá známé otevřené texty zašifrované neznámým klíčem a otevřené texty zašifrované souvisejícím klíčem . Dvojici s těmito vlastnostmi lze snadno identifikovat podle 32 běžných bitů prostého textu a 32 společných bitů šifrového textu. Tento pár lze použít k hledání klíčů stejným způsobem jako při zvoleném klíči a zvoleném útoku v otevřeném textu. [jeden] $2^{32}$ $P_{{i}}$ $K$ $2^{32}$ $P_{j}^{*}$ $K^{*}=(K_{R},ROL12(K_{L}))$

Srovnání s jinými typy útoků

Podle Bruce Schneiera existuje 7 hlavních způsobů kryptanalytického útoku [5] :

Útok pouze pomocí šifrovaného textu.
Pitva pomocí prostého textu.
Útok pomocí vybraného otevřeného textu.
Adaptivní útok pomocí prostého textu.
Zaútočte pomocí vybraného šifrovaného textu.
Otevření pomocí zvoleného klíče.
Banditská kryptoanalýza .

V případě útoku založeného na šifrovaném textu má kryptoanalytik přístup pouze k šifrovanému textu. Jedná se o nejobtížnější typ útoku kvůli malému množství dostupných informací.

Při útoku se známým holým textem zná kryptoanalytik holý i šifrovaný text. Tento typ útoku je účinnější než útok založený na šifrovaném textu díky většímu množství známých informací o kryptosystému.

Zvolený útok v otevřeném textu je silnějším typem útoku než známý útok v otevřeném textu. Možnost předvýběru otevřeného textu poskytuje více možností pro extrakci systémového klíče. Je také pravda, že pokud je kryptosystém zranitelný vůči známému útoku v prostém textu, pak je také zranitelný vůči vybranému útoku v prostém textu. [jeden]

Útok na odpovídající klíč je silnější než útok na odpovídající text. Okamžitě prolomí speciálně vytvořenou blokovou šifru, která je zabezpečená proti dalším útokům. U jakékoli blokové šifry může zvolený útok klíčem urychlit proces pokročilého vyhledávání v závislosti na počtu povolených inverzí klíče. Pro neomezený útok na uhodnutý klíč lze množství práce snížit jako druhou odmocninu. Tyto výsledky jsou nejlepší možné pro obecný útok, který se nespoléhá na žádnou konkrétní blokovou šifru.

Poznámky

↑ 1 2 3 Biham, 1993 .
↑ Winternitz & Hellman, 1987 .
↑ 1 2 3 4 Winternitz & Hellman, 1987 , s. 17
↑ 1 2 3 4 5 6 7 8 Winternitz & Hellman, 1987 , s. osmnáct
↑ Schneier, 2003 .

Literatura

Robert Winternitz, Martin Hellman . Útoky vybraným klíčem na blokovou šifru // Cryptologia: journal. - 1987. - Ne. 11:1 . - str. 16-20 . - doi : 10.1080/0161-118791861749 .
Eli Biham. Nové typy kryptoanalytických útoků pomocí souvisejících klíčů // Helleseth T. (eds) Pokroky v kryptologii . — EUROCRYPT '93. EUROCRYPT 1993. Lecture Notes in Computer Science, vol 765. Springer, Berlin, Heidelberg, 1993. doi : 10.1007/3-540-48285-7_34 .
B. Schneier. Aplikovaná kryptografie. - Triumph, 2003. - 816 s. - ISBN 5-89392-055-4 .