Dvě ryby

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. května 2022; ověření vyžaduje 1 úpravu .

Dvě ryby

Tvůrce	skupina specialistů vedená Brucem Schneierem
Vytvořeno	1998
Velikost klíče	128/192/256 bitů
Velikost bloku	128 bit
Počet kol	16
Typ	Síť Feistel

Twofish je symetrická bloková šifra s velikostí bloku 128 bitů a délkou klíče až 256 bitů. Počet kol 16. Vyvinuto skupinou specialistů pod vedením Bruce Schneiera . Byl jedním z pěti finalistů druhé fáze soutěže AES . Algoritmus je založen na algoritmech Blowfish , SAFER a SQUARE .

Charakteristickými rysy algoritmu jsou použití předem vypočítaných a na klíči závislých náhradních uzlů a složité schéma pro rozbalení šifrovacích podklíčů. Polovina n - bitového šifrovacího klíče se používá jako vlastní šifrovací klíč, druhá polovina se používá k úpravě algoritmu (na něm závisí substituční uzly).

Obecné informace

Twofish byl vyvinut speciálně pro splnění požadavků a doporučení NIST pro AES [1] :

128bitová bloková symetrická šifra,
délka klíče 128, 192 a 256 bitů,
žádné slabé klávesy
efektivní implementace softwaru (především na 32bitových procesorech) a hardwaru,
flexibilita (možnost používat další délky klíčů, použití při šifrování streamování, hashovací funkce atd.),
jednoduchost algoritmu - pro možnost jeho efektivní analýzy.

V jeho prospěch však nehrála složitost struktury algoritmu, a tedy složitost jeho analýzy na slabé klíče nebo skryté odkazy, stejně jako poměrně pomalá doba provádění ve srovnání s Rijndaelem na většině platforem [2 ] .

Algoritmus Twofish vznikl z pokusu upravit algoritmus Blowfish pro 128bitový vstupní blok. Nový algoritmus musel být snadno hardwarově implementovatelný (včetně použití menších tabulek), měl mít pokročilejší systém rozšíření klíče ( angl. key schedule ) a mít jednohodnotovou funkci F.

Ve výsledku byl algoritmus implementován jako smíšená Feistelova síť se čtyřmi větvemi, které se vzájemně modifikují pomocí Hadamarovy kryptotransformace ( angl. pseudo-Hadamar transform, PHT ).

Možnost efektivní implementace na moderních (na tehdejší dobu) 32bitových procesorech (stejně jako v čipových kartách a podobných zařízeních) je jedním z klíčových principů, kterými se řídili vývojáři Twofish.

Například funkce F při výpočtu PHT a přidávání do klíčové části K záměrně používá sčítání místo tradičního xor . To umožňuje použít instrukci LEA z rodiny procesorů Pentium, která umožňuje vypočítat Hadamardovu transformaci v jednom hodinovém cyklu . (V tomto případě však musí být kód zkompilován pro konkrétní hodnotu klíče). $(T_{0}+2T_{1}+K_{2r+9}){\bmod {2}}^{32}$

Algoritmus Twofish není patentován a může jej používat kdokoli bez jakýchkoli poplatků nebo licenčních poplatků. Používá se v mnoha šifrovacích programech, i když je méně běžný než Blowfish .

Popis algoritmu

Twofish rozdělí vstupní 128bitový datový blok na čtyři 32bitové dílčí bloky, na kterých se po proceduře vstupního bělení provede 16 cyklů transformací. Po posledním kole se provede výstupní bělení.

Bělení

Whitening je postup pro xorování dat s podklíči před prvním kolem a po posledním kole. Tato technika byla poprvé použita v šifře Khufu / Khare a nezávisle Ron Rivest v šifrovacím algoritmu DESX . Joe Killian (NEC) a Phillip Rogaway (University of California) ukázali, že bělení ztěžuje úkol vyčerpávajícího vyhledávání klíčů v DESX [3] . Vývojáři Twofish argumentují [4] , že v Twofish whitening také výrazně komplikuje úkol uhodnout klíč, protože kryptoanalytik nemůže zjistit, jaká data se dostávají do vstupu funkce prvního kola F.

Našly se však i negativní stránky. Zajímavou studii provedli specialisté z IBM Research Center. [5] Implementovali algoritmus Twofish na typickou čipovou kartu CMOS a analyzovali možnost útoku pomocí diferenciální analýzy výkonu (DPA). Napadena byla procedura vstupního bělení, protože přímo používá xor podklíčů se vstupními daty. Výsledkem bylo, že výzkumníci ukázali, že je možné plně vypočítat 128bitový klíč analýzou pouze 100 náhodných blokových šifrovacích operací.

Funkce g

Funkce g je základem algoritmu Twofish. Vstupem funkce je 32bitové číslo X, které je poté rozděleno do čtyř bajtů x0, x1, x2, x3. Každý z výsledných bajtů prochází jeho S-boxem. (Je třeba poznamenat, že S-boxy v algoritmu nejsou pevně dané, ale závisí na klíči). Výsledné 4 bajty na výstupech S-boxů jsou interpretovány jako vektor se čtyřmi složkami. Tento vektor je vynásoben pevnou maticí 4x4 MDS (oddělitelná maximální vzdálenost) a výpočty se provádějí v Galoisově poli modulo neredukovatelného polynomu. $GF(2^{8})$ $x^{8}+x^{6}+x^{5}+x^{3}+1$

Matice MDS je taková matice nad konečným polem K, že pokud ji vezmeme jako matici lineární transformace z prostoru do prostoru , pak libovolné dva vektory z prostoru tvaru (x, f(x)) budou mít alespoň m + 1 rozdílů ve složkách . To znamená, že množina vektorů ve tvaru (x, f(x)) tvoří kód s maximální vzdáleností oddělitelnou vlastností kódu. Takovým kodexem je například Reed-Solomonův kodex . $f(x)=(MDS)x$ $K^n$ $K^{m}$ $K^{{n+m}}$

V Twofish vlastnost maximální diverzity matice MDS znamená, že celkový počet měnících se bajtů vektoru a a vektoru je alespoň pět. Jinými slovy, jakákoli změna pouze na jeden bajt v a změní všechny čtyři bajty v b. $b=(MDS)a$

Hadamarova kryptotransformace (Pseudo-Hadamar Transform, PHT)

Crypto Hadamard transform je vratná transformace bitového řetězce délky 2n. Řetězec je rozdělen na dvě části aab stejné délky v n bitech. Transformace se vypočítá takto:

{\displaystyle a'=a+b\,{\pmod {2^{n))))

{\displaystyle b'=a+2b\,{\pmod {2^{n))))

Tato operace se často používá k „rozptýlení“ kódu (například v šifře SAFER ).

V Twofish se tato transformace používá při smíchání výsledků dvou g-funkcí (n = 32).

Otočit o 1 bit

V každém kole jsou dva pravé 32bitové bloky, které jsou xoredovány s výsledky funkce F, navíc otočeny o jeden bit. Třetí blok je posunut před operací xor, čtvrtý blok poté. Tyto posuny jsou záměrně přidány, aby narušily zarovnání bajtů, které je vlastní S-boxům a násobení matic MDS. Šifra však přestává být zcela symetrická, protože během šifrování a dešifrování by měly být posuny prováděny v opačných směrech.

Generování klíčů

Twofish je navržen pro práci se 128, 192 a 256 bitovými klíči. Z počátečního klíče se vygeneruje 40 32bitových podklíčů, z nichž prvních osm se používá pouze ve vstupních a výstupních bělicích operacích a zbývajících 32 se používá v šifrovacích kolech, dva podklíče na kolo. Funkce Twofish je, že původní klíč se také používá ke změně samotného šifrovacího algoritmu, protože S-boxy použité ve funkci g nejsou pevně dané, ale závisí na klíči.

Pro vytvoření kulatých podklíčů je původní klíč M rozdělen s permutací bajtů na dva identické bloky a . Potom se pomocí bloku a funkce h zašifruje hodnota 2*i a pomocí bloku se zašifruje hodnota 2*i+1, kde i je číslo aktuálního kola (0 - 15). Výsledné zašifrované bloky jsou smíchány Hadamardovou krypto-transformací a poté použity jako kulaté podklíče. $M_{o}$ $Mě}$ $M_{o}$ $Mě}$

Technické detaily

Podívejme se podrobněji na algoritmus pro generování kruhových podklíčů a také na klíčově závislou funkci g. Jak generování podklíče, tak tvorba g funkce v Twofish používá jednu hlavní funkci: h(X, L 0 , L 1 , …, L k ). Zde X, Lo , L1 , … , Lk jsou 32-bitová slova a k = N/64, kde N je délka původního klíče v bitech . Výsledkem funkce je jedno 32bitové slovo.

Funkce h

Funkce se provádí v k fázích. To znamená, že pro klíč o délce 256 bitů budou 4 stupně, pro klíč 192 bitů - 3 stupně, pro 128 bitů - 2 stupně.

V každé fázi je vstupní 32bitové slovo rozděleno na 4 bajty a každý bajt je podroben pevné bitové permutaci q 0 nebo q 1

Výsledek je reprezentován jako vektor o velikosti 4 bajtů a vynásobený maticí MDS. Výpočty se provádějí v Galoisově poli GF(2 8 ) modulo neredukovatelný polynom . $x^{8}+x^{6}+x^{5}+x^{3}+1$

Matice MDS má tvar:

${\mbox{MDS}}={\begin{pmatrix}01&EF&5B&5B\\5B&EF&EF&01\\EF&5B&01&EF\\EF&01&EF&5B\end{pmatrix}}$

Permutace q 0 a q 1

q 0 a q 1 jsou pevné permutace 8 bitů vstupního bytu x.

Byte x je rozdělen na dvě 4bitové poloviny a 0 a b 0 , přes které se provádějí následující transformace:

a_{0}=x/16

b_{0}=x{\bmod {16}}

a_{1}=a_{0}\oplus b_{0}

b_{1}=a_{0}\oplus {\mbox{ROR}}_{4}(b_{0},1)\oplus 8a_{0}{\bmod {16}}

a_{2}=t_{0}[a_{1}]

b_{2}=t_{1}[b_{1}]

a_{3}=a_{2}\oplus b_{2}

b_{3}=a_{2}\oplus {\mbox{ROR}}_{4}(b_{2},1)\oplus 8a_{2}{\bmod {16}}

a_{4}=t_{2}[a_{3}]

b_{4}=t_{3}[b_{3}]

{\displaystyle y=16b_{4}+a_{4))

Zde je 4bitový cyklický posun doprava a to , ti , t2 , t3 jsou tabulkové náhrady 4bitových čísel . ${\mbox{ROR}}_{4}$

Pro q 0 vypadají tabulky takto:

t 0 = [ 8 1 7 D 6 F 3 2 0 B 5 9 ECA 4 ] t 1 = [ ECB 8 1 2 3 5 F 4 A 6 7 0 9 D ] t 2 = [ BA 5 E 6 D 9 0 C 8 F 3 2 4 7 1 ] t 3 = [ D 7 F 4 1 2 6 E 9 B 3 0 8 5 CA ]

Pro q 1 vypadají tabulky takto:

t 0 = [ 2 8 BDF 7 6 E 3 1 9 4 0 AC 5 ] t 1 = [ 1 E 2 B 4 C 3 7 6 DA 5 F 9 0 8 ] t 2 = [ 4 C 7 5 1 6 9 A 0 ED 8 2 B 3 F ] t 3 = [ B 9 5 1 C 3 DE 6 4 7 F 2 0 8 A ]

Generování klíčů

Nechť M je původní klíč, N je jeho délka v bitech. Podklíče se generují následovně:

Původní klíč je rozdělen na 8*k bajtů , kde k = N / 64. $m_{0},...,m_{{8k-1}}$
Těchto 8*k bajtů je rozděleno na slova po čtyřech bytech a v každém slově jsou bajty obráceny. Výsledkem je 2*k 32bitových slov $M_{i}$

M_{i}=\sum _{j=0}^{3}m_{(4i+j)}\cdot 2^{8j}~~~~~i=0,...,2k- jeden

Výsledných 2*k 32bitových slov se rozdělí do dvou vektorů o velikosti k 32bitových slov. $Mě}$ $M_{o}$

M_{e}=(M_{0},M_{2},...,M_{2k-2})

M_{o}=(M_{1},M_{3},...,M_{2k-1})

Podklíče pro i-té kolo se počítají podle vzorců:

{\displaystyle \rho =2^{24}+2^{16}+2^{8}+2^{0))

A_{i}=h(2i\rho ,M_{e})

B_{i}={\mbox{ROL}}(h((2i+1)\rho ,M_{0}),8)

{\displaystyle K_{2i}=(A_{i}+B_{i}){\bmod {2^{32))))

K_{2i+1}={\mbox{ROL}}((A_{i}+2B_{i}){\bmod {2^{32}}},9)

Funkce g a S -boxy

Funkce g je definována pomocí funkce h : . $g(X)=h(X,S)$

Vektor S , stejně jako vektory Me a Mo , je rovněž vytvořen z původního klíče a skládá se z k 32bitových slov. Původní klíčové bajty jsou rozděleny do k skupin po osmi bytech. Každá taková skupina je považována za vektor s 8 složkami a vynásobená pevnou maticí RS 4×8 bajtů. V důsledku násobení se získá vektor sestávající ze čtyř bajtů. Výpočty jsou prováděny v Galoisově poli modulo neredukovatelném polynomu . Matice RS má tvar $GF(2^{8})$ $x^{8}+x^{6}+x^{3}+x^{2}+1$

.

Kryptoanalýza

Studie Twofish se sníženým počtem kol ukázala, že algoritmus má velkou rezervu v bezpečnosti a ve srovnání se zbytkem finalistů soutěže AES se ukázal jako nejvytrvalejší. Jeho neobvyklá struktura a relativní složitost však vyvolaly určité pochybnosti o kvalitě této síly.

Rozdělení původního klíče na dvě poloviny při vytváření kulatých podklíčů vyvolalo kritiku. Kryptografové Fauzan Mirza a Sean Murphy navrhli, že takové rozdělení umožňuje zorganizovat útok podle principu „rozděl a panuj“, tedy rozdělit úkol na dva podobné, ale jednodušší [6] . K takovému útoku však ve skutečnosti nedošlo.

Pro rok 2008 je nejlepší variantou kryptoanalýzy Twofish varianta zkrácené diferenciální kryptoanalýzy, kterou publikovali Shiho Moriai a Yiqun Lisa Yin v Japonsku v roce 2000 [7] . Ukázali, že k nalezení nezbytných rozdílů je zapotřebí 251 shodných otevřených textů . Přesto byly studie teoretického charakteru, žádný skutečný útok nebyl proveden. Tvůrce Twofish Bruce Schneier na svém blogu tvrdí, že takový útok je ve skutečnosti nemožný [8] .

Poznámky

↑ „Oznamování žádosti o nominace kandidátských algoritmů pro Advanced Encryption Standard (AES)“ Archivováno 5. června 2011 na Wayback Machine . Ministerstvo obchodu – Národní institut pro standardy a technologie – Federální rejstřík: 12. září 1997.
↑ Nechvatal J., Barker E., Bassham L., Burr W., Dworkin M., Foti J., Roback E. „Zpráva o vývoji standardu pokročilého šifrování (AES)“ Archivováno 30. prosince 2010 ve Wayback Machine (anglicky) . — Národní institut pro standardy a technologie.
↑ J. Kilian a P. Rogaway „Jak chránit DES před vyčerpávajícím vyhledáváním klíčů“ Archivováno 11. června 2010 ve Wayback Machine 2. února 2000
↑ N. Ferguson, J. Kelsey, B. Schneier, D. Whiting "A Twofish Retreat: Related-Key Attacks Against Reduced-Round Twofish" Archivováno 19. července 2008 na Wayback Machine Twofish Technical Report #6, 14. února 2000
↑ Suresh Chari, Charanjit Jutla, Josyula R. Rao, Pankaj Rohatgi „Varovná poznámka týkající se hodnocení kandidátů AES na čipových kartách“ Archivováno 13. října 2012 na Wayback Machine , 1999
↑ Fauzan Mirza, Sean Murphy „An Observation on the Key Schedule of Twofish“ Archivováno 21. prosince 2016 na Wayback Machine – Information Security Group, Royal Holloway, University of London – 26. ledna 1999
↑ Shiho Moriai, Yiqun Lisa Yin „Cryptanalysis of Twofish (II)“ Archivováno 1. června 2012 na Wayback Machine – Institutu ekonomických, informačních a komunikačních inženýrů
↑ Bruce Schneier „Twofish Cryptanalysis Rumors“ Archivováno 9. června 2012 na blogu Wayback Machine

Odkazy

Webová stránka Twofish .
Twofish zdrojové kódy .
Twofish: A 128-Bit Block Cipher Archived 29. srpna 2008 na Wayback Machine .
Šifrovací algoritmy – finalisté soutěže AES .
Seznam produktů používajících Twofish .

Symetrické kryptosystémy
Streamové šifry	A3 A5 A8 Decim F-FCSR Obilí HC-256 KCipher-2 MICKEY MUGI ŠTIKA Phelix RC4 Králičí TĚSNĚNÍ SNÍH SOSEMANUK Salsa20 STRUMOK Trivium VMPC
Síť Feistel	GOST 28147-89 (Magma) nafukovací ryba Kamélie CAST-128 CAST-256 CIPHERUNICORN-A CIPHERUNICORN-E CLEFIA Kobra OBCHOD DES DESX DFC E2 EnRUPT FEAL HPC IDEA KASUMI Khafre Chufu LOKI97 MacGuffin MARS PLETIVO MISTY1 NewDES NDS RC5 RC6 SEMÍNKO Simone Sinople skipjack SM4 Smítko ČAJ XTEA XXTEA Raiden RTEA Trojitý DES Dvě ryby
Síť SP	Saranče 3 způsob ABC ÁRIE AES (Rijndael) Akelarre Anubis BaseKing Bass Omatic Pás KRYPTON Diamant 2 grand cru Hierocrypt-3 Hierocrypt-L1 KHAZAD Kalyna Lucifer současnost, dárek Duha BEZPEČNĚJŠÍ ŽRALOK NÁMĚSTÍ Had tři ryby
jiný	ŽÁBA NUSH REDOC SC2000 SHACAL CS-Cipher