Rede Feistel

Uma rede Feistel é uma construção usada em algoritmos de cifra de bloco , em homenagem ao criptologista IBM Horst Feistel . Foi usado pela primeira vez em Lúcifer e DES . Esta estrutura oferece várias vantagens, a encriptação e a desencriptação têm uma arquitectura semelhante ou mesmo idêntica em certos casos. A implementação de hardware também é mais fácil com esse sistema, embora as coisas tenham mudado bastante desde o final dos anos 1970. Uma rede Feistel é baseada em princípios simples, incluindo permutações, substituições, trocas de blocos de dados e uma função que toma como entrada uma chave intermediária em cada andar .

É provável que Feistel não seja o único inventor dessa arquitetura. Durante uma palestra, Don Coppersmith deu a entender que Bill Notz e Lynn Smith (da equipe da IBM que trabalha com DES ) foram os grandes responsáveis pela origem da rede Feistel como a conhecemos.

Estrutura

Uma rede Feistel é subdividida em várias torres ou andares. Em sua versão balanceada , a rede processa dados em duas partes do mesmo tamanho. Em cada turno, os dois blocos são trocados e, em seguida, um dos blocos é combinado com uma versão transformada do outro bloco. Para simplificar, metade dos dados são codificados com a chave, então o resultado desta operação é adicionado graças a um xor (ou exclusivo) à outra metade dos dados. Então, na próxima rodada, invertemos: é a vez da última metade ser criptografada e, em seguida, ser adicionada com um xor à primeira metade, exceto que usamos os dados criptografados anteriormente (caso contrário, seria inútil fazer mais mais de duas voltas). O diagrama ao lado mostra o fluxo de dados (o ⊕ representa o xor). Cada rodada usa uma chave intermediária, normalmente retirada da chave mestra por meio de uma geração chamada programação de chave . As operações realizadas durante a criptografia com essas chaves intermediárias são específicas para cada algoritmo.

No caso do DES , a rede Feistel possui 16 voltas, cada uma com uma subchave. Essas diferentes chaves permitem melhorar a robustez de um algoritmo diante da criptanálise .

Alternativamente, a rede Feistel desequilibrada divide os dados em duas partes de tamanhos diferentes. Esta variante foi usada em MacGuffin de Bruce Schneier , ou Skipjack , candidato a AES .

Definição formal

Uma definição formal de uma rede Feistel pode ser fornecida de várias formas. Usamos aqui a notação usada por Knudsen em Diferenciais de ordem parcial e superior e aplicativos para DES .

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

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} ~

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

o expoente representa a subparte do bloco considerado (L à esquerda, R à direita).
$P ~$ corresponde ao bloco de texto claro, corresponde ao bloco esquerdo na entrada do passeio $P_ {i} ^ {L}$ $eu ~$
$C ~$ corresponde ao bloco de texto cifrado, corresponde ao bloco à direita na saída do passeio $C_ {i} ^ {R}$ $eu ~$
$K_ {i} ~$ é a chave do passeio , ela é calculada usando uma programação chave da chave principal $eu ~$
$r ~$ é o número de voltas no algoritmo
$+ ~$ é uma operação em um grupo comutativo (geralmente um XOR ou uma adição)

Composição das torres

Cada turno aplica várias transformações aos dados do turno anterior:

permutação de bits via P-Boxes
função não linear ( substituição ) com S-Boxes
mistura linear usando a função XOR
aplicação da chave do torno (integrada em uma função ou através de um XOR)

Os termos confusão e difusão são usados para descrever a propagação da informação na estrutura (termos usados por Claude Shannon ). Na verdade, uma modificação de um bit de entrada produzirá variações muito significativas nos estágios intermediários e na saída. Um termo mais recente para descrever esse fenômeno é o efeito avalanche . O uso de permutações permite melhorar a difusão, enquanto as substituições têm o efeito de aumentar a confusão.

Criptanálise

Os esquemas de Feistel foram amplamente analisados e revisados por especialistas. Vários ataques são possíveis, mas os dois principais são:

a criptoanálise linear ;
a criptoanálise diferencial .

Esses métodos provaram seu valor no DES e em outros algoritmos semelhantes. Mas isso não significa que o uso de uma rede Feistel levará necessariamente a vulnerabilidades significativas. Com a adição de diferentes técnicas e com bom design, pode-se melhorar significativamente a resistência de um algoritmo baseado em Feistel. Este é o caso do Blowfish, que é criptograficamente seguro a partir da data dedezembro 2008.

Em geral, os criptanalistas atacam primeiro as versões cifras diminuídas , ou seja, com menos voltas.

Algoritmos

Um grande número de algoritmos usa redes Feistel, com variações. Aqui está uma lista não exaustiva: