Detalhes

Categoria: Curso de Criptologia

Atualização: Terça, 21 Abril 2009 20:59

Autor: vovó Vicki

Acessos: 22140

1. Introdução

Desde a época em que estava escrevendo Applied Cryptography sou solicitado a recomendar um livro sobre criptoanálise. Infelizmente minha resposta é que, apesar de existirem bons livros sobre criptografia, não existem livros, bons ou ruins, sobre criptoanálise. É uma lacuna que não vejo ser preenchida nos próximos tempos. A criptoanálise é um campo tão dinâmico que qualquer livro de técnicas estaria obsoleto antes mesmo de ser impresso. E mesmo que de alguma forma o livro continuasse atual, teria pouco para ensinar sobre criptoanálise.

A única maneira de aprender criptoanálise é através da prática. Um estudante precisa simplesmente quebrar algoritmo por algoritmo inventando novas técnicas e modificando as existentes. Ler os resultados criptoanalíticos de outros ajuda, mas isto não substitui a experiência própria.

Esta resposta leva a uma outra pergunta: onde adquirir a prática? A Internet é uma fonte inesgotável de algoritmos medíocres - alguns até mesmo entram rastejando na literatura acadêmica - mas o estudante que começa com a criptoanálise não tem como saber quais algoritmos compensam ser estudados e quais estão além do seu alcance. Tentar quebrar os algoritmos que já foram quebrados (sem antes olhar o que outros já fizeram) é a única resposta.

Agora a pergunta é: quais são as cifras que devemos tentar quebrar e em qual sequência? Este paper é minha tentativa para dar uma resposta, na esperança de que esta resposta facilite o estudo da criptoanálise.

Este é um curso de criptoanálise de cifras de bloco para autodidatas. Neste curso, um estudante pode seguir um caminho ordenado através da literatura acadêmica e chegar ao fim plenamente capaz de quebrar novos algoritmos e publicar seus resultados criptoanlíticos.

O que fiz foi listar algoritmos publicados e criptoanálises publicadas numa ordem coerente: por tipo de criptoanálise e dificuldade. Uma das tarefas do estudante é ler os textos que descrevem os algoritmos e depois tentar reproduzir os resultados criptoanalíticos publicados (definitivamente é mais difícil aprender criptoanálise através de papers acadêmicos do que através de livros de texto, mas, quanto mais cedo um estudante se acostumar a ler textos acadêmicos, mais depressa conseguirá progredir). Os resultados em outros papers publicados servem como um "chave para a resposta".

A chave para a resposta nunca é definitiva; muito provavelmente existem outros ataques, até melhores dos que foram publicados. Alguns textos sobre criptoanálise possuem erros. Estudantes que seguirem este curso podem acabar conseguindo resultados publicáveis.

Até mesmo o melhor estudante não será capaz de encontrar todas as quebras publicadas sem olhar o texto de criptoanálise associado. Muitos destes resultados foram descobertos pelos melhores cérebros criptoanalíticos na academia. Penso que um estudante deveria dedicar pelo menos uma semana tentando quebrar um algoritmo sem olhar no paper da criptoanálise e depois disto dar uma olhada rápida no resultado - ou apenas ler o resumo, introdução e conclusão - para depois tentar quebrar o algoritmo por pelo menos mais três dias.

Se um estudante ainda não conseguir quebrar a cifra, neste ponto faz sentido ler e estudar a criptoanálise publicada. Se um estudante não conseguir quebrar nenhuma das cifras - especialmente as mais fáceis - isto é um bom indicativo de que deveria encontrar outra linha de trabalho.

As lições estão em ordem, mas a ordenação está meio solta nos tópicos. As primeiras lições são mais fáceis, mas depois tento misturar um pouco as coisas. Os estudantes podem pular lições que são mais difíceis e depois voltar para elas, ou até mesmo simplesmente pular algumas (existem muitas delas). Também não é minha intenção que o estudante complete uma lição antes de ir para a próxima. Um estudante esperto, provavelmente, irá trabalhar com mais de uma lição por vez.

Boa sorte.

2. O que significa "quebrar" uma cifra?

Quebrar uma cifra não necessariamente significa encontrar uma forma prática para que um interceptador possa recuperar o texto claro a partir do texto cifrado. Na criptografia acadêmica as regras são consideravelmente menos rígidas. Quebrar uma cifra simplesmente significa encontrar uma fraqueza na cifra que possa ser explorada com uma complexidade menor do que a força bruta. Não interessa se a força bruta requerer 2¹²⁸ encriptações; um ataque que precisar de 2¹¹⁰ encriptações já será considerado uma quebra. As quebras também podem necessitar quantidades irreais de texto claro conhecido ou escolhido - 2⁵⁶ blocos - ou quantidades irreais de armazenamento: 2⁸⁰. Colocando de forma simples, uma quebra pode ser apenas uma "fraqueza certificacional": evidência de que a cifra não atua como declarado.

Uma criptoanálise de sucesso pode significar a demonstração de uma quebra contra uma variedade de uma cifra com rodadas reduzidas - DES com 8 rodadas versus DES completo de 16 rodadas, por exemplo - ou uma variedade simplificada da cifra. A maioria das quebras começa como criptoanálise de variedades com rodadas reduzidas e, eventualmente (talvez alguns anos mais tarde), são estendidas para a cifra completa.

3. Porque cifras de bloco?

Pesquisas acadêmicas com cifras de bloco progrediram num rumo diferente do das pesquisas com cifras de fluxo. Papers sobre cifras de bloco tradicionalmente possuem esquemas concretos (com parâmetros e nomes específicos) ou quebras destes esquemas. Papers sobre cifras de fluxo com frequência são esquemas gerais ou técnicas de análise com aplicações gerais e exemplos. Apesar da criptoanálise de cifras de fluxo ser pelo menos tão importante quanto a criptoanálise de cifras de bloco, e mais importante no meio militar, é muito mais difícil alinhavar um curso usando textos acadêmicos. Uma boa fonte de cifras de fluxo está disponível online em http://www.rsa.com/rsalabs/node.asp?id=2002.

4. Pré-requisitos

É praticamente impossível entender alguns resultados criptoanalíticos sem um bom conhecimento de conceitos simples sobre probabilidade e estatística. O The Handbook of Applied Cryptography tem uma introdução rápida e muito útil sobre a teoria da probabilidade, entretanto, estudantes que estiverem vendo isto pela primeira vez, talvez encontrem uma introdução mais apropriada num livro de texto dedicado à probabilidade e à estatística.

Outros tópicos sobre matemática discreta e ciência da computação também são úteis, apesar de não serem de conhecimento obrigatório. Um estudante deveria saber ou estar preparado para aprender álgebra linear, teoria dos grupos, teoria da complexidade, análise combinatória e teoria de gráficos. Isto deveria ser estudado com afinco juntamente com a criptoanálise.

É impossível entender realmente um ataque criptoanalítico sem implementá-lo. Realizando um ataque descrito num paper pode ser muito instrutivo; implementando um novo ataque inventado por você, com frequência expõe sutilezas que não aparecem numa análise teórica. Por este motivo, a programação matemática numa linguagem como a C também é uma habilidade requerida.

4.1 Fundo histórico

A criptoanálise de algoritmos de encriptação pré-computador não é realmente aplicável à criptoanálise de algoritmos modernos, mas é uma leitura interessante e um bom exemplo do estado mental requerido para praticar criptoanálise. Não considero isto um pré-requisito requerido, mas o estudante interessado deveria considerar ler Helen Fourche Gaines, Cryptanalysis: A Study of Ciphers and their Solution (Dover Publications, 1939). Também são interessantes os volumes escritos por William F. Friedman e re-impressos pela Agean Park Press: Elements of Cryptanalysis; Military Cryptanalysis, Partes I, II, III e IV; The Riverbank Publications, Partes I, II e III; e Military Cryptanalytics, Parte I, Vol. 1 e 2, e Parte II, Vol. 1 e 2. A Agean Park Press está em http://www.ageanpress.com/books/.

Uma leitura cuidadosa de David Kahn, The Codebreakers (The Macmillan Company, 1967), é indispensável para um entendimento da história da criptografia. Eu a recomendo com veemência.

5. Obtendo material para o curso

Os papers usados no curso são de procedimentos de várias conferências diferentes. Tentei evitar publicações obscuras, mas, invariavelmente, algumas se infiltraram. Isto significa que muitas cifras de bloco boas não estão listadas abaixo: CAST é um exemplo típico. Por favor, não considere a exclusão de uma cifra como alguma evidência de força ou fraqueza, é simplesmente uma questão de disponibilidade.

A maioria dos papers são de procedimentos de conferências da Springer-Verlag, todos publicados na série Lecture Notes in Computer Science (LNCS). A maioria das bibliotecas de universidades assinam a série LNCS. No mínimo, um estudante deveria ter um CD-ROM com todos os procedimentos da Crypto e Eurocrypt (disponível no Springer-Verlag) e os procedimentos da série Fast Software Encryption (FSE). Existem muitos outros papers nestas séries, cuja leitura vale a pena, do que os citados aqui.

Mantenho uma página na web em http://www.counterpane.com com indicações para os papers na WWW. Com o CD-ROM, os procedimentos da FSE e meus recursos na Web é possível fazer praticamente tudo neste curso.