Kéthal

Az oldal jelenlegi verzióját még nem ellenőrizték tapasztalt közreműködők, és jelentősen eltérhet a 2022. május 21-én felülvizsgált verziótól ; az ellenőrzéshez 1 szerkesztés szükséges .

Kéthal

Teremtő	Bruce Schneier vezette szakembercsoport
Létrehozva	1998
Kulcsméret	128/192/256 bit
Blokkméret	128 bites
A körök száma	16
Típusú	Feistel hálózat

A Twofish egy szimmetrikus blokk-rejtjel, amelynek blokkmérete 128 bit, kulcshossza pedig legfeljebb 256 bit. A körök száma 16. Bruce Schneier vezette szakembercsoport fejlesztette ki . Egyike volt az AES verseny második szakaszának öt döntősének . Az algoritmus a Blowfish , SAFER és SQUARE algoritmusokon alapul .

Az algoritmus megkülönböztető jellemzői az előre kiszámított és kulcsfüggő cserecsomópontok használata, valamint a titkosítási alkulcsok feloldására szolgáló összetett séma. Az n bites titkosítási kulcs fele tényleges titkosítási kulcs, a másik fele pedig az algoritmus módosítására szolgál (a helyettesítő csomópontok ettől függenek).

Általános információk

A Twofish kifejezetten úgy lett kifejlesztve, hogy megfeleljen a NIST AES -re vonatkozó követelményeinek és ajánlásainak [1] :

128 bites blokkszimmetrikus titkosítás,
kulcshossz 128, 192 és 256 bit,
nincsenek gyenge billentyűk
hatékony szoftver (elsősorban 32 bites processzorokon) és hardveres megvalósítás,
rugalmasság (kiegészítő kulcshosszúságok használatának lehetősége, adatfolyam-titkosítás, hash funkciók stb.),
az algoritmus egyszerűsége – hatékony elemzésének lehetőségéért.

Azonban az algoritmus szerkezetének összetettsége, és ennek megfelelően a gyenge kulcsok vagy rejtett hivatkozások elemzésének bonyolultsága, valamint a Rijndaelhez képest a legtöbb platformon meglehetősen lassú végrehajtási idő nem kedvezett neki [2 ] .

A Twofish algoritmus egy 128 bites bemeneti blokk Blowfish algoritmusának módosítására tett kísérletből származik . Az új algoritmusnak hardveresen könnyen megvalósíthatónak kellett lennie (beleértve a kisebb táblák használatát is), fejlettebb kulcsbővítő rendszerrel ( eng. key schedule ) és egyértékű F függvényrel kellett rendelkeznie.

Ennek eredményeként az algoritmust egy vegyes Feistel-hálózatként valósították meg, négy ággal, amelyek Hadamar kriptotranszformációval módosítják egymást ( eng. pszeudo-Hadamar transzformáció, PHT ).

A hatékony megvalósítás lehetősége modern (akkori) 32 bites processzorokon (valamint intelligens kártyákon és hasonló eszközökön) az egyik kulcsfontosságú elv, amely a Twofish fejlesztőit vezérelte.

Például az F függvény a PHT kiszámításakor és a K kulcsrészhez való hozzáadáskor szándékosan az összeadást használja a hagyományos xor helyett . Ez lehetővé teszi a Pentium processzorcsalád LEA utasításának használatát, amely lehetővé teszi a Hadamard transzformáció kiszámítását egy órajel ciklusban . (Azonban ebben az esetben a kódot egy adott kulcsértékhez kell lefordítani). $(T_{0}+2T_{1}+K_{2r+9}){\bmod {2}}^{32}$

A Twofish algoritmus nem szabadalmaztatott, bárki használhatja díjak és jogdíjak nélkül. Számos titkosítási programban használatos, bár kevésbé elterjedt, mint a Blowfish .

Az algoritmus leírása

A Twofish a bemeneti 128 bites adatblokkot négy 32 bites alblokkra bontja, amelyeken a bemeneti fehérítési eljárás után 16 transzformációs kört hajtanak végre. Az utolsó kör után kimeneti fehérítés történik.

Fehérítés

A fehérítés az első kör előtt és az utolsó kör után adatok alkulcsokkal történő xorálására szolgáló eljárás. Ezt a technikát először a Khufu / Khare titkosításban használta, és függetlenül Ron Rivest a DESX titkosítási algoritmusban . Joe Killian (NEC) és Phillip Rogaway (University of California) kimutatták, hogy a fehérítés megnehezíti a DESX-ben [3] végzett átfogó kulcskeresést . A Twofish fejlesztői azzal érvelnek [4] , hogy a Twofish-ben a fehérítés jelentősen megnehezíti a kulcs kitalálását is, mivel a kriptoanalitikus nem tudja kideríteni, milyen adatok kerülnek az F első körös függvény bemenetére.

Voltak azonban negatív oldalai is. Érdekes tanulmányt készítettek az IBM Research Center szakemberei. [5] Megvalósították a Twofish algoritmust egy tipikus CMOS intelligens kártyán, és elemezték a támadás lehetőségét a Differential Power Analysis (DPA) segítségével. A bemeneti fehérítő eljárást támadták meg, mivel az közvetlenül az alkulcsok xor-ját használja a bemeneti adatokkal. Ennek eredményeként a kutatók kimutatták, hogy lehetséges egy 128 bites kulcs teljes kiszámítása mindössze 100 véletlenszerű blokk-titkosítási művelet elemzésével.

g függvény

A g függvény a Twofish algoritmus alapja. A függvénybemenet egy 32 bites X szám, amelyet azután négy x0, x1, x2, x3 bájtra osztanak fel. Az eredményül kapott bájtok mindegyike áthalad az S-boxon. (Megjegyzendő, hogy az algoritmus S-dobozai nem rögzítettek, hanem a kulcstól függenek). Az S-boxok kimenetein kapott 4 bájtot négy komponensből álló vektorként értelmezzük. Ezt a vektort megszorozzuk egy fix 4x4-es MDS (maximum distance separable) mátrixszal, és a számításokat a Galois-mezőben hajtjuk végre, az irreducibilis polinom modulja . $GF(2^{8})$ $x^{8}+x^{6}+x^{5}+x^{3}+1$

Az MDS mátrix olyan mátrix egy véges K mező felett, amelyet ha egy térből térbe történő lineáris transzformáció mátrixának vesszük , akkor az (x, f(x)) alak teréből bármely két vektor legalább m + 1 különbség van az összetevők között. Ez azt jelenti, hogy az (x, f(x)) alakú vektorok halmaza a maximális távolsággal elválasztható kód tulajdonságú kódot alkot. Ilyen kód például a Reed-Solomon kód . $f(x)=(MDS)x$ $K^n$ $K^{m}$ $K^{{n+m}}$

A Twofish-ben az MDS mátrix maximális diverzitási tulajdonsága azt jelenti, hogy az a vektor és a vektor változó bájtjainak száma összesen legalább öt. Más szóval, ha csak egy bájtot változtat, a b mind a négy bájtját megváltoztatja. $b=(MDS)a$

Hadamar kriptotranszformáció (Pseudo-Hadamar Transform, PHT)

A Crypto Hadamard transzformáció egy 2n hosszúságú bitsor reverzibilis transzformációja. A karakterláncot két, n bitben azonos hosszúságú a és b részre osztjuk. A transzformáció kiszámítása a következőképpen történik:

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

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

Ezt a műveletet gyakran használják a kód "szórására" (például a SAFER titkosításban ).

A Twofish-ben ezt a transzformációt két g-függvény (n = 32) összekeverésekor használják.

Forgatás 1 bittel

Minden körben a két jobb oldali 32 bites blokk, amelyek az F függvény eredményeivel vannak xorálva, még egy bittel elfordulnak. A harmadik blokk eltolódik az xor művelet előtt, a negyedik blokk után. Ezeket az eltolásokat szándékosan adják hozzá, hogy megtörjék az S-boxokban és az MDS-mátrixszorzásokban rejlő bájt-igazítást. A titkosítás azonban megszűnik teljesen szimmetrikus lenni, mivel a titkosítás és a visszafejtés során az eltolásokat ellentétes irányban kell végrehajtani.

Kulcsgenerálás

A Twofish 128, 192 és 256 bites kulcsokkal működik. A kezdeti kulcsból 40 db 32 bites alkulcs generálódik, amelyek közül az első nyolcat csak a bemeneti és kimeneti fehérítési műveletekben, a maradék 32-t pedig titkosítási körökben használjuk, körönként két alkulccsal. A Twofish jellemzője, hogy az eredeti kulcsot magát a titkosítási algoritmust is megváltoztatják, mivel a g függvényben használt S-boxok nem rögzítettek, hanem a kulcstól függenek.

Kerek alkulcsok létrehozásához az eredeti M kulcsot bájtok permutációjával két azonos blokkra osztják és . Ezután a blokk és a h függvény segítségével a 2*i értéket, a blokk segítségével pedig a 2*i+1 értéket titkosítjuk, ahol i az aktuális kör száma (0-15). A kapott titkosított blokkokat a Hadamard kriptotranszformáció keveri össze, majd kerek alkulcsként használja fel. $M_{o}$ $Nekem}$ $M_{o}$ $Nekem}$

Technikai részletek

Tekintsük részletesebben a kerek alkulcsok generálására szolgáló algoritmust, valamint a kulcstól függő g függvényt. Mind az alkulcs-generálás, mind a g függvényképzés a Twofish-ben egy fő függvényt használ: h(X, L 0 , L 1 , … , L k ). Itt X, L 0 , L 1 , … , L k 32 bites szavak, és k = N / 64, ahol N az eredeti kulcs hossza bitekben. A függvény eredménye egy 32 bites szó.

h függvény

A függvény végrehajtása k lépésben történik. Vagyis 256 bites kulcsnál 4 fokozat lesz, 192 bites kulcsnál 3 fokozat, 128 bitesnél 2 fokozat.

Minden szakaszban a bemeneti 32 bites szót 4 bájtra osztják, és minden bájtot fix bitpermutációnak vetnek alá q 0 vagy q 1

Az eredményt 4 bájtos vektorként ábrázoljuk, és megszorozzuk az MDS mátrixszal. A számításokat a GF(2 8 ) Galois-mezőben végezzük az irreducibilis polinom modulo-jában . $x^{8}+x^{6}+x^{5}+x^{3}+1$

Az MDS mátrix alakja:

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

q 0 és q 1 permutációk

q 0 és q 1 az x bemeneti bájt 8 bitjének rögzített permutációi.

Az x bájt két 4 bites a 0 és b 0 félre van felosztva , amelyeken a következő átalakítások hajtódnak végre:

a_{0}=x/16

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

{\displaystyle 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}]

{\displaystyle 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))

Itt van egy 4 bites ciklikus eltolás jobbra, és a t 0 , t 1 , t 2 , t 3 a 4 bites számok táblázatos helyettesítései. ${\mbox{ROR}}_{4}$

q 0 esetén a táblázatok így néznek ki:

t 0 = [ 8 1 7 D 6 F 3 2 0 B 5 9 ECA 4 ] t 1 = [ EKB 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 ]

q 1 esetén a táblázatok így néznek ki:

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 ]

Kulcsgenerálás

Legyen M az eredeti kulcs, N a hossza bitekben. Az alkulcsok a következőképpen jönnek létre:

Az eredeti kulcs 8*k bájtra van felosztva , ahol k = N / 64. $m_{0},...,m_{{8k-1}}$
Ezeket a 8*k bájtokat négy bájtos szavakra osztják, és minden szóban a bájtok megfordulnak. Az eredmény 2*k 32 bites szó $M_{i}$

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

Az eredményül kapott 2*k 32 bites szót két vektorra osztjuk , amelyek mérete k 32 bites szó. $Nekem}$ $M_{o}$

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

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

Az i. forduló alkulcsait a következő képletekkel számítjuk ki:

{\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)

Funkció g és S -boxok

A g függvényt a h : függvény segítségével definiáljuk . $g(X)=h(X,S)$

Az S vektor az M e és M o vektorokhoz hasonlóan szintén az eredeti kulcsból áll, és k 32 bites szóból áll. Az eredeti kulcsbájtok k nyolc bájtos csoportra vannak osztva . Mindegyik ilyen csoportot 8 komponensből álló vektorként kezelünk, és megszorozzuk egy 4×8 bájtos rögzített RS mátrixszal. A szorzás eredményeként egy négy bájtból álló vektort kapunk. A számításokat a Galois-mező modulo egy irreducibilis polinomban végezzük . Az RS mátrix alakja $GF(2^{8})$ $x^{8}+x^{6}+x^{3}+x^{2}+1$

.

Kriptanalízis

A Twofish csökkentett fordulószámú vizsgálata kimutatta, hogy az algoritmus nagy biztonsági résszel rendelkezik, és az AES verseny többi döntőséhez képest ez bizonyult a legkitartóbbnak. Szokatlan szerkezete és viszonylagos összetettsége azonban kétségeket ébreszt ennek az erősségnek a minőségével kapcsolatban.

Kritikát váltott ki az eredeti kulcs két részre osztása a kerek alkulcsok kialakítása során. Fauzan Mirza és Sean Murphy kriptográfusok azt javasolták, hogy egy ilyen felosztás lehetővé teszi az „oszd meg és uralkodj” elv szerinti támadás megszervezését, vagyis a feladat két hasonló, de egyszerűbb részre osztását [6] . Ilyen támadást azonban valójában nem hajtottak végre.

2008-ra a Twofish kriptoanalízis legjobb változata a csonka differenciális kriptoanalízis egyik változata, amelyet Shiho Moriai és Yiqun Lisa Yin publikált Japánban 2000-ben [7] . Megmutatták , hogy 251 egyező egyszerű szövegre van szükség a szükséges különbségek megtalálásához . Ennek ellenére a vizsgálatok elméleti jellegűek voltak, valódi támadást nem hajtottak végre. A Twofish alkotója, Bruce Schneier a blogján azzal érvel, hogy egy ilyen támadás a valóságban lehetetlen [8] .

Jegyzetek

↑ "A fejlett titkosítási szabvány (AES) algoritmus-jelöltjére vonatkozó kérelem bejelentése" Archiválva : 2011. június 5. a Wayback Machine -nél . Kereskedelmi Minisztérium – Nemzeti Szabványügyi és Technológiai Intézet – Szövetségi Nyilvántartás: 1997. szeptember 12.
↑ Nechvatal J., Barker E., Bassham L., Burr W., Dworkin M., Foti J., Roback E. "Report on the Development of the Advanced Encryption Standard (AES)" Archiválva : 2010. december 30., Wayback Machine (angol) . — Országos Szabványügyi és Technológiai Intézet.
↑ J. Kilian és P. Rogaway "Hogyan védjük meg a DES-t a kimerítő kulcskeresés ellen" Archiválva : 2010. június 11., a Wayback Machine 2000. február 2.
↑ N. Ferguson, J. Kelsey, B. Schneier, D. Whiting "A Twofish Retreat: Related-Key Attacks Against Reduced-Round Twofish" Archiválva : 2008. július 19., a Wayback Machine Twofish Technical Report #6, 2000. február 14.
↑ Suresh Chari, Charanjit Jutla, Josyula R. Rao, Pankaj Rohatgi "A Cautionary Note Regarding Evaluation of AES Candidates on Smart-Cards" Archiválva : 2012. október 13., a Wayback Machine , 1999
↑ Fauzan Mirza, Sean Murphy "Megfigyelés a Twofish kulcsfontosságú ütemtervéről" Archiválva : 2016. december 21., a Wayback Machine - Information Security Group, Royal Holloway, Londoni Egyetem - 1999. január 26.
↑ Shiho Moriai, Yiqun Lisa Yin "Cryptanalysis of Twofish (II)" archiválva : 2012. június 1., a Wayback Machine - The Institute of Economics, Information and Communication Engineers
↑ Bruce Schneier "Twofish Cryptanalysis Rumors" archiválva 2012. június 9-én a Wayback Machine blogon

Linkek

Twofish weboldal .
Twofish forráskódok .
Twofish: A 128-Bit Block Cipher archiválva 2008. augusztus 29-én a Wayback Machine -nél .
Titkosítási algoritmusok – Az AES verseny döntősei .
A Twofish-t használó termékek listája .

Szimmetrikus titkosítási rendszerek
Rejtjelfolyam adatfolyam	A3 A5 A8 Decim F-FCSR Gabona HC-256 KCipher-2 MICKEY MUGI CSUKA Phelix RC4 Nyúl FÓKA HÓ SOSEMANUK Salsa20 STRUMOK Trivium VMPC
Feistel hálózat	GOST 28147-89 (Magma) blowfish Kamélia CAST-128 CAST-256 CIPHERUNICORN-A CIPHERUNICORN-E CLEFIA Kobra ÜZLET DES DESX DFC E2 EnRUPT FEAL HPC ÖTLET KASUMI Khafre Khufu LOKI97 MacGuffin MARS HÁLÓ MISTY1 NewDES NDS RC5 RC6 MAG Simon Sinopoli skipjack SM4 Folt TEA XTEA XXTEA Raiden RTEA Tripla DES Kéthal
SP hálózat	Szöcske 3 út ABC ÁRIA AES (Rijndael) Akelarre Anubis BaseKing Bass Omatic Öv CRYPTON Gyémánt2 grand cru Hierocrypt-3 Hierocrypt-L1 KHAZAD Kalyna Lucifer jelenlegi Szivárvány BIZTONSÁGOSBAN CÁPA NÉGYZET Kígyó háromhal
Egyéb	BÉKA NUSH REDOC SC2000 SHACAL CS-Cipher