Akelarre
Versiunea actuală a paginii nu a fost încă examinată de colaboratori experimentați și poate diferi semnificativ de
versiunea revizuită la 28 martie 2021; verificările necesită
64 de modificări .
Akelarre |
Creator |
Echipa de autori G. Álvarez Marañón, A. Fúster Sabater, D. Guía Martínez, F. Montoya Vitini, A. Peinado Domínguez |
publicat |
1996 _ |
Dimensiunea cheii |
Multiplu de 64 de biți (recomandat - 128 de biți) |
Dimensiunea blocului |
128 de biți |
Numărul de runde |
Oricare (recomandat - 4) |
Tip de |
Rețeaua SP |
Akelarre este un cifru bloc dezvoltat de o echipă de autori spanioli și prezentat la SAC în 1996; combină dezvoltarea de bază a IDEA cu conceptele din RC5 . Numele akelarre este folosit și în bască pentru a se referi la o adunare de vrăjitoare [1] .
Descriere
Akelarre este un cifru bloc de 128 de biți. În acest caz, lungimea cheii este variabilă și trebuie să fie un multiplu de 64 de biți; numărul de treceri de criptare este, de asemenea, un parametru variabil. Valorile optime propuse de autori sunt o cheie de 128 de biți și 4 runde [2] . Funcția de criptare din Akelarre este structural similară cu cea furnizată în IDEA. Cu toate acestea, există o serie de diferențe semnificative între aceste cifruri în general: de exemplu, IDEA folosește o dimensiune a cuvântului de 16 biți, nu de 32 de biți, iar setul de operațiuni primitive utilizat este, de asemenea, diferit. Akelarre se aplică [3] :
Utilizarea unei deplasări ciclice cu un număr variabil de biți determină asemănarea acestui algoritm cu RC5 [4] . Toate operațiile enumerate aparțin unor grupuri algebrice diferite și sunt incompatibile în sensul că legile asociative și distributive nu sunt valabile pentru nicio pereche dintre ele. Acest lucru vă permite să ascundeți toate relațiile existente între textul simplu și textul cifrat și cheie, făcând dificilă criptoanaliza [5] .
Algoritm de operare
Din punct de vedere structural, algoritmul poate fi împărțit în două subpărți:
- Algoritm de criptare/decriptare.
- Algoritm pentru extinderea cheii introduse de utilizator.
Criptare
În primul rând, textul simplu X este împărțit în blocuri de 128 de biți, fiecare dintre acestea fiind împărțit la rândul său în 4 subblocuri X 1 ... X 4 , cărora le este deja aplicată transformarea primară. Întreaga procedură de criptare are loc în trei etape.
- Transformarea de intrare constă în adăugarea modulo a fragmentelor de cheie extinse Ki1 , respectiv Ki4 cu subblocuri X1 , X4 și aplicarea OR exclusiv pe biți (XOR) la fragmentele de cheie extinse Ki2 , Ki3 și subblocuri X2 , X3 . respectiv. Aceste transformări sunt necesare pentru a preveni consecințele unei posibile intrări în intrarea unei secvențe de toate zerourile sau toate cele, precum și pentru a face dificilă atacarea cifrului folosind criptoanaliza diferențială (vezi cheia slabă ).
![2^{32}](https://wikimedia.org/api/rest_v1/media/math/render/svg/a8c222ea8e5f187a2bb499395b6f4a6f38b43633)
- Runde de criptare:
- La începutul fiecărei runde se rotește un bloc de 128 de biți, rezultat din unirea subblocurilor formate ca urmare a transformării de intrare sau a rundei precedente; în a treia rundă ( ) numărul variabil de biți care specifică deplasarea este determinat de biții cel mai puțin semnificativi ai fragmentului de cheie K m1 format ca urmare a procedurii de extindere a cheii.
![r](https://wikimedia.org/api/rest_v1/media/math/render/svg/0d1ecb613aa2984f0576f70f86650b7c2a132538)
![m](https://wikimedia.org/api/rest_v1/media/math/render/svg/0a07d98bb302f3856cbabc47b2b9016692e3f7bc)
![{\displaystyle m=1,2,\ldots ,r}](https://wikimedia.org/api/rest_v1/media/math/render/svg/31ffd4071427cb91ba4975246380c24786e27e75)
- La următoarea etapă, blocul de 128 de biți este din nou împărțit în 4 sub-blocuri de 32 de biți, iar OR pe biți sunt calculate pentru o pereche din primele două și apoi pentru o pereche din ultimele două blocuri. Transformările ulterioare ale blocurilor rezultate C1 , C2 sunt determinate de funcționarea modulului AR (structură de adunare-rotație). Structura modulului constă din două coloane: C 1 este alimentat la intrarea primei, C 2 - a doua. Pentru C 1 :
- Primii 31 de biți ai C1 sunt rotiți la stânga (cantitatea deplasării este determinată de cei mai puțin semnificativi 5 biți ai C2 ) .
- Rezultatul obţinut la pasul precedent se adaugă modulo numărul cu unul dintre fragmentele cheii extinse K m8 .
![2^{32}](https://wikimedia.org/api/rest_v1/media/math/render/svg/a8c222ea8e5f187a2bb499395b6f4a6f38b43633)
- Ultimii 31 de biți ai blocului de ieșire al pasului precedent sunt rotiți la stânga ca în pasul 1.
- Blocul de 32 de biți obținut la pasul anterior este adăugat modulo numărul cu subcheia K m9 în mod similar cu pasul 2.
![2^{32}](https://wikimedia.org/api/rest_v1/media/math/render/svg/a8c222ea8e5f187a2bb499395b6f4a6f38b43633)
- Cei 31 de biți înalți ai blocului de ieșire ai pasului anterior sunt rotiți la stânga ca în pasul 1.
- Blocul de 32 de biți obținut în pasul anterior este adăugat modulo numărul cu subcheia K m10 ca în pasul 2.
![2^{32}](https://wikimedia.org/api/rest_v1/media/math/render/svg/a8c222ea8e5f187a2bb499395b6f4a6f38b43633)
- Pașii de la 3 la 6 sunt repeți până când au fost efectuate un total de 7 schimburi și 6 adăugări de subchei.
C 02 se procesează în mod similar , folosind doar tastele K m2 ... K m7 .
Din blocurile D 1 , D 2 obținute ca urmare a funcționării modulului , prin adăugarea cu blocurile formate prin divizarea blocului de 128 de biți la începutul rundei, se formează 4 valori de ieșire ale rundei ( fiecare dintre X1 , X3 este adăugat la D1 şi fiecare dintre X2 , X4- cu D2 ) . Aplicarea unei deplasări pe biți nu la întregul bloc, ci doar la 31 de biți se face pentru a evita posibila identitate a rezultatelor de ieșire și de intrare, ceea ce poate fi observat la utilizarea numerelor compuse
[6] .
- În timpul transformării finale, subblocul bloc de 128 de biți format prin concatenarea blocului de 128 de biți obținut după runda finală este deplasat ciclic la stânga cu numărul de biți determinat de ultimii 7 biți ai subcheii K f1 , după căruia blocul rezultat este împărțit în subblocuri de 32 de biți, cărora li se aplică operații asemănătoare cu cele ale blocului de intrare.transformări, dar cu tastele K f2 …K f5 [7] .
Decriptare
Algoritmul de decriptare este organizat în esență în același mod ca cel folosit pentru criptare, doar subcheile sunt deja generate pe baza cheilor de criptare. Corespondența dintre cheile pentru criptare și pentru decriptare este următoarea (aici, transformarea inițială este înțeleasă ca runda zero, iar transformarea finală este runda (r + 1)) [8] :
Rundă
|
Cheile utilizate în criptare
|
Cheile folosite la decriptare
|
Transformare inițială
|
|
|
1-a rundă
|
|
|
a 2-a rundă
|
|
|
runda a m-a
|
|
|
runda r-a
|
|
|
Transformare finală
|
|
|
Extensie cheie
Pentru ca algoritmul să funcționeze, este necesară o cheie formată din cel puțin 22 de sub-blocuri de 32 de biți (704 de biți) [9] . Următoarea descriere corespunde aplicării algoritmului unei chei de 128 de biți:
- Cheia utilizator este împărțită în 8 părți de 16 biți k 1 ... k 8 .
- Fiecare fragment individual este pătrat pentru a obține o valoare de 32 de biți, iar însumarea modulo a numărului de valori rezultate se realizează separat cu fiecare dintre constantele a 1 , a 2 ; ca urmare, pe baza fiecăreia dintre cheile inițiale k i1 , se formează două valori temporare K ti și K'ti . Constantele ar trebui alese pentru a evita posibila formare a unei chei formate doar din zerouri. Autorii au propus un 1 =A49ED284H și un 2 =73503DEH [10] .
![2^{32}](https://wikimedia.org/api/rest_v1/media/math/render/svg/a8c222ea8e5f187a2bb499395b6f4a6f38b43633)
- Din valorile temporare obținute la pasul anterior se formează fragmente ale cheii preliminare extinse K e1 ...K e8 . Fiecare dintre aceste fragmente este rezultatul concatenării a 8 biți low și 8 high K'ti , precum și a 8 low și 8 high biți K ti ; Cei 16 biți situați în mijlocul fiecăreia dintre valorile temporare sunt procesați într-o manieră similară procesării lui k 1 ... k 8 pentru a obține noi valori ale fragmentelor de cheie extinse [11] .
- Cheile utilizate în transformarea inițială ( K i1 …K i4 ), funcționarea modulului AR ( K m1 … K m13 pentru fiecare din m runde) și transformarea finală ( K f1 … K f5 ) se completează pe rând cu valorile K e1 formate în timpul funcționării algoritmului …K e8 [12] .
Sustenabilitate
Deja la un an de la prezentarea cifrului, lucrarea lui Niels Ferguson și Bruce Schneier a efectuat un atac care permite spargerea pe baza unui eșantion de cel mult 100 de texte clare. Atacul are loc în 4 etape: în primele două, conversiile inițiale și finale ale biților de subcheie sunt restaurate, iar următoarele două folosesc vulnerabilitățile schemei de expansiune a cheilor și cu o creștere a numărului de runde în algoritm, cantitatea de informații care poate fi obținută despre funcționarea schemei crește, de asemenea, brusc. Complexitatea organizării modulului AR datorită proprietăților sale (proprietăți de paritate) nu complică deloc hacking -ul [13] . În aceeași lucrare, este dat un alt atac, în care, în plus, utilizarea caracteristicii diferențiale a algoritmului face posibilă reducerea numărului de operații necesare în final la .
![2^{32}](https://wikimedia.org/api/rest_v1/media/math/render/svg/a8c222ea8e5f187a2bb499395b6f4a6f38b43633)
O altă lucrare în care criptanaliza Akelarre a fost realizată cu succes este a lui Lars Knudsen și Vincent Ridgeman. Ele descriu două atacuri posibile: unul se bazează pe utilizarea textului simplu , celălalt vă permite să dezvăluiți cheia folosind doar textul cifrat și unele informații despre textul simplu - în special, este suficient să știți că acesta este un text în limba engleză ASCII . La fel ca atacurile propuse în lucrarea lui Ferguson și Schneier, atacurile propuse în această lucrare nu depind de numărul de runde ale algoritmului sau de dimensiunea cheii, iar atacul doar cu text cifrat este printre cele mai aplicabile practic, întrucât deja o singură ascultare a canalului este suficientă pentru implementarea lui [14] .
Înțeles
Conceput ca un algoritm care combină cu succes elemente ale a doi algoritmi fiabili și cunoscuți IDEA și RC5 și are o arhitectură complexă, Akelarre nu a demonstrat o rezistență criptografică ridicată, ceea ce a arătat clar că combinarea componentelor a doi algoritmi bine protejați nu rezultă întotdeauna într-unul nou de încredere [15] . După cum se menționează în titlul uneia dintre lucrările care au investigat algoritmul [16] :
Două plusuri dau uneori un minus.
Text original (engleză)
[ arataascunde]
Două drepturi greșesc uneori.
Modificări
După criptoanaliza de succes a lui Akelarre, designerii săi au introdus o variantă actualizată numită Ake98 . Acest cifru diferă de noua casetă AR (Addition-Rotation box) a lui Akelarre originală prin permutarea cuvintelor efectuată la sfârșitul trecerii de criptare, precum și prin adăugarea de subchei la începutul fiecărei treceri de criptare. În același timp, parametri precum dimensiunea cheii și dimensiunea blocului au rămas, ca și înainte, ajustabili, dar dimensiunea minimă a acestora nu a fost definită de creatori [17] . Modulul AR funcționează în noua versiune ca un generator de numere pseudoaleatoare .
În 2004, Jorge Nakaara Jr. și Daniel Santana de Freita au găsit clase mari de chei slabe pentru Ake98. Aceste chei slabe permit analiza mai rapidă decât forța brută , folosind doar 71 de bucăți de text cunoscute pentru treceri de criptare de 11,5 în Ake98. În plus, în aceeași lucrare, a fost efectuată o evaluare a performanței algoritmului, care a arătat că, deși pentru numărul de runde de 25,5 sau mai mult, algoritmul nu are chei slabe, se dovedește a fi de 4 ori mai lent. decât IDEA , de 8 ori mai lent decât AES , și de 14 ori - RC6 [18] .
Note
- ↑ Stamp M. et al, 2007 , p. 160.
- ↑ Panasenko S., 2009 , p. 101.
- ↑ Álvarez MG și colab., 1996 , p. 2-3.
- ↑ Panasenko S., 2009 , p. 99.
- ↑ Álvarez MG și colab., 1996 , p. 2.
- ↑ Álvarez MG și colab., 1996 , p. 5-6.
- ↑ Panasenko S., 2009 , p. 98-100.
- ↑ Álvarez MG și colab., 1996 , p. 6.
- ↑ Álvarez MG și colab., 1996 , p. 7.
- ↑ Álvarez MG și colab., 1996 , p. 7-8.
- ↑ Panasenko S., 2009 , p. 101-102.
- ↑ Ferguson N. și colab., 1997 , p. 207-208.
- ↑ Ferguson N. și colab., 1997 , p. 210-211.
- ↑ Panasenko S., 2009 , p. 102-103.
- ↑ Knudsen L. și colab., 1997 , p. 223.
- ↑ Panasenko S., 2009 , p. 103.
- ↑ Júnior J. et al, 2005 , p. 208.
- ↑ Júnior J. et al, 2005 , p. 213-214.
Literatură
- Álvarez MG, Fúster SA, Guía MD, Montoya VF, Peinado DA Akelarre: a New Block Cipher Algorithm // SAC'96, Third Annual Workshop on Selected Areas in Cryptography - Queen's University, Kingston, Ontario, 1996, Proceedings. - 1996. - S. 1-14 .
- Panasenko S.P. Capitolul 3 // Algoritmi de criptare. Carte de referință specială - Sankt Petersburg. : BHV-SPb , 2009. - S. 97-103. — 576 p. — ISBN 978-5-9775-0319-8
- Ferguson N., Schneier B. Cryptanalysis of Akelarre // SAC'97: Fourth Annual Workshop on Selected Areas in Cryptography, Universitatea Carleton, Ottawa, 1997, Proceedings. - 1997. - S. 201-212 .
- Knudsen LR, Rijmen V. Two Rights Sometimes Make a Wrong // SAC'97: Fourth Annual Workshop on Selected Areas in Cryptography, Universitatea Carleton, Ottawa, 1997, Proceedings. - 1997. - S. 213-223 .
- Júnior J. N. , Freitas D. S. Cryptanalysis of Ake98 (english) // Progress in Cryptology - INDOCRYPT 2004 : 5th International Conference on Cryptology in India, Chennai, India, December 20-22, 2004. Proceedings / A. Berlin Viteautthana , K. , Heidelberg , New York, NY , Londra [etc.] : Springer Berlin Heidelberg , 2005. - P. 206-217. — 431 p. - ( Note de curs în Informatică ; Vol. 3348) - ISBN 978-3-540-24130-0 - ISSN 0302-9743 ; 1611-3349 - doi:10.1007/978-3-540-30556-9_17
- Stamp M., Low MR Criptanaliza aplicată: ruperea cifrurilor în lumea reală. - John Wiley & Sons, Inc., Hoboken, New Jersey, 2007. - P. 160. - ISBN 978-0-470-11486-5 .