Doi pești

Versiunea actuală a paginii nu a fost încă examinată de colaboratori experimentați și poate diferi semnificativ de versiunea revizuită pe 21 mai 2022; verificarea necesită 1 editare .

Doi pești

Creator	un grup de specialiști condus de Bruce Schneier
Creată	1998
Dimensiunea cheii	128/192/256 biți
Dimensiunea blocului	128 de biți
Numărul de runde	16
Tip de	Rețeaua Feistel

Twofish este un cifru bloc simetric cu o dimensiune a blocului de 128 de biți și o lungime a cheii de până la 256 de biți. Numărul de runde 16. Dezvoltat de un grup de specialiști condus de Bruce Schneier . A fost unul dintre cei cinci finaliști ai etapei a doua a competiției AES . Algoritmul se bazează pe algoritmii Blowfish , SAFER și SQUARE .

Caracteristicile distinctive ale algoritmului sunt utilizarea nodurilor de înlocuire pre-calculate și dependente de cheie și o schemă complexă pentru despachetarea subcheilor de criptare. Jumătate din cheia de criptare de n biți este folosită ca cheie de criptare reală, cealaltă jumătate este folosită pentru a modifica algoritmul (nodurile de substituție depind de acesta).

Informații generale

Twofish a fost dezvoltat special pentru a îndeplini cerințele și recomandările NIST pentru AES [1] :

Cifru bloc simetric pe 128 de biți,
lungimea cheii 128, 192 și 256 biți,
fără chei slabe
software eficient (în principal pe procesoare pe 32 de biți) și implementare hardware,
flexibilitate (abilitatea de a utiliza lungimi suplimentare de chei, utilizarea în criptarea în flux, funcții hash etc.),
simplitatea algoritmului – pentru posibilitatea analizei sale eficiente.

Cu toate acestea, complexitatea structurii algoritmului și, în consecință, complexitatea analizei sale pentru chei slabe sau legături ascunse, precum și timpul de execuție destul de lent în comparație cu Rijndael pe majoritatea platformelor, nu au jucat în favoarea sa [2] ] .

Algoritmul Twofish a apărut dintr-o încercare de a modifica algoritmul Blowfish pentru un bloc de intrare de 128 de biți. Noul algoritm trebuia să fie ușor de implementat în hardware (inclusiv utilizarea de tabele mai mici), să aibă un sistem de extindere a cheilor mai avansat ( ing. chei program ) și să aibă o funcție cu o singură valoare F.

Ca rezultat, algoritmul a fost implementat ca o rețea Feistel mixtă cu patru ramuri care se modifică reciproc folosind transformarea cripto Hadamar ( de exemplu, transformarea pseudo-Hadamar, PHT ).

Posibilitatea implementării eficiente pe procesoare moderne (pentru acea vreme) pe 32 de biți (precum și în smart carduri și dispozitive similare) este unul dintre principiile cheie care i-au ghidat pe dezvoltatorii Twofish.

De exemplu, funcția F, când calculează PHT și adaugă la partea cheie K, folosește în mod intenționat adăugarea în locul tradiționalului xor . Acest lucru face posibilă utilizarea instrucțiunii LEA din familia de procesoare Pentium, care permite calcularea transformării Hadamard într-un singur ciclu de ceas . (Cu toate acestea, în acest caz, codul trebuie compilat pentru o anumită valoare a cheii). $(T_{0}+2T_{1}+K_{2r+9}){\bmod {2}}^{32}$

Algoritmul Twofish nu este brevetat și poate fi folosit de oricine fără taxe sau redevențe. Este folosit în multe programe de criptare, deși este mai puțin comun decât Blowfish .

Descrierea algoritmului

Twofish împarte blocul de date de intrare pe 128 de biți în patru subblocuri de 32 de biți, pe care, după procedura de albire a intrării, sunt efectuate 16 runde de transformări. După ultima rundă, se efectuează albirea la ieșire.

Albire

Albirea este o procedură de xoring a datelor cu subchei înainte de prima rundă și după ultima rundă. Această tehnică a fost folosită pentru prima dată în cifrul Khufu / Khare și independent de Ron Rivest în algoritmul de criptare DESX . Joe Killian (NEC) și Phillip Rogaway (Universitatea din California) au arătat că albirea face ca sarcina de căutare exhaustivă a cheilor în DESX [3] să fie mai dificilă . Dezvoltatorii Twofish susțin [4] că albirea Twofish complică semnificativ sarcina de a ghici cheia, deoarece criptoanalistul nu poate afla ce date intră în intrarea funcției F din prima rundă.

Au existat însă și aspecte negative. Un studiu interesant a fost realizat de specialiști de la Centrul de Cercetare IBM. [5] Ei au implementat algoritmul Twofish pe un card inteligent CMOS tipic și au analizat posibilitatea unui atac folosind Analiza Putere Diferenţială (DPA). Procedura de albire a intrării a fost atacată, deoarece folosește direct xor de subchei cu datele de intrare. Drept urmare, cercetătorii au arătat că este posibil să se calculeze complet o cheie de 128 de biți analizând doar 100 de operațiuni aleatorii de criptare bloc.

Funcția g

Funcția g este baza algoritmului Twofish. Intrarea funcției este un număr X pe 32 de biți, care este apoi împărțit în patru octeți x0, x1, x2, x3. Fiecare dintre octeții rezultați este trecut prin caseta S. (Trebuie remarcat faptul că casetele S din algoritm nu sunt fixe, ci depind de cheie). Cei 4 octeți rezultați la ieșirile cutiilor S sunt interpretați ca un vector cu patru componente. Acest vector este înmulțit cu o matrice MDS fixă 4x4 (distanță maximă separabilă), iar calculele sunt efectuate în câmpul Galois modulo polinomul ireductibil. $GF(2^{8})$ $x^{8}+x^{6}+x^{5}+x^{3}+1$

O matrice MDS este o astfel de matrice peste un câmp finit K, încât dacă o luăm ca o matrice a unei transformări liniare din spațiu în spațiu , atunci oricare doi vectori din spațiul de forma (x, f(x)) vor au cel puţin m + 1 diferenţe de componente . Adică, un set de vectori de forma (x, f(x)) formează un cod cu proprietatea codului separabil la distanță maximă. Un astfel de cod, de exemplu, este codul Reed-Solomon . $f(x)=(MDS)x$ $K^n$ $K^{m}$ $K^{{n+m}}$

În Twofish, proprietatea de diversitate maximă a matricei MDS înseamnă că numărul total de octeți în schimbare ai vectorului a și ai vectorului este de cel puțin cinci. Cu alte cuvinte, orice modificare la doar un octet într-o modifică toți cei patru octeți din b. $b=(MDS)a$

Transformarea cripto Hadamar (Transformarea Pseudo-Hadamar, PHT)

Transformarea Crypto Hadamard este o transformare reversibilă a unui șir de biți cu lungimea 2n. Șirul este împărțit în două părți a și b de aceeași lungime în n biți. Transformarea se calculează după cum urmează:

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

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

Această operație este adesea folosită pentru a „împrăștia” codul (de exemplu, în cifrul SAFER ).

În Twofish, această transformare este utilizată atunci când se amestecă rezultatele a două funcții g (n = 32).

Rotiți cu 1 bit

În fiecare rundă, cele două blocuri drepte de 32 de biți care sunt xored cu rezultatele funcției F sunt rotite suplimentar cu un bit. Al treilea bloc este deplasat înainte de operația xor, al patrulea bloc după. Aceste schimbări sunt adăugate în mod deliberat pentru a rupe alinierea octeților care este inerentă în cutiile S și înmulțirile matricei MDS. Cu toate acestea, cifrul încetează să fie complet simetric, deoarece în timpul criptării și decriptării schimbările ar trebui să fie efectuate în direcții opuse.

Generare cheie

Twofish este proiectat să funcționeze cu chei de 128, 192 și 256 de biți. Din cheia inițială sunt generate 40 de subchei pe 32 de biți, dintre care primele opt sunt folosite doar în operațiunile de albire de intrare și ieșire, iar restul de 32 sunt folosite în runde de criptare, două subchei pe rundă. O caracteristică a Twofish este că cheia originală este folosită și pentru a schimba algoritmul de criptare în sine, deoarece casetele S utilizate în funcția g nu sunt fixe, ci depind de cheie.

Pentru a forma subchei rotunde, cheia originală M este împărțită cu o permutare de octeți în două blocuri identice și . Apoi, folosind blocul și funcția h, se criptează valoarea 2*i, iar folosind blocul , se criptează valoarea 2*i+1, unde i este numărul rundei curente (0 - 15). Blocurile criptate rezultate sunt amestecate prin cripto-transforma Hadamard și apoi utilizate ca subchei rotunde. $M_{o}$ $Pe mine}$ $M_{o}$ $Pe mine}$

Detalii tehnice

Să luăm în considerare mai detaliat algoritmul pentru generarea subcheilor rotunde, precum și funcția dependentă de cheie g. Atât generarea subcheilor, cât și formarea funcției g în Twofish folosesc o funcție principală: h(X, L 0 , L 1 , … , L k ). Aici X, L 0 , L 1 , … , L k sunt cuvinte de 32 de biți și k = N / 64, unde N este lungimea cheii originale în biți. Rezultatul funcției este un cuvânt de 32 de biți.

Funcția h

Funcția este executată în k pași. Adică pentru o lungime a cheii de 256 de biți vor fi 4 etape, pentru o cheie de 192 de biți - 3 etape, pentru 128 de biți - 2 etape.

La fiecare etapă, cuvântul de intrare pe 32 de biți este împărțit în 4 octeți, iar fiecare octet este supus unei permutări fixe de bit q 0 sau q 1

Rezultatul este reprezentat ca un vector de 4 octeți și înmulțit cu matricea MDS. Calculele sunt efectuate în câmpul Galois GF(2 8 ) modulo polinomul ireductibil . $x^{8}+x^{6}+x^{5}+x^{3}+1$

Matricea MDS are forma:

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

Permutările q 0 și q 1

q 0 și q 1 sunt permutări fixe a 8 biți ale octetului de intrare x.

Octetul x este împărțit în două jumătăți de 4 biți a 0 și b 0 , peste care sunt efectuate următoarele transformări:

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}]

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

Aici este o deplasare ciclică pe 4 biți la dreapta și t 0 , t 1 , t 2 , t 3 sunt înlocuiri de tabel ale numerelor de 4 biți. ${\mbox{ROR}}_{4}$

Pentru q 0 tabelele arată astfel:

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

Pentru q 1 tabelele arată astfel:

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 ]

Generare cheie

Fie M cheia originală, N fie lungimea ei în biți. Subcheile sunt generate după cum urmează:

Cheia originală este împărțită în 8*k octeți , unde k = N / 64. $m_{0},...,m_{{8k-1}}$
Acești 8*k octeți sunt împărțiți în cuvinte de patru octeți, iar în fiecare cuvânt octeții sunt inversați. Rezultatul este 2*k cuvinte pe 32 de biți $M_{i}$

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

Cele 2*k cuvinte de 32 de biți rezultate sunt împărțite în doi vectori cu o dimensiune de k cuvinte de 32 de biți. $Pe mine}$ $M_{o}$

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

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

Subcheile pentru runda a I-a sunt calculate prin formulele:

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

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

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

Funcția g și S -boxes

Functia g este definita in termenii functiei h : . $g(X)=h(X,S)$

Vectorul S , ca și vectorii M e și Mo , este de asemenea format din cheia originală și constă din k cuvinte de 32 de biți. Octeții cheie originali sunt împărțiți în k grupuri de opt octeți. Fiecare astfel de grup este tratat ca un vector cu 8 componente și înmulțit cu o matrice RS fixă de 4×8 octeți. Ca rezultat al înmulțirii, se obține un vector format din patru octeți. Calculele sunt efectuate în câmpul Galois modulo un polinom ireductibil . Matricea RS are forma $GF(2^{8})$ $x^{8}+x^{6}+x^{3}+x^{2}+1$

.

Criptanaliză

Un studiu al Twofish cu un număr redus de runde a arătat că algoritmul are o marjă mare de siguranță și, în comparație cu restul finaliștilor competiției AES, s-a dovedit a fi cel mai persistent. Cu toate acestea, structura sa neobișnuită și complexitatea relativă au ridicat unele îndoieli cu privire la calitatea acestei rezistențe.

Împărțirea cheii originale în două jumătăți în timpul formării subcheilor rotunde a provocat critici. Criptografii Fauzan Mirza și Sean Murphy au sugerat că o astfel de diviziune face posibilă organizarea unui atac conform principiului „împărți și cuceri”, adică împărțirea sarcinii în două similare, dar mai simple [6] . Cu toate acestea, un astfel de atac nu a fost efectiv efectuat.

Pentru 2008, cea mai bună variantă a criptoanalizei Twofish este o variantă a criptoanalizei diferențiale trunchiate, care a fost publicată de Shiho Moriai și Yiqun Lisa Yin în Japonia în 2000 [7] . Ei au arătat că sunt necesare 251 de texte clare potrivite pentru a găsi diferențele necesare . Cu toate acestea, studiile au fost de natură teoretică, nu a fost efectuat niciun atac real. Pe blogul său, creatorul Twofish Bruce Schneier susține că un astfel de atac este imposibil în realitate [8] .

Note

↑ „Announcing Request for Candidate Algorithm Nominations for the Advanced Encryption Standard (AES)” Arhivat 5 iunie 2011 la Wayback Machine . Departamentul de Comerț - Institutul Național de Standarde și Tehnologie - Registrul Federal: 12 septembrie 1997.
↑ Nechvatal J., Barker E., Bassham L., Burr W., Dworkin M., Foti J., Roback E. „Report on the Development of the Advanced Encryption Standard (AES)” Arhivat la 30 decembrie 2010 la Wayback Machine (engleză) . — Institutul Național de Standarde și Tehnologie.
↑ J. Kilian și P. Rogaway „How to Protect DES Against Exhaustive Key Search” Arhivat 11 iunie 2010 la Wayback Machine 2 februarie 2000
^ N. Ferguson, J. Kelsey, B. Schneier, D. Whiting „A Twofish Retreat: Related-Key Attacks Against Reduced-Round Twofish” Arhivat la 19 iulie 2008 la Wayback Machine Twofish Technical Report #6, 14 februarie 2000
↑ Suresh Chari, Charanjit Jutla, Josyula R. Rao, Pankaj Rohatgi „A Cautionary Note Regarding Evaluation of AES Candidates on Smart-Cards” Arhivat 13 octombrie 2012 la Wayback Machine , 1999
↑ Fauzan Mirza, Sean Murphy „An Observation on the Key Schedule of Twofish” Arhivat 21 decembrie 2016 la Wayback Machine - Information Security Group, Royal Holloway, University of London - 26 ianuarie 1999
↑ Shiho Moriai, Yiqun Lisa Yin „Cryptanalysis of Twofish (II)” Arhivat la 1 iunie 2012 la Wayback Machine - Institutul de Economie, Ingineri de Informații și Comunicații
↑ Bruce Schneier „Twofish Cryptanalysis Rumors” Arhivat 9 iunie 2012 pe blogul Wayback Machine

Link -uri

Pagina web Twofish .
Codurile sursă Twofish .
Twofish: A 128-Bit Block Cipher Arhivat 29 august 2008 la Wayback Machine .
Algoritmi de criptare - Finaliștii competiției AES .
Lista de produse care folosesc Twofish .

Criptosisteme simetrice
Cifruri în flux	A3 A5 A8 Decim F-FCSR Cereale HC-256 KCipher-2 MICKEY MUGI ŞTIUCĂ Phelix RC4 Iepure SIGILIU ZĂPADĂ SOSEMANUK Salsa20 STRUMOK Trivium VMPC
Rețeaua Feistel	GOST 28147-89 (Magma) blowfish Camelia CAST-128 CAST-256 CIFERUNICORN-A CIFERUNICORN-E CLEFIA Cobra AFACERE DES DESX DFC E2 ENRUPT FEAL HPC IDEE KASUMI Khafre Khufu LOKI97 MacGuffin MARTE PLASĂ CEȚA1 NewDES NDS RC5 RC6 SEMINTA Simon Sinople lista SM4 Speck CEAI XTEA XXTEA Raiden RTEA Triplu DES Doi pești
Rețeaua SP	Lăcustă 3 căi ABC ARIA AES (Rijndael) Akelarre Anubis BaseKing Bas Omatic Centura CRYPTON Diamant2 grand cru Hierocrypt-3 Hierocrypt-L1 KHAZAD Kalyna Lucifer prezent Curcubeu MAI SIGUR RECHIN PĂTRAT Şarpe trei pești
Alte	BROASCĂ NUSH REDOC SC2000 SHACAL CS-Cipher