Historie DES Vlastnosti DES Vady DES Popis DES Kritika DES Útoky 7. Šifrový standard DES a jeho kolegové Jan Paseka Ústav matematiky a statistiky Masarykova univerzita 29. listopadu 2021 Historie DES Popis DES Vlastnosti DES Kritika DES Vady DES Útoky a DES Využití DES Q Potřeba a historie vzniku DES • Potřeba DES • Využití DES Historie DES Popis DES Vlastnosti DES Kritika DES Vady DES Útoky Potreba DES Využití DES Fl Obrovský nárůst počítačové komunikace a nástup elektronických bankovních systémů v sedmdesátých letech byly jedním z hlavních faktorů pro rozhodnutí exekutivy Spojených států amerických na zajištění standardu pro bezpečný a spolehlivý transfer dat Federální banky a ostatních bank. Historie DES Popis DES Vlastnosti DES Kritika DES Vady DES Útoky Potreba DES Využití DES Fl Obrovský nárůst počítačové komunikace a nástup elektronických bankovních systémů v sedmdesátých letech byly jedním z hlavních faktorů pro rozhodnutí exekutivy Spojených států amerických na zajištění standardu pro bezpečný a spolehlivý transfer dat Federální banky a ostatních bank. Bylo tedy potřeba zajistitit ochranu dat jak v počítačích zpracovávaných a tamtéž ukládaných, tak i dat počítači Historie DES Popis DES Vlastnosti DES Kritika DES Vady DES Útoky Potřeba DES Využití DES Fl Obrovský nárůst počítačové komunikace a nástup elektronických bankovních systémů v sedmdesátých letech byly jedním z hlavních faktorů pro rozhodnutí exekutivy Spojených států amerických na zajištění standardu pro bezpečný a spolehlivý transfer dat Federální banky a ostatních bank. Bylo tedy potřeba zajistitit ochranu dat jak v počítačích zpracovávaných a tamtéž ukládaných, tak i dat počítači přenášených. Soutěž na tvorbu šifrovacího algoritmu vyhlásilo ministerstvo obchodu Spojených států amerických v roce 1973. Organizoval ji National Bureau of Standards (NBS). Historie DES Popis DES Vlastnosti DES Kritika DES Vady DES Útoky Potreba DES Využití DES Fl Obrovský nárůst počítačové komunikace a nástup elektronických bankovních systémů v sedmdesátých letech byly jedním z hlavních faktorů pro rozhodnutí exekutivy Spojených států amerických na zajištění standardu pro bezpečný a spolehlivý transfer dat Federální banky a ostatních bank. Bylo tedy potřeba zajistitit ochranu dat jak v počítačích zpracovávaných a tamtéž ukládaných, tak i dat počítači přenášených. Soutěž na tvorbu šifrovacího algoritmu vyhlásilo ministerstvo obchodu Spojených států amerických v roce 1973. Organizoval ji National Bureau of Standards (NBS). Požadovaným vlastnostem však nevyhověl žádný ze zaslaných algoritmů - základní idea byla, že šifrovací proces by mělo být možno provádět na malém čipu. ,DMflMlMl, t Historie DES Popis DES Vlastnosti DES Kritika DES Vady DES Útoky Potreba DES Využití DES Důsledkem pak by byla masová výroba těchto čipů, jejichž použití by zajišťovalo naprostou bezpečnost transferu dat. Historie DES Popis DES Vlastnosti DES Kritika DES Vady DES Útoky Potreba DES Využití DES Důsledkem pak by byla masová výroba těchto čipů, jejichž použití by zajišťovalo naprostou bezpečnost transferu dat. Pňtom sám algoritmus měl být bezpečný, pochopitelný, dostupný, výkonný, jeho bezpečnost neměla záviset na utajení algoritmu, vhodný pro nejrůznější aplikace a ekonomický pň elektronické realizaci -tj. čip by měl být levný. V srpnu 1974 byla výzva opakována. Historie DES Popis DES Vlastnosti DES Kritika DES Vady DES Útoky Potreba DES Využití DES Důsledkem pak by byla masová výroba těchto čipů, jejichž použití by zajišťovalo naprostou bezpečnost transferu dat. Pňtom sám algoritmus měl být bezpečný, pochopitelný, dostupný, výkonný, jeho bezpečnost neměla záviset na utajení algoritmu, vhodný pro nejrůznější aplikace a ekonomický pň elektronické realizaci -tj. čip by měl být levný. V srpnu 1974 byla výzva opakována. Tentokrát se algoritmus podařilo nalézt. Bylo akceptováno šifrovací schéma navržené firmou IBM. Její výzkumný tým pod vedením dr. Tuchmana jej založil na zdokonalení šifrovacího algoritmu LUCIFER, který IBM používala pro své potřeby. Historie DES Popis DES Vlastnosti DES Kritika DES Vady DES Útoky Potreba DES Využití DES Důsledkem pak by byla masová výroba těchto čipů, jejichž použití by zajišťovalo naprostou bezpečnost transferu dat. Pňtom sám algoritmus měl být bezpečný, pochopitelný, dostupný, výkonný, jeho bezpečnost neměla záviset na utajení algoritmu, vhodný pro nejrůznější aplikace a ekonomický pň elektronické realizaci -tj. čip by měl být levný. V srpnu 1974 byla výzva opakována. Tentokrát se algoritmus podařilo nalézt. Bylo akceptováno šifrovací schéma navržené firmou IBM. Její výzkumný tým pod vedením dr. Tuchmana jej založil na zdokonalení šifrovacího algoritmu LUCIFER, který IBM používala pro své potřeby. Na rozdíl od algoritmu LUCIFER, jež používal klíč o délce 128 bitů, délka klíče navržená pro NBS byla 64 bitů a z toho bylo 8 bitů odstraněno hned na začátku šifrování. Vlastnosti DES Kritika DES Vady DES Útoky NBS, IBM a N SA (National Security Agency) se dohodly, že NSA provede ohodnocení bezpečnosti DES (Data Encryption Standars), jak byl později nový algoritmus nazván, a IBM umožní jeho bezplatné využívání na území Spojených států amerických. DES byl patentován 24.2. 1975 a v březnu téhož roku byl zveřejněn pro všeobecné veřejné hodnocení. Vlastnosti DES Kritika DES Vady DES Útoky NBS, IBM a N SA (National Security Agency) se dohodly, že NSA provede ohodnocení bezpečnosti DES (Data Encryption Standars), jak byl později nový algoritmus nazván, a IBM umožní jeho bezplatné využívání na území Spojených států amerických. DES byl patentován 24.2. 1975 a v březnu téhož roku byl zveřejněn pro všeobecné veřejné hodnocení. Přes některé výhrady byl 23.11. 1976 přijat jako federální standard a jako takový zveřejněn 15.1. 1977. Algoritmus byl určen pro ochranu neutajovaných dat v civilním sektoru i vládních institucí vyjma ozbrojených složek, kde nemohl být používán ani k ochraně neutajovaných dat. Předpokládaná doba použití byla 10-15 let. Vlastnosti DES Kritika DES Vady DES Útoky NBS, IBM a N SA (National Security Agency) se dohodly, že NSA provede ohodnocení bezpečnosti DES (Data Encryption Standars), jak byl později nový algoritmus nazván, a IBM umožní jeho bezplatné využívání na území Spojených států amerických. DES byl patentován 24.2. 1975 a v březnu téhož roku byl zveřejněn pro všeobecné veřejné hodnocení. Přes některé výhrady byl 23.11. 1976 přijat jako federální standard a jako takový zveřejněn 15.1. 1977. Algoritmus byl určen pro ochranu neutajovaných dat v civilním sektoru i vládních institucí vyjma ozbrojených složek, kde nemohl být používán ani k ochraně neutajovaných dat. Předpokládaná doba použití byla 10-15 let. Schválen jako šifrovací standard (Federal Information Processing Standard - FIPS 46-3) v USA. Vlastnosti DES Kritika DES Vady DES Útoky DES vyhovuje normě ANSI z roku 1980 (ANSI X3, 92 -1981, pod názvem Data Encryption Algorithm, American National Standards Institute, New York, 1980). Proto je také někdy citován jako DEA. Vlastnosti DES Kritika DES Vady DES Útoky DES vyhovuje normě ANSI z roku 1980 (ANSI X3, 92 -1981, pod názvem Data Encryption Algorithm, American National Standards Institute, New York, 1980). Proto je také někdy citován jako DEA. Algoritmus měl být po svém přijetí v roce 1977 každých pět let hodnocen a jeho platnost potvrzována NBS. Vlastnosti DES Kritika DES Vady DES Útoky DES vyhovuje normě ANSI z roku 1980 (ANSI X3, 92 -1981, pod názvem Data Encryption Algorithm, American National Standards Institute, New York, 1980). Proto je také někdy citován jako DEA. Algoritmus měl být po svém přijetí v roce 1977 každých pět let hodnocen a jeho platnost potvrzována NBS. V roce 1984 zahájila NSA program "Commercial COMSEC Endorsement Program" (CCEP), určený pro zabezpečování ochrany vládních informací, v rámci něhož mělo být připraveno i nahrazování DES. Vlastnosti DES Kritika DES Vady DES Útoky DES vyhovuje normě ANSI z roku 1980 (ANSI X3, 92 -1981, pod názvem Data Encryption Algorithm, American National Standards Institute, New York, 1980). Proto je také někdy citován jako DEA. Algoritmus měl být po svém přijetí v roce 1977 každých pět let hodnocen a jeho platnost potvrzována NBS. V roce 1984 zahájila NSA program "Commercial COMSEC Endorsement Program" (CCEP), určený pro zabezpečování ochrany vládních informací, v rámci něhož mělo být připraveno i nahrazování DES. Byly vyvinuty hardwarové bezpečnostní moduly, provádějící šifrové algoritmy navržené pro tentokrát NSA. Tyto algoritmy byly typu 1 a typu 2. Vlastnosti DES Kritika DES Vady DES Útoky První byl určen pro utajované vládní informace a druhý pro neutajované vládní informace (měl nahradit DES). Později byla aplikace zařízení s algoritmem typu 2 rozšířena i na soukromý sektor. Po 1.1. 1988 neměla už NSA v úmyslu doporučovat DES pro vládní použití. Bylo však zjištěno, že by to způsobilo značné potíže v bankovním sektoru. DES byl v této době už masově používán v nejrůznějších zařízeních včetně mezinárodního bankovního spojení. To vedlo ministerstvo obchodu USA ke zmírnění stanoviska NSA. Vlastnosti DES Kritika DES Vady DES Útoky První byl určen pro utajované vládní informace a druhý pro neutajovane vládní informace (měl nahradit DES). Později byla aplikace zařízení s algoritmem typu 2 rozšířena i na soukromý sektor. Po 1.1. 1988 neměla už NSA v úmyslu doporučovat DES pro vládní použití. Bylo však zjištěno, že by to způsobilo značné potíže v bankovním sektoru. DES byl v této době už masově používán v nejrůznějších zařízeních včetně mezinárodního bankovního spojení. To vedlo ministerstvo obchodu USA ke zmírnění stanoviska NSA. V lednu 1988 NBS znovu potvrdil možnost používat DES v dalších 5 letech, avšak ne pro federální nefinanční použití. Ve federálních nefinančních institucích musel být DES nahrazován algoritmy vyvinutými NSA v rámci CCEP Vlastnosti DES Kritika DES Vady DES Útoky Algoritmy jsou utajovány a nesmí být exportovány ze Spojených států amerických. Čipy, které je realizují, mají ochranný kryt. Vlastnosti DES Kritika DES Vady DES Útoky Algoritmy jsou utajovány a nesmí být exportovány ze Spojených států amerických. Čipy, které je realizují, mají ochranný kryt. Výrobci produktů musí při jejich výrobě dodržovat zvláštní postup stanovený NSA. Tato opatření na ochranu nových algoritmů přinášejí do celé koncepce jejich využívání velké rozpory. Algoritmy jsou utajovány a nesmí být exportovány ze Spojených států amerických. Čipy, které je realizují, mají ochranný kryt. Výrobci produktů musí při jejich výrobě dodržovat zvláštní postup stanovený NSA. Tato opatření na ochranu nových algoritmů přinášejí do celé koncepce jejich využívání velké rozpory. Jejich softwarová implementace by nebyla schválena, protože by zde nemohla být zajištěna ochrana algoritmu před jeho odhalením. Přitom v mnoha aplikacích je softwarová implementace nezbytná. Historie DES Popis DES Vlastnosti DES Kritika DES Vady DES Útoky a DES Využití DES Algoritmy jsou utajovány a nesmí být exportovány ze Spojených států amerických. Čipy, které je realizují, mají ochranný kryt. Výrobci produktů musí při jejich výrobě dodržovat zvláštní postup stanovený NSA. Tato opatření na ochranu nových algoritmů přinášejí do celé koncepce jejich využívání velké rozpory. Jejich softwarová implementace by nebyla schválena, protože by zde nemohla být zajištěna ochrana algoritmu před jeho odhalením. Přitom v mnoha aplikacích je softwarová implementace nezbytná. Otázkou zůstávají i mezinárodní spoje, kde se předpokládá vývoz těchto zařízení. Je pravděpodobné, že dnes je už povolen přísně regulovaný vývoz, i když algoritmy zůstávají nadále utajeny. Vlastnosti DES Kritika DES Vady DES Útoky Vzhledem k tomu, že uvedená obranná opatření fungují velmi dobře, o zařízeních nevíme téměř nic, dokonce neznáme, ani jejich výkonové charakteristiky. Vlastnosti DES Kritika DES Vady DES Útoky Vzhledem k tomu, že uvedená obranná opatření fungují velmi dobře, o zařízeních nevíme téměř nic, dokonce neznáme, ani jejich výkonové charakteristiky. Také není dosud nic známo o rozhodnutí, které mělo být přijato NBS v únoru r. 1993, týkajícím se dalšího existence DES ve finančním sektoru pro léta 1993-1997. Vlastnosti DES Kritika DES Vady DES Útoky Vzhledem k tomu, že uvedená obranná opatření fungují velmi dobře, o zařízeních nevíme téměř nic, dokonce neznáme, ani jejich výkonové charakteristiky. Také není dosud nic známo o rozhodnutí, které mělo být přijato NBS v únoru r. 1993, týkajícím se dalšího existence DES ve finančním sektoru pro léta 1993-1997. DES se od roku 1977 stal nejrozšířenějším kryptografickým systémem ve světě. Je všeobecným nástrojem bezpečnosti ve veřejném i soukromém sektoru. Vlastnosti DES Kritika DES Vady DES Útoky Vzhledem k tomu, že uvedená obranná opatření fungují velmi dobře, o zařízeních nevíme téměř nic, dokonce neznáme, ani jejich výkonové charakteristiky. Také není dosud nic známo o rozhodnutí, které mělo být přijato NBS v únoru r. 1993, týkajícím se dalšího existence DES ve finančním sektoru pro léta 1993-1997. DES se od roku 1977 stal nejrozšířenějším kryptografickým systémem ve světě. Je všeobecným nástrojem bezpečnosti ve veřejném i soukromém sektoru. Ve finančním sektoru se používá k ochraně všech aspektů síťové komunikace a autentizace a de facto se stal mezinárodním standardem. Je včleněn do maloobchodních i velkoobchodních systémů, je přístupný v nedrahém hardwaru a jako volný software. < a ►< s ►<==►<== ► = Vlastnosti DES Kritika DES Vady DES Útoky Pouze ve Spojených státech amerických vývoz hardwaru i softwaru s DES dosud podléhá kontrole. DES je dostupný ve všech možných formách: ve formě čipů, zásuvkových modulů do PC nebo celých šifrovacích jednotek. Vlastnosti DES Kritika DES Vady DES Útoky Pouze ve Spojených státech amerických vývoz hardwaru i softwaru s DES dosud podléhá kontrole. DES je dostupný ve všech možných formách: ve formě čipů, zásuvkových modulů do PC nebo celých šifrovacích jednotek. Jsou k dispozici oficiální programy pro softwarovou realizaci a pro kontrolu správnosti jeho realizace v zařízeních. Standardizaci na bázi DES podporuje pět největších standardizačních organizací: ABA, ANSI, GSA, ISO a NBS. Vlastnosti DES Kritika DES Vady DES Útoky Pouze ve Spojených státech amerických vývoz hardwaru i softwaru s DES dosud podléhá kontrole. DES je dostupný ve všech možných formách: ve formě čipů, zásuvkových modulů do PC nebo celých šifrovacích jednotek. Jsou k dispozici oficiální programy pro softwarovou realizaci a pro kontrolu správnosti jeho realizace v zařízeních. Standardizaci na bázi DES podporuje pět největších standardizačních organizací: ABA, ANSI, GSA, ISO a NBS. Standardy NBS jsou používány jako základ standardů dalších organizací. DES se používá pro šifrování PIN (Personál Identification Number) v různých druzích platebních, přístupových aj. karet. Vlastnosti DES Kritika DES Vady DES Útoky Také v několika amerických vládních organizacích vytváří DES základní mechanismus ochrany (ministerstvo ekonomiky, ministerstvo spravedlnosti). V USA na bázi DES vznikl kryptografický průmysl. Vlastnosti DES Kritika DES Vady DES Útoky Také v několika amerických vládních organizacích vytváří DES základní mechanismus ochrany (ministerstvo ekonomiky, ministerstvo spravedlnosti). V USA na bázi DES vznikl kryptografický průmysl. Na konci roku 1999 bylo doporučeno, aby se přešlo z DES na její vylepšenou verzi 3DES (triple DES; trojitý DES). 3DES je trojnásobná aplikace DES algoritmu, pokaždé s jiným klíčem. Klíč šifry 3DES je tedy 168 bitů dlouhý. Vlastnosti DES Kritika DES Vady DES Útoky Také v několika amerických vládních organizacích vytváří DES základní mechanismus ochrany (ministerstvo ekonomiky, ministerstvo spravedlnosti). V USA na bázi DES vznikl kryptografický průmysl. Na konci roku 1999 bylo doporučeno, aby se přešlo z DES na její vylepšenou verzi 3DES (triple DES; trojitý DES). 3DES je trojnásobná aplikace DES algoritmu, pokaždé s jiným klíčem. Klíč šifry 3DES je tedy 168 bitů dlouhý. I když je algoritmus DES již vlastně minulostí, neboť jej lze snadno prolomit, 3DES je stále nasazován v mnoha aplikacích. Například Secure shell (ssh), shadow hesla v Unixu, šifrování uživatelských hesel v databázových serverech Sybase, Nortel VPN, apod. 0 Popis šifrovacího algoritmu DES • Bloková šifra • Použití NP-těžkých problémů v šifrovacích Historie DES Popis DES Vlastnosti DES Kritika DES Vady DES Útoky Bloková šifra NP-težké problémy DES patří do třídy blokových šifer. Otevřený text (OT) je rozdělen na bloky po 64 bitech. Historie DES Popis DES Vlastnosti DES Kritika DES Vady DES Útoky Bloková šifra NP-težké problémy DES patří do třídy blokových šifer. Otevřený text (OT) je rozdělen na bloky po 64 bitech. Každý z těchto bloků M otevřeného textu je jako celek zpracováván na blok C šifrového textu (ŠT) také o délce 64 bitů. Historie DES Popis DES Vlastnosti DES Kritika DES Vady DES Útoky Bloková šifra NP-težké problémy DES patří do třídy blokových šifer. Otevřený text (OT) je rozdělen na bloky po 64 bitech. Každý z těchto bloků M otevřeného textu je jako celek zpracováván na blok C šifrového textu (ŠT) také o délce 64 bitů. Píšeme jako obvykle C=EK(h4), M=DK(C), kde K je klíč o délce 56 bitů (vznikne z osmibajtového klíčového slova vynecháním jeho paritních bitů). Historie DES Popis DES Vlastnosti DES Kritika DES Vady DES Útoky Bloková šifra NP-težké problémy DES patří do třídy blokových šifer. Otevřený text (OT) je rozdělen na bloky po 64 bitech. Každý z těchto bloků M otevřeného textu je jako celek zpracováván na blok C šifrového textu (ŠT) také o délce 64 bitů. Píšeme jako obvykle C=EK{M), M=DK{C), kde K je klíč o délce 56 bitů (vznikne z osmibajtového klíčového slova vynecháním jeho paritních bitů). Zpracování bloku M probíhá v 16 krocích. V každém z nich je z klíče K vybráno podle určitého postupu 48 bitů tvořících pracovní klíč K/. Historie DES Popis DES Vlastnosti DES Kritika DES Vady DES Útoky Bloková šifra NP-težké problémy Vlastní blokový algoritmus při šifrování zpracovává blok M tak, že M je nejprve podroben počáteční permutací IP, která permutuje všech 64 bitů, a poté je rozdělen na pravou polovinu R0 a levou polovinu /_0, každá o 32 bitech. Historie DES Popis DES Vlastnosti DES Kritika DES Vady DES Útoky Bloková šifra NP-težké problémy Vlastní blokový algoritmus při šifrování zpracovává blok M tak, že M je nejprve podroben počáteční permutací IP, která permutuje všech 64 bitů, a poté je rozdělen na pravou polovinu R0 a levou polovinu /_0, každá o 32 bitech. Pak probíhá 16 totožných kroků, kdy je z dvojice (/_,, /?/) za účasti pracovního klíče K, vytvořena dvojice (L,-+1, f?,-+1), / = 0,1,..., 15. Historie DES Popis DES Vlastnosti DES Kritika DES Vady DES Útoky Bloková šifra NP-težké problémy Vlastní blokový algoritmus při šifrování zpracovává blok M tak, že M je nejprve podroben počáteční permutací IP, která permutuje všech 64 bitů, a poté je rozdělen na pravou polovinu R0 a levou polovinu /_0, každá o 32 bitech. Pak probíhá 16 totožných kroků, kdy je z dvojice (/_,, /?/) za účasti pracovního klíče K, vytvořena dvojice (L,-+1, f?,-+1), / = 0,1,..., 15. Rj je nejprve rozšířen z 32 bitů na 48 bitů prostřednictvím expanze E tak, že E(Ri) = E(/i, r2,..., r31, r32) = / I I i \ v ■ / V 32, hJzJzJA^bjA, ^6, r71 r8, r9, • • • , r28, r29, r30, r31 , r32, ^ J, a k výsledku je v modulu 2 tj. bit po bitu přečten klíč/fc., , t> t Historie DES Popis DES Vlastnosti DES Kritika DES Vady DES Útoky Bloková šifra NP-težké problémy Výstup E(Rj) © Kj je rozdělen do osmi částí po 6 bitech, které procházejí přes substituční boxy S-i až S8. Historie DES Popis DES Vlastnosti DES Kritika DES Vady DES Útoky Bloková šifra NP-težké problémy Výstup E(Rj) © Kj je rozdělen do osmi částí po 6 bitech, které procházejí přes substituční boxy S-i až S8. Tyto S-boxyjsou v podstatě pamětí ROM 6x4 bity a výstup je tedy celkem 8x4=32-bitový. Historie DES Popis DES Vlastnosti DES Kritika DES Vady DES Útoky Bloková šifra NP-težké problémy Výstup E (Rj) e K, je rozdělen do osmi částí po 6 bitech, které procházejí přes substituční boxy S-i až S8. Tyto S-boxyjsou v podstatě pamětí ROM 6x4 bity a výstup je tedy celkem 8x4=32-bitový. Většinou se tyto boxy popisují i zadávají tak, že krajní bity vstupu (1. a 6. bit) vybírají jeden ze čtyř možných boxů 4x4 bity a výstup těchto boxů se uvádí v tabulce. Historie DES Popis DES Vlastnosti DES Kritika DES Vady DES Útoky Bloková šifra NP-težké problémy Výstup E (Rj) © K, je rozdělen do osmi částí po 6 bitech, které procházejí přes substituční boxy S-i až S8. Tyto S-boxyjsou v podstatě pamětí ROM 6x4 bity a výstup je tedy celkem 8x4=32-bitový. Většinou se tyto boxy popisují i zadávají tak, že krajní bity vstupu (1. a 6. bit) vybírají jeden ze čtyř možných boxů 4x4 bity a výstup těchto boxů se uvádí v tabulce. Přitom se jejich vstupní i výstupní 4-bitová hodnota pro jednoduchost zapisuje dekadicky jako 0 až 15. Jsou to permutace na množině {0,1,..., 15}. Historie DES Popis DES Vlastnosti DES Kritika DES Vady DES Útoky Bloková šifra NP-težké problémy Výstup E (Rj) e K, je rozdělen do osmi částí po 6 bitech, které procházejí přes substituční boxy S-i až S8. Tyto S-boxyjsou v podstatě pamětí ROM 6x4 bity a výstup je tedy celkem 8x4=32-bitový. Většinou se tyto boxy popisují i zadávají tak, že krajní bity vstupu (1. a 6. bit) vybírají jeden ze čtyř možných boxů 4x4 bity a výstup těchto boxů se uvádí v tabulce. Přitom se jejich vstupní i výstupní 4-bitová hodnota pro jednoduchost zapisuje dekadicky jako 0 až 15. Jsou to permutace na množině {0,1,..., 15}. Výstup z S-boxů, tj. 8x4=32 bity, je upraven permutací P (32 na 32 bitů). Historie DES Popis DES Vlastnosti DES Kritika DES Vady DES Útoky loková šifra NP-těžké problémy Vzniklé 32-bitové slovo je označováno f(Rh K,), neboť je funkcí klíče Kj a slova f?,. □ t3 Historie DES Popis DES Vlastnosti DES Kritika DES Vady DES Útoky Bloková šifra NP-težké problémy Vzniklé 32-bitové slovo je označováno f(Rh K/), neboť je funkcí klíče Kj a slova fí,. Poslední operace v i-tém kroku je _Z-/+1 =Rj A/+1 =Lj®f(RhKj). (2.2) Po proběhnutí 16. kroku je provedena záměna L16 a fř16 a 64-bitový blok (fř16, L16) je permutován permutací/P~1 (permutací inverzní k /P). Historie DES Popis DES Vlastnosti DES Kritika DES Vady DES Útoky Bloková šifra NP-težké problémy Vzniklé 32-bitové slovo je označováno f(Rh K/), neboť je funkcí klíče Kj a slova fí,. Poslední operace v i-tém kroku je _Z-/+1 =Rj A/+1 =Lj®f(RhKj). (2.2) Po proběhnutí 16. kroku je provedena záměna L16 a fř16 a 64-bitový blok (fř16, L16) je permutován permutací/P~1 (permutací inverzní k /P). Výsledek je již C = EK{M). Historie DES Vlastnosti DES Vady DES Popis DES Kritika DES Útoky loková šifra NP-těžké problémy 1 u Levá polovina IP 32 L, 32 Li+ 32 LJ(i Historie DES Vlastnosti DES Vady DES Popis DES Kritika DES Útoky loková šifra NP-těžké problémy 1 u Levá polovina IP 32 L, 32 Li+ 32 LJ(i Registr C Posunutí SHL Tvorba klíčů K{ [Permutace PCl) 56 Permutační výber PC2| -c P^raco^^^Hŕ^^J 1S 28 Registr D no í POSUUUtí zs I SHL Pi Historie DES Popis DES Vlastnosti DES Kritika DES Vady DES Útoky Bloková šifra NP-težké problémy Registr C Posunutí SHL p, 2H 28 Tvorba klíčů Kj (Permutace P(7l) 56 Permutační výběr FCŽ\ -Q ^racovii^klíč^^^ 1S 28 Registr D 2-S Posunutí SHL p, Tvorba pracovních klíčů K, probíhá při šifrování tak, že klíč K o 56 bitech je podroben permutaci PC1 a poté je naplněn do dvou 28-bitových registrů C a D. Obsah registrů C, D je v každém kroku /, / = 0,1,..., 15 cyklicky posunut doleva o p, bitů. Historie DES Popis DES Vlastnosti DES Kritika DES Vady DES Útoky Bloková šifra NP-težké problémy Registr C Posunutí SHL p, 2H 28 Tvorba klíčů Kj (Permutace P(7l) 56 28 2-S Registr D Tvorba pracovních klíčů K, probíhá při šifrování tak, že klíč K o 56 bitech je podroben permutaci PC1 a poté je naplněn do dvou 28-bitových registrů C a D. Obsah registrů C, D je v každém kroku /, / = 0,1,..., 15 cyklicky posunut doleva o p, bitů. Posun pí je v krocích 0, 1, 8 a 15 jednobitový a ve zbývajících dvoubitový. Posunutí SHL ;-. Permutační \ ýběr PC2| | Pracovní klíč K i 1 Historie DES Popis DES Vlastnosti DES Kritika DES Vady DES Útoky Bloková šifra NP-težké problémy Registr C Posunutí SHL p, 2H 28 Tvorba klíčů Kj [Permutace P(7l) 56 28 2-S Registr D Posunutí SHL p, Tvorba pracovních klíčů K, probíhá při šifrování tak, že klíč K o 56 bitech je podroben permutaci PC1 a poté je naplněn do dvou 28-bitových registrů C a D. Obsah registrů C, D je v každém kroku /, / = 0,1,..., 15 cyklicky posunut doleva o p, bitů. Posun p j je v krocích 0, 1, 8 a 15 jednobitový a ve zbývajících dvoubitový. Výsledné 56-bitové zřetězení registrů C, D je podrobeno permutačnímu výběru PC2. Permutační \ ýběr PC2| | Pracovní klíč K i 1 Historie DES Popis DES Vlastnosti DES Kritika DES Vady DES Útoky Bloková šifra NP-težké problémy Registr C Posunutí SHL p, 2H Tvorba klíčů Kí ■K i (Permutace PCI j 56 Permutáciu výb ěr PC 1 | Pracovní klí č Kt j 1« 18 28 Registr D 2.S Posunutí SHL ;,. PC2 svůj vstup 56 bitů nejen permutuje, ale i redukuje na 48 bitů vynecháním některých bitů. Výstup z PC2 už tvoří pracovní klíč Kj. Klíče Kj lze vytvářet buď souběžně se z p raco vá ním otevře n é h o textu nebo předem. Historie DES Popis DES Vlastnosti DES Kritika DES Vady DES Útoky Bloková šifra NP-težké problémy Registr C Posunutí SHL p, 2H Tvorba klíčů Kí (Permutace PCI j 56 2.S Registr D Posunutí SHL Pi PC2 svůj vstup 56 bitů nejen permutuje, ale i redukuje na 48 bitů vynecháním některých bitů. Výstup z PC2 už tvoří pracovní klíč Kj. Klíče Kj lze vytvářet buď souběžně se z p raco vá ním otevře n é h o textu nebo předem. Postup formování klíčů Kj je takový, že v uvedených 16x48=768 bitech je každý bit klíče K obsažen 12 až 15-kráta objevuje se na různých pozicích. Permutační výb ěr PC I | Pracovní klí č Kt j I8 Historie DES Popis DES Vlastnosti DES Kritika DES Vady DES Útoky Bloková šifra NP-težké problémy Registr C 28 Posunutí SHL p, Tvorba klíčů Kí ■K i (Permutace PCI j 56 PC2 svůj vstup 56 bitů nejen permutuje, ale i redukuje na 48 bitů vynecháním některých bitů. 28 Registr D Posunutí SHL Pi Permutační výb ěr PC 1 | Pracovní klí č Kt 1 1« 18 Výstup z PC2 už tvoří pracovní klíč Kj. Klíče Kj lze vytvářet buď souběžně se z p raco vá ním otevře n é h o textu nebo předem. Postup formování klíčů Kj je takový, že v uvedených 16x48=768 bitech je každý bit klíče K obsažen 12 až 15-kráta objevuje se na různých pozicích. Tímto je popis šifrovací části blokového algoritmu uzavřen. Historie DES Popis DES Vlastnosti DES Kritika DES Vady DES Útoky Bloková šifra NP-težké problémy Filozofie algoritmu je taková, aby při dešifrování nemuselo být použito zcela jiné hardwarové schéma. Historie DES Popis DES Vlastnosti DES Kritika DES Vady DES Útoky Bloková šifra NP-težké problémy Filozofie algoritmu je taková, aby při dešifrování nemuselo být použito zcela jiné hardwarové schéma. Dešifrování M = DK(C) probíhá stejným postupem jako šifrování! Historie DES Popis DES Vlastnosti DES Kritika DES Vady DES Útoky Bloková šifra NP-težké problémy Filozofie algoritmu je taková, aby při dešifrování nemuselo být použito zcela jiné hardwarové schéma. Dešifrování M = DK(C) probíhá stejným postupem jako šifrování! Pouze pořadí výběru klíčů K, je obrácené - místo K0, ..., /C15 se používá pořadí /C15, Ku, ..., K2, Kí, K0. Historie DES Popis DES Vlastnosti DES Kritika DES Vady DES Útoky Bloková šifra NP-težké problémy Filozofie algoritmu je taková, aby při dešifrování nemuselo být použito zcela jiné hardwarové schéma. Dešifrování M = DK{C) probíhá stejným postupem jako šifrování! Pouze pořadí výběru klíčů K, je obrácené - místo K0, , ..., /C15 se používá pořadí /C15, Ku, ..., K2, Kí, K0. Vytváříme-li klíče postupně, pak ve výše uvedeném popisu se místo SHL musí použít SHR a tabulka posunů (0,1,2,2,2,2,2,2,1,2,2,2,2,2,2,1), jinak zůstane vše zachováno. Historie DES Popis DES Vlastnosti DES Kritika DES Vady DES Útoky Bloková šifra NP-težké problémy Filozofie algoritmu je taková, aby při dešifrování nemuselo být použito zcela jiné hardwarové schéma. Dešifrování M = DK{C) probíhá stejným postupem jako šifrování! Pouze pořadí výběru klíčů K, je obrácené - místo K0, , ..., /C15 se používá pořadí /C15, Ku, ..., K2, Kí, K0. Vytváříme-li klíče postupně, pak ve výše uvedeném popisu se místo SHL musí použít SHR a tabulka posunů (0,1,2,2,2,2,2,2,1,2,2,2,2,2,2,1), jinak zůstane vše zachováno. Tento princip zpracování (/_,, fí,) na (L/+1, fí/+1) se nazývá Feistelůvprincip podle dr. Horsta Feistela, kryptologa IBM a vynálezce šifrovacího algoritmu LUCIFER. Historie DES Vlastnosti DES Vady DES Popis DES Kritika DES Útoky Bloková šifra Bloková šifra VIII - Tabulka permutací IP PC1 PC2 P IP PC1 PC2 P 1 58 57 14 16 17 62 59 26 2 2 50 49 17 7 18 54 51 8 8 3 42 41 11 20 19 46 43 16 24 4 34 33 24 21 20 38 35 7 14 5 26 25 1 29 21 30 27 27 32 6 18 17 5 12 22 22 19 20 27 7 10 9 3 28 23 14 11 13 3 8 2 1 28 17 24 6 3 2 9 9 60 58 15 1 25 64 69 41 19 10 52 50 6 15 26 56 52 52 13 11 44 42 21 23 27 48 44 31 30 12 36 34 10 26 28 40 36 37 6 13 28 26 23 5 29 32 63 47 22 14 20 18 19 18 30 24 55 55 11 15 12 10 12 31 31 16 47 30 4 16 4 2 4 10 32 8 39 40 25 Historie DES Vlastnosti DES Vady DES Popis DES Kritika DES Útoky Bloková šifra Bloková šifra IX - Tabulka permutací IP PC1 PC2 IP PC1 PC2 33 57 31 51 49 61 29 34 49 23 45 50 53 21 35 41 15 33 51 45 13 36 33 7 48 52 37 5 37 25 62 44 53 29 28 38 17 54 49 54 21 20 39 9 46 39 55 13 12 40 1 38 56 56 5 4 41 59 30 34 57 63 42 51 22 53 58 55 43 43 14 46 59 47 44 35 6 42 60 39 45 27 61 50 61 31 46 19 53 36 62 23 47 11 45 29 63 15 48 3 37 32 64 7 Historie DES Vlastnosti DES Vady DES Popis DES Kritika DES Útoky Bloková šifra Bloková šifra X - Tabulka permutací S-box S1 X1 x6 0 1 2 3 4 5 (X2,X3,X4,X5) 6 7 8 9 10 11 12 13 14 15 0 0 14 4 13 1 2 15 11 8 3 10 6 12 5 9 0 7 0 1 0 15 7 4 14 2 13 1 10 6 12 11 9 5 3 8 1 0 4 1 14 8 13 6 2 11 15 12 9 7 3 10 5 0 1 1 15 12 8 2 4 9 1 7 5 11 3 14 10 0 6 13 S-box S2 X1 x6 0 1 2 3 4 5 (X2,X3,X4,X5) 6 7 8 9 10 11 12 13 14 15 0 0 15 1 8 14 6 11 3 4 9 7 2 13 12 0 5 10 0 1 3 13 4 7 15 2 8 14 12 0 1 10 6 9 11 5 1 0 0 14 7 11 10 4 13 1 5 8 12 6 9 3 2 15 1 1 13 8 10 1 3 15 4 2 11 6 7 12 0 5 14 9 Historie DES Popis DES Vlastnosti DES Kritika DES Vady DES Útoky loková šifra NP-těžké problémy S-box S3 (X2,X3,X4,X5) X1 x6 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 0 0 10 0 9 14 6 3 15 5 1 13 12 7 11 4 2 8 0 1 13 7 0 9 3 4 6 10 2 8 5 14 12 11 15 1 1 0 13 6 4 9 8 15 3 0 11 1 2 12 5 10 14 7 1 1 1 10 13 0 6 9 8 7 4 15 14 3 11 5 2 12 S-box S4 (X2,X3,X4,X5) X1 x6 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 0 0 7 13 14 3 0 6 9 10 1 2 8 5 11 12 4 15 0 1 13 8 11 5 6 15 0 3 4 7 2 12 1 10 14 9 1 0 10 6 9 0 12 11 7 13 15 1 3 14 5 2 8 4 1 1 3 15 0 6 10 1 13 8 9 4 5 11 12 7 2 14 □ o1 - ► = s *0 O* Historie DES Popis DES Vlastnosti DES Kritika DES Vady DES Útoky loková šifra NP-těžké problémy S-box S5 X1 x6 0 1 2 3 4 5 (X2,X3,X4,X5) 6 7 8 9 10 11 12 13 14 15 0 0 2 12 4 1 7 10 11 6 8 5 3 15 13 0 14 9 0 1 14 11 2 12 4 7 13 1 5 0 15 10 3 9 8 6 1 0 4 2 1 11 10 13 7 8 15 9 12 5 6 3 0 14 1 1 11 8 12 7 1 14 2 13 6 15 0 9 10 4 5 3 S-box S6 X1 x6 0 1 2 3 4 5 (X2,X3,X4,X5) 6 7 8 9 10 11 12 13 14 15 0 0 12 1 10 15 9 2 6 8 0 13 3 4 14 7 5 11 0 1 10 15 4 2 7 12 9 5 6 1 13 14 0 11 3 8 1 0 9 14 15 5 2 8 12 3 7 0 4 10 1 13 11 6 1 1 4 3 2 12 9 5 15 10 11 14 1 7 6 0 8 13 Historie DES Popis DES Vlastnosti DES Kritika DES Vady DES Útoky loková šifra NP-těžké problémy S-box S7 X1 x6 0 1 2 3 4 5 (X2,X3,X4,X5) 6 7 8 9 10 11 12 13 14 15 0 0 4 11 2 14 15 0 8 13 3 12 9 7 5 10 6 1 0 1 13 0 11 7 4 9 1 10 14 3 5 12 2 15 8 6 1 0 1 11 4 13 12 3 7 14 10 15 6 8 0 5 9 2 1 1 6 11 13 8 1 4 10 7 9 5 0 15 14 2 3 12 S-box S8 x6 0 1 2 3 4 5 (X2,X3,X4,X5) 6 7 8 9 10 11 12 13 14 15 0 0 13 2 8 4 6 15 11 1 10 9 3 14 5 0 12 7 0 1 1 15 13 8 10 3 7 4 12 5 6 11 0 14 9 2 1 0 7 11 4 1 9 12 14 2 0 6 10 13 15 3 5 8 1 1 2 1 14 7 4 10 8 13 15 12 9 0 3 5 6 11 V současné době neexistuje rychlý (tj. pracující v polynomiální době) algoritmus pro žádný NP-těžký problém, a pokud NP^P, takový algoritmus neexistuje. Je tedy přirozený nápad založit kryptosystém na NP-těžkém problému, aby rozbití šifrovacího systému bylo ekvivalentní nalezení rychlého algoritmu, který by řešil NP-těžký problém. V současné době neexistuje rychlý (tj. pracující v polynomiální době) algoritmus pro žádný NP-těžký problém, a pokud NP^P, takový algoritmus neexistuje. Je tedy přirozený nápad založit kryptosystém na NP-těžkém problému, aby rozbití šifrovacího systému bylo ekvivalentní nalezení rychlého algoritmu, který by řešil NP-těžký problém. To je mj. základní idea pro DES. Uvažme následující výpočetní problém. Algebraické rovnice nad Z2 Vstup: Polynomy p^,...,pkv proměnných x1,..., xn nad Z2 Otázka: Mají polynomy společný nulový bod (x1,____xn) v Historie DES Vlastnosti DES Vady DES Popis DES Kritika DES Útoky Například následující tři rovnice x-| x4x6 + X2X4X5 - 1 =0 x-i x2 + x2x3 + X3X4 - 1 =0 x1 x3 + X4X5 + x1 x6 - 1 =0 mají společné řešení (1,0,1,1,1,1). Ačkoliv výše uvedený problém je lehký pro malá k a n, se zvětšováním těchto parametrů se obtížnost vyřešení neustále zvyšuje. Historie DES Popis DES Vlastnosti DES Kritika DES Vady DES Útoky NP-težké problémy Například následující tři rovnice x-| x4x6 + X2X4X5 - 1 =0 x-i x2 + x2x3 + X3X4 - 1 =0 x1 x3 + X4X5 + x1 x6 - 1 =0 mají společné řešení (1,0,1,1,1,1). Ačkoliv výše uvedený problém je lehký pro malá k a n, se zvětšováním těchto parametrů se obtížnost vyřešení neustále zvyšuje. Lze navíc dokázat, že platí Věta 2.1 Problém rozhodnout, zda algebraický systém rovnic modulo 2 má řešení, je NP-těžký. ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ U I J PT^^^^^^^ Výše uvedená věta byla použita při tvorbě šifrovacího systému LUCIFER navrženého IBM a popsaného H. Feistelem v roce 1973. Výše uvedená věta byla použita při tvorbě šifrovacího systému LUCIFER navrženého IBM a popsaného H. Feistelem v roce 1973. Systém pracuje následovně. Bez újmy na obecnosti lze předpokládat, že délka zprávy M je 2n (pokud by byla větší, použijeme rozdělení do bloků délky 2n a na každý blok aplikujeme šifrovací proceduru). Výše uvedená věta byla použita při tvorbě šifrovacího systému LUCIFER navrženého IBM a popsaného H. Feistelem v roce 1973. Systém pracuje následovně. Bez újmy na obecnosti lze předpokládat, že délka zprávy M je 2n (pokud by byla větší, použijeme rozdělení do bloků délky 2n a na každý blok aplikujeme šifrovací proceduru). Zprávu M rozdělíme na dva stejné bloky délky n, tj. M = (M0, M1). Klíč K bude vektor k, který určuje podklíče k-i, k2,..., kd_-|. Pro 2 < / < d, rekurzivně definujeme _M/ = M/.2 + f(k|_1,M/.1),_(^3) kde f je nějaká libovolná pevně zvolená nelineární transformace a počítáme modulo 2. <*> <*> = Historie DES Popis DES Vlastnosti DES Kritika DES Vady DES Útoky NP-těžké problémy Závěrečný kryptogram C je určen vztahem C = e(M,K) = (Md_uMd). (2.4) Závěrečný kryptogram C je určen vztahem _C = e(M, K) = (Md_,,Md)._(Z4) Zprávu M lze získat z kryptogramu C opačným postupem -všechno, co musí příjemce zprávy provést, je obrácení pořadí 2.3. Závěrečný kryptogram C je určen vztahem _C = e(M, K) = (Md_,,Md)._(Z4) Zprávu M lze získat z kryptogramu C opačným postupem -všechno, co musí příjemce zprávy provést, je obrácení pořadí 2.3. Tedy _M/-2 = M/ + f(ki_l7M/_1)7_(^5) d > i > 2, až dospějeme k původní zprávě M = (M0, M1). Historie DES Popis DES Vlastnosti DES Kritika DES Vady DES Útoky NP-težké problémy Závěrečný kryptogram C je určen vztahem _C = e(M, K) = (Md_,,Md)._(Z4) Zprávu M lze získat z kryptogramu C opačným postupem -všechno, co musí příjemce zprávy provést, je obrácení pořadí 2.3. Tedy _M/-2 = M/ + f(ki_1,M/_1),_(^5) d > i > 2, až dospějeme k původní zprávě M = (M0, M1). Za předpokladu, že příjemce zná tvar funkce f a hodnoty šifrovacích klíčů, je dešifrování kryptogramu právě tak těžké jako jeho zašifrování. <*><*><*> == Historie DES Popis DES Vlastnosti DES Kritika DES Vady DES Útoky NP-těžké problémy Poznamenejme, že díky (2.5) funkce f nemusí být invertibilní. Historie DES Popis DES Vlastnosti DES Kritika DES Vady DES Útoky NP-težké problémy Poznamenejme, že díky (2.5) funkce f nemusí být invertibilní. V typické situaci, Mr. X může znát tvar funkce f, ale nesmí znát klíče. Zda je pak schopen získat klíče pomocí luštění s pomocí volby, závisí na tvaru f. Historie DES Popis DES Vlastnosti DES Kritika DES Vady DES Útoky NP-težké problémy Poznamenejme, že díky (2.5) funkce f nemusí být invertibilní. V typické situaci, Mr. X může znát tvar funkce f, ale nesmí znát klíče. Zda je pak schopen získat klíče pomocí luštění s pomocí volby, závisí na tvaru f. Je-li f lineární transformace, je určení klíče výpočetně snadné. Avšak, v případě, že f je nelineární transformace, např. kde každé p, je polynom v proměnných (x-|,..., xn; y-|,..., yn) pak určení klíče ze znalosti M a C se redukuje na problém vyřešení algebraických rovnic pro klíčové proměnné. Jak jsme viděli, to je NP-těžký problém. Historie DES Popis DES Vlastnosti DES Kritika DES Vady DES Útoky NP-težké problémy Jak jsme viděli, to je NP-těžký problém. Dosáhli jsme tedy našeho cíle: nalezení kryptosystému, který má lehký proces šifrování a dešifrování, ale který zároveň vynucuje po Mr. X, aby při hledání klíče pomocí luštění s pomocí volby řešil NP-těžký problém. Za předpokladu, že NP-těžké problémy jsou nezvládnutelné, je bezpečnost systému zajištěna. Historie DES Popis DES Vlastnosti DES Kritika DES Vady DES Útoky NP-težké problémy Jak jsme viděli, to je NP-těžký problém. Dosáhli jsme tedy našeho cíle: nalezení kryptosystému, který má lehký proces šifrování a dešifrování, ale který zároveň vynucuje po Mr. X, aby při hledání klíče pomocí luštění s pomocí volby řešil NP-těžký problém. Za předpokladu, že NP-těžké problémy jsou nezvládnutelné, je bezpečnost systému zajištěna. Je zde však následující problém. Klasická teorie složitosti se téměř úplně zabývá s nejhorším možným chováním. Ačkoliv tedy určení klíče je těžký problém, nemáme jistotu, že neexistuje velký počet "snadných vstupů". • Popis vlivu • Režimy činnosti DES Q Vlastnosti DES Q Útoky na DES Vlastnosti DES Kritika DES Vady DES Útoky Režimy činnosti DES Cílem počáteční permutace /Pje provést rozprostření vlivu bitů z jedněch bajtů otevřeného textu M do ostatních. Vlastnosti DES Kritika DES Vady DES Útoky Režimy činnosti DES Cílem počáteční permutace /Pje provést rozprostření vlivu bitů z jedněch bajtů otevřeného textu M do ostatních. Permutace /P~1 je zde proto, aby se v dešifrovacím procesu napravil účinek IP. Kryptograficky je tato permutace nevýznamná a v rozborech je zanedbávaná. Vlastnosti DES Kritika DES Vady DES Útoky Režimy činnosti DES Cílem počáteční permutace IP je provést rozprostření vlivu bitů z jedněch bajtů otevřeného textu M do ostatních. Permutace /P~1 je zde proto, aby se v dešifrovacím procesu napravil účinek IP. Kryptograficky je tato permutace nevýznamná a v rozborech je zanedbávaná. Skutečně, při útoku se znalostí otevřeného textu M, tj. při znalosti odpovídajících si dvojic M otevřeného textu a C šifrového textu, si vliv permutace IP na otevřený i šifrový text snadno eliminujeme. Uvažujeme-li IP~\M) a /P(C), je to totéž, jako by schéma tyto permutace vůbec neobsahovalo. Vlastnosti DES Kritika DES Vady DES Útoky Režimy činnosti DES Cílem počáteční permutace IP je provést rozprostření vlivu bitů z jedněch bajtů otevřeného textu M do ostatních. Permutace /P~1 je zde proto, aby se v dešifrovacím procesu napravil účinek IP. Kryptograficky je tato permutace nevýznamná a v rozborech je zanedbávaná. Skutečně, při útoku se znalostí otevřeného textu M, tj. při znalosti odpovídajících si dvojic M otevřeného textu a C šifrového textu, si vliv permutace IP na otevřený i šifrový text snadno eliminujeme. Uvažujeme-li IP~\M) a /P(C), je to totéž, jako by schéma tyto permutace vůbec neobsahovalo. Také závěrečná výměna slov L a R je zde jen proto, aby dešifrovací proces byl shodný se šifrovacím, tj. pro možnost zahájení rekonstrukce předchozích dvojic (/_, R) z následujících. < a ► <*>< ==►<==► == Historie DES Popis DES Vlastnosti DES Kritika DES Vady DES Útoky Režimy činnosti DES Výběrové statistické testy pak mohou potvrdit jen některé vlastnosti, ale nemohou vyloučit nekonečně mnoho dalších. To se týká například vlastnosti komplementárnosti, kterou budeme diskutovat dále. Jak na ni máme přijít statistickými testy, když nevíme, že vůbec existuje? Historie DES Popis DES Vlastnosti DES Kritika DES Vady DES Útoky Režimy činnosti DES Výberové statistické testy pak mohou potvrdit jen některé vlastnosti, ale nemohou vyloučit nekonečně mnoho dalších. To se týká například vlastnosti komplementárnosti, kterou budeme diskutovat dále. Jak na ni máme přijít statistickými testy, když nevíme, že vůbec existuje? Dalšími požadovanými vlastnostmi jsou konfuze a difúze. Historie DES Popis DES Vlastnosti DES Kritika DES Vady DES Útoky Režimy činnosti DES Výběrové statistické testy pak mohou potvrdit jen některé vlastnosti, ale nemohou vyloučit nekonečně mnoho dalších. To se týká například vlastnosti komplementárnosti, kterou budeme diskutovat dále. Jak na ni máme přijít statistickými testy, když nevíme, že vůbec existuje? Dalšími požadovanými vlastnostmi jsou konfúze a difúze. Jedná se o to, aby měl každý bit klíče K a otevřeného textu M vliv na každý bit šifrového textu C a aby tento vliv byl velmi komplikovaný. Historie DES Popis DES Vlastnosti DES Kritika DES Vady DES Útoky Režimy činnosti DES Výberové statistické testy pak mohou potvrdit jen některé vlastnosti, ale nemohou vyloučit nekonečně mnoho dalších. To se týká například vlastnosti komplementárnosti, kterou budeme diskutovat dále. Jak na ni máme přijít statistickými testy, když nevíme, že vůbec existuje? Dalšími požadovanými vlastnostmi jsou konfúze a difúze. Jedná se o to, aby měl každý bit klíče K a otevřeného textu M vliv na každý bit šifrového textu C a aby tento vliv byl velmi komplikovaný. Na složitost zde pak mají největší vliv S-boxy. Historie DES Popis DES Vlastnosti DES Kritika DES Vady DES Útoky Režimy činnosti DES Výberové statistické testy pak mohou potvrdit jen některé vlastnosti, ale nemohou vyloučit nekonečně mnoho dalších. To se týká například vlastnosti komplementárnosti, kterou budeme diskutovat dále. Jak na ni máme přijít statistickými testy, když nevíme, že vůbec existuje? Dalšími požadovanými vlastnostmi jsou konfúze a difúze. Jedná se o to, aby měl každý bit klíče K a otevřeného textu M vliv na každý bit šifrového textu C a aby tento vliv byl velmi komplikovaný. Na složitost zde pak mají největší vliv S-boxy. Každý výstupní bit S-boxu je nelineární funkcí všech vstupních bitů (při vyjádření operacemi 0 a A). <*> i ^ Historie DES Vlastnosti DES Vady DES Popis DES Kritika DES Útoky Režimy činnosti DES Popis vlivu V V případě, že by S-boxy realizovaly lineární funkci, celé schéma by realizovalo pouze lineární funkci. Historie DES Popis DES Vlastnosti DES Kritika DES Vady DES Útoky Režimy činnosti DES V případě, že by S-boxy realizovaly lineární funkci, celé schéma by realizovalo pouze lineární funkci. Potom by ovšem všech 64 bitů šifrového textu C bylo jen různými lineárními kombinacemi bitů otevřeného textu M a klíče K. Ale takovéto schéma bychom mohli okamžitě rozluštit řešením soustavy lineárních rovnic. Historie DES Popis DES Vlastnosti DES Kritika DES Vady DES Útoky Režimy činnosti DES V případě, že by S-boxy realizovaly lineární funkci, celé schéma by realizovalo pouze lineární funkci. Potom by ovšem všech 64 bitů šifrového textu C bylo jen různými lineárními kombinacemi bitů otevřeného textu M a klíče K. Ale takovéto schéma bychom mohli okamžitě rozluštit řešením soustavy lineárních rovnic. Nelineárním vlastnostem se při studiu DES věnovala velká pozornost, neboť zajišťují požadovanou konfúzi. Bohužel, kritéria návrhu S-boxů zůstávají doposud tajná a přitom právě zde bylo nalezeno mnoho slabin. Historie DES Popis DES Vlastnosti DES Kritika DES Vady DES Útoky Režimy činnosti DES V případě, že by S-boxy realizovaly lineární funkci, celé schéma by realizovalo pouze lineární funkci. Potom by ovšem všech 64 bitů šifrového textu C bylo jen různými lineárními kombinacemi bitů otevřeného textu M a klíče K. Ale takovéto schéma bychom mohli okamžitě rozluštit řešením soustavy lineárních rovnic. Nelineárním vlastnostem se při studiu DES věnovala velká pozornost, neboť zajišťují požadovanou konfúzi. Bohužel, kritéria návrhu S-boxů zůstávají doposud tajná a přitom právě zde bylo nalezeno mnoho slabin. U DES byly stanoveny 4 základní módy činnosti, které byly odvozeny od různých potřeb. Základem je vlastní blokový algoritmus, tj. zobrazení EK : X X, kde X = {0,1 }{1'2'''''64^ je množina všech 64-bitoyýcb bloků. ^ Historie DES Popis DES Vlastnosti DES Kritika DES Vady DES Útoky Režimy činnosti DES Tento algoritmus je zároveň prvním módem. O ECB - Elektronická kódová kniha, píšeme _C=EK(M),_(3/1) kde M je otevřený text a C je šifrový text. Jedná se skutečně o kódovou knihu, neboť při opakovaných blocích otevřeného textu M jsou šifrové zprávy C stejné. Proto by bylo možné při šifrování zpráv tímto módem z operativních informací domýšlet část zašifrovaného obsahu bez nutnosti jejich luštění. Historie DES Popis DES Vlastnosti DES Kritika DES Vady DES Útoky Režimy činnosti DES Tento algoritmus je zároveň prvním módem. O ECB - Elektronická kódová kniha, píšeme _C=EK(M),_(3/1) kde M je otevřený text a C je šifrový text. Jedná se skutečně o kódovou knihu, neboť při opakovaných blocích otevřeného textu M jsou šifrové zprávy C stejné. Proto by bylo možné při šifrování zpráv tímto módem z operativních informací domýšlet část zašifrovaného obsahu bez nutnosti jejich luštění. Formalizovane části zpráv by bylo možné opakovat v zašifrovaném tvaru (platební příkazy, standardní hlášení). Proto se tento mód nepoužívá k šifrování zpráv, ale jen k vir r r \ \ r v o šifrovaní khcu. Historie DES Popis DES Vlastnosti DES Kritika DES Vady DES Útoky Režimy činnosti DES O CBC - Zřetězení šifrového textu, symbolicky zapsáno jako _Cn = EK(Mn®Cn- , Historie DES Popis DES Vlastnosti DES Kritika DES Vady DES Útoky Krátkýklíč Konference Slabosti DES 2. konference Doporučovali rozšířit klíč na 128 nebo 256 bitů nebo šifrovat víckrát za sebou s použitím nezávislých klíčů, tedy šifrový text C=EKJEK2{...EKm{M)...)). Historie DES Popis DES Vlastnosti DES Kritika DES Vady DES Útoky Krátkýklíč Konference Slabosti DES 2. konference NBS reagoval na jejich argumenty svoláním pracovní konference, která se konala 30.-31. srpna 1976 a byla zaměřena na to, zda předpovědi a tvrzení Diffieho a Hellmana jsou realistické. Historie DES Popis DES Vlastnosti DES Kritika DES Vady DES Útoky Krátkýklíč Konference Slabosti DES 2. konference NBS reagoval na jejich argumenty svoláním pracovní konference, která se konala 30.-31. srpna 1976 a byla zaměřena na to, zda předpovědi a tvrzení Diffieho a Hellmana jsou realistické. Závěr z konference byl, že tehdejší technologií by jejich stroj nebylo možné sestrojit, a pokud se ho sestrojit podaří, nebude to dříve než po roce 1990 (a to asi za 72 000 000 $). Historie DES Popis DES Vlastnosti DES Kritika DES Vady DES Útoky Krátkýklíč Konference Slabosti DES 2. konference NBS reagoval na jejich argumenty svoláním pracovní konference, která se konala 30.-31. srpna 1976 a byla zaměřena na to, zda předpovědi a tvrzení Diffieho a Hellmana jsou realistické. Závěr z konference byl, že tehdejší technologií by jejich stroj nebylo možné sestrojit, a pokud se ho sestrojit podaří, nebude to dříve než po roce 1990 (a to asi za 72 000 000 $). Proti zvětšení klíče bylo argumentováno tím, že by to vedlo k prodražení čipů, horším podmínkám vývozu a že to není nezbytné ani pro zamýšlené aplikace, ani pro uvažovanou životnost schématu (10-15 let). Historie DES Popis DES Vlastnosti DES Kritika DES Vady DES Útoky Krátkýklíč Konference Slabosti DES 2. konference Diffie a Hellman na to odpověděli článkem "Exhaustive Cryptoanalysis of the NBS Data Encryption Standard' (1977), v němž vyčerpávajícím způsobem a podloženými argumenty dokazovali, že jejich odhady jsou správné {dnes víme, že měli pravdu). Historie DES Popis DES Vlastnosti DES Kritika DES Vady DES Útoky Krátkýklíč Konference Slabosti DES 2. konference Diffie a Hellman na to odpověděli článkem "Exhaustive Cryptoanalysis of the NBS Data Encryption Standard' (1977), v němž vyčerpávajícím způsobem a podloženými argumenty dokazovali, že jejich odhady jsou správné {dnes víme, že měli pravdu). Mezitím i interní studie IBM odhadla, že by takový stroj mohl být sestrojen do roku 1981 a za cenu 200 000 000 $, tedy v rámci jejich tolerance. Historie DES Popis DES Vlastnosti DES Kritika DES Vady DES Útoky Krátkýklíč Konference Slabosti DES 2. konference Diffie a Hellman na to odpověděli článkem "Exhaustive Cryptoanalysis of the NBS Data Encryption Standard' (1977), v němž vyčerpávajícím způsobem a podloženými argumenty dokazovali, že jejich odhady jsou správné {dnes víme, že měli pravdu). Mezitím i interní studie IBM odhadla, že by takový stroj mohl být sestrojen do roku 1981 a za cenu 200 000 000 $, tedy v rámci jejich tolerance. V roce 1997 byla agenturou RSA vypsána kryptoanalytická soutěž s cílem prolomit šifru DES se znalostí začátku otevřeného textu a neznámým klíčem o délce 56 bitů. Historie DES Popis DES Vlastnosti DES Kritika DES Vady DES Útoky Krátkýklíč Konference Slabosti DES 2. konference Diffie a Hellman na to odpověděli článkem "Exhaustive Cryptoanalysis of the NBS Data Encryption Standard' (1977), v němž vyčerpávajícím způsobem a podloženými argumenty dokazovali, že jejich odhady jsou správné {dnes víme, že měli pravdu). Mezitím i interní studie IBM odhadla, že by takový stroj mohl být sestrojen do roku 1981 a za cenu 200 000 000 $, tedy v rámci jejich tolerance. V roce 1997 byla agenturou RSA vypsána kryptoanalytická soutěž s cílem prolomit šifru DES se znalostí začátku otevřeného textu a neznámým klíčem o délce 56 bitů. Vítězem se stal řešitelský tým DES challenge pod vedením R Verbena. Historie DES Popis DES Vlastnosti DES Kritika DES Vady DES Útoky Krátkýklíč Konference Slabosti DES 2. konference Využil distribuovaného výpočtu a postupu, který definovali Diffie a Hellman o 24 let dříve. Historie DES Popis DES Vlastnosti DES Kritika DES Vady DES Útoky Krátkýklíč Konference Slabosti DES 2. konference Využil distribuovaného výpočtu a postupu, který definovali Diffie a Hellman o 24 let dříve. S výpočetním výkonem roku 1999 stačilo k prolomení šifry méně než 24 hodin. Historie DES Popis DES Vlastnosti DES Kritika DES Vady DES Útoky Krátkýklíč Konference Slabosti DES 2. konference Využil distribuovaného výpočtu a postupu, který definovali Diffie a Hellman o 24 let dříve. S výpočetním výkonem roku 1999 stačilo k prolomení šifry méně než 24 hodin. Na konci roku 1999 bylo doporučeno, aby se přešlo z DES na její vylepšenou verzi 3DES triple DES; trojitý DES). Historie DES Popis DES Vlastnosti DES Kritika DES Vady DES Útoky Krátkýklíč Konference Slabosti DES 2. konference Využil distribuovaného výpočtu a postupu, který definovali Diffie a Hellman o 24 let dříve. S výpočetním výkonem roku 1999 stačilo k prolomení šifry méně než 24 hodin. Na konci roku 1999 bylo doporučeno, aby se přešlo z DES na její vylepšenou verzi 3DES triple DES; trojitý DES). 3DES je trojnásobná aplikace klíčem. Klíč šifry 3DES je tedy 168 bitů dlouhý. Historie DES Vlastnosti DES Vady DES „.....,„ Popis DES Kritika DES Útoky Slabostl Konference 2. konference Komplementárnost a pracovní bloky I Protože Diffie, Hellman a dalších pět jejich kolegů nesouhlasili s tím, že IBM a NSA utajují výsledky svého zkoumání bezpečnosti DES a návrhová kritéria, zorganizovali během srpna 1976 vlastní krátké studium DESu "Results of an initial attempt to cryptoanalyze the NBS Data Encryption Standard' (1976). Historie DES Vlastnosti DES Vady DES „.....,„ Popis DES Kritika DES Útoky Slabostl Konference 2. konference Komplementárnost a pracovní bloky I Protože Diffie, Hellman a dalších pět jejich kolegů nesouhlasili s tím, že IBM a NSA utajují výsledky svého zkoumání bezpečnosti DES a návrhová kritéria, zorganizovali během srpna 1976 vlastní krátké studium DESu "Results of an initial attempt to cryptoanalyze the NBS Data Encryption Standard' (1976). Z něho vyplynuly další závažné slabosti DES: vlastnost komplementárnosti, určité pravidelnosti v S-boxech a jejich dostatečná nelinearita. Protože Diffie, Hellman a dalších pět jejich kolegů nesouhlasili s tím, že IBM a NSA utajují výsledky svého zkoumání bezpečnosti DES a návrhová kritéria, zorganizovali během srpna 1976 vlastní krátké studium DESu "Results ofan initial attempt to cryptoanalyze the NBS Data Encryption Standarď (1976). Z něho vyplynuly další závažné slabosti DES: vlastnost komplementárnosti, určité pravidelnosti v S-boxech a jejich dostatečná nelinearita. Poukazovali na to, že veřejný standard by měl mít i veřejná návrhová kritéria. V opačném případě to budí nedůvěru. Těm, kdo návrhová kritéria znají, umožňuje využít jejich slabosti k luštění, a jsou tedy proti ostatním zvýhodněni. Historie DES Vlastnosti DES Vady DES „.....,„ Popis DES Kritika DES Útoky Slabostl Konference 2. konference Komplementárnost a pracovní bloky II Mohlo by jít buď o osoby, které se k těmto tajným informacím dostanou neoprávněně (např. cizí tajné služby), nebo o samotné ochránce (IBM, NSA). To by u veřejného standardu nemělo být. Historie DES Vlastnosti DES Vady DES „.....,„ Popis DES Kritika DES Útoky Slabostl Konference 2. konference Komplementárnost a pracovní bloky II Mohlo by jít buď o osoby, které se k těmto tajným informacím dostanou neoprávněně (např. cizí tajné služby), nebo o samotné ochránce (IBM, NSA). To by u veřejného standardu nemělo být. Účastníci studia se domnívali, že NSA si ve skutečnosti nepřeje silný standard, aby jej mohla snadněji luštit. Historie DES Vlastnosti DES Vady DES „.....,„ Popis DES Kritika DES Útoky Slabostl Konference 2. konference Komplementárnost a pracovní bloky II Mohlo by jít buď o osoby, které se k těmto tajným informacím dostanou neoprávněně (např. cizí tajné služby), nebo o samotné ochránce (IBM, NSA). To by u veřejného standardu nemělo být. Účastníci studia se domnívali, že NSA si ve skutečnosti nepřeje silný standard, aby jej mohla snadněji luštit. Nesouhlasili s tím, že by DES měl být odolný jen proti 'luštění se znalostí otevřeného textu", což NBS do požadavků dal, ale i proti luštění s možností volby otevřeného textď, což původně požadováno nebylo. Historie DES Popis DES Vlastnosti DES Kritika DES Vady DES Útoky Krátkýklíč Konference Slabosti DES 2. konference Nato NBS zorganizoval pracovní setkání matematiků v září 1976 k analýze kvality DES a možnosti, že by mohl obsahovat "trojského koně" {"Report of the workshop on cryptography on support of computer security). Historie DES Popis DES Vlastnosti DES Kritika DES Vady DES Útoky Krátkýklíč Konference Slabosti DES 2. konference Nato NBS zorganizoval pracovní setkání matematiků v září 1976 k analýze kvality DES a možnosti, že by mohl obsahovat "trojského koně" {"Report of the workshop on cryptography on support of computer security). Přestože jiní účastníci na různé nedostatky také upozorňovali, fakticky nebyla předložena žádná konkrétní metoda na jejich přímé využití. Představitel IBM na konferenci k problému "trojského koně" dokonce prohlásil: "Musíte nám důvěřovat, my všichni jsme dobří skauti". Také NBS a NSA prohlásily, že neznají žádné metody, jak využít objevené kvazilinearity. Historie DES Popis DES Vlastnosti DES Kritika DES Vady DES Útoky Krátkýklíč Konference Slabosti DES 2. konference Nato NBS zorganizoval pracovní setkání matematiků v září 1976 k analýze kvality DES a možnosti, že by mohl obsahovat "trojského koně" {"Report ofthe workshop on cryptography on support of computer security). Přestože jiní účastníci na různé nedostatky také upozorňovali, fakticky nebyla předložena žádná konkrétní metoda na jejich přímé využití. Představitel IBM na konferenci k problému "trojského koně" dokonce prohlásil: "Musíte nám důvěřovat, my všichni jsme dobří skauti". Také NBS a NSA prohlásily, že neznají žádné metody, jak využít objevené kvazilinearity. Bezprostředně po skončení konferencí se NBS rozhodl ponechat DES beze změn. Toto rozhodnutí způsobil zejména tlak průmyslu, který už potřeboval konečný verdikt, aby mohl vyrábět čipy. Historie DES Popis DES Vlastnosti DES Kritika DES Vady DES Útoky Krátkýklíč Konference Slabosti DES 2. konference Změny v DES by tento proces nejméně o rok oddálily. Aféra kolem utajovaní však zanechala na NSA nesmazatelný stín podezření. Historie DES Popis DES Vlastnosti DES Kritika DES Vady DES Útoky Krátkýklíč Konference Slabosti DES 2. konference Změny v DES by tento proces nejméně o rok oddálily. Aféra kolem utajovaní však zanechala na NSA nesmazatelný stín podezření. Zvláště když vyšetřovací komise Senátu USA potvrdila, že NSA přesvědčila IBM o vhodnosti redukce délky klíče. Původně totiž IBM pro své potřeby používala 128-bitový klíč. Historie DES Popis DES Vlastnosti DES Kritika DES Vady DES Útoky Krátkýklíč Konference Slabosti DES 2. konference Změny v DES by tento proces nejméně o rok oddálily. Aféra kolem utajovaní však zanechala na NSA nesmazatelný stín podezření. Zvláště když vyšetřovací komise Senátu USA potvrdila, že NSA přesvědčila IBM o vhodnosti redukce délky klíče. Původně totiž IBM pro své potřeby používala 128-bitový klíč. V roce 1978 prohlásil Davis na podporu DES následující: "Každý, kdo si zakoupí kryptografické zařízení pracující na základě DES, může být ujištěn o specifické úrovni bezpečnosti dat: totiž je potřeba použít 255 pokusů a metodu prověření všech možností, aby bylo možno získat klíč pro použitý šifrovací algoritmus." O Skryté vady DES • Komplementárnost • Nevhodný návrh S-boxů • Slabé a poloslabé klíče Historie DES Popis DES Vlastnosti DES Kritika DES Vady DES Útoky Komplementárnost S-boxy Slabé klíče Objevená vlastnost komplementárnosti spočívá v tom, že ze vztahu C = E k (M) plyne non C = Enon /c(non M), (5.1) kde non označuje negaci bit po bitu. Historie DES Popis DES Vlastnosti DES Kritika DES Vady DES Útoky Komplementárnost S-boxy Slabé klíče Objevená vlastnost komplementárnosti spočívá v tom, že ze vztahu C = E k (M) plyne non C = Enon /c(non M), (5.1) kde non označuje negaci bit po bitu. To je pravidelnost, která by se v takovémto prípade rozhodně neměla objevit. Autoři rozboru její odhalení považovali diplomaticky řečeno za velmi znepokojující. Historie DES Popis DES Vlastnosti DES Kritika DES Vady DES Útoky Komplementárnost S-boxy Slabé klíče Objevená vlastnost komplementárnosti spočívá v tom, že ze vztahu C = E k (M) plyne non C = Enon /c(non M), (5.1) kde non označuje negaci bit po bitu. To je pravidelnost, která by se v takovémto prípade rozhodně neměla objevit. Autoři rozboru její odhalení považovali diplomaticky řečeno za velmi znepokojující. Tvůrcům schématu tato vlastnost pravděpodobně unikla. Je umožněna tím, že negace klíče i vstupu se při jejich součtu mod 2 ve funkci f zruší: K) = ř(non /?, non K). (5.2) Historie DES Popis DES Vlastnosti DES Kritika DES Vady DES Útoky Komplementárnost S-boxy Slabé klíče Totiž označíme-li R'0 = non Fľ0, Ľ0 = non L0 a šifrujeme-li zprávu M' = (Lq, fíg) klíčem /C; = non K obdržíme postupně: M' = non M. Historie DES Popis DES Vlastnosti DES Kritika DES Vady DES Útoky Komplementárnost S-boxy Slabé klíče Totiž označíme-li R'Q = non R0, Ľ0 = non L0 a šifrujeme-li zprávu M' = (ľq, R'0) klíčem K' = non K obdržíme postupně: M' = non M. Pokud (Ľh R',) = non (L,-, R,), pak , ) = non (L/+1, /'), protože (Ľi+vR'i+1) = (R>i,Ľi®f(R>i,K;)) = (non f?/, (non /_/) 0 ŕ(non f?/, non K/)) = (non f?/, (non /_/) 0 ŕ(f?/, K/)) = (non f?/, non fľ/+-|) = non(L/+1j/?+1/). Speciálně tedy (Ľ16, f?^6) = non (L16, f?16) tj. non E k (M) = Enon /c(non M). Historie DES Popis DES Vlastnosti DES Kritika DES Vady DES Útoky Komplementárnost S-boxy Slabé klíče Totiž označíme-li R'Q = non R0, Ľ0 = non L0 a šifrujeme-li zprávu M' = (ľq, R'0) klíčem K' = non K obdržíme postupně: M' = non M. Pokud (Ľh R',) = non (L,-, f?,), pak , ) = non (L/+1, /'), protože (Ui+vR'i+1) = (R>i,Ui®f(R>i,K;)) = (non /?/, (non /_/) 0 ř(non /?/, non K/)) = (non Rh (non /_/) 0 ř(fř/, K/)) = (non /?/, non fř/+i) = non(L/+1j/?+1/). Speciálně tedy (/_'16, fí^6) = non (L16, fř16) tj. non Ek(M) = Enon /c(non M). To se dá pak využít i k luštění v případě, že hledáme klíč K a máme k dispozici dvojice (M, C-i) a (non M, C2), které vznikly při šifrování tímto neznámým klíčem. i Historie DES Popis DES Vlastnosti DES Kritika DES Vady DES Útoky Komplementárnost S-boxy Slabé klíče Proveďme zašifrování EK{M). Není-li tento výraz roven C-i, vylučujeme klíč K. Kdyby byl při šifrování non M použít klíč non K, obdrželi bychom Cz = £non /c(non M) = non EK{M). (5.3) Historie DES Popis DES Vlastnosti DES Kritika DES Vady DES Útoky Komplementárnost S-boxy Slabé klíče Proveďme zašifrování EK{M). Není-li tento výraz roven C-i, vylučujeme klíč K. Kdyby byl při šifrování non M použít klíč non K, obdrželi bychom Cz = £non /c(non M) = non EK{M). (5.3) Nejsou-li si oba krajní výrazy, které máme k dispozici, rovny, můžeme vyloučit i klíč non K. Historie DES Popis DES Vlastnosti DES Kritika DES Vady DES Útoky Komplementárnost S-boxy Slabé klíče Proveďme zašifrování EK(M). Není-li tento výraz roven C-i, vylučujeme klíč K. Kdyby byl při šifrování non M použít klíč non K, obdrželi bychom Cz = £non /c(non M) = non EK(M). (5.3) Nejsou-li si oba krajní výrazy, které máme k dispozici, rovny, můžeme vyloučit i klíč non K. Tím jsme nahradili jedno šifrování (klíčem non K) za pouhé porovnávání výrazů, což je proti šifrování časově zanedbatelné. Prostor klíčů je tedy de facto poloviční a hledání 2-krát rychlejší. Historie DES Popis DES Vlastnosti DES Kritika DES Vady DES Útoky Komplementárnost S-boxy Slabé klíče Proveďme zašifrování EK{M). Není-li tento výraz roven C-i, vylučujeme klíč K. Kdyby byl při šifrování non M použít klíč non K, obdrželi bychom Cz = £non /c(non M) = non EK{M). (5.3) Nejsou-li si oba krajní výrazy, které máme k dispozici, rovny, můžeme vyloučit i klíč non K. Tím jsme nahradili jedno šifrování (klíčem non K) za pouhé porovnávání výrazů, což je proti šifrování časově zanedbatelné. Prostor klíčů je tedy de facto poloviční a hledání 2-krát rychlejší. Vlastnost komplementarity by navíc mohla ve špatně navržených protokolech způsobit i nežádoucí odhalení chráněných informací. Při všech možných aplikacích na ni musí být dáván pozor. «n> == Historie DES Popis DES Vlastnosti DES Kritika DES Vady DES Útoky Komplementárnost S-boxy Slabé klíče Je smutné, že mnozí kryptologové (zejména z NBS) tuto vlastnost nepovažují za podstatnou. Ostatně v oficiálním popisu DES vypracovaném NBS se také tvrdí, že klíč je 64-bitový. Historie DES Popis DES Vlastnosti DES Kritika DES Vady DES Útoky Komplementárnost S-boxy Slabé klíče Je smutné, že mnozí kryptologové (zejména z NBS) tuto vlastnost nepovažují za podstatnou. Ostatně v oficiálním popisu DES vypracovaném NBS se také tvrdí, že klíč je 64-bitový. Rozhodně nejde o chybu, ale o vytvoření dojmu, že tomu tak je. Historie DES Popis DES Vlastnosti DES Kritika DES Vady DES Útoky Komplementárnost S-boxy Slabé klíče Je smutné, že mnozí kryptologové (zejména z NBS) tuto vlastnost nepovažují za podstatnou. Ostatně v oficiálním popisu DES vypracovaném NBS se také tvrdí, že klíč je 64-bitový. Rozhodně nejde o chybu, ale o vytvoření dojmu, že tomu tak je. S 'dobrýmiskauty1 tedy není asi všechno v pořádku. Historie DES Popis DES Vlastnosti DES Kritika DES Vady DES Útoky Komplementárnost S-boxy Slabé klíče Je smutné, že mnozí kryptologové (zejména z NBS) tuto vlastnost nepovažují za podstatnou. Ostatně v oficiálním popisu DES vypracovaném NBS se také tvrdí, že klíč je 64-bitový. Rozhodně nejde o chybu, ale o vytvoření dojmu, že tomu tak je. S "dobrými skauty1 tedy není asi všechno v pořádku. Kromě tajných návrhových kritérií, která mohla obsahovat další skryté vady, v studiu bylo poukázáno na velkou korelovanost a nedostatečnou nelinearitu výstupních bitů S-boxů. Historie DES Popis DES Vlastnosti DES Kritika DES Vady DES Útoky Komplementárnost S-boxy Slabé klíče Je smutné, že mnozí kryptologové (zejména z NBS) tuto vlastnost nepovažují za podstatnou. Ostatně v oficiálním popisu DES vypracovaném NBS se také tvrdí, že klíč je 64-bitový. Rozhodně nejde o chybu, ale o vytvoření dojmu, že tomu tak je. S "dobrými skauty tedy není asi všechno v pořádku. Kromě tajných návrhových kritérií, která mohla obsahovat další skryté vady, v studiu bylo poukázáno na velkou korelovanost a nedostatečnou nelinearitu výstupních bitů S-boxů. Například box S4 má pětasedmdesátiprocentní nadbytečnost. Historie DES Vlastnosti DES Vady DES Popis DES Kritika DES Útoky >mplementárnost box Slabé klíče S-box S4 (X1, x6) (X2,X3,X4,X5) 00 01 1 0 11 0 0 0 0 0 1 1 1 1 1 0 1 1 0 1 0 0 0 1 1 0 0 0 1 1 1 0 1 1 0 0 0 0 1 1 0 1 1 1 1 0 0 1 0 1 1 1 0 1 0 1 1 1 0 0 1 0 0 0 0 0 0 1 1 0 0 1 1 0 1 0 1 0 0 0 0 0 1 1 0 0 1 0 0 0 0 0 0 0 1 1 0 1 1 0 0 1 0 1 0 0 1 0 1 0 1 1 0 1 1 1 1 1 0 1 1 0 0 0 0 0 1 1 0 1 0 0 1 0 0 0 0 0 1 1 1 1 1 0 1 0 1 1 1 1 0 1 0 0 0 1 1 1 1 0 1 1 0 0 0 1 0 0 0 0 0 0 1 0 1 0 0 1 1 1 1 1 0 0 1 1 0 0 1 0 0 1 0 0 1 1 1 0 0 0 1 0 1 0 0 1 0 1 0 1 0 0 0 0 0 1 0 0 0 1 1 0 1 0 1 1 0 0 1 0 1 0 1 1 1 0 0 1 1 1 0 1 0 1 1 1 1 0 0 1 0 1 1 0 0 0 1 0 1 0 1 1 1 0 0 1 1 0 1 1 1 0 0 1 0 1 0 0 0 1 0 0 1 1 1 1 1 1 0 0 1 0 0 1 1 1 0 1 0 0 0 0 0 1 0 1 1 1 1 1 1 1 1 1 0 0 1 0 1 0 1 1 _ . 1 J 0 š. Historie DES Popis DES Vlastnosti DES Kritika DES Vady DES ýtoky Komplementarnost Slabé klíče Jeho 4 menší boxy 4x4 (při hodnotách krajních bitů x-i x6 = 00,01,10,11) jsou snadno odvoditelné pouze od prvního z nich (00). Historie DES Vlastnosti DES Vady DES Popis DES Kritika DES Útoky Komplementarnost Slabé klice y S-boxy Jeho 4 menší boxy 4x4 (při hodnotách krajních bitů x-i x6 = 00,01,10,11) jsou snadno odvoditelné pouze od prvního z nich (00). Platí dokonce vztah S4(x 0 000001) = (12)(34)S4(x) 0 (x6j non x6j non x6j x6), (5.4) Historie DES Vlastnosti DES Vady DES Popis DES Kritika DES Útoky Komplementarnost Slabé klice y S-boxy Jeho 4 menší boxy 4x4 (při hodnotách krajních bitů x-i x6 = 00,01,10,11) jsou snadno odvoditelné pouze od prvního z nich (00). Platí dokonce vztah S4(x 0 000001) = (12)(34)S4(x) 0 (x6, non x6, non x6, x6), (5.4) kde x = (x-i, x2, x3, x4, x5, x6) je vstup a symbolický zápis (1,2) znamená výměnu 1. a 2. bitu. Historie DES Vlastnosti DES Vady DES Popis DES Kritika DES Útoky Komplementarnost Slabé klice y S-boxy Jeho 4 menší boxy 4x4 (při hodnotách krajních bitů x-i x6 = 00,01,10,11) jsou snadno odvoditelné pouze od prvního z nich (00). Platí dokonce vztah S4(x 0 000001) = (12)(34)S4(x) 0 (x6, non x6, non x6, x6), _(5^) kde x = (x1, x2, x3, x4, x5, x6) je vstup a symbolický zápis (1,2) znamená výměnu 1. a 2. bitu. Označíme-li / = (y-i, 72,73,74) jako výstup, vyplývá odud, že součet (y-i e y2) je na x6 závislý pouze lineárně a (/1 0/20/30 /O na něm nezávisí vůbec. Taková pravděpodobnost je nežádoucí. = Historie DES Popis DES Vlastnosti DES Kritika DES Vady DES Útoky Komplementárnost S-boxy Slabé klíče Hodně pozornosti bylo věnováno studiu klíčů. Budou-li registry C a D na počátku obsahovat konstantní bity (buď nuly nebo jedničky), pak je operace SHL a PC2 je nijak nezmění a klíče Kj si budou rovny. Tím nastane i nežádoucí rovnost EK = DK. Historie DES Popis DES Vlastnosti DES Kritika DES Vady DES Útoky Komplementárnost S-boxy Slabé klíče Hodně pozornosti bylo věnováno studiu klíčů. Budou-li registry C a D na počátku obsahovat konstantní bity (buď nuly nebo jedničky), pak je operace SHL a PC2 je nijak nezmění a klíče Kj si budou rovny. Tím nastane i nežádoucí rovnost EK = DK. Celkem existují 4 tyto slabé klíče (podle toho, zda registry C nebo D obsahují nuly nebo jedničky). Podobnou vlastnost má 6 dvojic tzv. poloslabých klíčů a K2, pro něž platí EKa EKz = Id neboli EKa = DKz. Historie DES Popis DES Vlastnosti DES Kritika DES Vady DES Útoky Komplementárnost S-boxy Slabé klíče Hodně pozornosti bylo věnováno studiu klíčů. Budou-li registry C a D na počátku obsahovat konstantní bity (buď nuly nebo jedničky), pak je operace SHL a PC2 je nijak nezmění a klíče Kj si budou rovny. Tím nastane i nežádoucí rovnost EK = DK. Celkem existují 4 tyto slabé klíče (podle toho, zda registry C nebo D obsahují nuly nebo jedničky). Podobnou vlastnost má 6 dvojic tzv. poloslabých klíčů a K2, pro něž platí EKa EKz = Id neboli EKa = DKz. Ty vznikají tak, že jejich klíče jsou shodné, ale v opačném pořadí jejich použití. Tím vzniká efekt, že při šifrování druhým klíčem probíhá postupné dešifrování klíčem prvním. To nastane např. u této dvojice klíčů (01FE01FE01FE01FE, FE01FE01FE01FE01). Historie DES Popis DES Vlastnosti DES Kritika DES Vady DES Útoky Komplementárnost S-boxy Slabé klíče Hodně pozornosti bylo věnováno studiu klíčů. Budou-li registry C a D na počátku obsahovat konstantní bity (buď nuly nebo jedničky), pak je operace SHL a PC2 je nijak nezmění a klíče Kj si budou rovny. Tím nastane i nežádoucí rovnost EK = DK. Celkem existují 4 tyto slabé klíče (podle toho, zda registry C nebo D obsahují nuly nebo jedničky). Podobnou vlastnost má 6 dvojic tzv. poloslabých klíčů a K2, pro něž platí EKa EKz = Id neboli EKa = DKz. Ty vznikají tak, že jejich klíče jsou shodné, ale v opačném pořadí jejich použití. Tím vzniká efekt, že při šifrování druhým klíčem probíhá postupné dešifrování klíčem prvním. To nastane např. u této dvojice klíčů (01FE01FE01FE01FE, FE01FE01FE01FE01). Historie DES Popis DES Vlastnosti DES Kritika DES Vady DES Útoky Hellman Další vlastnosti Analytické útoky O Útoky na DES • Hellmanův časopaměťový útok • Další zajímavé vlastnosti • Analytické útoky Východisko k luštění lze nalézt i v efektivním využití času a paměti. Vychází se ze znalosti konkrétního otevřeného textu, který se velmi často objevuje ve zprávách, např. osm za sebou jdoucích mezer. Historie DES Popis DES Vlastnosti DES Kritika DES Vady DES Útoky Hellman Další vlastnosti Analytické útoky Východisko k luštění lze nalézt i v efektivním využití času a paměti. Vychází se ze znalosti konkrétního otevřeného textu, který se velmi často objevuje ve zprávách, např. osm za sebou jdoucích mezer. Při zachycení jemu odpovídajícímu šifrového textu můžeme klíč luštit vyzkoušením všech jeho možností (čas t=256 šifrování, paměť m=1 slovo) nebo tím, že si předem připravíme tabulku všech možných dvojic (klíč, šifrový text) (čas t=1, paměť m=256 slov) a porovnáním šifrového textu. V obou případech je celková spotřeba "časopaměti" tm=256 - spotřebu času lze přelít do paměti a naopak. Historie DES Popis DES Vlastnosti DES Kritika DES Vady DES Útoky Hellman Další vlastnosti Analytické útoky Východisko k luštění lze nalézt i v efektivním využití času a paměti. Vychází se ze znalosti konkrétního otevřeného textu, který se velmi často objevuje ve zprávách, např. osm za sebou jdoucích mezer. Při zachycení jemu odpovídajícímu šifrového textu můžeme klíč luštit vyzkoušením všech jeho možností (čas t=256 šifrování, paměť m=1 slovo) nebo tím, že si předem připravíme tabulku všech možných dvojic (klíč, šifrový text) (čas t=1, paměť m=256 slov) a porovnáním šifrového textu. V obou případech je celková spotřeba "časopaměti" tm=256 - spotřebu času lze přelít do paměti a naopak. Hellman v roce 1980 přišel na to, jak část tabulky vypočítat předem a ve velmi zhuštěné podobě ji uložit do paměti. Luštění potom probíhá částečně jako šifrování a částečně jako porovnávání. < □ ► , t, t