Cifra Feistel

Na criptografia, uma cifra de Feistel ou rede de Feistel é uma estrutura simétrica usada na construção de cifras de bloco, o nome é uma homenagem ao físico e criptógrafo alemão Horst Feistel, que foi o pioneiro na pesquisa enquanto trabalhava na IBM (EUA); esta cifra é comumente conhecida como rede de Feistel. Uma grande quantidade das cifras de bloco utilizam este esquema, incluindo o Data Encryption Standard (DES). A estrutura de Feistel tem a vantagem de que as operações de cifragem e decifragem são muito semelhantes, sendo idênticas em alguns casos, necessitando apenas da utilização das chaves na ordem inversa. Portanto, a quantidade de código ou de circuitos necessária para implementar tal cifra é praticamente a metade, pois não precisamos implementar dois algoritmos diferentes, um para cifragem e outro para decifragem.

Uma rede de Feistel é uma cifra iterada com uma função interna chamada função rodada.^[1]

História

As redes de Feistel foram vistas pela primeira vez comercialmente na cifra Lucifer da IBM, projetada por Horst Feistel e Don Coppersmith. As redes de Feistel se ganharam maior importância quando o Governo Federal dos Estados Unidos adotou o DES (uma cifra baseada na cifra de Lucifer, com mudanças realizadas pela NSA). Tal como outros componentes do DES, a natureza iterativa da construção de Feistel torna fácil a implementação do sistema de encriptação em hardware. (particularmente no hardware disponível na época em que o DES foi projetado).

Trabalho teórico

Muitas cifras de blocos simétricas modernas e algumas antigas também se baseiam nas redes de Feistel (e.g. a cifra de bloco GOST 28147-89), e a estrutura e propriedades da cifra de Feistel tem sido extensivamente explorado por criptógrafos. Especificamente, Michael Luby e Charles Rackoff analisaram a construção da cifra de Feistel, e provaram que se a função rodada é uma função pseudoaleatória criptograficamente segura, como Ki usado como semente, então 3 rodadas é suficiente para tornar a cifra de blocos uma permutação pseudoaleatória, enquanto que 4 rodadas é suficiente para torna-la uma permutação pseudoaleatória forte (o que significa que esta permanece pseudoaleatória mesmo na presença de um adversário que tenha acesso ao oráculo).^[2]

Devido a este importante resultado alcançado por Luby e Rackoff, as cifras de Feistel são as vezes chamadas de cifras de bloco Luby-Rackoff. Além disso, o trabalho teórico generalizou a construção de alguma forma, e forneceu limites mais precisos para a segurança.^[3]

Detalhes da construção

Seja ${\rm {F}}$ a função rodada e sejam $K_{0},K_{1},\ldots ,K_{n}$ as subchaves para as rodadas $0,1,\ldots ,n$ , respectivamente.

Então a operação básica é como se segue:

Divida o bloco do texto em claro em duas partes de mesmo tamanho, ( $L_{0}$ , $R_{0}$ ) Para cada rodada $i=0,1,\dots ,n$ , compute

L_{i+1}=R_{i}\,

R_{i+1}=L_{i}\oplus {\rm {F}}(R_{i},K_{i})

.

Então o criptograma é $(R_{n+1},L_{n+1})$ .

A decriptação do criptograma $(R_{n+1},L_{n+1})$ é alcançada pela seguinte computação $i=n,n-1,\ldots ,0$

R_{i}=L_{i+1}\,

L_{i}=R_{i+1}\oplus {\rm {F}}(L_{i+1},K_{i})

.

Então $(L_{0},R_{0})$ é o texto em claro novamente.

Uma vantagem do modelo de Feistel comparado a rede substituição-permutação é que a função rodada ${\rm {F}}$ não tem inversa.

O diagrama ilustra a encriptação e a decriptação. Note que há uma inversão na ordem das subchaves durante a decriptação; esta é a única diferença entre a encriptação e a decriptação.

Cifra de Feistel Desbalanceada

A cifra de Feistel desbalanceada usa uma estrutura modificada onde $L_{0}$ e $R_{0}$ não possuem o mesmo tamanho.^[4] O algoritmo de encriptação Skipjack é um exemplo de tal cifra. O transponder de assinatura digital do Texas Instruments usa a propriedade da cifra de Feistel desbalanceada para realizar autenticação desafio-resposta.^[5]

O Thorp shuffle é um caso extremo de uma cifra de Feistel desbalanceada na qual um dos lado é um único bit. Este provavelmente apresenta uma maior segurança que uma cifra de Feistel mas requer mais rodadas.^[6]

Outros usos

A construção de Feistel é também usada em algoritmos de criptografia de cifras de bloco. Por exemplo, o esquema Optimal Asymmetric Encription Padding (OAEP) usa uma simples rede de Feistel para aleatorizar os criptogramas em certo esquema de encriptação de chave assimétrica.

Um algoritmo de Feistel generalizado pode ser usado para criar permutações fortes em pequenos domínios (veja Format-Preserving Encryption).

Redes de Feistel como um componente de projeto

Seja a cifra inteira uma cifra de Feistel ou não, redes de Feistel podem ser usadas como componentes de um projeto de cifra. Por exemplo, o MISTY1 é uma cifra de Feistel usando uma rede Feistel de 3 rodadas em sua função rodada, o Skipjack é uma cifra de Feistel modificada usando uma rede de Feistel em sua permutação G, e o Threefish (parte do Skein) é uma cifra de bloco Feistel que não utiliza uma função MIX.

Lista de cifras de Feistel

Cifras de Feistel ou modificações da cifra de Feistel: Blowfish, Camellia, CAST-128, DES, FEAL, ICE, KASUMI, LOKI97, Lucifer, MARS, MAGENTA, MISTY1, RC5, TEA, Triple DES, Twofish, XTEA, GOST 28147-89

Generalizações da cifra de Feistel: CAST-256, MacGuffin, RC2, RC6, Skipjack, SMS4, CLEFIA

Referências

↑ Handbook of Applied Cryptography by Alfred J. Menezes, Paul C. van Oorschot, Scott A. Vanstone. Fifth Printing (August 2001) page 251.
↑ Luby, Michael; Rackoff, Charles (1988), «How to Construct Pseudorandom Permutations from Pseudorandom Functions», SIAM Journal on Computing, ISSN 0097-5397, 17 (2): 373–386, doi:10.1137/0217022
↑ Patarin, Jacques (2003), Boneh, Dan, ed., «Luby-Rackoff: 7 Rounds Are Enough for 2^n(1−ε) Security» (PDF), Advances in Cryptology—CRYPTO 2003, Lecture Notes in Computer Science, 2729: 513–529, doi:10.1007/b11817, consultado em 27 de julho de 2009
↑ http://www.schneier.com/paper-unbalanced-feistel.html
↑ S. Bono, M. Green, A. Stubblefield, A. Rubin, A. Juels, M. Szydlo. "Security Analysis of a Cryptographically-Enabled RFID Device". In Proceedings of the USENIX Security Symposium, August 2005. (pdf)
↑ Ben Morris, Phillip Rogaway, Till Stegers. "How to Encipher Messages on a Small Domain". CRYPTO 2009. (pdf)

[1] Handbook of Applied Cryptography by Alfred J. Menezes, Paul C. van Oorschot, Scott A. Vanstone. Fifth Printing (August 2001) page 251.

[pseudorandom-2] Luby, Michael; Rackoff, Charles (1988), «How to Construct Pseudorandom Permutations from Pseudorandom Functions», SIAM Journal on Computing, ISSN 0097-5397, 17 (2): 373–386, doi:10.1137/0217022

[7-rounds-3] Patarin, Jacques (2003), Boneh, Dan, ed., «Luby-Rackoff: 7 Rounds Are Enough for 2^n(1−ε) Security» (PDF), Advances in Cryptology—CRYPTO 2003, Lecture Notes in Computer Science, 2729: 513–529, doi:10.1007/b11817, consultado em 27 de julho de 2009

[4] ttp://www.schneier.com/paper-unbalanced-feistel.html

[crypto-rfid-5] S. Bono, M. Green, A. Stubblefield, A. Rubin, A. Juels, M. Szydlo. "Security Analysis of a Cryptographically-Enabled RFID Device". In Proceedings of the USENIX Security Symposium, August 2005. (pdf)

[thorp-6] Ben Morris, Phillip Rogaway, Till Stegers. "How to Encipher Messages on a Small Domain". CRYPTO 2009. (pdf)

[1]

[2]

[3]

[4]

[5]

[6]