MARTE | |
---|---|
Creator | Carolyn Barwick, Don Coppersmith |
Creată | 1998 _ |
publicat | 1998 _ |
Dimensiunea cheii | 128-448 biți |
Dimensiunea blocului | 128 de biți |
Numărul de runde | 32 |
Tip de | Rețeaua Feistel |
MARS este un cifr candidat AES dezvoltat de IBM , care a creat DES la un moment dat . IBM spune că algoritmul MARS se bazează pe cei 25 de ani de experiență criptoanalitică a companiei și, împreună cu puterea sa criptografică ridicată, cifrul permite implementarea eficientă chiar și în limitele cardurilor inteligente .
Don Coppersmith , unul dintre autorii cifrului Lucifer ( DES ), cunoscut pentru o serie de articole despre criptologie, a luat parte la dezvoltarea cifrului : îmbunătățirea structurii cutiilor S împotriva criptoanalizei diferențiale , metoda de multiplicare rapidă a matricei ( Algoritmul Coppersmith-Winograd ), criptoanaliza RSA . În plus față de el, la dezvoltarea algoritmului au luat parte Carolyn Barwick , Edward D'Evignon , Rosario Genaro , Shai Halevi , Charanjit Jutla , Steven M. Matyas Jr. , Luke O'Connor , Mohamed Pereviyan , David Safford , Nevenko Zunich .
Conform regulilor competiției AES , participanții ar putea face modificări minore la algoritmii lor. Profitând de această regulă, autorii MARSa au modificat procedura de extindere a cheii, ceea ce a făcut posibilă reducerea cerințelor pentru non-volatil și RAM . O versiune modificată a algoritmului va fi furnizată mai jos.
Pe baza rezultatelor competiției AES , MARS a ajuns în finală , dar a pierdut în fața lui Rijndael . După anunțarea rezultatelor (19 mai 2000), echipa de dezvoltare și-a format propria opinie cu privire la concursul AES [1] , unde a comentat pretențiile la creația lor.
MARS este acum distribuit în întreaga lume sub o licență fără drepturi de autor .
MARS este un cifru bloc simetric cu o cheie secretă. Dimensiunea blocului pentru criptare este de 128 de biți, dimensiunea cheii poate varia de la 128 la 448 de biți inclusiv (multiplii de 32 de biți). Creatorii au căutat să combine viteza de codificare și puterea cifrului în algoritmul lor. Rezultatul este unul dintre cei mai puternici algoritmi din competiția AES .
Algoritmul este unic prin faptul că a folosit aproape toate tehnologiile existente utilizate în criptoalgoritmi, și anume:
Utilizarea amestecării duble prezintă o dificultate pentru criptoanaliza , pe care unii o atribuie dezavantajelor algoritmului. În același timp, în acest moment nu există atacuri eficiente asupra algoritmului, deși unele chei pot genera subchei slabe.
Autorii cifrului au pornit de la următoarele ipoteze:
Cifrul MARS a folosit următoarele metode de criptare:
Structura algoritmului MARS poate fi descrisă după cum urmează:
În prima fază, fiecare cuvânt de date este suprapus cu un cuvânt cheie, iar apoi sunt opt runde de amestecare conform rețelei Feistel de al treilea tip, împreună cu unele amestecări suplimentare. În fiecare rundă, folosim un cuvânt de date (numit cuvânt sursă) pentru a modifica alte trei cuvinte (numite cuvinte țintă). Tratăm cei patru octeți ai cuvântului original ca indici în două casete S, S 0 și S 1 , fiecare constând din 256 de cuvinte de 32 de biți, apoi XOR sau anexăm datele corespunzătoare din caseta S în alte trei cuvinte.
Dacă cei patru octeți ai cuvântului original sunt b 0 , b 1 , b 2 , b 3 (unde b 0 este primul octet și b 3 este octetul înalt), atunci folosim b 0 , b 2 ca indici în blocul S 0 și octeții b 1 , b 3 , ca indici în S-box S 1 . Mai întâi XOR S 0 la primul cuvânt țintă și apoi adăugați S 1 la același cuvânt. De asemenea, adăugăm S 0 la al doilea cuvânt țintă și blocăm XOR-S 1 la al treilea cuvânt țintă. În cele din urmă, rotim cuvântul original cu 24 de biți spre dreapta.
În runda următoare, rotim cele patru cuvinte pe care le avem: astfel încât primul cuvânt țintă curent devine următorul cuvânt sursă, al doilea cuvânt țintă curent devine primul cuvânt țintă nou, al treilea cuvânt țintă devine următorul al doilea cuvânt țintă și cuvântul sursă curent devine al treilea cuvânt țintă.
Mai mult, după fiecare dintre cele patru runde, adăugăm unul dintre cuvintele țintă înapoi la cuvântul original. Mai exact, după prima și a cincea rundă, adăugăm al treilea cuvânt țintă înapoi la cuvântul original, iar după a doua și a șasea rundă, adăugăm primul cuvânt țintă înapoi la cuvântul original. Motivul acestor operațiuni suplimentare de amestecare este eliminarea câtorva atacuri cripto diferențiale simple în faza de amestecare pentru a rupe simetria în faza de amestecare și a obține un flux rapid.
Pseudocod 1. // Prima suprapunere a unei chei pe date 2. 3. 4. // Apoi 8 reprize de amestecare înainte 5. // folosiți D[0] pentru a modifica D[1]; D[2]; D[3] 6. // accesează 4 S-box 7.8.9.10 _ _ _ 11. // și rotiți cuvântul original la dreapta 12. 13. // faceți și operațiuni suplimentare de amestecare 14. 15. // adaugă D[3] cuvântului original 16. 17. // adaugă D[1] cuvântului original 18. // rotiți matricea D[ ] 19.20 .Nucleul criptografic al MARS este o rețea Feistel de tip 3 care conține 16 runde. În fiecare rundă, folosim funcția E-cheie, care este o combinație de înmulțiri, rotații și apeluri S-box. Funcția preia un cuvânt de date ca intrare și returnează trei cuvinte, cu care operația de adăugare sau XOR la alte trei cuvinte de date va fi efectuată ulterior. În plus, cuvântul sursă este rotit cu 13 biți spre stânga.
Pentru a oferi rezistență serioasă la atacurile cripto, cele trei valori de ieșire ale funcției E (O 1 , O 2 , O 3 ) sunt utilizate în primele opt runde și în ultimele opt runde în ordine diferite. În primele opt runde, adăugăm O 1 și O 2 la primul și, respectiv, al doilea cuvânt țintă și XOR O 3 la al treilea cuvânt țintă. Pentru ultimele opt runde, adăugăm O 1 și O 2 la al treilea și, respectiv, al doilea cuvânt țintă și XOR O 3 la primul cuvânt țintă.
Pseudocod 1. // Efectuați 16 runde de criptare folosind cheia 2. 3. 4. 5. 6. // primele 8 runde de conversie forward 7. 8. 9. // apoi 8 runde de transformare inversă 10. 11. 12. 13. // rotiți matricea D[ ] 14. 15. E-funcțieFuncția E preia un cuvânt de date ca intrare și folosește încă două cuvinte cheie, producând trei cuvinte ca rezultat. În această funcție, folosim trei variabile temporare, notate L, M și R (pentru stânga, mijloc și dreapta).
Inițial, setăm R la valoarea cuvântului original deplasat cu 13 biți la stânga și setăm M la suma cuvintelor originale și primul cuvânt cheie. Apoi folosim primii nouă biți ai lui M ca index pentru una dintre cele 512 cutii S (care se obține prin combinarea S 0 și S 1 prin amestecare de fază) și stocăm în L valoarea cutiei S corespunzătoare.
Apoi înmulțim al doilea cuvânt cheie cu R, memorând valoarea în R. Apoi rotim R cu 5 poziții spre stânga (deci cei 5 biți înalți devin cei 5 biți inferiori ai lui R după rotație). Apoi XOR R în L și, de asemenea, ne uităm la cei cinci biți de jos ai lui R pentru a determina cantitatea de schimbare (de la 0 la 31) și rotim M la stânga cu acea cantitate. Apoi, rotim R cu alte 5 poziții la stânga și XOR L în L. În cele din urmă, ne uităm din nou la cei 5 biți cei mai puțin semnificativi ai lui R ca valoare de rotație și rotim L cu acea cantitate spre stânga. Astfel, rezultatul funcției E este de 3 cuvinte (în ordine): L, M, R.
Pseudocod 1. // folosiți 3 variabile temporare L; M; R 2. //adăugați primul cuvânt cheie 3. // înmulțiți cu al doilea cuvânt cheie, care trebuie să fie par 4. 5. // ia S-box 6. 7. // acești biți descriu cantitatea de rotație ulterioară 8. // prima rotatie prin variabila 9. 10. 11. 12. // acești biți descriu cantitatea de rotație ulterioară 13. // a doua rotație variabilă paisprezece.Amestecarea înapoi este aproape aceeași cu cea înainte, cu excepția faptului că datele sunt procesate în ordine inversă. Adică, dacă am combina mixarea înainte și inversă, astfel încât ieșirile și intrările lor să fie conectate în ordine inversă (D[0] înainte și D[3] invers, D[1] înainte și D[2] invers), atunci nu ar vedea rezultatul amestecării. Ca și în amestecul direct, aici folosim și un cuvânt sursă și trei cuvinte țintă. Luați în considerare primii patru octeți ai cuvântului original: b 0 , b 1 , b 2 , b 3 . Vom folosi b 0 , b 2 ca indice pentru S-box - S 1 , și b 1 b 3 pentru S 0 . Să XOR S 1 [b 0 ] în primul cuvânt țintă, scădem S 0 [b 3 ] din al doilea cuvânt, S 1 [b 2 ] din al treilea cuvânt țintă și apoi XOR S 0 [b 1 ] de asemenea la al treilea cuvânt țintă . În cele din urmă, rotim cuvântul original cu 24 de locuri spre stânga. Pentru runda următoare, rotim cuvintele disponibile astfel încât primul cuvânt țintă curent să devină următorul cuvânt sursă, al doilea cuvânt țintă curent să devină primul cuvânt țintă, al treilea cuvânt țintă curent să devină al doilea cuvânt țintă și cuvântul sursă curent devine al treilea cuvânt țintă. În plus, înainte de una dintre cele patru runde „speciale”, scădem unul dintre cuvintele țintă din cuvântul sursă: înainte de a patra și a opta rundă, scădem primul cuvânt țintă; înainte de a treia și a șaptea rundă, scădem al treilea. cuvântul țintă din cuvântul sursă.
Pseudocod 1. // Faceți 8 reprize de amestecare înapoi 2. 3. // operații suplimentare de amestecare 4. 5. //scăderea D[3] din cuvântul original 6. 7. // scade D[1] din cuvântul original 8. // se referă la cele patru elemente ale S-box-urilor 9. 10. 11. 12. 13. // și rotiți cuvântul original spre stânga paisprezece. 15. // rotiți matricea D[] 16. 17. 18. // Scădere cuvânt cheie 19.20 .Procesul de decodare este inversul procesului de codificare. Codul de decriptare este similar (dar nu identic) cu codul de criptare.
Mixare directă 1. // Suprapunerea cheii inițiale 2. 3. 4. // Apoi faceți 8 runde de amestecare înainte 5. 6. // rotiți matricea D[] 7. 8. // și rotiți cuvântul original la dreapta 9. 10. // accesează 4 elemente ale S-box-urilor 11. 12. 13. 14. 15. // amestecare suplimentară 16. 17. // adaugă D[3] cuvântului original 18. 29. // adaugă D[1] cuvântului original douăzeci. Miez criptografic 1. // Rulați 16 runde folosind tasta de suprapunere 2. 3. // rotiți matricea D[] 4. 5. 6. 7. 8. // ultimele 8 runde în ordine directă 9. 10. 11. // primele 8 runde în ordine inversă 12. 13. 14. 15.
La crearea unui S-box S, elementele sale au fost generate de un generator pseudo-aleatoriu, după care au fost testate pentru diferite proprietăți liniare și diferențiale. S-box-urile pseudo-aleatorie au fost generate cu următorii parametri:
(unde este al-lea cuvânt din ieșirea SHA-1 ) Aici i este considerat a fi un întreg fără semn de 32 de biți, iar c1, c2, c3 sunt niște constante. În implementarea IBM: c1 = 0xb7e15162; c2 = 0x243f6a88 (care sunt notația binară a părții fracționale a și respectiv). c3 a fost schimbat până când au fost găsite cutii S cu proprietăți adecvate. SHA-1 funcționează pe fluxuri de date și folosește little endian.
Proprietăți S-boxProprietăți diferențiale .
XOR | Scădere |
---|---|
Proprietăți liniare
procedura de extindere a cheilor extinde matricea dată de chei k[], constând din n cuvinte de 32 de biți (unde n este un număr întreg de la 4 la 14) într-o matrice K[] de 40 de elemente. Cheia originală nu trebuie să urmeze nicio structură. În plus, procedura de extindere a cheilor garantează următoarele proprietăți ale cuvântului cheie utilizat în multiplicare în miezul criptografic al algoritmului:
Să descriem algoritmul de extindere a cheii.
Cifrul a fost un candidat AES , după câteva modificări minore în timpul primului tur al competiției, legate de o modificare a procedurii de extindere a cheii, MARS a trecut cu succes în finală.
În finala competiției, MARS a avut o serie de neajunsuri:
Pentru toate aceste deficiențe, comisia de experți a evidențiat un avantaj major al acestui algoritm - simetria sa. Pe baza deficiențelor identificate, MARS, așa cum era de așteptat, nu a devenit câștigătorul AES.
După anunțarea rezultatelor competiției AES, echipa MARS și-a lansat recenzia întregii competiții. A pus sub semnul întrebării criteriile de evaluare a competiției. Ei credeau că principala caracteristică a cifrului ar trebui să fie tocmai fiabilitatea și rezistența acestuia (de exemplu, la atacuri cu forță brută ). În plus, au răspuns la fiecare pretenție a juriului la algoritmul lor.
1. MARS nu este potrivit pentru implementarea hardware Printre plângerile referitoare la cifr au fost implementarea sa hardware dificilă, care ar putea duce la povara Internetului, precum și introducerea unor scheme mari, de dimensiuni.
Dezvoltatorii susțin că implementarea lor este capabilă să funcționeze la o viteză de 1,28 Gbps, ceea ce este acceptabil pentru Internet, iar costul cipurilor lor poate fi mare (13 USD pentru un cip de 12 Gbps sau 1 USD pentru un cip de 1 Gbps), dar în prețul va scădea semnificativ în viitor.2. MARS nu este potrivit pentru implementare pe dispozitive cu memorie redusă Pentru implementarea pe carduri SMART, algoritmii au doar 128 de octeți de memorie. Pentru procedura de extindere a cheii, MARS necesită 512 octeți.
Dezvoltatorii cred că nu există niciun motiv pentru a implementa AES pe o resursă atât de vulnerabilă cu memorie scăzută precum cardurile inteligente, deoarece toate aceste resurse pot fi convertite ușor și rapid în sisteme cu chei publice.3. MARS nu este potrivit pentru implementare pe FPGA MARS nu este potrivit pentru implementare pe platforme unde rotația nu este permisă (în funcție de factori externi).
Dezvoltatorii observă că această problemă nu este fatală, dar necesită puțin timp pentru a adapta algoritmul la această platformă.4. Extinderea tastei MARS este o operațiune foarte grea
Dezvoltatorii susțin că aceasta este o declarație ridicolă. Ei susțin că au raportul „ideal” între memoria suplimentară per cheie și debit (25 de octeți per cheie)În concluzie, dezvoltatorii își oferă analiza algoritmilor participanților la AES, conform rezultatelor cărora MARS, împreună cu Serpent , a fost cel mai bun candidat pentru titlul de AES. [unu]
În prezent, nu există atacuri eficiente asupra acestui algoritm. Deși are câteva puncte slabe [1] :
Criptosisteme simetrice | |
---|---|
Cifruri în flux | |
Rețeaua Feistel | |
Rețeaua SP | |
Alte |