Redes de Feistel: blocos fundamentais das cifras modernas

No início da década de 1970, Horst Feistel, no centro de pesquisa da IBM, trabalhava na cifra Lucifer quando desenvolveu uma ideia fundamental: é possível construir uma cifra invertível usando uma função de rodada não invertível.

Isso foi revolucionário porque é difícil projetar funções invertíveis que também sejam seguras. A construção de Feistel contorna completamente esse requisito, permitindo o uso de funções de rodada unidirecionais de complexidade arbitrária.

Em uma cifra de Feistel, o bloco de entrada é dividido em duas metades iguais: L, à esquerda, e R, à direita. Cada rodada aplica a função de rodada F a R, calcula o XOR do resultado com L e, em seguida, troca as metades.

Após n rodadas, as duas metades são recombinadas para produzir o texto cifrado. A troca garante que ambas as metades sejam processadas em rodadas alternadas, misturando-as completamente.

A função de rodada F em uma rede Feistel recebe a metade direita e a subchave da rodada como entradas e produz uma saída que é combinada por XOR com a metade esquerda. É fundamental que F não precise ser invertível.

F pode ser arbitrariamente complexa: qualquer combinação de substituições, permutações, operações XOR e aritmética modular. Quanto mais complexa e não linear for F, mais forte será a cifra, pois a descriptografia nunca precisa inverter F.

A descriptografia em uma cifra de Feistel usa exatamente a mesma estrutura da criptografia, mas aplica as subchaves das rodadas em ordem inversa. Isso é possível porque o XOR é sua própria inversa: se A XOR B = C, então C XOR B = A.

Como a descriptografia nunca chama F^-1, a inversa de F, a função de rodada pode ser um resumo criptográfico irreversível, uma tabela de consulta ou qualquer operação complexa sem afetar a invertibilidade da cifra.

A elegância matemática das redes Feistel está no fato de que a estrutura baseada em XOR garante a invertibilidade, independentemente do que F faça. Mesmo que F seja uma função unidirecional como SHA-256, a cifra de Feistel completa continua invertível.

Isso torna as cifras de Feistel extremamente flexíveis. Os criptógrafos podem se concentrar inteiramente em tornar F tão confusa e difusora quanto possível, sabendo que a própria estrutura da rede cuida da invertibilidade.

O Padrão de Criptografia de Dados (DES), publicado em 1977, é uma cifra Feistel de 16 rodadas que opera em blocos de 64 bits com uma chave de 56 bits. Cada rodada usa uma subchave diferente de 48 bits, derivada da chave principal.

A função de rodada do DES inclui uma permutação de expansão, XOR com a subchave, oito caixas S que fornecem não linearidade e uma permutação da caixa P. A combinação fornece confusão e difusão, conforme exigido pelos princípios de projeto de cifras de Shannon.

O Blowfish, projetado por Bruce Schneier em 1993, é uma cifra Feistel de comprimento de chave variável, de 32 a 448 bits, com 16 rodadas. Ele usa caixas S dependentes da chave, tornando impraticáveis os ataques pré-computados.

O Twofish, finalista da competição do AES, amplia as ideias do Blowfish com blocos de 128 bits e 16 rodadas. Ambos continuam sem ataques capazes de quebrá-los e são usados em aplicações como o bcrypt, que utiliza uma versão modificada do Blowfish para gerar resumos criptográficos de senhas.

Uma cifra Feistel balanceada divide o bloco em duas metades iguais. Uma Feistel não balanceada usa metades desiguais, como uma divisão de 3/4 e 1/4.

As redes Feistel não balanceadas podem oferecer vantagens de segurança em determinados contextos e são usadas em algumas cifras especializadas. A família de cifras CAST usa uma estrutura Feistel balanceada de 64 bits.

Em 1988, Michael Luby e Charles Rackoff provaram que uma rede Feistel de 3 rodadas usando funções de rodada pseudoaleatórias é uma permutação pseudoaleatória segura (PRP), e que uma versão de 4 rodadas é uma PRP forte.

Esse resultado teórico deu às redes Feistel uma base sólida de segurança comprovável, não apenas confiança empírica. Ele confirmou que a própria estrutura Feistel contribui para a segurança, além da contribuição da função de rodada.

A Rede de Substituição e Permutação (SPN) usada pelo AES aplica substituição e permutação ao bloco inteiro simultaneamente, em vez de processar metade do bloco por rodada. Isso proporciona uma difusão mais rápida.

O AES alcança difusão completa em apenas 4 rodadas, enquanto a estrutura Feistel do DES precisa de mais rodadas para obter uma difusão comparável. A SPN do AES também se adapta melhor às arquiteturas modernas de processadores com instruções SIMD.

O teorema de Luby-Rackoff trata a função de rodada F como uma função verdadeiramente aleatória. Na prática, F é uma função pseudoaleatória, uma cifra com chave ou uma função de resumo, e não um oráculo verdadeiramente aleatório.

Essa lacuna entre as demonstrações teóricas e as implementações práticas é um tema recorrente na criptografia. As demonstrações fornecem confiança, mas baseiam-se em modelos idealizados. A segurança no mundo real também depende de implementações seguras, livres de vulnerabilidades de canais laterais.

Teste sua compreensão do projeto de redes Feistel.

As redes Feistel são estruturas de cifras de bloco que usam uma função de rodada que não precisa ser invertível. A descriptografia funciona executando a mesma estrutura ao contrário, com as subchaves em ordem inversa.

DES, Blowfish e Twofish são cifras Feistel. O teorema de Luby-Rackoff fornece garantias teóricas de segurança. O AES usa uma estrutura SPN, oferecendo melhor difusão por rodada.