MARS (kryptografie)
| MARS | |
|---|---|
| Tvůrce | Carolyn Barwick, Don Coppersmith |
| Vytvořeno | 1998 _ |
| zveřejněno | 1998 _ |
| Velikost klíče | 128-448 bitů |
| Velikost bloku | 128 bit |
| Počet kol | 32 |
| Typ | Síť Feistel |
MARS je kandidátská šifra AES vyvinutá společností IBM , která svého času vytvořila DES . IBM říká , že algoritmus MARS čerpá z 25 let zkušeností firmy v oblasti kryptoanalytiky a spolu s vysokou kryptografickou silou umožňuje šifra efektivní implementaci i v rámci omezení čipových karet .
Na vývoji šifry se podílel Don Coppersmith , jeden z autorů luciferské šifry ( DES ), známý řadou článků o kryptologii : zlepšení struktury S-boxů proti diferenciální kryptoanalýze , metoda rychlého násobení matic ( Coppersmith-Winogradův algoritmus ), kryptoanalýza RSA . Kromě něj se na vývoji algoritmu podíleli Carolyn Barwick , Edward D'Evignon , Rosario Genaro , Shai Halevi , Charanjit Jutla , Steven M. Matyas Jr. , Luke O'Connor , Mohamed Perevyan , David Safford , Nevenko Zunich .
Podle pravidel soutěže AES mohli účastníci provést drobné změny ve svých algoritmech. S využitím tohoto pravidla autoři MARSa změnili klíčový postup rozšiřování, což umožnilo snížit požadavky na energeticky nezávislou a RAM . Upravená verze algoritmu bude poskytnuta níže.
Na základě výsledků soutěže AES se MARS probojoval do finále, ale prohrál s Rijndaelem . Po vyhlášení výsledků (19. května 2000) si vývojový tým vytvořil vlastní názor na soutěž AES [1] , kde se vyjádřil k nárokům na jejich duchovní dítě.
MARS je nyní celosvětově distribuován pod bezplatnou licencí .
Stručný popis algoritmu
MARS je bloková symetrická šifra s tajným klíčem. Velikost bloku pro šifrování je 128 bitů, velikost klíče se může lišit od 128 do 448 bitů včetně (násobky 32 bitů). Tvůrci se ve svém algoritmu snažili spojit rychlost kódování a sílu šifry. Výsledkem je jeden z nejsilnějších algoritmů v soutěži AES .
Algoritmus je jedinečný v tom, že využívá téměř všechny existující technologie používané v kryptoalgoritmech, a to:
- nejjednodušší operace ( sčítání , odčítání , vylučování nebo )
- suplování pomocí substituční tabulky
- pevný cyklický posun
- datově závislý cyklický posun
- modul násobení 2 32
- bělení klíčů
Použití dvojitého míchání představuje obtíž pro kryptoanalýzu , kterou někteří připisují nevýhodám algoritmu. Současně v tuto chvíli neexistují žádné účinné útoky na algoritmus, ačkoli některé klíče mohou generovat slabé podklíče.
Struktura algoritmu
Autoři šifry vycházeli z následujících předpokladů:
- Volba operací . MARS byl navržen pro použití na nejpokročilejších počítačích té doby. Aby bylo dosaženo co nejlepšího obranného výkonu, byly do něj zahrnuty nejvíce „silné operace“ v nich podporované. To umožnilo větší poměr securityper-instruction pro různé implementace šifry.
- Struktura šifry . Dvacet let zkušeností v oblasti kryptografie přivedlo tvůrce algoritmu k myšlence, že každé kolo šifrování hraje roli v zajištění bezpečnosti šifry. Zejména můžeme vidět, že první a poslední kolo se obvykle velmi liší od středních ("centrálních") kol algoritmu, pokud jde o ochranu před kryptanalytickými útoky. Při vytváření MARSa byla tedy použita smíšená struktura, kde se první a poslední kolo šifrování výrazně liší od těch středních.
- Analýza . S největší pravděpodobností bude algoritmus s heterogenní strukturou lépe odolávat kryptoanalytickým metodám budoucnosti než algoritmus se všemi identickými koly. Vývojáři algoritmu MARS mu dali vysoce heterogenní strukturu - kola algoritmu se od sebe velmi liší.
Šifra MARS používala následující metody šifrování:
- Práce s 32bitovými slovy . Všechny operace platí pro 32bitová slova. to znamená, že všechny původní informace jsou rozděleny do bloků po 32 bitech. (pokud se ukázalo, že blok je kratší, pak byl doplněn na 32 bitů)
- Síť Feistel . Tvůrci šifry věřili, že jde o nejlepší kombinaci rychlosti šifrování a šifrovací síly. MARS používá síť Feistel typu 3.
- Symetrie algoritmu . Pro odolnost šifry vůči různým útokům byla všechna její kola provedena zcela symetricky , to znamená, že druhá část kola je zrcadlovým opakováním její první části.
Strukturu algoritmu MARS lze popsat následovně:
- Předklíčování: 32bitové podbloky A, B, C, D jsou překryty 4 fragmenty rozšířeného klíče k 0 ...k 3 pomocí modulo 2 32 ;
- Provádí se 8 kol přímého míchání (bez účasti šifrovacího klíče);
- Je provedeno 8 kol přímé konverze kryptoměn;
- Je provedeno 8 kol reverzní krypto transformace; [2]
- Je provedeno 8 kol zpětného míchání, rovněž bez účasti šifrovacího klíče;
- Konečné překrytí fragmentů rozšířeného klíče k 36 ...k 39 operací odčítání modulo 2 32 .
Přímé míchání
V první fázi je každé datové slovo překryto klíčovým slovem a poté následuje osm kol míchání podle Feistelovy sítě třetího typu spolu s nějakým dalším mícháním. V každém kole používáme jedno datové slovo (nazývané zdrojové slovo) k úpravě tří dalších slov (nazývaných cílová slova). Zacházíme se čtyřmi bajty původního slova jako s indexy do dvou S-boxů, S 0 a S 1 , z nichž každý se skládá z 256 32-bitových slov, a pak XOR nebo připojujeme odpovídající data S-boxu do tří dalších slov.
Pokud jsou čtyři bajty původního slova b 0 , b 1 , b 2 , b 3 (kde b 0 je první bajt a b 3 je horní bajt), pak použijeme b 0 , b 2 jako indexy do bloku S 0 a bajty bi , b3 , jako indexy v S- boxu Si . Nejprve XOR S 0 k prvnímu cílovému slovu a poté přidejte S 1 ke stejnému slovu. Také přidáme S 0 ke druhému cílovému slovu a blokujeme XOR-S 1 ke třetímu cílovému slovu. Nakonec původní slovo otočíme o 24 bitů doprava.
V dalším kole střídáme čtyři slova, která máme: takže aktuální první cílové slovo se stane dalším zdrojovým slovem, aktuální druhé cílové slovo se stane novým prvním cílovým slovem, třetí cílové slovo se stane dalším druhým cílovým slovem a aktuální zdrojové slovo se stane třetím cílovým slovem.
Navíc po každém ze čtyř kol přidáme jedno z cílových slov zpět k původnímu slovu. Konkrétně po prvním a pátém kole přidáme třetí cílové slovo zpět k původnímu slovu a po druhém a šestém kole přidáme první cílové slovo zpět k původnímu slovu. Důvodem těchto dodatečných směšovacích operací je eliminace několika jednoduchých diferenciálních kryptografických útoků ve fázi směšování, aby se narušila symetrie ve fázi směšování a dosáhlo se rychlého toku.
Pseudokód 1. // První překrytí klíče na datech 2. 3. 4. // Poté 8 kol míchání dopředu 5. // použijte D[0] k úpravě D[1]; D[2]; D[3] 6. // přístup ke 4 S-boxům 7.8.9.10 _ _ _ 11. // a otočte původní slovo doprava 12. 13. // také provádět další operace míchání 14. 15. // přidejte D[3] k původnímu slovu 16. 17. // přidejte D[1] k původnímu slovu 18. // otočení pole D[ ] 19:20 .
![D \left [ i \right ] = D[i] + K[i]](https://wikimedia.org/api/rest_v1/media/math/render/svg/02f9be5ab65e74f957e4dcde25f1b321cb72b306)
![D \left [1 \right ] = D[1] \oplus S0[ ~nízký ~bajt ~z ~D[0] ]](https://wikimedia.org/api/rest_v1/media/math/render/svg/3f42bdf438ccf944072d0d33f55990aafe44d06a)
![D \left [ 1 \right ] = D[1] + S1[ ~2. ~bajt ~z ~D[0] ]](https://wikimedia.org/api/rest_v1/media/math/render/svg/3b0bb206e0601aa738c49f122aa86c4cf6bb487e)
![D \left [ 2 \right ] = D[2] + S0[ ~3. ~bajt ~z ~D[0] ]](https://wikimedia.org/api/rest_v1/media/math/render/svg/82ca4ac4596b09db2cf2ede73d3cc7bf06053756)
![D[3] = D[3] \oplus S1[ ~vysoký ~bajt ~z ~D[0] ]](https://wikimedia.org/api/rest_v1/media/math/render/svg/0bbffc19bb1e158e418c8414c4512f502f381bc7)
![D[0] = D[0]\ggg 24](https://wikimedia.org/api/rest_v1/media/math/render/svg/dec526b6f2b441133d738f8e4d1551828449a4f0)
![D \left [ 0 \right ] = D[0] + D[3]](https://wikimedia.org/api/rest_v1/media/math/render/svg/b1fea1e500d7ecd4abc0332f50a058f33a2bbe56)
![D \left [0 \right ] = D[0] + D[1]](https://wikimedia.org/api/rest_v1/media/math/render/svg/8057418f0f6bdee65f0022fa9ccb1f76648eeced)
![(D[3]; D[2]; D[1]; D[0]) \leftarrow (D[0]; D[3]; D[2]; D[1])](https://wikimedia.org/api/rest_v1/media/math/render/svg/3e133a96e71f3a374a44a870994e1553444241a0)
Kryptografické jádro
Kryptografickým jádrem MARS je síť Feistel typu 3 obsahující 16 nábojů. V každém kole používáme klíčovou E-funkci, což je kombinace násobení, rotace a volání S-boxu. Funkce vezme jedno slovo dat jako vstup a vrátí tři slova, se kterými se následně provede operace sčítání nebo XOR k dalším třem slovům dat. Zdrojové slovo je navíc otočeno o 13 bitů doleva.
Aby byla zajištěna vážná odolnost vůči kryptografickým útokům, jsou tři výstupní hodnoty E-funkce (O 1 , O 2 , O 3 ) použity v prvních osmi kolech a v posledních osmi kolech v různém pořadí. V prvních osmi kolech přidáme O 1 a O 2 k prvnímu a druhému cílovému slovu a XOR O 3 ke třetímu cílovému slovu. V posledních osmi kolech přidáme O 1 a O 2 ke třetímu a druhému cílovému slovu a XOR O 3 k prvnímu cílovému slovu.
Pseudokód 1. // Proveďte 16 kol šifrování pomocí klíče 2. 3. 4. 5. 6. // prvních 8 kol dopředné konverze 7. 8. 9. // pak 8 kol inverzní transformace 10. 11. 12. 13. // otočení pole D[] 14. 15. E-funkce
![(out1; ~out2; ~out3) ~= ~E-funkce(D[0]; ~K[2i + 4]; ~K[2i + 5])](https://wikimedia.org/api/rest_v1/media/math/render/svg/f2fbab177474c4d896e6c283787115eb9567b607)
![D[0] = D[0]\lll 13](https://wikimedia.org/api/rest_v1/media/math/render/svg/32e9e2d765ed0d34ca13a62d6ab179704df608b7)
![D[2] = D \left [ 2 \right ] + out2](https://wikimedia.org/api/rest_v1/media/math/render/svg/2698710885797744f0e83cc2901eb93f1e75fb10)
![D[1] = D \left [ 1 \right ] + out1](https://wikimedia.org/api/rest_v1/media/math/render/svg/73cf0f906a1462d5efb4a0ce388d99e513a02ec5)
![D[3] = D[3] \oplus out3](https://wikimedia.org/api/rest_v1/media/math/render/svg/b8cf9cadd3690d0fadb6367a9ff7560bc17b0603)
![D[3] = D \left [ 3 \right ] + out1](https://wikimedia.org/api/rest_v1/media/math/render/svg/640d7283ff04f5ef3a3eeb27a38629337c87bc49)
![D[1] = D[1] \oplus out3](https://wikimedia.org/api/rest_v1/media/math/render/svg/3849e825dc5db0af082e832ba8712282f2aacbbf)
![(D[3]; ~D[2]; ~D[1]; ~D[0]) \leftarrow (D[0]; ~D[3]; ~D[2]; ~D[1])](https://wikimedia.org/api/rest_v1/media/math/render/svg/5628dd18018a505a92b160e262e903336629cf37)
E-funkce bere jedno slovo dat jako vstup a používá další dvě klíčová slova, čímž vytváří tři slova jako výstup. V této funkci používáme tři dočasné proměnné, označené L, M a R (pro levou, střední a pravou).
Zpočátku nastavíme R na hodnotu původního slova posunutou o 13 bitů doleva a nastavíme M na součet původních slov a prvního klíčového slova. Potom použijeme prvních devět bitů M jako index k jednomu z 512 S-boxů (který se získá spojením S 0 a S 1 fázovým mícháním) a uložíme do L hodnotu odpovídajícího S-boxu.
Poté vynásobíme druhé klíčové slovo R, přičemž hodnotu uložíme do R. Poté R otočíme o 5 pozic doleva (takže z 5 vysokých bitů se po otočení stane 5 nízkých bitů R). Pak XOR R do L a také se podíváme na spodních pět bitů R, abychom určili velikost posunu (od 0 do 31), a otočíme M doleva o tuto hodnotu. Dále otočíme R o dalších 5 pozic doleva a XOR L do L. Nakonec se znovu podíváme na 5 nejméně významných bitů R jako velikost rotace a otočíme L o tuto hodnotu doleva. Výsledkem E-funkce jsou tedy 3 slova (v pořadí): L, M, R.
Pseudokód 1. // použijte 3 dočasné proměnné L; M; R 2. //přidejte první klíčové slovo 3. // vynásobte druhým klíčovým slovem, které musí být sudé 4. 5. // vezmi S-box 6. 7. // tyto bity popisují velikost následné rotace 8. // první otočení proměnnou 9. 10. 11. 12. // tyto bity popisují velikost následné rotace 13. // druhá proměnná rotace čtrnáct.
![L = S \left [ i \right ]](https://wikimedia.org/api/rest_v1/media/math/render/svg/27b0821eba78bf8a29bb5f917637eb7704a6b782)
Reverzní míchání
Zpětné náhodné přehrávání je téměř stejné jako náhodné přehrávání dopředu, kromě skutečnosti, že data jsou zpracovávána v opačném pořadí. To znamená, že pokud bychom kombinovali míchání vpřed a vzad tak, že jejich výstupy a vstupy by byly zapojeny v obráceném pořadí (D[0] vpřed a D[3] vzad, D[1] vpřed a D[2] vzad), pak neuvidí výsledek míchání. Stejně jako u přímého míchání i zde používáme jedno zdrojové slovo a tři cílová slova. Uvažujme první čtyři bajty původního slova: b 0 , b 1 , b 2 , b 3 . Použijeme b 0 , b 2 jako index k S-boxu - S 1 a b 1 b 3 pro S 0 . Dejme XOR S 1 [b 0 ] do prvního cílového slova, odečteme S 0 [b 3 ] od druhého slova, odečteme S 1 [b 2 ] od třetího cílového slova a pak XOR S 0 [b 1 ] také na třetí cílové slovo. Nakonec původní slovo otočíme o 24 míst doleva. Pro další kolo střídáme dostupná slova tak, aby se aktuální první cílové slovo stalo dalším zdrojovým slovem, aktuální druhé cílové slovo se stalo prvním cílovým slovem, aktuální třetí cílové slovo se stalo druhým cílovým slovem a aktuální zdrojové slovo se stává třetím cílovým slovem. Před jedním ze čtyř „speciálních“ kol navíc odečteme jedno z cílových slov od zdrojového slova: před čtvrtým a osmým kolem odečteme první cílové slovo, před třetím a sedmým kolem odečteme třetí cílové slovo ze zdrojového slova.
Pseudokód 1. // Proveďte 8 kol zpětného míchání 2. 3. // další operace míchání 4. 5. //odečteme D[3] od původního slova 6. 7. // odečtěte D[1] od původního slova 8. // odkazují na čtyři prvky S-boxů 9. 10. 11. 12. 13. // a otočte původní slovo doleva čtrnáct. 15. // otočení pole D[] 16. 17. 18. // Odečtěte klíčové slovo 19:20 .
![D[0] = D[0] - ~D[3]](https://wikimedia.org/api/rest_v1/media/math/render/svg/cd2630c477895e2024e554d60a4dec1b1eaac435)
![D[0] = D[0] - ~D[1]](https://wikimedia.org/api/rest_v1/media/math/render/svg/a8dc73e6c1178cb1b94d62f9a70283485ac13422)
![D[1] = D[1] \oplus S1[ ~nízký ~bajt ~z ~D[0] ]](https://wikimedia.org/api/rest_v1/media/math/render/svg/94c9f9a4913618d3d97acf4e913f509d9e7a67c2)
![D[2] = D[2] - ~S0[ ~vysoký ~bajt ~z ~D[0] ]](https://wikimedia.org/api/rest_v1/media/math/render/svg/8dbfbd4707d67cc35b31bd1f561d49ef60ca597f)
![D[3] = D[3] \oplus S1[ ~3. ~bajt ~z ~D[0] ]](https://wikimedia.org/api/rest_v1/media/math/render/svg/c9ec09b6fc86e50326fa3c47a25fbd2bedafc679)
![D[3] = D[3] - ~S0[ ~2. ~bajt ~z ~D[0] ]](https://wikimedia.org/api/rest_v1/media/math/render/svg/3de1da25219ee6cbe3a70e070cf2000f945df8d7)
![D[0] = D[0]\lll 24](https://wikimedia.org/api/rest_v1/media/math/render/svg/116afd1161f0e477a819b1cba6feecc9ec8adc81)
![D[i] = D[i] - ~K[36 + i]](https://wikimedia.org/api/rest_v1/media/math/render/svg/a0e51b923445a70926fc5eeb37549700bd66b2a9)
Dešifrování
Proces dekódování je opakem procesu kódování. Dešifrovací kód je podobný (ale ne totožný) s šifrovacím kódem.
Přímé míchání 1. // Počáteční překrytí klíče 2. 3. 4. // Poté proveďte 8 kol míchání dopředu 5. 6. // otočení pole D[] 7. 8. // a otočte původní slovo doprava 9. 10. // přístup ke 4 prvkům S-boxů 11. 12. 13. 14. 15. // dodatečné míchání 16. 17. // přidat D[3] k původnímu slovu 18. 29. // přidat D[1] k původnímu slovu dvacet. Kryptografické jádro 1. // Spusťte 16 kol pomocí překryvného klíče 2. 3. // otočení pole D[] 4. 5. 6. 7. 8. // posledních 8 kol v přímém pořadí 9. 10. 11. // prvních 8 kol v opačném pořadí 12. 13. 14. 15.![D\left [ i \right ] = D[i] + K[36 + i]](https://wikimedia.org/api/rest_v1/media/math/render/svg/05816b034a3981320cf2f59ad592725bd579594e)
![(D[3]; ~D[2]; ~D[1]; ~D[0]) \leftarrow (D[2]; ~D[1]; ~D[0]; ~D[3])](https://wikimedia.org/api/rest_v1/media/math/render/svg/a6ce2e6f9c02acb2bfab1856e692e9e643eb1e7e)
![D[3] = D[3] \oplus S0[ ~2. ~bajt ~z ~D[0] ]](https://wikimedia.org/api/rest_v1/media/math/render/svg/fc2fcda2a7b88a743d9eeb98029a4c3f1b8084a9)
![D[3] = D[3] + S1[ ~3. ~bajt ~z ~D[0] ]](https://wikimedia.org/api/rest_v1/media/math/render/svg/38891cf4535cd44fb5e3795a989f3c2d213b4405)
![D[2] = D[2] + S0[ ~vysoký ~bajt ~z ~D[0] ]](https://wikimedia.org/api/rest_v1/media/math/render/svg/a318b13411e4bd1ac0e2a70c1bc8b48027d21257)
![D[0] = D\levá [ 0 \vpravo ] + D[3]](https://wikimedia.org/api/rest_v1/media/math/render/svg/f250d5efe5a0aceaa03b6d8b92ce247e40296ee4)
![D[0] = D\levá [ 0 \vpravo ] + D[1]](https://wikimedia.org/api/rest_v1/media/math/render/svg/61f2cd6d74aa66077d9192608101fbe45456f110)
![D[0] = D[0] \ggg 13](https://wikimedia.org/api/rest_v1/media/math/render/svg/8d943ac2623cbc9b1279721ed984ce5aad7f93bf)
![(out1; ~out2; ~out3) = E-funkce (D[0]; ~K[2i + 4]; ~K[2i + 5])](https://wikimedia.org/api/rest_v1/media/math/render/svg/9a3dbbce50ad30e98142a3dd5dcdbba4c372f4ed)
![D[2] = D \left [ 2 \right ] - out2](https://wikimedia.org/api/rest_v1/media/math/render/svg/2c73d0df38189c1dd0a68c8a8859edbf817e410d)
![D[1] = D\levý [ 1 \pravý ] - out1](https://wikimedia.org/api/rest_v1/media/math/render/svg/7f024d4e5481da12bb1a6ac3f431feee771e6f2f)
![D[3] = D\left [ 3 \right ] - out1](https://wikimedia.org/api/rest_v1/media/math/render/svg/7923305561026698d380fdc5db7b1dd4a973cdd6)
![D[0] = D\levá [ 0\pravá ] - D[3]](https://wikimedia.org/api/rest_v1/media/math/render/svg/b5e71da8c7f6901aa0f14f60609599254fdc0a64)
![D[0] = D\levá [ 0 \vpravo ] - D[1]](https://wikimedia.org/api/rest_v1/media/math/render/svg/25145a6a5df958c1daad7fb39461733de4d5f7e6)
![D[2] = D[2] - S0[ ~3. ~bajt ~z ~D[0] ]](https://wikimedia.org/api/rest_v1/media/math/render/svg/06c069dd382c60f08b838a40713760824bcdd033)
![D[1] = D[1] - S1[ ~2. ~bajt ~z ~D[0] ]](https://wikimedia.org/api/rest_v1/media/math/render/svg/14973403290efd66a8c769dddd89414b900f654c)
![D[1] = D[1] \oplus S0[ ~nízký ~bajt ~z ~D[0] ]](https://wikimedia.org/api/rest_v1/media/math/render/svg/ae8b04259f2a7927e47cb19c1050efc5bd70a718)
![D[i] = D\levý [ i\vpravo ] - K[i]](https://wikimedia.org/api/rest_v1/media/math/render/svg/4b8deb49478791706a19981d3f32646fa0856d33)
Vlastnosti algoritmu
S-bloky
Při vytváření S-boxu S byly jeho prvky generovány pseudonáhodným generátorem, poté byly testovány na různé lineární a diferenciální vlastnosti. Pseudonáhodné S-boxy byly generovány s následujícími parametry:
![i = 0\ldots102; j = 0\ldots4, S[5i+j] = \mathrm{SHA-1}(5i \vert c1 \vert c2 \vert c3)](https://wikimedia.org/api/rest_v1/media/math/render/svg/9422a32effe630e281a486cf8ecc501570db63d8)
(kde je j-té slovo ve výstupu SHA-1 ) Zde i je považováno za 32bitové celé číslo bez znaménka a c1, c2, c3 jsou nějaké konstanty. V implementaci IBM: c1 = 0xb7e15162; c2 = 0x243f6a88 (což je binární zápis zlomkové části resp .). c3 byl měněn, dokud nebyly nalezeny S-boxy s vhodnými vlastnostmi. SHA-1 funguje na datových tocích a používá little endian.
Vlastnosti S-boxu
Diferenciální vlastnosti .
- S-box nesmí obsahovat slova sestávající ze všech 0 nebo 1
- Každé dva S-boxy S 0 , S 1 se od sebe musí lišit alespoň ve 3 ze 4 bajtů. (Protože tato podmínka je u pseudonáhodných S-boxů extrémně nepravděpodobná, je jeden ze dvou S-boxů upraven)
- S-box neobsahuje dva prvky jako nebo
- S-box neobsahuje dvě dvojice prvků, jejichž xor-diference jsou stejné, a dvě dvojice prvků, jejichž uspořádaný rozdíl je roven
- Každé dva prvky S-boxu se musí lišit minimálně o 4 bity
![S[i], S[j] (i \neq j)](https://wikimedia.org/api/rest_v1/media/math/render/svg/ccdc856410f9cb0ecba66cb9fed77d8959961c70)
![S \left [ i \right ] = S \left [ j \right ] ; S \left [ i \right ] = -S \left [ j \right ]](https://wikimedia.org/api/rest_v1/media/math/render/svg/521ef901cb428cc259e41f73771d341116fdc227)
![S\left [ i \right ] = -S\left [ j \right ]](https://wikimedia.org/api/rest_v1/media/math/render/svg/a0124628ebb06b6717b918cd9993e1b3a4614111)
| XOR | Odčítání |
|---|---|
![S[27] \oplus S[101] = S[292] \oplus S[360] = 0x117f1a43](https://wikimedia.org/api/rest_v1/media/math/render/svg/44657ba7c4f22d970682373bb9cc0d4a0cd6e2d2)
![S \left [ 13 \right ] - S[138] = S[364]-S[297] = 0x75082c89](https://wikimedia.org/api/rest_v1/media/math/render/svg/383c1096858bc361c92886ba3daa6586761cdec2)
![S[27] \oplus S[292] = S[101] \oplus S[360] = 0x2b05b22a](https://wikimedia.org/api/rest_v1/media/math/render/svg/3823391354757bd5ec2e28768949becd8bafa30d)
![S \left [ 19 \right ] -S[168] = S[509] -S[335] = 0x0b7fc4bd](https://wikimedia.org/api/rest_v1/media/math/render/svg/68160b5f5926907148ecd1704481efac17bd3567)
![S[27] \oplus S[360] = S[101] \oplus S[292] = 0x3a7aa869](https://wikimedia.org/api/rest_v1/media/math/render/svg/74c364c988288aea4ed652f6b0273fd7d8ae9dae)
![S \left [ 49 \right ] -S[97] = S[142]-S[392] = 0x725ca4be](https://wikimedia.org/api/rest_v1/media/math/render/svg/0816b44f9e0c2dc9e28bdaed27db851351d89163)
![S \left [ 131 \right ] -S[333] = S[348]-S[211]= 0xc73689fe](https://wikimedia.org/api/rest_v1/media/math/render/svg/6c5f25c7c1ca9ab689aac0d75f4d5ea95fb5d4d1)
![S \left [ 13 \right ] -S[364] = S[138] -S[297] = 0x86dedc7c](https://wikimedia.org/api/rest_v1/media/math/render/svg/c60fc4d001e1f328aedc4ed9ef3baff66aa4dda0)
![S \left [ 131 \right ] -S[348] = S[333]-S[211]= 0x22492124](https://wikimedia.org/api/rest_v1/media/math/render/svg/79742be59ff64528b04edb195e7154739cace412)
![S \left [ 19 \right ] -S[509] = S[168] -S[335] = 0x9ce0ed93](https://wikimedia.org/api/rest_v1/media/math/render/svg/6a5ee0175b7ffe2c0004650d58f581d741456696)
![S \left [ 49 \right ] -S[142] = S[97] -S[392] = 0x5d91f03a](https://wikimedia.org/api/rest_v1/media/math/render/svg/1007b3910a35ff03e6573ed593cd4d3ab7de9966)
Lineární vlastnosti
- Poměr offsetu: . Je nutné, aby tento výraz byl větší než alespoň
- One-bit offset: Tento výraz musí být větší než alespoň
- Dvoubitový offset: . Je nutné, aby tento výraz byl větší než alespoň
- Jedna bitová korelace : . Tento výraz je nutné minimalizovat mezi všemi možnými S-boxy, které splňují předchozí body
![\left | Pr_x[parita(S[x]) = 0] - 1/2 \vpravo |](https://wikimedia.org/api/rest_v1/media/math/render/svg/89659276dc13c8cc0c66e280fb6b41f68818354e)
![\forall j \left | Pr_x[S[x]_j = 0] - 1/2 \vpravo |](https://wikimedia.org/api/rest_v1/media/math/render/svg/5343adb647f02bb3f2c0b2199ba47701bc5384ad)
![\forall j \left | Pr_x[S[x]_j \oplus S[x]_{j+1} = 0] - 1/2 \vpravo |](https://wikimedia.org/api/rest_v1/media/math/render/svg/e91776aef42e4ac846e618fe181ce20ceebe7b4a)
![\forall i,j \left | Pr_x [S[x]_j = x_i] - 1/2 \vpravo |](https://wikimedia.org/api/rest_v1/media/math/render/svg/ca1db239b274ec197ef459c84dabeb3c785a7215)
Rozšíření klíče
procedura rozšíření klíče rozšíří dané pole klíčů k[], skládající se z n 32bitových slov (kde n je celé číslo od 4 do 14) na pole K[] o 40 prvcích. Původní klíč nemusí mít žádnou strukturu. Procedura rozšíření klíče navíc zaručuje následující vlastnosti klíčového slova použitého při násobení v kryptografickém jádru algoritmu:
- dva nejméně významné bity klíčového slova budou vždy jedničky
- žádné z klíčových slov nebude obsahovat deset po sobě jdoucích 0 nebo 1
Popišme klíčový expanzní algoritmus.
- Nejprve je pole kompletně přepsáno do mezilehlého pole sestávajícího z 15 prvků.
- Tento proces se pak opakuje 4x. Při každé iteraci se vygeneruje 10 rozšířených klíčových slov. proměnná zobrazující aktuální číslo iterace. (0 pro první iteraci, 1 pro druhou atd.)
- Pole T[] se převede podle následujícího pravidla:
- Dále pole zamícháme pomocí 4 kol sítě Feistel typu 1. Následující operaci opakujeme čtyřikrát:
- Dále vezmeme deset slov z pole T[] a vložíme je jako dalších deset slov do pole K[] a znovu je zamícháme:
- Nakonec projdeme šestnáct slov používaných pro násobení (K[5],K[7]…K[35]) a upravíme je tak, aby odpovídala dvěma výše popsaným vlastnostem.
- Zapíšeme dva nejméně významné bity K[i] podle vzorce a místo těchto dvou bitů zapíšeme jeden, .
- Sbíráme masku M pro bity w , které patří sekvencím deseti nebo více nul nebo jedniček. Například tehdy a jen tehdy, pokud patří do sekvence 10 nebo více stejných prvků. Poté resetujeme (nastavíme je na 0) hodnoty těch jedniček M, které jsou na koncích nula nebo jedničky, a také těch, které jsou ve vysokých a nízkých bitech. Nechť naše slovo vypadá například takto: (výraz nebo znamená, že 0 nebo 1 se bude ve slově i krát opakovat). Pak bude maska M vypadat takto: . Takže resetujeme bity ve 4, 15, 16, 28 pozicích, tzn
- Dále pro opravu použijeme tabulku čtyř slov B[]. Všechny prvky tabulky B jsou vybrány tak, aby pro ně a pro všechny jejich cyklické posuny byla splněna vlastnost, že nemají sedm po sobě jdoucích 0 nebo 1. V implementaci IBM byla použita tabulka . Dále se dva zapsané bity j použijí k výběru slova z tabulky B a nejméně významných pět bitů slova K[i-1] se použije k otočení jeho prvků,
- Nakonec se vzor p převede XOR na původní slovo, přičemž se vezme v úvahu maska M: . Stojí za zmínku, že 2 nejméně významné bity z M jsou 0, pak dva nejméně významné bity konečného slova budou jedničky a použití tabulky B umožňuje zaručit, že v poli nebude 10 po sobě jdoucích 0 nebo 1. slovo
![k[]](https://wikimedia.org/api/rest_v1/media/math/render/svg/c6a3562b70a6e40dec2b573590d5c1af8b0fa178)
![T[]](https://wikimedia.org/api/rest_v1/media/math/render/svg/5036ef572ccf36952aaf95225905b620a0780edd)
![T[0 \ldots n-1] = k[0 \ldots n-1]; T[n] = n; T[n + 1 \ldots 14] = 0](https://wikimedia.org/api/rest_v1/media/math/render/svg/8f4d1d8552f1152e4acde36e29c13483565c8de5)
![i = 0 \ldots 14, T[i] = T[i] \oplus ((T[i - 7 \mod 15] \oplus T[i - 2 \mod 15]) \lll 3) \oplus (4i + j)](https://wikimedia.org/api/rest_v1/media/math/render/svg/176ec06f69bb7052d7ff76f083e9bc1173f441bb)
![T[i] = (T[i] + S[nízká ~9 ~bitů ~z ~T[i - 1 \mod 15]]) \lll 9; i = 0,1\ldots14](https://wikimedia.org/api/rest_v1/media/math/render/svg/398fda0511e4115994db89921dd1fc40a8d8e138)
![K[10j + i] = T[4i \mod 15]; i = 0,1\ldots9](https://wikimedia.org/api/rest_v1/media/math/render/svg/deab3697fde2a038238429d1a04ba555799e5d3d)
![j = K[i]\land 3](https://wikimedia.org/api/rest_v1/media/math/render/svg/ce5c50a99afc823d900856e5386f639355b58bb3)
![w = K[i]\ nebo 3](https://wikimedia.org/api/rest_v1/media/math/render/svg/36845e50bf24b685f9a4b57632355df29aecac19)
![B[] = \left \{ 0xa4a8d57b,0x5b5d193b, 0xc8a8309b, 0x73f9a978 \right \}](https://wikimedia.org/api/rest_v1/media/math/render/svg/92a878d0d4d14e2e74416f2e406feb73b25da181)
![p = B[j] \lll (nejnižší ~5 ~bitů ~z ~K[i-1]).](https://wikimedia.org/api/rest_v1/media/math/render/svg/13a191d743b86e434c147306f6dc47c8b64da7b6)
![K[i] = w \oplus (p \land M)](https://wikimedia.org/api/rest_v1/media/math/render/svg/7e14ccab72d7e0040dfc7d9b287541dd4d5feece)
Výhody a nevýhody algoritmu
Šifra byla kandidátem na AES , po drobných změnách v prvním kole soutěže, souvisejících se změnou postupu rozšíření klíče, MARS úspěšně prošel do finále.
Ve finále soutěže měl MARS řadu nedostatků:
- Složitá struktura . Složitá heterogenní struktura algoritmu ztěžovala nejen jeho analýzu, ale i implementaci.
- Implementace . Problémy byly při implementaci šifry na platformách, které nepodporovaly 32bitové operace násobení a rotace o libovolný počet bitů.
- Omezené zdroje . Neschopnost implementovat algoritmus v hardwaru s malými zdroji operační nebo energeticky nezávislé paměti .
- Ochrana . Ukázalo se, že MARS je špatně chráněn před útoky za běhu a spotřeby energie .
- Rozšíření klíče . MARS byl horší než ostatní finalisté AES v podpoře klíčové expanze za chodu.
- Paralelizace . Je možné paralelizovat pouze malou část algoritmu.
Pro všechny tyto nedostatky odborná komise vyzdvihla jednu velkou výhodu tohoto algoritmu - jeho symetrii. Na základě zjištěných nedostatků se MARS podle očekávání nestal vítězem AES.
Odpověď pro analytiky AES
Po vyhlášení výsledků soutěže AES zveřejnil tým MARS svoji recenzi celé soutěže. Zpochybnila kritéria pro hodnocení soutěže. Domnívali se, že hlavní charakteristikou šifry by měla být právě spolehlivost a její odolnost (např. proti útokům hrubou silou ), navíc odpovídali na každé tvrzení poroty jejich algoritmu.
1. MARS není vhodný pro hardwarovou implementaci Mezi stížnostmi na šifru byla její obtížná hardwarová implementace, která by mohla vést k zátěži internetu, a také k zavádění rozsáhlých schémat.
Vývojáři tvrdí, že jejich implementace je schopna pracovat rychlostí 1,28 Gb/s, což je přijatelné pro internet, a náklady na jejich čipy mohou být vysoké (13 USD za čip 12 Gb/s nebo 1 USD za čip 1 Gb/s), ale v jejich cena v budoucnu výrazně klesne.2. MARS není vhodný pro implementaci na zařízeních s nízkou pamětí Pro implementaci na SMART kartách mají algoritmy pouze 128 bajtů paměti. Pro proceduru rozšíření klíče vyžaduje MARS 512 bajtů.
Vývojáři se domnívají, že není důvod implementovat AES na tak zranitelný zdroj s nízkou pamětí, jako jsou čipové karty, protože všechny tyto zdroje lze snadno a rychle převést na systémy s veřejným klíčem.3. MARS není vhodný pro implementaci na FPGA MARS není vhodný pro implementaci na platformách, kde není povolena rotace (v závislosti na vnějších faktorech).
Vývojáři poznamenávají, že tento problém není fatální, ale přizpůsobení algoritmu této platformě chvíli trvá.4. Rozšíření klíče MARS je velmi náročná operace
Vývojáři tvrdí, že jde o směšné tvrzení. Tvrdí, že mají „ideální“ poměr mezi další pamětí na klíč a propustností (25 bajtů na klíč)Na závěr vývojáři uvádějí svou analýzu algoritmů účastníků AES, podle jejíchž výsledků byl MARS spolu s Serpentem nejlepším kandidátem na titul AES. [jeden]
Analýza zabezpečení algoritmu
V současné době neexistují žádné účinné útoky na tento algoritmus. I když má několik slabin [1] :
- Podklíče s velkým počtem opakovaných nul nebo jedniček mohou vést k účinným útokům na MARS, protože na jejich základě budou generovány slabé podklíče.
- Dva nejméně významné bity použité při násobení jsou vždy 1. Vždy tedy existují dva vstupní bity, které se během procesu násobení klíče nemění, a také dva výstupní bity, které jsou nezávislé na klíči.
Literatura
- Panasenko S. P. Šifrovací algoritmy. Speciální referenční kniha - Petrohrad. : BHV-SPb , 2009. - S. 65-68, 219-228. — 576 s. — ISBN 978-5-9775-0319-8
Poznámky
- ↑ 1 2 3 Výzkum kryptografie . Získáno 13. listopadu 2011. Archivováno z originálu 16. května 2006.
- ↑ Fáze 3 a 4 se nazývají „kryptografické jádro“ algoritmu MARS
- ↑ Výzkum kryptografie . Získáno 14. listopadu 2011. Archivováno z originálu dne 23. května 2009.
Odkazy
- Specifikace algoritmu (verze AES)
- Zdrojový kód MARS-1248 v jazyce C
- Oficiální šifrovací stránka
- Popis problému generovaných S-boxů
- Komentáře tvůrců šifry
| Symetrické kryptosystémy | |
|---|---|
| Streamové šifry | |
| Síť Feistel | |
| Síť SP | |
| jiný | |