Bloková šifra je druh symetrické šifry [1] , která pracuje se skupinami bitů pevné délky - bloky, jejichž charakteristická velikost se pohybuje v rozmezí 64‒256 bitů. Pokud je původní text (nebo jeho zbytek) menší než velikost bloku, je před šifrováním doplněn . Bloková šifra je ve skutečnosti substitucí na abecedě bloků, která v důsledku toho může být mono- nebo polyalfabetická. [2] Bloková šifra je důležitou součástí mnoha kryptografických protokolů a je široce používána k ochraně dat přenášených po síti.
Na rozdíl od šifrovacího bloku , kde se délka klíče rovná délce zprávy, je bloková šifra schopna zašifrovat jednu nebo více zpráv jedním klíčem s celkovou délkou větší, než je délka klíče. Přenos klíče, který je malý ve srovnání se zprávou přes šifrovaný kanál, je mnohem jednodušší a rychlejší než přenos samotné zprávy nebo klíče stejné délky, což umožňuje každodenní použití. Šifra však v tomto případě přestává být neprolomitelná. Blokové šifry se liší od proudových šifer v tom, že zpracovávají bity ve skupinách, nikoli v proudu. Blokové šifry jsou zároveň pomalejší než proudové. [3] Symetrické systémy mají oproti asymetrickým výhodu v rychlosti šifrování, která jim umožňuje zůstat relevantní i přes slabší mechanismus přenosu klíče (příjemce musí znát tajný klíč, který musí být přenášen již zavedeným šifrovaným kanálem. V asymetrických šifrách může být veřejný klíč potřebný pro šifrování znám všem a není potřeba šifrovací klíč sdílet).
Mezi výhody blokových šifer patří podobnost postupů šifrování a dešifrování , které se zpravidla liší pouze v pořadí akcí. To zjednodušuje vytváření šifrovacích zařízení, protože umožňuje použití stejných bloků v šifrovacím a dešifrovacím řetězci. Flexibilita blokových šifer umožňuje jejich použití ke konstrukci dalších kryptografických primitiv: generátor pseudonáhodné sekvence , proudová šifra, imitace vkládání a kryptografické hashe . [čtyři]
Moderní model blokové šifry je založen na myšlence iterativních blokových šifer navržených v publikaci Clauda Shannona z roku 1949 „ Teorie komunikace v tajných systémech “. Tento koncept vám umožňuje dosáhnout určité úrovně zabezpečení kombinací snadno proveditelných substitučních a permutačních operací [ 5 ] .
Až do 70. let byla kryptografie údělem armády a zpravodajských důstojníků, v otevřeném tisku nebyly prakticky žádné publikace [6] . Průkopníkem byla šifra „ Lucifer “, vyvinutá v roce 1970 společností IBM a založená na síti SP-net . Myšlenkou šifry bylo použití kombinací jednoduchých, a tedy rychle vypočítaných operací jak v hardwaru, tak v softwaru. Schéma se však ukázalo jako neúspěšné: bylo příliš těžkopádné, což vedlo k nízké rychlosti šifrování v softwarové implementaci (asi 8 kb/s) a v hardwaru (97 kb/s).
Začaly se objevovat obavy o stabilitu tohoto algoritmu. Principy vyvinuté při konstrukci Lucifera (SP-network a Feistel network , pojmenované po jednom z vývojářů) však tvořily základ pro konstrukci blokových šifer.
V roce 1973 vyhlásil Národní institut pro standardy a technologie ( NIST ) soutěž na vývoj standardu pro šifrování dat, jejímž vítězem se v roce 1974 stala šifra DES (Data Encryption Standard), která je ve skutečnosti vylepšenou verzí Lucifera. . Zveřejnění šifry v roce 1977 bylo zásadní pro veřejné pochopení moderního modelu blokové šifry. Zároveň to dalo podnět k rozvoji kryptoanalytických útoků .
Po schválení Americkým národním normalizačním institutem v roce 1981 byl algoritmus dlouhou dobu používán v civilním sektoru a šel i za hranice Spojených států amerických . Šifra však měla značný nedostatek – malou délku klíče, která dala vzniknout mnoha útokům spojeným s paralelním výčtem, a blížící se možnost její implementace. Nedostatek adekvátní ochrany proti útokům šifry DES dal vzniknout mnoha algoritmům, které jsou jak složitější verzí DES ( 3DES ), tak zcela odlišnými schématy ( NewDES , FEAL , IDEA ).
V roce 1997 byl zahájen program přijetí AES (Advanced Encryption Standard). Soutěž sestávala ze tří fází, jejichž konečným vítězem se stal algoritmus RIJNDAEL vyvinutý Belgičany J. Daemenem a V. Rijmenem. AES, stejně jako jeho předchůdci, je také postaven pomocí sítě SP.
Dnes existuje mnoho útoků, kterým musí bloková šifra odolat, počínaje útokem hrubou silou jako nejtriviálnějším. [7]
Bloková šifra se skládá ze dvou párových algoritmů: šifrování a dešifrování . [8] Oba algoritmy lze reprezentovat jako funkce. Šifrovací funkce E ( angl. encryption - encryption ) přijímá jako vstup datový blok M ( angl. message - message) o velikosti n bitů a klíč K ( angl. key - key) o velikosti k bitů a dává blok šifrového textu C ( eng. cipher ) na výstupu - cipher) o velikosti n bitů:
Pro libovolný klíč K je EK bijektivní funkce ( permutace ) na množině n - bitových bloků. Dešifrovací funkce D (anglicky decryption - decryption ) přijímá šifrový text C, klíč K jako vstup a na výstupu dává M:
je zároveň opakem šifrovací funkce:
aVšimněte si, že klíč požadovaný pro šifrování a dešifrování je stejný, což je důsledek symetrie blokové šifry.
„Navrhnout blokovou šifru není těžké. Obtíž spočívá v navržení blokové šifry, která je nejen bezpečná, ale také snadno popsatelná a snadno implementovatelná.“
Bruce Schneier , kryptograf a specialista na počítačovou bezpečnost .
Průkopníky ve vývoji blokových šifer byli zaměstnanci IBM při práci na šifře „ Lucifer “. [9] Navrhli první základy, které byly použity při vývoji následných obvodů. Zároveň je třeba vzít v úvahu, že nová šifra by měla být nejen odolná vůči všem známým typům útoků, ale také poměrně jednoduchá na implementaci.
Většina blokových šifer je iterativní. To znamená, že daná šifra převádí bloky otevřeného textu konstantní délky na bloky šifrovaného textu stejné délky pomocí cyklických reverzibilních funkcí známých jako kruhové funkce. [10] Důvodem je jednoduchost a rychlost provádění softwarových i hardwarových implementací. Obloukové funkce obvykle používají různé klávesy odvozené od původní klávesy:
,kde C i je hodnota bloku po i-tém kole, C 0 = M je otevřený text, K i je klíč použitý v i-tém kole a získaný z původního klíče K.
Velikost bloku n je pevný parametr blokové šifry, obvykle 64 nebo 128 bitů, ačkoli některé šifry umožňují několik různých hodnot. Délka 64 bitů byla přijatelná až do poloviny 90. let, kdy se používalo 128 bitů, což zhruba odpovídá velikosti strojového slova a umožňuje efektivní implementaci na většině běžných výpočetních platforem. Různá schémata šifrování umožňují šifrovat prostý text libovolné délky. Každý má určité vlastnosti: pravděpodobnost chyby, snadný přístup, zranitelnost vůči útokům. Od roku 2006 byl 80bitový klíč schopen zabránit útoku hrubou silou .
SP-network ( anglicky substitution-permutation network, SPN ) je jedním z nejdůležitějších typů iterativních blokových šifer. Šifra založená na SP-net přijímá blok a klíč jako vstup a provádí několik střídavých kol, sestávajících ze střídavých substitučních fází a permutačních fází [ 11 ] . K dosažení bezpečnosti stačí jeden S-box, ale takový blok bude vyžadovat velké množství paměti. Proto se používají malé S-boxy smíchané s P-boxy [6] . Fáze nelineární substituce míchá klíčové bity s bity prostého textu, což Shannonovi vyvolává rozpaky Fáze lineární permutace distribuuje redundanci v celé datové struktuře, což vede k difúzi [12] [13] .
S - box nahrazuje malý blok vstupních bitů jiným blokem výstupních bitů. Tato substituce musí být individuální, aby byla zaručena reverzibilita. Účelem S-boxu je nelineární transformace, která zabraňuje provádění lineární kryptoanalýzy . Jednou z vlastností S-boxu je lavinový efekt , to znamená, že změna jednoho bitu na vstupu vede ke změně všech bitů na výstupu [14] .
P-blok - permutace všech bitů: blok přijme výstup S-boxu jako vstup, prohodí všechny bity a pošle výsledek do S-boxu dalšího kola. Důležitou vlastností P-boxu je schopnost distribuovat výstup jednoho S-boxu na vstupy co největších S-boxů.
Pro každé kolo se používá jiný klíč , získaný z původního . Takový klíč se nazývá kulatý klíč. Lze jej získat rozdělením původního klíče na stejné části, nebo nějakou transformací celého klíče.
Feistelova síť je obecná metoda pro transformaci libovolné funkce F na permutaci na množině bloků. [15] Skládá se z cyklicky se opakujících buněk – kol. V každém kole je blok otevřeného textu rozdělen na dvě stejné části. Funkce kulatá
vezme jednu polovinu (na obrázku vlevo), transformuje ji pomocí klíče K i a výsledek spojí s druhou polovinou pomocí operace výhradního OR (XOR). Tento klíč je dán počátečním klíčem K a je pro každé kolo jiný. Poté se poloviny prohodí (jinak se převede pouze jedna polovina bloku) a podají se do dalšího kola. Transformace sítě Feistel je vratná operace.
Pro funkci F existují určité požadavky :
Pokud nebude splněn první požadavek, bude síť vystavena rozdílovým útokům (podobné zprávy budou mít podobné šifry). V druhém případě jsou akce šifry lineární a k prolomení postačí řešení soustavy lineárních rovnic [3] .
Tento design má hmatatelnou výhodu: postupy šifrování / dešifrování jsou stejné, pouze deriváty původních klíčů se používají v opačném pořadí. To znamená, že stejné bloky lze použít jak pro šifrování, tak pro dešifrování, což jistě zjednodušuje implementaci šifry. Nevýhodou schématu je, že v každém kole se zpracovává pouze polovina bloku, což vede k nutnosti zvýšit počet kol. [2]
Při konstrukci algoritmu se bere v úvahu vytvoření skupiny , ve které jsou prvky množina bloků šifrovaného textu se všemi klíči a skupinovou operací je složení šifrovacích kol. Pokud daná šifra tvoří téměř kompletní skupinu, nemá smysl používat vícenásobné šifrování [6] .
Bloková šifra sama o sobě umožňuje šifrovat pouze jednotlivé datové bloky předem stanovené délky. Pokud je délka zprávy menší než délka bloku ( angl. blocklength ), pak se doplní na požadovanou délku. Pokud je však délka zprávy delší, je nutné ji rozdělit do bloků. Zároveň existuje několik způsobů, jak takové zprávy zašifrovat, nazývané provozní režimy blokové šifry.
Nejjednodušším režimem činnosti blokové šifry je režim elektronické kódové knihy nebo režim jednoduché substituce ( Eng. Electronic CodeBook, ECB ), kde jsou všechny bloky otevřeného textu šifrovány nezávisle na sobě. Při použití tohoto režimu jsou však statistické vlastnosti otevřených dat částečně zachovány, protože každý identický datový blok jednoznačně odpovídá zašifrovanému datovému bloku. U velkého množství dat (například videa nebo zvuku) to může vést k úniku informací o jejich obsahu a poskytnout větší prostor pro kryptoanalýzu .
Odstranění statistických závislostí v prostém textu je možné pomocí předběžné archivace, ale neřeší to problém úplně, protože servisní informace archiváře zůstávají v souboru , což není vždy přijatelné.
K překonání těchto problémů byly vyvinuty další režimy provozu [16] [17] , stanovené mezinárodní normou ISO/IEC 10116 [18] a definované národními směrnicemi, jako je NIST 800-38A [19] a BSI TR- 02102 [20]
Obecnou myšlenkou je použití náhodného čísla, často označovaného jako inicializační vektor (IV). V oblíbeném režimu Cipher Block Chaining ( CBC ) musí být IV z důvodu bezpečnosti náhodné nebo pseudonáhodné. Jakmile je definován, je XORed s prvním blokem prostého textu. Dalším krokem je zašifrování výsledku a získání prvního bloku šifry, který použijeme jako IV pro druhý blok a tak dále. V režimu Cipher Feedback ( CFB ) je IV přímo zašifrován, načež je přidán modulo dva (XOR, exkluzivní OR) s prvním blokem. Přijatý blok šifry je použit jako IV pro další šifrování. Režim nemá žádné zvláštní výhody oproti ostatním. Na rozdíl od předchozích režimů režim Output Feedback ( OFB ) šifruje IV cyklicky a tvoří proud klíčů přidávaných do bloků zpráv. Výhodou režimu je naprostá shoda šifrovacích a dešifrovacích operací. Režim čítače ( anglicky Counter, CTR ) je podobný OFB, ale umožňuje paralelní výpočet šifry: IV se spojí s číslem bloku bez jedničky a výsledek se zašifruje. Výsledný blok je přidán do odpovídajícího bloku zpráv.
Mějte na paměti, že inicializační vektor se musí v různých relacích lišit. Jinak se dostáváme k problému režimu ECB. Je možné použít náhodné číslo, ale to vyžaduje přiměřeně dobrý generátor náhodných čísel. Obvykle se proto nastavuje určité číslo – popisek známý oběma stranám (například číslo relace) a nazývá se nonce ( Number Used Once ) . Utajení tohoto čísla se obvykle nevyžaduje. Další IV je výsledkem šifrování nonce. V případě režimu čítače se nonce používá k vytvoření kulatého klíče K i [3] :
kde i je kulaté číslo.Jak je uvedeno výše, pokud je délka samotné zprávy nebo posledního bloku menší než délka bloku, je třeba jej doplnit . Pouhé vyplnění nulovými bity problém nevyřeší, protože přijímač nebude schopen najít konec užitečného zatížení. Navíc tato možnost vede k útokům Oracle z dodatku [21] .
V praxi je proto použitelné řešení standardizované jako "Complement Method 2" ( Bit Completion ) v ISO/IEC 9797-1, kdy se na konec zprávy přidá 1 bit a zbývající prostor se vyplní nulami [22] . V tomto případě byla prokázána odolnost vůči takovým útokům [23] .
Stejně jako všechny šifry, jejichž algoritmy jsou známé, i blokové šifry podléhají kryptografickým útokům. Cílem útoku je vyvinout crackovací algoritmus, který je efektivnější než vyčerpávající hledání všech možných klíčů. Pokud je takové řešení nalezeno, je útok považován za úspěšný. Zároveň je šifra prolomena, pokud dojde k útoku, který umožňuje prolomení během doby, po kterou informace zůstává relevantní, a provedení takového útoku je pro útočníka výhodné.
Angličtina Útok skutečnou silou . Díky vlastnosti blokové šifry jako vratnosti funkce se její výstup stává odlišitelným od skutečné náhodné sekvence díky narozeninovému paradoxu . Tato vlastnost vede ke snížení bezpečnosti šifry a nutnosti brát v úvahu velikost bloku. Existuje tedy kompromis mezi velkými bloky, které snižují výkon šifry, a nespolehlivými malými bloky [24] .
Neméně důležitou roli hraje velikost klíče. Raná šifra DES se vyznačovala velikostí klíče 56 bitů, což, jak praxe ukázala, zjevně nestačí pro spolehlivý přenos dat. Byl to útok hrubou silou, který jako první zlomil DES. Modernější algoritmy jako AES a GOST 28147-89 mají velikost klíče 128 bitů, respektive 256 bitů, takže takové útoky nemají smysl [25] .
Angličtina Diferenciální kryptoanalýza . V roce 1990 Eli Biham a Adi Shamir definovali myšlenku diferenciální kryptoanalýzy. Touto metodou bylo možné prolomit šifru DES . Konstantní šifry S-box a kódované šifry v režimu e-knihy jsou náchylné k podobnému útoku . Tato metoda pracuje s dvojicemi šifrových textů, u kterých je znám rozdíl mezi odpovídajícími otevřenými texty, a zvažuje vývoj těchto rozdílů. Spolu s lineární je nejčastější při útocích na blokovou šifru [6] .
Angličtina Lineární kryptoanalýza . Lineární kryptoanalýza je metoda prolomení šifry založená na hledání afinních aproximací, aby algoritmus fungoval. Vyvinutý japonským matematikem Mitsuru Matsui , který jako první použil tuto techniku k útoku na DES a FEAL . Metoda je založena na aplikaci operace "Exclusive OR" (XOR) na bloky otevřeného textu, šifrového textu a jejich výsledek, což umožňuje získat výsledek XORingu klíčových bitů. Struktura S-bloku má silný vliv na odolnost proti liniovým útokům. Když byla metoda vyvinuta, ukázalo se, že DES pro ni má slabost, protože při jejím vývoji nikdo takové útoky nečekal [6] .
Angličtina Mezigalská kryptoanalýza . Integrální kryptoanalýza je typ útoku, který je zvláště použitelný pro blokové šifry postavené na SP-netu. Na rozdíl od diferenciální kryptoanalýzy, která používá pár vybraných holých textů s fixním rozdílem vypočítaným pomocí operace XOR, integrální dešifrování používá soubory holých textů, ve kterých jsou některé části konstanty, zatímco jiné se liší mezi možnými hodnotami. Taková množina má nutně modulo 2 (XOR) součet 0, zatímco odpovídající součet šifrovaného textu obsahuje informace o operacích šifry.
Kromě výše popsaných existují další typy útoků:
Každá nová šifra musí prokázat odolnost vůči všem známým typům útoků.
V praxi se bloková šifra hodnotí podle různých kritérií [26] [27] :
Luciferova šifra je obecně považována za první blokovou šifru. Algoritmus byl vyvinut společností IBM v 70. letech 20. století pro vlastní potřeby a je založen na práci Horsta Feistela . Finalizovaná verze byla přijata jako federální standard zpracování informací vlády USA : FIPS PUB 46 Data Encryption Standard (DES) - standard pro šifrování dat.
DES má velikost bloku 64 bitů a klíč 56 bitů. Následně se 64bitové bloky staly obecně akceptovanými při konstrukci šifry. Délka klíče závisela na několika faktorech, včetně vládních omezení, a v důsledku toho se stala zjevnou nevýhodou algoritmu - nestačilo odolat útokům hrubou silou. V roce 1993 Michael Wiener zkonstruoval stroj za 1 milion dolarů schopný rozbít DES za 3,5 hodiny hrubou silou a v roce 1998 byl stroj schopný praskání. Kromě toho pro klíče algoritmu existuje řada hodnot, které jsou považovány za slabé [6] .
Existuje vylepšená verze algoritmu nazvaná Triple DES nebo 3DES. Rychlost algoritmu se snížila třikrát, ale systém se ukázal být mnohem odolnější vůči vyčerpávajícímu vyhledávání díky ztrojnásobené délce klíče (168 bitů a 112 tajných bitů). Volitelně si můžete vybrat dvojitý klíč (112 bitů a 80 tajných bitů). Od roku 2011 si tříklíčový systém zachovává zabezpečení, ale dvouklíčová verze s 80bitovým zabezpečením již nevyhovuje moderním požadavkům [28] .
GOST 28147-89, ruský šifrovací standard zavedený v roce 1990, je také standardem CIS. Šifra je založena na 32kolové síti Feistel s 256bitovým klíčem. V květnu 2011 se kryptoanalytik Nicolas Courtois pokusil o útok, který zkrátil dobu prolomení o faktor 28 (256), ale vyžadoval 264 párů holého textu/ šifrovaného textu , což nelze považovat za úspěšný útok, protože s takovým množstvím holého textu není potřeba pro znalost šifrového textu. [29] [30]
Kvůli přítomnosti velkého počtu kol nejsou útoky založené na diferenciální a lineární kryptoanalýze životaschopné, protože ty jsou citlivé na počet kol. Úplné vyhledávání s takovou délkou klíče je naprosto nesmyslné. K dosažení lavinového efektu vyžaduje GOST 8 ran, což může být slabina algoritmu, ale při 32 kolech to tolik nevadí. Otázka bezpečnosti GOST zůstává otevřená [6] .
AES, přijatý NIST v roce 2001 po 5 letech veřejné soutěže, nahradil DES jako federální standard Spojených států. Šifru vyvinuli dva belgičtí kryptografové Daimen Yoan a Raymen Vincent . Velikost bloku je 128 bitů a velikosti klíčů jsou 128, 192 a 256 bitů, ačkoli velikost bloku může být specifikována libovolným počtem bitů násobkem 32, s minimální hodnotou 128 bitů. Maximální velikost bloku je 256 bitů, přičemž velikost klíče nemá žádné teoretické omezení. Podporu této šifry zavedl Intel v řadě procesorů x86 .
Blokovou šifru lze použít ke konstrukci dalších kryptografických primitiv :
Slovníky a encyklopedie |
---|
Symetrické kryptosystémy | |
---|---|
Streamové šifry | |
Síť Feistel | |
Síť SP | |
jiný |