Detalhes

Categoria: Curso de Criptologia

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

Autor: vovó Vicki

Acessos: 22640

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.

6. O curso

6.1 Background

Leia pelo menos dois dos seguintes livros: B. Schneier, Applied Cryptography, Second Edition (John Wiley & Sons, 1996), D.R. Stinson, Cryptography: Theory and Practice (CRC Press, 1995) e A. J. Menezes, P.C. van Oorschot e S.A. Vanstone, Handbook of Applied Cryptography (CRC Press, 1997). Concentre-se nos capítulos sobre cifras de bloco, mas recomendo fortemente que você leia tudo.

6.2 Criptoanálise básica

Tente fazer a criptoanálise dos seguintes algoritmos simplificados:

• RC5 de 8 rodadas sem qualquer rotação.
• RC5 de 8 rodadas com a quantidade de rotação igual ao número de rodadas.
• DES de 12 rodadas sem qualquer caixa S (S-boxes).
• Regra B do Skipjack de 8 rodadas (Uma descrição do Skipjack pode ser encontrada na web).
• DES de 4 rodadas.
• Uma cifra genérica "fechada" (isto é, cifrando com a chave A e depois a chave B é o mesmo que cifrar com a chave C, para todas as chaves).
• DES de 6 rodadas.
• Regra A do Skipjack de 4 rodadas seguida por quatro rodadas com a regra B do Skipjack.

Todos estes algoritmos são descritos em B. Schneier, Applied Cryptography, Second Edition (John Wiley & Sons, 1996) e em A. J. Menezes, P.C. van Oorschot e S.A. Vanstone, Handbook of Applied Cryptography (CRC Press, 1997).

6.3 Criptoanálise da FEAL

Parece que praticamente qualquer ataque criptoanalítico moderno funciona contra a FEAL. Primeiro leia o algoritmo: A. Shimizu e S. Miyaguchi, "Fast Data Encipherment Algorithm FEAL" (Advances in Cryptology - EUROCRYPT '87 Proceedings, Springer-Verlag, 1988, pp. 267-278). Agora, tente quebrá-lo. Alguns ataques podem ser encontrados em: B. Den Boer, "Cryptanalysis of F.E.A.L." (Advances in Cryptology - EUROCRYPT '88 Proceedings, Springer-Verlag, 1988, pp. 275-280), H. Gilbert e P. Chasse, "A Statistical Attack on the FEAL-8 Cryptosystem" (Advances in Cryptology - CRYPTO '90 Proceedings, Springer-Verlag, 1991, pp. 22-33) e A. Tardy-Corfdir e H. Gilbert, "A Known Plaintext Attack of FEAL-4 and FEAL-6" (Advances in Cryptology - CRYPTO '91 Proceedings, Springer-Verlag, 1992, pp. 172-182). Você também pode reinventar tanto a criptoanálise diferencial quanto a criptoanálise linear se se esforçar bastante.

6.4 Criptoanálise diferencial

Leia os capítulos 1 até 5 de E. Biham e A. Shamir, Differential Cryptanalysis of the Data Encryption Standard (Springer-Verlag, 1993). Se você não conseguir encontrar o livro, leia E. Biham e A. Shamir, "Differential Cryptanalysis of the Full 16-Round DES" (Advances in Cryptology - CRYPTO '91 Proceedings, Springer-Verlag, 1992, pp. 487-496).

6.5 Criptoanálise diferencial da FEAL

Ataque a FEAL usando a criptoanálise diferencial. Uma solução, que é o primeiro paper que fala sobre ataques diferenciais, é S. Murphy, "The Cryptanalysis of FEAL-4 with 20 Chosen Plaintexts" (Journal of Cryptology, v. 2, n. 3, 1990, pp. 145-154). Veja também o capítulo 6 de E. Biham and A. Shamir, Differential Cryptanalysis of the Data Encryption Standard (Springer-Verlag, 1993).

6.6 Criptoanálise diferencial da LOKI-89

A primeira versão da LOKI agora é chamada de LOKI-89. Leia L. Brown, J. Pieprzyk e J. Seberry, "LOKI: A Cryptographic Primitive for Authentication and Secrecy Applications" (Advances in Cryptology - AUSCRYPT '90 Proceedings, Springer-Verlag, 1990, pp. 229-236). Encontre um ataque diferencial; uma solução está em L.R. Knudsen, "Cryptanalysis of LOKI" (Advances in Cryptology - ASIACRYPT '91, Springer-Verlag, 1993, pp. 22-35). O livro de Biham e Shamir também discute esta criptoanálise.

6.7 Criptoanálise diferencial da MacGuffin

Leia M. Blaze e B. Schneier, "The MacGuffin Block Cipher Algorithm" (Fast Software Encryption, Second International Workshop Proceedings, Springer-Verlag, 1995, pp. 97-110). Tente quebrar a cifra. Um ataque diferencial está em V. Rijmen e B. Preneel, "Cryptanalysis of MacGuffin" (Fast Software Encryption, Second International Workshop Proceedings, Springer-Verlag, 1995, pp. 353-358). Existem muito mais ataques, nenhum dos quais publicado. Vale a pena dedicar um tempo para este algoritmo e até mesmo voltar para ele mais tarde neste curso. Na medida em que você aprender mais técnicas, descobrirá mais ataques.

6.8 Criptoanálise diferencial do Khafre

Leia a descrição do Khafre em R. C. Merkle, "Fast Software Encryption Functions" (Advances in Cryptology - CRYPTO '90 Proceedings, Springer-Verlag, 1991, pp. 476-501). Tente quebrá-lo. Um ataque diferencial está em E. Biham e A. Shamir, "Differential Cryptanalysis of Snefru, Khafre, REDOC II, LOKI, and Lucifer" (Advances in Cryptology - CRYPTO '91 Proceedings, Springer-Verlag, 1992, pp. 156-171). Veja também o livro de Biham e Shamir.

6.9 Criptoanálise diferencial do PES

O precursor do IDEA foi o PES; veja X. Lai e J. Massey, "A Proposal for a New Block Encryption Standard" (Advances in Cryptology - EUROCRYPT '90 Proceedings, Springer-Verlag, 1991, pp. 389-404). Tente quebrá-lo usando a criptoanálise diferencial. Resultados (e um redesenho) estão em X. Lai, J. Massey e S. Murphy, "Markov Ciphers and Differential Cryptanalysis" (Advances in Cryptology - CRYPTO '91 Proceedings, Springer-Verlag, 1991, pp. 17-38).

6.10 Criptoanálise linear

Leia M. Matsui, "Linear Cryptanalysis Method for DES Cipher" (Advances in Cryptology - EUROCRYPT '93 Proceedings, Springer-Verlag, 1994, pp. 386-397). Tente melhorar os resultados. Uma solução está em M. Matsui, "The First Experimental Cryptanalysis of the Data Encryption Standard" (Advances in Cryptology - CRYPTO '94 Proceedings, Springer-Verlag, 1994, pp. 1-11).

6.11 Criptoanálise linear da FEAL

Tente quebrar a FEAL usando técnicas da criptoanálise linear. Soluções estão em M. Matsui e A. Yamagishi, "A NewMethod for Known Plaintext Attack of FEAL Cipher" (Advances in Cryptology - EUROCRYPT '92 Proceedings, Springer-Verlag, 1993, pp. 81-91) e K. Ohta e K. Aoki, "Linear Cryptanalysis of the Fast Data Encipherment Algorithm" (Advances in Cryptology - CRYPTO '94 Proceedings, Springer-Verlag, 1994, pp. 12-16). Veja também S. Moriai, K. Aoki e K. Ohta, "Improving the Search Algorithm for the Best Linear Expression" (Advances in Cryptology - EUROCRYPT '95 Proceedings, Springer-Verlag, 1995, pp. 157-170).

6.12 Características Condicionais Diferenciais

Características condicionais foram introduzidas por I. Ben-Aroya e E. Biham, "Differential Cryptanalysis of Lucifer" (Advances in Cryptology - CRYPTO '93 Proceedings, Springer-Verlag, 1994, pp. 187-199). Leia as seções 1-3 sobre o Lucifer e características condicionais. Depois tente encontrar o ataque antes de ler a seção 4. Leia o início da seção 5, sobre o RDES. Tente encontrar o ataque antes de ler o resto do paper.

6.13 Criptoanálise rotacional de chaves relacionadas

Leia os resultados obtidos com a LOKI-89 e a LOKI-91 em E. Biham, "New Types of Cryptanalytic Attacks Using Related Keys" (Journal of Cryptology, v. 7, n. 4, 1994, pp. 229-246). Se não conseguir o jornal, leia a cópia preliminar (Advances in Cryptology - EUROCRYPT '93, Springer-Verlag, 1994, pp. 398-409). Ataque a variante do DES descrita na seção 5 (seção 6 na versão Eurocrypt).

6.14 Criptoanálise Diferencial-Linear

Leia S. Langford e M. Hellman, "Differential-Linear Cryptanalysis" (Advances in Cryptology - CRYPTO '94 Proceedings, Springer-Verlag, 1994, pp. 17-26). Tente aplicar estas técnicas à FEAL. A resposta está em K. Aoki e K. Ohta, "Differential-Linear Cryptanalysis of FEAL-8" (IEICE Transactions: Fundamentals of Electronics, Communications, and Computer Sciences (Japan), v. E79-A, n. 1, 1996, pp. 20-27). Boa sorte para encontrar este jornal - é japonês.

6.15 Relações entre a criptoanálise diferencial e a linear

Leia E. Biham, "On Matsui's Linear Cryptanalysis" (, Springer-Verlag, 1995, pp. 398-412) e F. Chabaud e S. Vaudenay, "Links Between Dierential and Linear Cryptanalysis" (Advances in Cryptology - EUROCRYPT '94 Proceedings, Springer-Verlag, 1995, pp. 356-365).

6.16 Criptoanálise diferencial de ordem mais alta

Se conseguir achar, leia X. Lai, "Higher Order Derivatives and Differential Cryptanalysis" (Communications and Cryptograpy, Kluwer Academic Publishers, 1994, pp. 227-233). Leia a seção 4 de L.R. Knudsen, "Truncated and Higher Order Dierentials" (Fast Software Encryption, 2nd International Workshop Proceedings, Springer-Verlag, 1995, pp. 196-211).

6.17 Criptoanálise diferencial de ordem mais alta da KN-Cipher

Leia K. Nyberg e L.R. Knudsen, "Provable Security Against Differential Cryptanalysis" (Journal of Cryptology, v. 8, n. 1, 1995, pp. 27-37). A cifra na seção 5 é chamada de KN-Cipher; tente quebrá-la usando diferenciais de ordem mais alta. A Kiefer também é descrita em K. Kiefer, "A New Design Concept for Building Secure Block Ciphers" (Proceedings of Pragocrypt '96, CTU Publishing House, 1996, pp. 30-41). Uma boa solução se encontra em T. Shimoyama, S. Moriai e T. Kaneko, "Improving the Higher Order Differential Attack and Cryptanalysis of the KN Cipher" (Information Security. First International Workshop ISW '97 Proceedings, Springer-Verlag, 1998, pp. 32-42).

6.18 Aproximações lineares múltiplas

Leia B. Kaliski Jr. e M. Robshaw, "Linear Cryptanalysis Using Multiple Approximations" (Advances in Cryptology | CRYPTO '94 Proceedings, Springer-Verlag, 1994, pp. 26-39). Tente quebrar a FEAL usando estas técnicas. Uma solução está em B. Kaliski Jr. e M. Robshaw, "Linear Cryptanalysis Using Multiple Approximations and FEAL" (Fast Software Encryption, Second International Workshop Proceedings, Springer-Verlag, 1995, pp. 249-264).

6.19 Criptoanálise do TWOPRIME

Leia C. Ding, V. Niemi, A. Renvall e A. Salomaa, "TWOPRIME: A Fast Stream Ciphering Algorithm" (Fast Software Encryption, 4th International Workshop Proceedings, Springer-Verlag, 1997, pp. 88-102). TWOPRIME, na realidade, é uma cifra de bloco. Tente quebrá-la; existe todo tipo de ataque. Resultados estão em D. Coppersmith, D. Wagner, B. Schneier e J. Kelseym, "Cryptanalysis of TWOPRIME" (Fast Software Encryption, 5th International Workshop Proceedings, Springer-Verlag, 1998, pp. 32-48).

6.20 Criptoanálise do Blowfish

Leia B. Schneier, "Description of a New Variable-Length Key, 64-Bit BlockCipher (Blowfish)" (Fast Software Encryption, Cambridge Security Workshop Proceedings, Springer-Verlag, 1994, pp. 191-204) e tente quebrar o Blowfish. Alguns resultados foram publicados em S. Vaudenay, "On the Weak Keys in Blowfish" (Fast Software Encryption, 3rd International Workshop Proceedings, Springer-Verlag, 1996, pp. 27-32). Também existe um ataque diferencial contra o Blowfish de cinco rodadas numa tese de V. Rijmen's Ph.D.

6.21 Criptoanálise do ICE

Leia M. Kwan, "The Design of ICE Encryption Algorithm" (Fast Software Encryption, 4th International Workshop Proceedings, Springer-Verlag, 1997, pp. 69-82). Um ataque diferencial está em B. Van Rompay, L.R. Knudsen e V. Rijmen, "Differential Cryptanalysis of ICE Encryption Algorithm" (Fast Software Encryption, 5th International Workshop Proceedings, Springer-Verlag, 1998, pp. 270-283).

6.22 Criptoanálise do LOKI-91

O LOKI foi redesenhado; a nova versão foi chamada de LOKI-91. Leia L. Brown, M. Kwan, J. Pieprzyk e J. Seberry, "Improving Resistance to Differential Cryptanalysis and the Redesign of LOKI" (Advances in Cryptology - ASIACRYPT '91 Proceedings, Springer-Verlag, 1993, pp. 36-50). Procure por qualquer tipo de criptoanálise; alguns resultados podem ser encontrados em L.R. Knudsen, "Cryptanalysis of LOKI91" (Advances in Cryptology - AUSCRYPT '92, Springer-Verlag, 1993, pp. 196-208). Um ataque linear (contra o LOKI-91 e o LOKI-89) pode ser encontrado em T. Tokita, T. Sorimachi e M. Matsui, "Linear Cryptanalysis of LOKI and s² DES" (Advances in Cryptology - ASIACRYPT '94, Springer-Verlag, 1995, pp. 293-303).

6.23 Criptoanálise do CMEA

Leia as seções 1 e 2 de D. Wagner, B. Schneier e J. Kelsey, "Cryptanalysis of the Cellular Message Encryption Algorithm" (Advances in Cryptology - CRYPTO '97 Proceedings, Springer-Verlag, 1997, pp. 526-537). Tente quebrar o algoritmo antes de ler o resto do paper.

6.24 Criptoanálise do IDEA

O IDEA é descrito (sendo chamado de IPES) em X. Lai, J. Massey e S. Murphy, "Markov Ciphers and Differential Cryptanalysis" (Advances in Cryptology - CRYPTO '91 Proceedings, Springer-Verlag, 1991, pp. 17-38). A análise mais fácil é tentar achar chaves fracas; uma resposta está em J. Daemen, R. Govaerts e J. Vandewalle, "Weak Keys for IDEA" (Advances in Cryptology - CRYPTO '93 Proceedings, Springer-Verlag, 1994, pp. 224-231). Procure por outros ataques; algumas soluções estão em W. Meier, "On the Security of the IDEA Block Cipher" (Advances in Cryptology - EUROCRYPT '93 Proceedings, Springer- Verlag, 1994, pp. 371-385) e em P. Haawkes e L. O'Connor, "On Applying Linear Cryptanalysis to IDEA" (Advances in Cryptology - ASIACRYPT '96, Springer-Verlag, 1996, pp. 105-115).

6.25 Diferenciais truncados

Leia L.R. Knudsen, "Truncated and Higher Order Differentials" (Fast Software Encryption, 2nd International Workshop Proceedings, Springer-Verlag, 1995, pp. 196-211), seções de 1 a 4. Tente aplicar as técnicas de diferenciais truncados antes de ler os resultados na seção 5. Tente quebrar o SAFER usando diferenciais truncados. Resultados estão em L.R. Knudsen e T.A Berson, "Truncated Differentials of SAFER" (Fast Software Encryption, 3rd International Workshop Proceedings, Springer-Verlag, 1996, pp. 15-26).

6.26 Criptoanálise diferencial de chaves relacionadas

Leia J. Kelsey, B. Schneier e D. Wagner, "Key-Schedule Cryptanalysis of IDEA, G-DES, GOST, SAFER, and Triple-DES" (Advances in Cryptology - CRYPTO '96 Proceedings, Springer-Verlag, 1996, pp. 237-251). Tente aplicar as técnicas em 3-Way, DES-X e TEA antes de ler J. Kelsey, B. Schneier e D. Wagner, "Related-Key Cryptanalysis of 3-WAY, Biham-DES, CAST, DES-X, NewDES, RC2, and TEA" (Information and Communications Security, First International Conference Proceedings, Springer-Verlag, 1997, pp. 203-207).

6.27 Generalizações da criptoanálise linear

Leia C. Harpes, G. Kramer e J. Massey, "A Generalization of Linear Cryptanalysis and the Applicability of Matsui's Piling-up Lemma" (Advances in Cryptology - EUROCRYPT '95 Proceedings, Springer-Verlag, 1995, pp. 24-38), C. Harpes e J. Massey, "Partitioning Cryptanalysis" (Fast Software Encryption, 4th International Workshop Proceedings, Springer-Verlag, 1997, pp. 13-27). Tente aplicar estas técnicas ao DES antes de ler o Apêndice C do segundo paper. Leia as seções de 1 a 4 de B. Kaliski Jr. e M. Robshaw, "Linear Cryptanalysis Using Multiple Approximations" (Advances in Cryptology - CRYPTO '94 Proceedings, Springer-Verlag, 1994, pp. 26-39). Tente aplicar as técnicas ao LOKI91 antes de ler a seção 5.

6.28 Criptoanálise do Akelarre

Leia G. Alvarez, D. De la Guia, F. Montoya e A. Peinado, "Akelarre: A New Block Cipher Algorithm" (Workshop on Selected Areas in Cryptography (SAC '96) Workshop Record, Queens University, 1996, pp. 1-14). Tente quebrar o algoritmo. Resultados estão em L.R. Knudsen e V. Rijmen, "Two Rights Sometimes Make a Wrong" (Workshop on Selected Areas in Cryptography (SAC '97) Workshop Record, School of Computer Science, Carleton University, 1997, pp. 213-223) e N. Ferguson e B. Schneier, "Cryptanalysis of Akelarre" (Workshop on Selected Areas in Cryptography (SAC '97) Workshop Record, School of Computer Science, Carleton University, 1997, pp. 201-212). Se você não conseguir achar outras, uma descrição do Akelarre está no último paper.

6.29 Whitening

Leia J. Kilian e P. Rogaway, "How to Protect DES Against Exhaustive Key Search" (Advances in Cryptology - CRYPTO '96 Proceedings, Springer-Verlag, 1996, pp. 252-267).

6.30 Teoria da criptoanálise diferencial e linear

Leia os seguintes papers: K. Nyberg, "Linear Approximation of Block Ci- phers" (Advances in Cryptology - EUROCRYPT '94 Proceedings, Springer-Verlag, 1995, pp. 439-444), K. Nyberg e L. Knudsen, "Provable Security Against a Differential Attack," (Journal of Cryptology, v. 8, n. 1, 1995, pp. 27-37) e K. Nyberg e L. Knudsen, "Provable Security Against a Differential Cryptanalysis" (Advances in Cryptology - CRYPTO '92 Proceedings, Springer-Verlag, 1993, pp. 566-574).

6.31 Criptoanálise da VINO

Leia A. Di Porto e W. Wolfowicz, "VINO: A Block Cipher Including Variable Permutations" (Fast Software Encryption, Cambridge Security Workshop Proceedings, Springer-Verlag, 1994, pp. 205-210). Nenhuma criptoanálise foi publicada até agora; tente ser o primeiro.

6.32 Ataque de interpolação

Leia as seções de 1 a 3.3 de T. Jakobsen e L. Knudsen, "The Interpolation Attack on Block Ciphers" (Fast Software Encryption, 4th International Workshop Proceedings, Springer-Verlag, 1997, pp. 28-40). Leia as modificações no SHARK na seção 3.4 e tente quebrá-lo antes de ler o restante do paper.

6.33 Ataques a funções de rodadas não-surjetivas

Leia E. Biham e A. Biryukov, "An Improvement of Davies' Attack on DES" (Advances in Cryptology - EUROCRYPT '94 Proceedings, Springer-Verlag, 1995, pp. 461-467). Também vale a pena ler B. Rijmen, B. Preneel e E. De Win, "On Weaknesses of Non-surjective Round Functions" (Designs, Codes, and Cryptography, v. 12, n. 3, 1997, pp. 253-266).

6.34 Criptoanálise do KHUFU

Leia a descrição do KHUFU em R.C. Merkle, "Fast Software Encryption Functions" (Advances in Cryptology - CRYPTO '90 Proceedings, Springer-Verlag, 1991, pp. 476-501). Tente quebrá-lo. Uma análise está em H. Gilbert and P. Chauvaud, "A Chosen-Plaintext Attack on the 16-Round Khufu Cryptosystem" (Advances in Cryptology - CRYPTO '94 Proceedings, Springer-Verlag, 1994, pp. 359-368).

6.35 Criptoanálise do SAFER

Leia J.L. Massey, "SAFER K-64: A Byte-Oriented Block-Ciphering Algorithm" (Fast Software Encryption, Cambridge Security Workshop Proceedings, Springer-Verlag, 1994, pp. 1-17). Tente atacar esta cifra. Resultados podem ser encontrados em J.L. Massey, "SAFER K-64: One Year Later" (Fast Software Encryption, 2nd International Workshop Proceedings, Springer-Verlag, 1995, pp. 212-241), S. Vaudenay, "On the Need for Multipermutations: Cryptanalysis of MD4 and SAFER" (Fast Software Encryption, Second International Workshop Proceedings, Springer-Verlag, 1995, pp. 286-297) e L.R. Knudsen, "A Key-Schedule Weakness in SAFER K-64" (Advances in Cryptology - CRYPTO '95 Proceedings, Springer-Verlag, 1995, pp. 274-286).

6.36 Modos de operação

Leia E. Biham, "On Modes of Operation" (Fast Software Encryption, Cambridge Security Workshop Proceedings, Springer-Verlag, 1994, pp. 116-120) e E. Biham, "Cryptanalysis of Multiple Modes of Operation" (Advances in Cryptology - ASIACRYPT '94 Proceedings, Springer-Verlag, 1995, pp. 278-292). Leia as seções 1 e 2 de E. Biham, "Cryptanalysis of Ladder-DES" (Fast Software Encryption, 4th International Workshop Proceedings, Springer-Verlag, 1997, pp. 134-138). Tente quebrar a construção antes de ler o restante do paper. Leia também D. Wagner, "Analysis of Some Recently Proposed Modes of Operation" (Fast Software Encryption, 5th International Workshop Proceedings, Springer-Verlag, 1998, pp. 254-269) e tente quebrar as construções antes de ler a análise.

6.37 Criptoanálise avançada do IDEA

Tente quebrar o IDEA usando diferenciais truncados e características diferenciais-lineares. Resultados estão em J. Borst, L.R. Knudsen e V. Rijmen, "Two Attacks on Reduced IDEA" (Advances in Cryptology - EUROCRYPT '97, Springer-Verlag, 1997, pp. 1-13) e P. Hawkes, "Differential-Linear Weak Key Classes of IDEA" (Advances in Cryptology - EUROCRYPT '98 Proceedings, Springer-Verlag, 1998, pp. 112-126).

6.38 Criptoanálise do TEA

Leia D. Wheeler e R. Needham, "TEA, a Tiny Encryption Algorithm" (Fast Software Encryption, 2nd International Workshop Proceedings, Springer-Verlag, 1995, pp. 97-110). Nenhuma criptoanálise, exceto a do esquema de chaves, foi publicada; tente ser o primeiro.

6.39 Criptoanálise do RC5

Leia R.L. Rivest, "The RC5 Encryption Algorithm" (Fast Software Encryption, 2nd International Workshop Proceedings, Springer-Verlag, 1995, pp. 86-96). Tente quebrar o RC5. Você pode achar alguns resultados em B.S. Kaliski e Y.L. Yin, "On Differential and Linear Cryptanalysis of the RC5 Encryption Algorithm" (Advances in Cryptology - CRYPTO '95 Proceedings, Springer-Verlag, 1995, pp. 445-454), L.R. Knudsen e W. Meier, "Improved Dierential Attacks on RC5" (Advances in Cryptology - CRYPTO '96 Proceedings, Springer-Verlag, 1996, pp. 216-228) e A.A. Selcuk, "New Results in Linear Cryptanalysis of RC5" (Fast Software Encryption, 5th International Workshop Proceedings, Springer- Verlag, 1998, pp. 1-16).

6.40 Criptoanálise do MISTY

Leia M. Matsui, "New Structure of Block Ciphers with Provable Security Against Differential and Linear Cryptanalysis" (Fast Software Encryption, 3rd International Workshop Proceedings, Springer-Verlag, 1996, pp. 205-218) e M. Matsui, "New Block Encryption Algorithm MISTY" (Fast Software Encryption, 4th International Workshop Proceedings, Springer-Verlag, 1997, pp. 54-68). O único resultado criptoanalítico que conheço está em H. Tanaka, K. Hisamatsu e T. Kaneko, "Higher Order Differential Attack of MISTY without FL Functions" (The Institute of Electronics, Information, and Communication Engineers, ISEC98-5, 1998).

6.41 Criptoanálise do Square

Leia J. Daemen, L. Knudsen e V. Rijmen, "The Block Cipher Square" (Fast Software Encryption, 4th International Workshop Proceedings, Springer-Verlag, 1997, pp. 149-165), menos a seção 6. Tente atacar esta cifra antes de ler esta seção.

6.42 Submissões para o AES

Em 1998, o National Instutute of Standards and Technology solicitou candidatos de cifras de bloco para substituir o DES. Foram recebidas quinze submissões. Leia sobre o processo e as submissões no site do NIST, que inclui links para detalhes de várias submissões: http://www.nist.gov/aes/. Quebre tudo o que conseguir; envie os resultados para o NIST.

7. Conclusão

O único modo de se tornar um bom projetista de algoritmos é sendo um bom criptoanalista: quebrando algoritmos. Muitos deles. Sempre e sempre. Apenas depois que um estudante mostrou sua habilidade em criptoanalisar os algoritmos de outros é que seus próprios projetos serão levados a sério.

Já que uma grande quantidade de cifras é inventada todos os anos - algumas publicadas, algumas patenteadas, algumas proprietárias - como podem os criptoanalistas saber quais compensam ser estudadas? Eles olham para o pedigree do algoritmo. Um algoritmo que tenha sido inventado por alguém que mostrou ser capaz de quebrar algoritmos - estudou a literatura, talvez usando este curso, e publicou algumas quebras de sua autoria que não haviam sido descobertas antes - tem uma chance muito maior de inventar uma cifra segura do que alguém que deu uma lida rápida na literatura e depois inventou alguma coisa. Nos dois casos o inventor acredita que sua cifra é segura; no primeiro caso, a opinião do inventor tem valor.

Os criptoanalistas também procuram por documentações que dêem sustentação ao projeto. Novamente, projeto é fácil, a análise é que é difícil. Projetos que surgem com análises detalhadas - quebras de variantes simplificados, versões com rodadas reduzidas, implementações alternativas - mostram que o inventor sabia o que estava fazendo quando criou a cifra. Uma simples revisão das submissões para o AES mostra quais projetos são sérios e quais não; a maioria dos projetos sérios eram compostos principalmente de criptoanálise.

Qualquer um pode criar um algoritmo que ele mesmo não consegue quebrar. Não é nem ao menos difícil. O difícil é a criptoanálise e apenas um criptoanalista experiente pode projetar uma boa cifra.

Tradução vovó Vicki

Por favor, observe: o texto foi escrito por Bruce Schneier há quase 10 anos! Muita coisa mudou, mas os princípios continuam os mesmos e este roteiro não deixou de ser o caminho das pedras para quem quer começar e tem interesse em se tornar um especialista em criptologia no século XXI

O paper original, A Self-Study Course in Block-Cipher Cryptanalysis está disponível na seção de Downloads/Criptologia/Papers.