MARS (kryptografi)

MARS
Skaber	Carolyn Barwick, Don Coppersmith
Oprettet	1998 _
offentliggjort	1998 _
Nøglestørrelse	128-448 bit
Blokstørrelse	128 bit
Antal runder	32
Type	Feistel netværk

MARS er en AES kandidat chiffer udviklet af IBM , som skabte DES på én gang . IBM siger, at MARS-algoritmen trækker på firmaets 25 års kryptoanalytiske ekspertise, og sammen med dens høje kryptografiske styrke tillader chifferen effektiv implementering selv inden for begrænsningerne af smart cards .

Don Coppersmith , en af forfatterne af Lucifer -chifferet ( DES ), kendt for en række artikler om kryptologi, deltog i udviklingen af chifferen : forbedring af strukturen af S-bokse mod differentiel kryptoanalyse , den hurtige matrixmultiplikationsmetode ( Coppersmith-Winograd-algoritme ), RSA - kryptanalyse . Ud over ham deltog Carolyn Barwick , Edward D'Evignon , Rosario Genaro , Shai Halevi , Charanjit Jutla , Steven M. Matyas Jr. i udviklingen af algoritmen . , Luke O'Connor , Mohamed Perevyan , David Safford , Nevenko Zunich .

I henhold til reglerne for AES -konkurrencen kunne deltagerne foretage mindre ændringer i deres algoritmer. Ved at udnytte denne regel ændrede forfatterne af MARSa nøgleudvidelsesproceduren, hvilket gjorde det muligt at reducere kravene til ikke-flygtig og RAM . En ændret version af algoritmen vil blive givet nedenfor.

Baseret på resultaterne af AES -konkurrencen kom MARS til finalen, men tabte til Rijndael . Efter offentliggørelsen af resultaterne (19. maj 2000) dannede udviklingsteamet deres egen mening om AES -konkurrencen [1] , hvor de kommenterede påstandene til deres hjerne.

MARS distribueres nu over hele verden under en royalty-fri licens .

Kort beskrivelse af algoritmen

MARS er en bloksymmetrisk chiffer med en hemmelig nøgle. Blokstørrelsen for kryptering er 128 bit, nøglestørrelsen kan variere fra 128 til 448 bit inklusive (multipler af 32 bit). Skaberne forsøgte at kombinere kodningshastigheden og chifferens styrke i deres algoritme. Resultatet er en af de stærkeste algoritmer i AES- konkurrencen .

Algoritmen er unik ved, at den brugte næsten alle eksisterende teknologier brugt i kryptoalgoritmer, nemlig:

simpleste operationer ( addition , subtraktion , eksklusiv eller )
substitutioner ved hjælp af en substitutionstabel
fast cyklisk skift
dataafhængigt cyklisk skift
multiplikation modulo 2 32
nøgleblegning

Brugen af dobbelt shuffling udgør en vanskelighed for kryptoanalyse , som nogle tilskriver ulemperne ved algoritmen. Samtidig er der i øjeblikket ingen effektive angreb på algoritmen, selvom nogle nøgler kan generere svage undernøgler.

Algoritmestruktur

Forfatterne af chifferen gik ud fra følgende antagelser:

Valg af operationer . MARS er designet til at blive brugt på tidens mest avancerede computere . For at opnå den bedste defensive præstation blev de mest "stærke operationer" understøttet i dem inkluderet i den. Dette muliggjorde et større sikkerheds-per-instruktionsforhold for forskellige chifferimplementeringer.
Chifferens struktur . Tyve års erfaring inden for kryptografi førte skaberne af algoritmen til ideen om, at hver runde af kryptering spiller en rolle i at sikre chifferens sikkerhed. Især kan vi se, at den første og sidste runde normalt er meget forskellige fra de mellemliggende ("centrale") runder af algoritmen med hensyn til beskyttelse mod kryptoanalytiske angreb. Ved oprettelsen af MARSa blev der således brugt en blandet struktur, hvor den første og sidste runde af kryptering adskiller sig væsentligt fra de mellemliggende.
Analyse . Mest sandsynligt vil en algoritme med en heterogen struktur være bedre i stand til at modstå fremtidens kryptoanalytiske metoder end en algoritme med alle runder identiske. Udviklerne af MARS-algoritmen gav den en meget heterogen struktur - algoritmens runder er meget forskellige fra hinanden.

MARS-krypteringen brugte følgende krypteringsmetoder:

Arbejde med 32-bit ord . Alle handlinger gælder for 32-bit ord. det vil sige, at al den originale information er opdelt i blokke på 32 bit. (hvis blokken viste sig at være kortere, så var den polstret til 32 bit)
Feistel netværk . Skaberne af chifferen mente, at dette var den bedste kombination af krypteringshastighed og kryptografisk styrke. MARS bruger et Type 3 Feistel-netværk.
Symmetri af algoritmen . For krypteringens modstand mod forskellige angreb blev alle dens runder lavet fuldstændig symmetriske , det vil sige, at den anden del af runden er en spejlgentagelse af dens første del.

Strukturen af MARS-algoritmen kan beskrives som følger:

Pre-keying: 32-bit underblokke A, B, C, D er overlejret med 4 fragmenter af den udvidede nøgle k 0 ...k 3 af modulo 2 32 ;
8 runder af direkte blanding udføres (uden deltagelse af krypteringsnøglen);
Der udføres 8 runder af direkte kryptokonvertering;
Der udføres 8 runder med omvendt kryptotransformation; [2]
Der udføres 8 runder med back-mixing, også uden deltagelse af krypteringsnøglen;
Den endelige overlejring af fragmenter af den udvidede nøgle k 36 ... k 39 ved operationen af subtraktion modulo 2 32 .

Direkte blanding

I den første fase overlejres hvert dataord med et nøgleord, og derefter er der otte omgange med blanding efter Feistel-netværket af den tredje type, sammen med noget ekstra blanding. I hver runde bruger vi et dataord (kaldet kildeordet) til at ændre tre andre ord (kaldet målordene). Vi behandler de fire bytes af det oprindelige ord som indekser i to S-bokse, S 0 og S 1 , som hver består af 256 32-bit ord, og derefter XOR eller tilføjer de tilsvarende S-boks data til tre andre ord.

Hvis de fire bytes af det oprindelige ord er b 0 , b 1 , b 2 , b 3 (hvor b 0 er den første byte og b 3 er den høje byte), så bruger vi b 0 , b 2 som indekser i blok S 0 og bytes b 1 , b 3 , som indekser i S-boksen S 1 . Først XOR S 0 til det første målord og derefter tilføje S 1 til det samme ord. Vi tilføjer også S 0 til det andet målord og blokerer XOR-S 1 til det tredje målord. Til sidst roterer vi det oprindelige ord 24 bit til højre.

I næste runde roterer vi de fire ord, vi har: så det aktuelle første målord bliver det næste kildeord, det nuværende andet målord bliver det nye første målord, det tredje målord bliver det næste andet målord, og nuværende kildeord bliver det tredje målord.

Desuden tilføjer vi efter hver af de fire runder et af målordene tilbage til det oprindelige ord. Konkret tilføjer vi efter første og femte runde det tredje målord tilbage til det oprindelige ord, og efter anden og sjette runde tilføjer vi det første målord tilbage til det oprindelige ord. Grunden til disse yderligere blandingsoperationer er at eliminere nogle få simple differentielle kryptoangreb i blandingsfasen for at bryde symmetrien i blandingsfasen og få et hurtigt flow.

Pseudokode 1. // Første overlejring af en nøgle på dataene 2. 3.

for ~i ~= ~0 ~til ~3 ~do

D \venstre [ i \højre ] = D[i] + K[i]

4. // Derefter 8 omgange med fremblanding 5. // brug D[0] til at ændre D[1]; D[2]; D[3]

for ~i = ~0 ~til ~7 ~do

6. // adgang til 4 S-bokse 7.8.9.10 _ _ _

D \venstre [1 \right ] = D[1] \oplus S0[ ~lav ~byte ~af ~D[0] ]

D \venstre [ 1 \højre ] = D[1] + S1[ ~2. ~byte ~af ~D[0] ]

D \left [ 2 \right ] = D[2] + S0[ ~3rd ~byte ~af ~D[0] ]

D[3] = D[3] \oplus S1[ ~høj ~byte ~af ~D[0] ]

11. // og drej det oprindelige ord til højre 12.

D[0] = D[0]\ggg 24

13. // udfører også yderligere blandingsoperationer 14. 15. // tilføje D[3] til det oprindelige ord

hvis ~i ~= ~0 ~eller ~4 ~så

D \venstre [ 0 \højre ] = D[0] + D[3]

16. 17. // tilføje D[1] til det oprindelige ord

hvis ~i ~= ~1 ~eller ~5 ~så

D \venstre [0 \right ] = D[0] + D[1]

18. // roter array D[ ] 19.20 .

(D[3]; D[2]; D[1]; D[0]) \venstrepil (D[0]; D[3]; D[2]; D[1])

end-for

Kryptografisk kerne

Den kryptografiske kerne i MARS er et type 3 Feistel-netværk, der indeholder 16 runder. I hver runde bruger vi nøglen E-funktion, som er en kombination af multiplikationer, rotationer og S-boks-kald. Funktionen tager et dataord som input og returnerer tre ord, med hvilke operationen med addition eller XOR til andre tre dataord efterfølgende vil blive udført. Derudover roteres kildeordet 13 bit til venstre.

For at give alvorlig modstand mod kryptoangreb bruges de tre outputværdier af E-funktionen (O 1 , O 2 , O 3 ) i de første otte runder og i de sidste otte runder i forskellige rækkefølger. I de første otte runder tilføjer vi O 1 og O 2 til henholdsvis det første og andet målord og XOR O 3 til det tredje målord. I de sidste otte runder tilføjer vi O 1 og O 2 til henholdsvis tredje og andet målord og XOR O 3 til det første målord.

Pseudokode 1. // Lav 16 runder med kryptering med nøglen 2. 3. 4. 5. 6. // første 8 runder fremadkonvertering

for ~i ~= ~0 ~til ~15 ~do

(ud1; ~ud2; ~ud3) ~= ~E-funktion(D[0]; ~K[2i + 4]; ~K[2i + 5])

D[0] = D[0]\lll 13

D[2] = D \venstre [ 2 \højre ] + ud2

hvis ~i ~< ~8 ~så

7. 8. 9. // derefter 8 runder omvendt transformation

D[1] = D \venstre [ 1 \højre ] + ud1

D[3] = D[3] \oplus ud3

andet

10. 11. 12.

D[3] = D \venstre [ 3 \højre ] + ud1

D[1] = D[1] \oplus ud3

end-if

13. // roter array D[ ] 14. 15.

(D[3]; ~D[2]; ~D[1]; ~D[0]) \venstrepil (D[0]; ~D[3]; ~D[2]; ~D[1])

end-for

E-funktion

E-funktionen tager ét ord med data som input og bruger yderligere to nøgleord, hvilket producerer tre ord som output. I denne funktion bruger vi tre midlertidige variable, betegnet L, M og R (for venstre, midterste og højre).

Indledningsvis satte vi R til værdien af det oprindelige ord, der blev flyttet 13 bit til venstre, og satte M til summen af de oprindelige ord og det første nøgleord. Vi bruger derefter de første ni bit af M som et indeks til en af de 512 S-bokse (som opnås ved at kombinere S 0 og S 1 ved faseblanding), og lagrer i L værdien af den tilsvarende S-boks.

Derefter multiplicerer vi det andet nøgleord med R, og gemmer værdien i R. Så roterer vi R 5 positioner til venstre (så de 5 høje bit bliver de 5 lave bits af R efter rotationen). Derefter XOR R til L, og ser også på de nederste fem bits af R for at bestemme mængden af skift (fra 0 til 31), og roterer M til venstre med denne mængde. Dernæst roterer vi R yderligere 5 positioner til venstre og XOR L ind i L. Til sidst ser vi igen på de 5 mindst signifikante bits af R som mængden af rotation og roterer L med den mængde til venstre. Resultatet af E-funktionen er således 3 ord (i rækkefølge): L, M, R.

Pseudokode 1. // brug 3 midlertidige variable L; M; R 2. //tilføj det første søgeord

M = ~in + ~tast1

3. // gange med det andet nøgleord, som skal være lige

R = (i \lll 13) \nogle gange tast2

4. 5. // tag S-boks

i = ~laveste ~9 ~bit ~af ~M

L = S \venstre [ i \højre ]

6. 7. // disse bits beskriver mængden af efterfølgende rotation

R = R\lll 5

r = ~laveste ~5 ~bit ~af ~R

8. // første rotation ved variabel

M = M

9. 10. 11. 12. // disse bits beskriver mængden af efterfølgende rotation

L = L + R

R = R\lll 5

L = L + R

r = ~laveste ~5 ~bit ~af ~R

13. // anden variabel rotation

L = L \lll r

fjorten.

output(L; ~M; ~R)

Omvendt blanding

Tilbage shuffle er næsten det samme som fremad shuffle, bortset fra at dataene behandles i omvendt rækkefølge. Det vil sige, at hvis vi kombinerede frem- og tilbageblanding, så deres udgange og indgange ville blive forbundet i omvendt rækkefølge (D[0] fremad og D[3] tilbage, D[1] fremad og D[2] tilbage), så ville ikke se resultatet af blandingen. Som ved direkte blanding bruger vi også her ét kildeord og tre målord. Overvej de første fire bytes af det oprindelige ord: b 0 , b 1 , b 2 , b 3 . Vi vil bruge b 0 , b 2 som et indeks til S-boksen - S 1 , og b 1 b 3 for S 0 . Lad os XOR S 1 [b 0 ] ind i det første målord, trække S 0 [b 3 ] fra det andet ord, trække S 1 [b 2 ] fra det tredje målord og derefter XOR S 0 [b 1 ] også for at det tredje målord . Til sidst roterer vi det oprindelige ord 24 steder til venstre. Til næste runde roterer vi de tilgængelige ord, så det aktuelle første målord bliver det næste kildeord, det aktuelle andet målord bliver det første målord, det aktuelle tredje målord bliver det andet målord og det aktuelle kildeord bliver det tredje målord. Derudover trækker vi før en af de fire "særlige" runder et af målordene fra kildeordet: før fjerde og ottende runde trækker vi det første målord fra; før tredje og syvende runde trækker vi den tredje fra målord fra kildeordet.

Pseudokode 1. // Lav 8 omgange med tilbageblanding 2.

for ~i ~= ~0 ~til ~7 ~do

3. // yderligere blandingsoperationer 4. 5. //træk D[3] fra det oprindelige ord

hvis ~i ~= ~2 ~eller ~6 ~så

D[0] = D[0] - ~D[3]

6. 7. // trække D[1] fra det oprindelige ord

hvis ~i ~= ~3 ~eller ~7 ~så

D[0] = D[0] - ~D[1]

8. // henviser til de fire elementer i S-bokse 9. 10. 11. 12.

D[1] = D[1] \oplus S1[ ~lav ~byte ~af ~D[0] ]

D[2] = D[2] - ~S0[ ~high ~byte ~af ~D[0] ]

D[3] = D[3] \oplus S1[ ~3rd ~byte ~af ~D[0] ]

D[3] = D[3] - ~S0[ ~2. ~byte ~af ~D[0] ]

13. // og drej det oprindelige ord til venstre fjorten.

D[0] = D[0]\lll 24

15. // roter array D[] 16. 17.

(D[3]; D[2]; D[1]; D[0]) \venstrepil (D[0]; D[3]; D[2]; D[1])

end-for

18. // Træk nøgleord fra 19.20 .

for ~i ~= ~0 ~til ~3 ~do

D[i] = D[i] - ~K[36 + i]

Dekryptering

Afkodningsprocessen er det omvendte af kodningsprocessen. Dekrypteringskoden ligner (men ikke identisk) med krypteringskoden.

Direkte blanding 1. // Indledende nøgleoverlejring 2. 3.

for ~i ~= ~0 ~til ~3 ~do

D\venstre [ i \right ] = D[i] + K[36 + i]

4. // Derefter laves 8 runder fremadblanding 5.

for ~i ~= ~7 ~ned ~til ~0 ~do

6. // roter array D[] 7.

(D[3]; ~D[2]; ~D[1]; ~D[0]) \venstrepil (D[2]; ~D[1]; ~D[0]; ~D[3])

8. // og drej det oprindelige ord til højre 9.

D[0] = D[0]\ggg 24

10. // adgang til 4 elementer af S-bokse 11. 12. 13. 14.

D[3] = D[3] \oplus S0[ ~2. ~byte ~af ~D[0] ]

D[3] = D[3] + S1[ ~3. ~byte ~af ~D[0] ]

D[2] = D[2] + S0[ ~høj ~byte ~af ~D[0] ]

D[1] = D[1] \oplus S1[ ~lav ~byte ~af ~D[0] ]

15. // yderligere blanding 16. 17. // tilføje D[3] til det oprindelige ord

hvis ~i ~= ~2 ~eller ~6 ~så

D[0] = D\venstre [ 0 \right ] + D[3]

18. 29. // tilføje D[1] til det oprindelige ord

hvis ~i ~= ~3 ~eller ~7 ~så

D[0] = D\venstre [ 0 \right ] + D[1]

tyve.

end-for

Kryptografisk kerne 1. // Kør 16 runder med overlay-tasten 2.

for ~i ~= ~15 ~ned ~til ~0 ~do

3. // roter array D[] 4. 5. 6. 7. 8. // sidste 8 runder i direkte rækkefølge

(D[3]; ~D[2]; ~D[1]; ~D[0]) \venstrepil (D[2]; ~D[1]; ~D[0]; ~D[3])

D[0] = D[0] \ggg 13

(ud1; ~ud2; ~ud3) = E-funktion(D[0]; ~K[2i + 4]; ~K[2i + 5])

D[2] = D \venstre [ 2 \højre ] - ud2

hvis ~i ~< ~8 ~så

9. 10. 11. // første 8 runder i omvendt rækkefølge

D[1] = D\venstre [ 1 \højre ] - ud1

D[3] = D[3] \oplus ud3

andet

12. 13. 14. 15.

D[3] = D\venstre [ 3 \højre ] - ud1

D[1] = D[1] \oplus ud3

end-if

end-for

Omvendt blanding 1. // Lav 8 omgange med tilbageblanding 2.

for ~i ~= ~7 ~ned ~til ~0 ~do

3. // Roter array D[] fire.

(D[3]; ~D[2]; ~D[1]; ~D[0]) \venstrepil (D[2]; ~D[1]; ~D[0]; ~D[3])

5. // yderligere blandingsoperationer 6. 7. // trække D[3] fra det oprindelige ord

hvis ~i ~= ~0 ~eller ~4 ~så

D[0] = D\venstre [ 0\højre ] - D[3]

8. 9. // trække D[1] fra det oprindelige ord

hvis ~i ~= ~1 ~eller ~5 ~så

D[0] = D\venstre [ 0 \right ] - D[1]

10. // Drej det oprindelige ord til venstre elleve.

D[0] = D[0]\lll 24

12. // henviser til de fire elementer i S-bokse 13. 14. 15. 16. 17.

D[3] = D[3] \oplus S1[ ~høj ~byte ~af ~D[0] ]

D[2] = D[2] - S0[ ~3. ~byte ~af ~D[0] ]

D[1] = D[1] - S1[ ~2. ~byte ~af ~D[0] ]

D[1] = D[1] \oplus S0[ ~lav ~byte ~af ~D[0] ]

end-for

18. // trække en undernøgle fra dataene 19.20 .

for ~i ~= ~0 ~til ~3 ~do

D[i] = D\venstre [ i\højre ] - K[i]

Funktioner af algoritmen

S-blokke

Ved oprettelse af en S-boks S blev dens elementer genereret af en pseudo-tilfældig generator, hvorefter de blev testet for forskellige lineære og differentielle egenskaber. Pseudo-tilfældige S-bokse blev genereret med følgende parametre:

$i = 0\ldots102; j = 0\ldots4, S[5i+j] = \mathrm{SHA-1}(5i \vert c1 \vert c2 \vert c3)$

(hvor er det j-te ord i SHA-1 output ) Her anses i for at være et 32-bit heltal uden fortegn, og c1, c2, c3 er nogle konstanter. I IBM-implementeringen: c1 = 0xb7e15162; c2 = 0x243f6a88 (som er den binære notation af brøkdelen af hhv .). c3 blev ændret indtil S-bokse med passende egenskaber blev fundet. SHA-1 fungerer på datastrømme og bruger lidt endian. $SHA-1(j)$ $e$ $\pi$

S-boks egenskaber

Differentielle egenskaber .

S-boks må ikke indeholde ord, der består af alle 0'ere eller 1'ere
Hver anden S-boks S 0 , S 1 skal adskille sig fra hinanden i mindst 3 ud af 4 bytes. (Da denne tilstand er yderst usandsynlig for pseudo-tilfældige S-bokse, er en af de to S-bokse modificeret)
En S-boks indeholder ikke to elementer, sådan at eller $S[i], S[j](i \neq j)$ $S \venstre [i \højre] = S \venstre [j \højre]; S \venstre [ i \ højre ] = -S \ venstre [ j \ højre ]$ $S\venstre [ i \højre ] = -S\venstre [ j \højre ]$
S-boksen indeholder ikke to par af elementer, hvis xor-forskelle er ens, og to par af elementer, hvis ordnede forskel er lig med
Hvert andet element i S-boksen skal afvige med mindst 4 bit

Krav #4 blev ikke opfyldt i IBM-implementeringen til AES, men blev rettet umiddelbart efter finalen. Det er blevet observeret, at følgende elementer er til stede i S-bokse, i modsætning til dette krav [3] :

XOR	Subtraktion
$S[27] \oplus S[101] = S[292] \oplus S[360] = 0x117f1a43$	$S \venstre [ 13 \højre ] - S[138] = S[364]-S[297] = 0x75082c89$
$S[27] \oplus S[292] = S[101] \oplus S[360] = 0x2b05b22a$	$S \venstre [ 19 \right ] -S[168] = S[509] -S[335] = 0x0b7fc4bd$
$S[27] \oplus S[360] = S[101] \oplus S[292] = 0x3a7aa869$	$S \venstre [ 49 \right ] -S[97] = S[142]-S[392] = 0x725ca4be$
	$S \venstre [ 131 \right ] -S[333] = S[348]-S[211]= 0xc73689fe$
	$S \venstre [ 13 \right ] -S[364] = S[138] -S[297] = 0x86dedc7c$
	$S \venstre [ 131 \right ] -S[348] = S[333]-S[211]= 0x22492124$
	$S \venstre [ 19 \right ] -S[509] = S[168] -S[335] = 0x9ce0ed93$
	$S \venstre [ 49 \right ] -S[142] = S[97] -S[392] = 0x5d91f03a$

Lineære egenskaber

Offset forhold: . Det er nødvendigt, at dette udtryk er større end mindst $\venstre | Pr_x[paritet(S[x]) = 0] - 1/2 \højre |$ $1/32$
One-bit offset: Dette udtryk skal være større end mindst $\forall j \venstre | Pr_x[S[x]_j = 0] - 1/2 \højre |$ $1/30$
To-bit offset: . Det er nødvendigt, at dette udtryk er større end mindst $\forall j \venstre | Pr_x[S[x]_j \oplus S[x]_{j+1} = 0] - 1/2 \right |$ $1/30$
En smule korrelation :. Det er nødvendigt at minimere dette udtryk blandt alle mulige S-bokse, der opfylder de foregående punkter $\forall i,j \venstre | Pr_x [S[x]_j = x_i] - 1/2 \højre |$

Nøgleudvidelse

nøgleudvidelsesproceduren udvider det givne array af nøgler k[], bestående af n 32-bit ord (hvor n er et heltal fra 4 til 14) til et array K[] med 40 elementer. Den originale nøgle behøver ikke følge nogen struktur. Derudover garanterer nøgleudvidelsesproceduren følgende egenskaber for nøgleordet, der bruges til multiplikation i den kryptografiske kerne af algoritmen:

de to mindst signifikante bits af søgeordet vil altid være et
ingen af søgeordene vil indeholde ti på hinanden følgende 0'ere eller 1'ere

Lad os beskrive nøgleudvidelsesalgoritmen.

Først er arrayet fuldstændigt omskrevet til et mellemliggende array bestående af 15 elementer. $k[]$ $T[]$ $T[0 \ldots n-1] = k[0 \ldots n-1]; T[n] = n; T[n + 1 \ldprikker 14] = 0$
Denne proces gentages derefter 4 gange. Ved hver iteration genereres 10 udvidede nøgleord. variabel, der viser det aktuelle iterationsnummer. (0 for den første iteration, 1 for den anden osv.) $j$
1. Arrayet T[] konverteres i henhold til følgende regel: $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)$
2. Dernæst blander vi arrayet ved hjælp af 4 runder af Type 1 Feistel Network. Vi gentager følgende operation fire gange: $T[]$ $T[i] = (T[i] + S[lav ~9 ~bit ~af ~T[i - 1 \mod 15]]) \lll 9; i = 0,1\ldots14$
3. Derefter tager vi ti ord fra T[]-arrayet og indsætter dem som de næste ti ord i K[]-arrayet, blander igen: $K[10j + i] = T[4i \mod 15]; i = 0,1\ldots9$
Til sidst gennemgår vi de seksten ord, der bruges til multiplikation (K[5],K[7]...K[35]) og modificerer dem, så de matcher de to egenskaber beskrevet ovenfor.
1. Vi skriver de to mindst signifikante bits af K[i] ned efter formlen , og så skriver vi i stedet for disse to bits en, . $j = K[i]\land 3$ $w = K[i]\lor 3$
2. Vi samler en maske M for bits w , der hører til sekvenser på ti eller flere nuller eller enere. For eksempel hvis og kun hvis det tilhører en sekvens på 10 eller flere identiske elementer. Derefter nulstiller vi (indstil dem til 0) værdierne for dem M, der er i enden af nul- eller en-sekvenser, såvel som dem, der er i de høje og lave bits. Lad for eksempel vores ord se sådan ud: (udtrykket eller betyder, at 0 eller 1 vil blive gentaget i ordet i gange). Så vil masken M se sådan ud: . Så vi nulstiller bitsene i 4, 15, 16, 28 positioner, dvs $M_l=1$ $w_l$ $w = 0^{3}1^{13}0^{12}1011$ $0^i$ $1^i$ $0^{3}1^{25}0^{4}$ $M = 0^{4}1^{11}001^{10}0^{5}$
3. Yderligere, til korrektion, bruger vi en tabel med fire ord B[]. Alle elementer i tabel B er valgt på en sådan måde, at for dem og for alle deres cykliske skift er egenskaben opfyldt, at de ikke har syv på hinanden følgende 0'er eller 1'ere. I IBM-implementeringen blev tabellen brugt . Dernæst bruges de to skrevne bit j til at vælge et ord fra tabel B, og de mindst signifikante fem bits af ordet K[i-1] bruges til at rotere dets elementer, $B[] = \venstre \{ 0xa4a8d57b,0x5b5d193b, 0xc8a8309b, 0x73f9a978 \right \}$ $p = B[j] \lll (laveste ~5 ~bit ~af ~K[i-1]).$
4. Til sidst XORedles mønsteret p til det oprindelige ord, idet der tages hensyn til masken M :. Det er værd at bemærke, at de 2 mindst signifikante bits af M er 0, så vil de to mindst signifikante bits af det sidste ord være enere, og ved at bruge tabel B er det muligt at garantere, at der ikke vil være 10 på hinanden følgende 0 eller 1 i ord $K[i] = w \oplus (p \land M)$

Fordele og ulemper ved algoritmen

Chifferen var en AES - kandidat , efter nogle mindre ændringer i løbet af konkurrencens første runde, relateret til en ændring i nøgleudvidelsesproceduren, gik MARS med succes videre til finalen.

I finalen i konkurrencen havde MARS en række mangler:

Kompleks struktur . Algoritmens komplekse heterogene struktur gjorde det svært ikke kun at analysere den, men også at implementere den.
Implementering . Der var problemer ved implementering af chifferen på platforme, der ikke understøttede 32-bit multiplikation og rotationsoperationer med et vilkårligt antal bits.
Begrænsede ressourcer . Manglende evne til at implementere algoritmen i hardware med små ressourcer af operationel eller ikke-flygtig hukommelse .
Beskyttelse . MARS viste sig at være dårligt beskyttet mod angreb på køretid og strømforbrug .
Nøgleudvidelse . MARS var værre end de andre AES-finalister til at støtte nøgleudvidelsen i farten.
Parallellerbarhed . Det er muligt at parallelisere kun en lille del af algoritmen.

For alle disse mangler fremhævede ekspertkommissionen en stor fordel ved denne algoritme - dens symmetri. Baseret på de identificerede mangler blev MARS, som forventet, ikke vinderen af AES.

Svar til AES-analytikere

Efter offentliggørelsen af resultaterne af AES-konkurrencen udgav MARS-holdet deres anmeldelse af hele konkurrencen. Det satte spørgsmålstegn ved kriterierne for at vurdere konkurrencen. De mente, at det vigtigste kendetegn ved chifferen netop skulle være pålideligheden og dens modstand (for eksempel mod brute-force- angreb). Derudover besvarede de alle krav fra juryen til deres algoritme.

1. MARS er ikke egnet til hardwareimplementering Blandt klagerne over chifferen var dens vanskelige hardwareimplementering, hvilket kunne føre til byrden af internettet, samt indførelsen af store, i størrelse ordninger.

Udviklerne hævder, at deres implementering er i stand til at fungere med en hastighed på 1,28 Gbps, hvilket er acceptabelt for internettet, og prisen på deres chips kan være høj ($13 for en 12Gbps-chip eller $1 for en 1Gbps-chip), men i deres prisen vil falde markant i fremtiden.

2. MARS er ikke egnet til implementering på enheder med lav hukommelse Til implementering på SMART-kort har algoritmerne kun 128 bytes hukommelse. Til nøgleudvidelsesproceduren kræver MARS 512 bytes.

Udviklerne mener, at der ikke er nogen grund til at implementere AES på en så sårbar ressource med lav hukommelse som smart cards, da alle disse ressourcer nemt og hurtigt kan konverteres til offentlige nøglesystemer.

3. MARS er ikke egnet til implementering på FPGA MARS er ikke egnet til implementering på platforme, hvor rotation ikke er tilladt (afhængigt af eksterne faktorer).

Udviklerne bemærker, at dette problem ikke er fatalt, men det tager lidt tid at tilpasse algoritmen til denne platform.

4. MARS nøgleudvidelse er en meget tung operation

Udviklerne hævder, at dette er en latterlig udtalelse. De hævder at have det "ideelle" forhold mellem yderligere hukommelse pr. nøgle og gennemløb (25 bytes pr. nøgle)

Som konklusion giver udviklerne deres analyse af AES-deltagernes algoritmer, ifølge resultaterne af hvilke MARS sammen med Serpent var den bedste kandidat til titlen AES. [en]

Algoritmesikkerhedsanalyse

Der er i øjeblikket ingen effektive angreb på denne algoritme. Selvom det har flere svagheder [1] :

Undernøgler med et stort antal gentagne nuller eller enere kan føre til effektive angreb på MARS, da svage undernøgler vil blive genereret baseret på dem.
De to mindst signifikante bit, der bruges i multiplikation, er altid 1. Der er således altid to inputbits, der er uændrede under nøglemultiplikationsprocessen, samt to outputbits, der er uafhængige af nøglen.

Litteratur

Panasenko S. P. Krypteringsalgoritmer. Særlig opslagsbog - St. Petersborg. : BHV-SPb , 2009. - S. 65-68, 219-228. — 576 s. — ISBN 978-5-9775-0319-8

Noter

↑ 1 2 3 Kryptografiforskning . Hentet 13. november 2011. Arkiveret fra originalen 16. maj 2006. (ubestemt)
↑ Trin 3 og 4 kaldes den "kryptografiske kerne" af MARS-algoritmen
↑ Kryptografiforskning . Hentet 14. november 2011. Arkiveret fra originalen 23. maj 2009. (ubestemt)

Links

Symmetriske kryptosystemer
Stream-cifre	A3 A5 A8 Decim F-FCSR Korn HC-256 KCipher-2 MICKEY MUGI GEDD Phelix RC4 Kanin FORSEGLE SNE SOSEMANUK Salsa 20 STRUMOK Trivium VMPC
Feistel netværk	GOST 28147-89 (Magma) blæsefisk Camellia CAST-128 CAST-256 CIFERUNIKORN-A CIFERUNIKORN-E CLEFIA Cobra DEL DES DESX DFC E2 ENRUPT FEAL HPC IDE KASUMI Khafre Khufu LOKI97 MacGuffin MARS MESH MISTY1 NyDES NDS RC5 RC6 FRØ Simon Sinople skipjack SM4 Speck TE XTEA XXTEA Raiden RTEA Triple DES To fisk
SP netværk	Græshoppe 3 vejs ABC ARIA AES (Rijndael) Akelarre Anubis BaseKing Bas Omatic Bælte CRYPTON Diamant 2 grand cru Hierocrypt-3 Hierocrypt-L1 KHAZAD Kalyna Lucifer til stede Regnbue SIKRERE HAJ FIRKANT Slange tre fisk
Andet	FRØ NUSH REDOC SC2000 SHACAL CS-Cipher