Madryga

En criptografia, Madryga és un xifratge de blocs publicat el 1984 per WE Madryga. Va ser dissenyat per ser fàcil i eficient per a la implementació en programari. Des de llavors s'han trobat greus debilitats a l'algoritme, però va ser un dels primers algorismes de xifratge que va utilitzar rotacions depenent de les dades, més tard utilitzat en altres xifratges, com ara RC5 i RC6.

Madryga
Detall
Estructura	Xarxa del tipus RC4

En la seva proposta, Madryga va exposar dotze objectius de disseny que generalment es consideren bons objectius en el disseny d'un xifrat de blocs. DES ja n'havia complert nou. Els tres que DES no va complir van ser:

1. Qualsevol clau possible hauria de produir un xifrat fort. (Vol dir que no hi ha claus febles, que té DES.)
2. La longitud de la clau i el text s'han de poder ajustar per satisfer els diferents requisits de seguretat.
3. L'algorisme hauria de ser implementable de manera eficient en programari en grans sistemes centrals, miniordinadors i microordinadors, i en lògica discreta. (DES té una gran quantitat de permutacions bit a bit, que són ineficients en les implementacions de programari.)

L'algoritme

Madryga va complir l'objectiu de ser eficient en programari: les úniques operacions que utilitza són XOR i rotacions, ambdues operant només en bytes sencers. Madryga té una clau de longitud variable, sense límit superior a la seva longitud.

Madryga s'especifica amb vuit rondes, però això es pot augmentar per proporcionar més seguretat si cal. En cada ronda, l'algoritme passa per tot el text en clar n vegades, on n és la longitud del text en clar en bytes. L'algoritme mira tres bytes alhora, de manera que Madryga és un xifratge de blocs de 24 bits. XOR fa un byte de clau amb el byte més a la dreta i gira els altres dos com un bloc. La rotació varia amb la sortida del XOR. Aleshores, l'algoritme es mou un byte cap a la dreta. Per tant, si estigués treballant en els bytes 2, 3 i 4, després d'haver acabat de girar i fer-los XOR, repetiria el procés als bytes 3, 4 i 5.

El calendari clau és molt senzill. Per començar, la clau sencera és XORed amb una constant aleatòria de la mateixa longitud que la clau, després es gira a l'esquerra 3 bits. Es torna a girar després de cada iteració de rotació i XOR. El byte més a la dreta s'utilitza en cada iteració a XOR amb el byte més a la dreta del bloc de dades.

L'algoritme de desxifrat és simplement el contrari de l'algoritme de xifratge. A causa de la naturalesa de l'operació XOR, és reversible.

Cripanàlisi

D'un cop d'ull, Madryga sembla menys segur que, per exemple, DES. Totes les operacions de Madryga són lineals. Les caixes S de DES són el seu únic component no lineal, i els defectes d'ells són el que pretenen explotar tant la criptoanàlisi diferencial com la criptoanàlisi lineal. Tot i que les rotacions de Madryga depenen de les dades en petit grau, encara són lineals.

Eli Biham ha revisat l'algoritme sense fer una anàlisi formal. Va notar que "la paritat de tots els bits del text sense format i el text xifrat és una constant, depenent només de la clau. Per tant, si teniu un text sense format i el seu corresponent text xifrat, podeu predir la paritat del text xifrat per a qualsevol text pla. " Aquí, la paritat es refereix a la suma XOR de tots els bits.

El 1995, Ken Shirriff va trobar un atac diferencial a Madryga que requereix 5.000 textos en pla escollits. Biryukov i Kushilevitz (1998) van publicar un atac diferencial millorat que només requeria 16 parells de text en pla escollit, i després van demostrar que es podia convertir en un atac només de text xifrat utilitzant ^2-12 textos xifrats, sota hipòtesis raonables sobre la redundància del text en pla (per exemple, Anglès codificat ASCII ). Un atac de només text xifrat és devastador per a un xifrat de blocs modern; com a tal, probablement sigui més prudent utilitzar un altre algorisme per xifrar dades sensibles.