Design do DES e a cifra Lucifer

Em 1971, Horst Feistel, do IBM Research, desenvolveu uma cifra chamada Lucifer como parte de um projeto de segurança bancária para a Lloyd's of London. Lucifer foi uma das primeiras cifras de blocos modernas, usando uma chave de 128 bits e blocos de 128 bits.

Lucifer demonstrou que era possível construir uma cifra de blocos forte usando a estrutura de Feistel: rodadas alternadas de substituição e permutação aplicadas às metades dos blocos. Ela foi a antecessora direta do DES.

O DES aplica 16 rodadas da estrutura de Feistel a blocos de 64 bits. Em cada rodada, o bloco de 64 bits é dividido em duas metades de 32 bits. A metade direita é expandida para 48 bits, combinada com XOR com uma subchave de 48 bits, passa pelas caixas S, é permutada e combinada com XOR com a metade esquerda.

As metades são então trocadas e o processo se repete. Após 16 rodadas, uma permutação final produz o texto cifrado de 64 bits. A decifragem usa a mesma estrutura, com as subchaves na ordem inversa.

O DES cifra dados em blocos de 64 bits (8 bytes). Esse tamanho fixo de bloco era adequado ao hardware de 1977, mas se tornou um problema de segurança. Com dados suficientes, colisões do paradoxo do aniversário se tornam prováveis.

Com blocos de 64 bits, padrões estatísticos surgem após aproximadamente 2^32 blocos (~32 GB de dados cifrados com a mesma chave). Esse ataque Sweet32 tornou o 3DES inseguro para tráfego de alto volume, como HTTPS.

O DES usa uma chave de 64 bits, mas 8 desses bits são bits de paridade usados para detectar erros, não para cifrar. Portanto, o comprimento efetivo da chave é de apenas 56 bits.

Isso significa que existem apenas 2^56 (aproximadamente 72 quatrilhões) de chaves DES possíveis. Pelos padrões de 1977, isso era considerado adequado. Em 1997, já era comprovadamente possível quebrá-la com um adversário determinado.

O DES começa com uma permutação inicial (IP), que reorganiza os 64 bits do bloco de texto claro, e termina com uma permutação final (IP^-1), que é sua inversa exata. Essas permutações não acrescentam nenhuma força criptográfica.

Elas foram projetadas para obter eficiência de hardware em arquiteturas específicas de circuitos integrados dos anos 1970, permitindo carregar bits mais rapidamente nos registradores. A análise moderna confirma que elas não contribuem em nada para a segurança.

As oito caixas S (caixas de substituição) são o centro da não linearidade do DES. Cada caixa S recebe 6 bits de entrada e produz 4 bits de saída usando uma tabela de consulta fixa. Os 2 bits externos selecionam a linha, e os 4 bits internos selecionam a coluna.

Sem a não linearidade fornecida pelas caixas S, o DES seria uma cifra puramente linear, trivialmente quebrável por álgebra linear. O projeto específico das caixas S do DES resiste à criptoanálise diferencial.

Depois das caixas S, o DES aplica uma permutação de caixa P que reorganiza os 32 bits de saída das caixas S. Isso fornece difusão, espalhando a saída de cada caixa S para afetar várias caixas S na rodada seguinte.

A caixa P foi cuidadosamente projetada para maximizar a difusão: cada bit de saída de uma caixa S afeta pelo menos duas caixas S diferentes na rodada seguinte, garantindo um efeito avalanche rápido.

DES deriva 16 subchaves diferentes de 48 bits da chave mestra de 56 bits, uma para cada rodada. O esquema de chaves começa aplicando uma escolha permutada (PC-1) para remover os bits de paridade e reordenar os bits da chave.

Os 56 bits são divididos em duas metades de 28 bits, que sofrem uma rotação para a esquerda de 1 ou 2 posições a cada rodada. Em seguida, uma escolha permutada (PC-2) seleciona 48 dos 56 bits para formar a subchave de cada rodada.

A NSA trabalhou com a IBM durante o desenvolvimento do DES, reduzindo o comprimento da chave de 128 bits do Lucifer para 56 bits e modificando o projeto das caixas S. Isso desencadeou décadas de controvérsia sobre a possível introdução de portas dos fundos.

Na década de 1990, funcionários da NSA confirmaram que haviam reforçado as caixas S contra a criptoanálise diferencial, uma técnica descoberta pela IBM em 1974. A NSA conhecia a criptoanálise diferencial havia anos antes da comunidade acadêmica, o que sugere que tornou o DES mais resistente, não mais fraco.

O DES foi adotado como o Padrão Federal de Processamento de Informações 46 em janeiro de 1977, após um processo de avaliação competitiva. Ele se tornou a cifra padrão para dados governamentais não sigilosos e foi amplamente adotado pelo setor bancário e pela indústria.

A padronização do DES foi historicamente significativa: foi o primeiro algoritmo criptográfico publicamente disponível e endossado pelo governo. Ela impulsionou o desenvolvimento de implementações em hardware e estabeleceu o modelo para futuros processos de padronização de cifras.

O DES em si é uma cifra de bloco, que criptografa exatamente 64 bits por vez. As mensagens reais são mais longas, portanto os modos de operação definem como aplicar a cifra a vários blocos. Os modos comuns incluem ECB (criptografa cada bloco de forma independente), CBC (aplica XOR a cada bloco com o texto cifrado anterior antes da criptografia), CFB, OFB e CTR.

ECB é o modo mais fraco: blocos de texto simples idênticos produzem blocos de texto cifrado idênticos, criando padrões visíveis. Os modos CBC e CTR eliminam essa fraqueza e são preferidos para uso prático de DES e 3DES.

Teste seus conhecimentos sobre os parâmetros de projeto do DES.

O DES evoluiu da cifra Lucifer da IBM para uma cifra de Feistel de 16 rodadas, com blocos de 64 bits e chaves efetivas de 56 bits. Sua segurança provém de 8 caixas S não lineares, que fornecem confusão, da caixa P, que fornece difusão, e de 16 rodadas, que amplificam o efeito avalanche.

O envolvimento da NSA no projeto das caixas S foi controverso, mas acabou melhorando a resistência à criptoanálise diferencial. A chave de 56 bits do DES, projetada para o hardware de 1977, mostrou-se inadequada no final da década de 1990.