Xarxa de Feistel

Una xarxa de Feistel és una construcció utilitzada en els algorismes de xifratge per blocs, designada en honor del criptòleg d'IBM, Horst Feistel. Es va fer servir per primera vegada en Lucifer i DES. Aquesta estructura ofereix diversos avantatges, el xifratge i el desxifratge tenen una arquitectura similar fins i tot idèntica en certs casos. La implementació material és també més fàcil amb aquest sistema fins i tot amb els canvis que hi ha hagut des de la fi dels anys 1970. Una xarxa de Feistel descansa sobre principis senzills entre els quals les permutacions, les substitucions, els intercanvis de blocs de dades i una funció que pren per entrada una clau intermediària a cada etapa.

És versemblant que Feistel no sigui l'únic inventor d'aquesta arquitectura. Durant una conferència Don Coppersmith va donar a entendre que Bill Notz i Lynn Smith (de l'equip d'IBM que treballava en el DES) havien estat en gran part l'origen de la xarxa de Feistel tal com la coneixem.

Estructura

Una xarxa de Feistel es subdivideix en diverses rondes o etapes. En la seva versió equilibrada, la xarxa tracta les dades en dues parts d'idèntica mida. A cada etapa, els dos blocs s'intercanvien després un dels blocs es combina amb una versió transformada de l'altre bloc. Per simplificar, la meitat de les dades es codifiquen amb la clau, després el resultat d'aquesta operació s'afegeix gràcies a un xor (o exclusiu) a l'altra meitat de les dades. Després en la ronda següent, s'inverteix: és a la ronda de l'última meitat de ser avaluada després de ser afegida amb un xor a la primera meitat, excepte que s'utilitzen les dades no avaluades anteriorment (si no fos això no serviria de res fer més de dos rondes). L'esquema adjunt mostra la marxa de les dades ("més" encerclat representa el xor).

Cada ronda utilitza una clau intermediària, en general treta de la clau principal via una generació anomenada programació de claus. Les operacions efectuades durant el xifratge amb aquestes claus intermediàries s'especifiquen a cada algorisme.

En el cas de DES, la xarxa de Feistel posseeix 16 rondes, cadascuna amb una subclau. Aquestes diferents claus permeten millorar la robustesa d'un algorisme de cara al criptoanàlisi. Una variant, la xarxa de Feistel no-equilibrada talla les dades en dues parts de mides diferents. Aquesta variant ha estat utilitzada en McGuffin de Bruce Schneier, o també Skipjack, candidat a AES.

Definició formal

Una definició formal d'una xarxa de Feistel es pot donar de diverses formes. Es reprèn aquí la notació utilitzada per Knudsen en Parcial and Higher Order Differentials and Aplicacions to DES.

C_{0}^{L}=P^{L}~

i

C_{0}^{R}=P^{R}~

C_{i}=(C_{i}^{L},C_{i}^{R})=(C_{i-1}^{R},f(C_{i-1}^{R},K_{i})+C_{i-1}^{L})~

C^{L}=C_{r}^{L}~

i

C^{R}=C_{r}^{R}~

l'exponent representa la sub-part del bloc considerada (L a l'esquerra, R a la dreta).

$P~$ correspon al bloc de text clar, $P_{i}^{L}$ correspon al bloc de l'esquerra en l'entrada de la ronda $i~$

$C~$ correspon al bloc de text xifrat, $C_{i}^{R}$ correspon al bloc de la dreta en la sortida de la ronda $i~$

$K_{i}~$ és la clau de la ronda $i~$ , es calcula gràcies a una programació de claus de la clau principal

$r~$ és el nombre de rondes en l'algorisme

$+~$ és una operació d'un grup commutatiu (sovint un XOR o una addició)

Composició de les rondes

Cada ronda aplica diverses transformacions sobre les dades que provenen de la ronda precedent:

permutació dels bits via les caixes-P

funció no lineal (substitució) amb les caixes-S

bareja lineal utilitzant la funció XOR

aplicació de la clau de la ronda (integrada en una funció o via un XOR)

S'utilitzen els termes de confusió i difusió per descriure la propagació de les informacions en l'estructura (termes utilitzats per Claude Elwood Shannon). En efecte, una modificació d'un bit en entrada produirà variacions molt importants en les etapes intermèdies i en la sortida. Un terme més recent per descriure aquest fenomen és el d'efecte allau. La utilització de les permutacions permet millorar la difusió mentre que les substitucions tenen com a efecte augmentar la confusió.

Criptoanàlisi

Els esquemes de Feistel s'han analitzat àmpliament i s'han examinat pels experts. Hi ha diversos atacs possibles però els dos principals són:

el criptoanàlisi lineal;

el criptoanàlisi diferencial.

Aquests mètodes s'han provat sobre DES i sobre altres algorismes similars. Però això no significa que la utilització d'una xarxa de Feistel comportarà obligatòriament vulnerabilitats significatives. Gràcies a l'addició de diferents tècniques i amb un disseny ben fet, es pot millorar considerablement la resistència d'un algorisme basat en Feistel. És el cas de Blowfish que és criptogràficament segur a data de desembre de 2008.

En general, els criptoanalistes ataquen primer versions disminuïdes dels xifratges, és a dir amb menys rondes.

Algorismes

Un gran nombre d'algorismes utilitza xarxes de Feistel, amb variants. Heus aquí una llista no exhaustiva:

DES

Blowfish

Twofish

Camellia

OAEP

RC5