Criptoanálise

A máquina Enigma, utilizada na cifragem e decifragem de mensagens secretas.

A criptoanálise é a arte de tentar descobrir o texto cifrado e/ou a lógica utilizada em sua encriptação (chave). As pessoas que participam desse esforço são denominadas criptoanalistas. Da fusão da criptografia com a criptoanálise, forma-se a criptologia.

A criptoanálise representa o esforço de decodificar ou decifrar mensagens sem que se tenha o conhecimento prévio da chave secreta que as gerou. As diversas técnicas de criptoanálise são os caminhos que os analistas podem seguir para conseguir descobrir ou quebrar a codificação das mensagens que estiverem cifradas, e não apenas a simples decifração de uma mensagem.

Atualmente, a criptoanálise é utilizada a fim de se consultar as tentativas de quebra de segurança de outros tipos de algoritmos e de protocolos criptográficos. Em geral, a quebra ou então, a publicação de uma criptografia é um ato ilegal, previsto em lei. Entretanto, a criptoanálise exclui geralmente os ataques que não alvejam primeiramente fraquezas na criptografia real. Os métodos, tais como o suborno, coerção física, furto de dados, keylogger, embora esses tipos de ataque advém pela necessidade da segurança computacional, estão gradativamente tornando-se menos eficazes em relação a criptoanálise tradicional.

História

A criptoanálise tem se desenvolvido junto com a criptografia, e essa competição pode ser seguida com a história da criptografia, cifras novas que estão sendo projetadas para substituir projetos velhos, e as novas técnicas de criptoanálise inventadas para quebrar os esquemas melhorados. Na prática, são vistos como os dois lados da mesma moeda: a fim de criar uma criptografia segura.

Criptoanálise clássica

Primeira página do manuscrito - Decifrando mensagens criptográficas de Al-Kindi's

Embora o termo criptoanálise seja relativamente recente (foi inventada por William Friedman, em 1920), métodos para quebrar códigos e cifras são muito mais velhos. A primeira explicação gravada, conhecida da criptoanálise, foi realizada pelo árabe Abu Yusuf Yaqub ibn Ishaq al-Sabbah Al-Kindi em Um Guia em Decifração de Mensagens Criptografadas.

A análise de frequência é a ferramenta básica para quebrar cifras clássicas. Em línguas naturais, determinadas letras do alfabeto aparecem mais frequentemente do que outras; em inglês, “e” é a letra mais comum em toda a amostra dada do texto. Similarmente, o dígrafo “th” é o par mais provável de letras, e assim por diante. A análise de frequência confia numa cifra que não esconde esses padrões de frequência. Por exemplo, numa cifra simples de substituição (em que cada letra é substituída simplesmente por outra), a letra mais frequente numa mensagem cifrada de um texto em português seria a que representa a letra “a”.

A análise de frequência confia tanto no conhecimento linguístico, como o faz nas estatísticas, mas, como as cifras se tornaram mais complexas, a matemática aproximou-se gradualmente da criptoanálise. Essa mudança era particularmente evidente durante a Segunda Guerra Mundial, quando os esforços para quebrar cifras de linha central requereram níveis novos de sofisticação matemática. Além disso, a automatização era aplicada pela primeira vez na criptoanálise com a máquina Colossus.

Criptoanálise moderna

Replica de um dispositivo de Bomba

Com a computação usada para beneficiar a criptoanálise na Segunda Guerra Mundial, criaram-se novos possíveis métodos de criptografia de ordem de magnitude elevada e mais complexos do que eram antes.

Avaliando tudo, a criptografia moderna tornou muito mais intensa a criptoanálise do que os sistemas “papel-e-caneta” do passado, e parece agora ser superior à criptoanálise pura. As notas do historiador David Kahn: “Muitos são os criptossistemas oferecidos pelas centenas dos vendedores comerciais hoje que não podem ser quebrados por qualquer método conhecido da criptoanálise. Certamente que, em tais sistemas, mesmo um ataque de texto escolhido, em que um texto selecionado é combinado contra sua mensagem cifrada, não pode entregar a chave que destrava outras mensagens. Por isso, então, a criptoanálise está inoperante. Mas esse não é o fim da história. A criptoanálise pode estar inoperante, mas há – para misturar minhas metáforas – mais do que um único caminho para tirar a pele de um gato”.

Kahn pode ter sido prematuro em sua análise. As cifras fracas não foram extintas, e os métodos criptanalíticos empregados por agências de inteligência remanescem não publicados. Na academia, os projetos novos são apresentados regularmente, e também quebrados frequentemente: a cifra de bloco Madryga de 1984 foi tida como obsoleta devido aos ataques de mensagem cifrada somente em 1998. FEAL-4, proposta como um substituto para o DES, foi demolido por uma enxurrada de ataques vindos da comunidade acadêmica, muito deles completamente praticáveis. Na indústria, também, cifras não são livres de falhas: por exemplo, os algoritmos A5/1, A5/2 e CMEA, usados na tecnologia de telefone celular, podem ser quebrados em horas, minutos ou até em tempo real usando equipamentos computacionais amplamente disponíveis ao público. Em 2001, Wired Equivalent Privacy (WEP), um protocolo usado para a segurança de redes Wi-Fi, foi revelada ser suscetível de um ataque prático de chave relacionada. Essa fraqueza não era realmente do algoritmo em si, mas principalmente devido ao seu uso impróprio dentro do protocolo, de modo a comprometer sua força.

Formas

• Criptoanálise linear é uma forma genérica de criptoanálise. A criptoanálise linear é uma das formas de ataque mais largamente utilizada em cifragem em blocos. A outra maneira é a criptoanálise diferencial.
• Inventado por Martin Hellman e Susan K. Langford em 1994, o ataque por criptoanálise diferencial-linear é uma mistura da criptoanálise linear com a criptoanálise diferencial.
• Criptoanálise diferencial é uma forma genérica de criptoanálise aplicável primeiramente à cifra em bloco, mas também a cifra em fluxo e a cryptographic hash function. Em geral, é o estudo de como as diferenças em uma entrada podem condicionar a diferença resultante na saída. No caso de uma cifra em bloco, isto se refere a um conjunto de técnicas para traçar diferenças através da rede de transformações, descobrindo onde a cifra exibe riscos não aleatórios e explorando tal propriedade para recuperar a chave secreta.

Resultado

A criptoanálise bem sucedida influenciou sem dúvida a história; a habilidade de ler os segredos presumidos e as plantas de outros, pode ser uma vantagem decisiva. Por exemplo, na 1º Guerra Mundial, quebrar o telegrama de Zimmermann era fundamental para trazer os Estados Unidos para guerra. Na segunda guerra mundial, a criptoanálise das cifras alemães - incluindo a máquina Enigma e a cifra de Lorenz – foi conhecido como o ponto decisivo para chegar ao fim da guerra européia por alguns meses e determinar o resultado eventual. Os Estados Unidos beneficiaram-se também da criptoanálise do código ROXO japonês.

Os governos reconheceram por muito tempo os benefícios potenciais da criptoanálise para a inteligência militar e diplomática, e têm estabelecido as organizações dedicadas a quebrar os códigos e as cifras de outras nações, por exemplo, GCHQ e o NSA, as organizações que são ainda muito ativas hoje. Até 2004, relatou-se que os Estados Unidos tinham quebrado cifras Iranianas. Não se sabe, entretanto, se este era criptoanálise pura, ou se outros métodos foram utilizados.

Ataques característicos

Os ataques criptanalíticos variam de potência e o quanto eles podem ameaçar os criptosistemas de mundo-real (real-world). Uma fraqueza de certificação é um ataque teórico que seja improvável de ser aplicado em qualquer situação de mundo-real (real-world); a maioria dos resultados encontrados nas pesquisas criptanalíticas modernas são destes tipos. Essencialmente, a importância de um ataque é dependente das respostas das três perguntas seguintes:

• Que conhecimento e potencial são necessários como pré-requisito?
• Quanta informação secreta adicional é deduzida?
• O que é a complexidade computacional?

Classificação do sucesso da criptoanálise

Os resultados da criptoanálise podem também variar na utilidade. Por exemplo, o criptógrafo Lars Knudsen (1998) classificou vários tipos de ataque em cifras do bloco de acordo com a quantidade e a qualidade da informação secreta que foi descoberta:

• Ruptura total - o atacante deduz a chave secreta.
• Dedução global - o atacante descobre um algoritmo funcionalmente equivalente para a criptografia e descriptografia, mas sem aprender a chave.
• Dedução (local) do exemplo - o atacante descobre os plaintexts adicionais (ou as mensagens cifradas) não conhecidos previamente.
• Dedução da informação - o atacante ganha alguma informação de Shannon sobre os plaintexts (ou as mensagens cifradas) não conhecidos previamente.
• Algoritmo distinguindo - o atacante pode distinguir a cifra de uma permutação aleatória.

As considerações similares aplicam-se aos ataques em outros tipos de algoritmo criptográficos.

Complexibilidade

Os ataques podem também ser caracterizados pela quantidade de recursos que requerem. Isto pode estar no formulário de:

• Tempo - o número “das operações primitivas” que devem ser executadas. Isto é completamente frouxamente; as operações primitivas podiam ser instruções de computador básicas, tais como a adição, XOR, deslocamento, e assim por diante, ou métodos inteiros de criptografia.
• Memória - a quantidade de armazenamento requerida para executar o ataque.
• Dados - a quantidade dos plaintexts e das mensagens cifradas requeridas.

Criptoanálise de criptografia assimétrica

A criptografia assimétrica (ou a criptografia de chave pública) é a criptografia que usa duas chaves; uma confidencial, e uma pública. Tais cifras invariáveis confiam em problemas matemáticos “difíceis” como a base de sua segurança, assim um ponto óbvio do ataque é desenvolver métodos para resolver esses problemas.

A segurança da criptografia das duas chaves depende dos problemas matemáticos.

Os esquemas assimétricos são projetados em torno da dificuldade de resolver vários problemas matemáticos. Se um algoritmo melhorado puder resolver o problema, o sistema está enfraquecido então. Por exemplo, a segurança do esquema da troca da chave de Diffie-Hellman depende da dificuldade de calcular o logaritmo discreto. Em 1983, Don Coppersmith encontrou uma maneira mais rápida de encontrar logaritmos discretos (em determinados grupos), desse modo usam-se grupos criptográficos maiores (ou tipos diferentes de grupos). A segurança de RSA depende (em parte) da dificuldade da fatoração do inteiro - uma descoberta da fatoração acabaria com a segurança de RSA.

Em 1980, era possível fatorar um número de 50 dígitos em 10^12 operações de computador elementares. Em 1984 o último modelo de fatorar algoritmos tinha avançado a um ponto onde um número de 75 dígitos poderia ser fatorado em 10^12 operações. O avanço da tecnologia computacional significou também que as operações poderiam ser executadas com uma velocidade muito maior. A partir da lei de Moore, pode-se dizer que a velocidade dos computadores continuará a aumentar.

Um dígito de 150 números do tipo, usado uma vez em RSA foram fatorados. O esforço era maior do que acima, mas não era utilizado em computadores modernos rápidos. Pelo começo do século XXI, 150 números do dígito foram considerados já não um tamanho chave grande bastante para RSA. Os números com cem dígitos diversos eram considerados ainda difíceis de fatorar em 2005, embora os métodos continuarão provavelmente a melhorar ao longo do tempo, requerendo com que o tamanho chave mantenha o ritmo ou os algoritmos novos serão usados.

Uma outra característica que destinge os esquemas assimétricos é que, ao contrário dos ataques em criptosistemas simétricos, qualquer criptanálise tem a oportunidade de empregar o conhecimento ganho da chave pública.

Aplicações computacionais quantum

Os computadores quantum têm potencial para serem usados na criptanálise. Porque os estados quantum podem existir na superposição, um paradigma novo para a computação é possível. Peter Shor dos laboratórios Bell provou a possibilidade, e as várias equipes têm demonstrado um outro aspecto da engenharia de computadores quantum há anos. Assim, somente a prova de projetos da possibilidade foi demonstrada.

Ligações externas

• Curso de Criptografia com Maple