Uma rápida introdução à criptografia: Parte II
As cifras vistas até então, na Parte I, são relativamente simples pois precisam ser utilizadas por pessoas diretamente. Algo excessivamente complexo levaria a um longo tempo para codificação e decodificação mas, também, leva a possibilidade de erros em alguma, ou ambas, operações.
A automatização das cifras permite não só uma maior velocidade no processo, com menos erros, mas também cifras bem mais complexas que dificultem o processo de criptoanálise.
O caso mais popular de automatização de cifras é a Enigma, uma máquina criptográfica alemã utilizada principalmente na Segunda Guerra Mundial. A Enigma é uma máquina eletromecânica que implementa uma cifra polialfabética. O operador, criando uma mensagem cifrada, digitaria no teclado a mensagem original letra a letra. A cada letra teclada, a máquina ilumina uma letra no painel. Assim, se o operador digita “A” e a máquina acende “F”, então o operador substituiria a letra “A” por “F” na mensagem.
A Enigma possui duas partes principais. A primeira é o painel de cabos. Este painel implementa uma substituição simples entre letras. Se duas letras estão conectadas no painel, uma é substituída pela outra. Se uma letra não está conectada, ela não é substituída. O teclado é conectado diretamente ao painel de cabos.
A segunda parte importante são os rotores. Na versão original, três rotores estão presentes. Cada rotor implementa um circuito elétrico que substitui uma letra na entrada a uma letra na saída, de forma fixa.
O sinal elétrico que chega no primeiro rotor advém diretamente do painel de cabos. Na Enigma, os rotores são colocados de forma sequencial, de forma que a saída de uma alimente a entrada de outra. Cada rotação do rotor implementa uma tabela de substituição monoalfabética diferente. Se os rotores fossem estáticos, eles em conjunto ainda implementariam apenas uma substituição monoalfabética. Porém, a Enigma rotaciona os rotores a medida que a mensagem é digitada. O primeiro rotor gira uma posição a cada letra digitada; o segundo rotor gira uma posição a cada rotação completa do primeiro rotor; o terceiro, gira uma posição a cada rotação completa do segundo rotor. O efeito é uma cifra polialfabética complexa.
Para iniciar a codificação e permitir a correta decodificação, os dois operadores se comunicando devem concordar com uma configuração inicial para as máquinas: quais três rotores serão utilizados (de um conjunto de cinco), a ordem dos rotores, a posição inicial de cada uma e a configuração dos cabos no painel de cabos. Esta configuração é a chave da cifra. Naturalmente, não se pode transmitir a chave por meio não seguro. A solução adotada envolvia os operadores receberem periodicamente um livro contendo chaves diárias. De posse deste livro, a cada dia todos os operadores introduziam a chave indicada pelo livro no início do dia.
Se todas as mensagens em um dia fossem codificadas com a mesma chave, isso potencialmente introduziria uma insegurança na cifra — métodos de criptoanálise tipicamente dependem de uma grande quantidade de mensagens cifradas com a mesma chave para serem efetivos. Para aumentar a segurança, a política de uso da Enigma faz uso da chave de mensagem. Cada mensagem contém uma nova chave a ser utilizada na próxima mensagem. Por padrão, esta chave apenas indica uma nova posição inicial dos rotores (o painel é mantido fixo ao longo do dia). A posição de cada rotor é dada por uma letra e, assim, uma chave de mensagem é uma combinação de três letras. Estas três letras são escolhidas arbitrariamente pelo operador enviando a mensagem e é a primeira parte da mensagem sendo enviada.
O operador que recebe a mensagem cifrada utiliza a chave anterior (se for a primeira mensagem, esta é a chave diária) para decodificar a mensagem; a decodificação revelará a próxima chave e, antes de decodificar a próxima mensagem a configuração da máquina deve ser alterada de acordo.
As mensagens cifradas podem ser transmitidas por diversos meios, incluindo telégrafo e rádio, que são sujeitas a erros na transmissão. Enquanto poucos erros no meio de uma mensagem usualmente não causam problemas, um erro na transmissão da chave de mensagem impediria a decodificação de todas as mensagens posteriores até o final do dia. Como precaução, os operadores eram instruídos a repetirem a chave no início da mensagem. Se a chave for “ABC”, então o início da mensagem conteria “ABCABC”.
Durante muito tempo a Enigma foi considerada inquebrável. Com três rotores (de cinco) e dez cabos, o número de chaves possíveis é de 159 quintilhões, tornando impossível a quebra por força bruta na época.
A complexidade da Enigma estava muito além da capacidade dos criptoanalistas tradicionais da época para encontrar atalhos e evitar força bruta. Ademais, a máquina já estava em uso antes do início da Segunda Guera Mundial e a pressão para quebrar a cifra era baixa. Uma exceção era a Polônia, espremida entre a Alemanha e a União Soviética e constantemente preocupada com as aspirações militares de seus vizinhos. De fato, o primeiro grande avanço na criptoanálise da Enigma veio do matemático polonês Marian Rejewski que fez uso da repetição da chave para desenvolver um método para reduzir consideravelmente o número de chaves possíveis. Adicionalmente, Rejewski desenvolveu as chamadas bombas, máquinas Enigma adaptadas para encontrar automaticamente chaves. Para a Enigma original, as bombas eram capazes de encontrar a chave diária em cerca de 2 horas.
Os poloneses efetivamente quebraram a Enigma na época pré-guerra, tornando toda comunicação alemã transparente. Ao mesmo tempo, o ocidente ainda acreditava que a Enigma era essencialmente inquebrável. Os aliados apenas foram informados dos avanços na criptoanálise da Enigma quando, na iminência da Segunda Guerra, todas Enigmas passaram a utilizar mais rotores e mais cabos, tornando excessivamente custoso o processo de criptoanálise para os poloneses.
A tarefa de dar continuidade na criptoanálise ficou centralizada no Reino Unido, em particular em Bletchley Park, onde criptoanalistas, incluindo Alan Turing, receberam com grande entusiasmo a prova de que a Enigma podia ser quebrada afinal.
Com muito mais recursos que os poloneses, os britânicos foram capazes de desenvolver mais e melhores bombas. O primeiro computador eletrônico programável da história, o Colossus, foi desenvolvido neste contexto, ainda que para decifrar outra máquina criptográfica alemã — a Cifra de Lorenz. Criticamente, os criptoanalistas também desenvolveram diversas técnicas para substituir o processo de Rejewski uma vez que ficava evidente que os alemães iriam se dar conta em algum momento que a repetição da chave era uma fraqueza da cifra, o que de fato ocorreu.
Entre estas técnicas estavam se aproveitar do fato de que as chaves de mensagem não costumavam ser bem escolhidas. Com frequência eram utilizadas iniciais de nomes e tentativas de criar chaves aleatórias “batendo as mãos no teclado” geram padrões bem definidos (se a primeira letra vinha do lado esquerdo do teclado, a próxima provavelmente viria do lado direito e a terceira novamente do lado esquerdo, por exemplo). Turing em particular se aproveitou da estrutura rígida de certas mensagens para deduzir algumas palavras, que eram então utilizadas para auxiliar no processo.
Como resultado dos esforços iniciados por Rejewski, os aliados puderam interceptar comunicações alemãs sem grandes problemas, o que certamente teve papel decisivo na guerra.
O próximo grande avanço em cifras veio por meio dos computadores digitais. Cifras como algoritmos para computadores podem ser extremamente complexos, sem restrições físicas as quais máquinas eletromecânicas estão sujeitas. Adicionalmente, é trivial trocar o algoritmo em um computador, permitindo múltiplas cifras em uma só máquina.
A popularização de computadores trouxe muitas novas cifras disponíveis para uso, em particular devido a necessidade de comunicação segura em um mundo incrementalmente globalizado. De fato, o grande número de cifras começou a se tornar um problema, pois a negociação entre partes sobre qual cifra utilizar era um passo indesejado na comunicação.
Em 1977, o órgão estadunidense responsável por estabelecer padrões nacionais definiu um padrão de cifra recomendado para uso civil no país. O Data Encryption Standard (DES) é uma cifra que opera diretamente em bits, ao contrário de letras, fonemas ou outros símbolos de maior ordem. A vantagem de operar diretamente em bits é a facilidade de codificar e decodificar conteúdos genéricos e não apenas texto —e.g. imagens, sons, vídeos, programas.
As cifras vistas até então são cifras de fluxo. Estas cifras se caracterizam por codificarem um símbolo por vez — como na Enigma, uma letra entra e uma letra sai. O DES, no entanto, é uma cifra de bloco. Esta cifra recebe um bloco de 64 bits e o codifica por inteiro, independente do seu conteúdo. Em uma codificação direta, 64 bits são suficientes para 8 caracteres ASCII, o que significa que 8 caracteres são criptografados de forma simultânea e influenciam uns aos outros: mudar um único caracter (de fato, um único bit) altera completamente o bloco resultante. Isto torna completamente ineficaz qualquer tipo de análise de frequência e virtualmente todos os métodos tradicionais de criptoanálise de cifras de fluxo.
O DES trabalha com chaves de 64 bits, dos quais 8 são bits de verificação e, portanto, 56 bits são realmente úteis, resultando em 2⁵⁶ possíveis chaves. Interessantemente, a proposta original do DES, vinda da IBM, utilizava todos 64 bits como chave, mas o governo americano decidiu reduzir o número de bits úteis para garantir que o número de chaves estivesse dentro das possibilidades de quebra por força bruta pelos supercomputadores do governo.
A operação do DES envolve misturar os bits da chave com os bits do bloco de forma que o processo seja reversível quando a mesma chave é utilizada para decodificação. Este site explica o algoritmo completo.
No final da década de 90, os 56 bits já não eram mais suficientes com o crescimento da capacidade computacional e novas técnicas de criptoanálise, em particular a criptoanálise diferencial. Hoje é possível testar todas as chaves de 56 bits em pouco mais de um dia com hardware especializado.
Muitos algoritmos foram propostos no final da década de 90 para substituir o vácuo deixado pelo DES. O 3DES (Triple-DES) é ainda hoje popular e faz uso de três DES concatenados, com uma chave de 168 bits. Porém, em 2001 um novo padrão foi definido, denominado Advanced Encryption Standard (AES). O AES tem várias semelhanças com o DES, mas foi desenvolvido para ser resistente às técnicas descobertas após o DES e suportar chaves maiores, permitindo a escolha entre 128, 192 ou 256 bits.
A segurança do AES, e de todos os algoritmos vistos até então, advém da esperança de não haver atalhos para encontrar a chave (e que a chave não é algo óbvio ou conhecida, naturalmente). É necessário testar todas as chaves possíveis e há um número exponencial delas. Atalhos como os encontrados para a Enigma podem reduzir drasticamente o número de chaves que devem ser testadas ou mesmo retornar diretamente a chave. Criptoanalistas procuram por estes atalhos constantemente. Até então, o AES se mostrou bastante seguro e é hoje um padrão de facto mundial, amplamente utilizado para criptografia em diversas aplicações. Mesmo o uso da menor chave, 128 bits, garante ampla proteção contra ataques de força bruta e os poucos ataques conhecidos não são muito efetivos.
