Criptoanálise

Criptoanálise (do grego kryptós, "oculto", e analýein, "analisar&# 34;) refere-se ao processo de análise de sistemas de informação para entender os aspectos ocultos dos sistemas. A criptoanálise é usada para violar sistemas de segurança criptográficos e obter acesso ao conteúdo de mensagens criptografadas, mesmo que a chave criptográfica seja desconhecida.

Além da análise matemática de algoritmos criptográficos, a criptoanálise inclui o estudo de ataques de canal lateral que não visam pontos fracos nos próprios algoritmos criptográficos, mas, em vez disso, exploram pontos fracos em sua implementação.

Embora o objetivo tenha sido o mesmo, os métodos e técnicas de criptoanálise mudaram drasticamente ao longo da história da criptografia, adaptando-se à crescente complexidade criptográfica, desde os métodos de papel e caneta do passado, até máquinas como o Computadores britânicos Bombes e Colossus em Bletchley Park na Segunda Guerra Mundial, aos esquemas computadorizados matematicamente avançados do presente. Métodos para quebrar sistemas criptográficos modernos geralmente envolvem a resolução de problemas cuidadosamente construídos em matemática pura, sendo o mais conhecido a fatoração de números inteiros.

Visão geral

Na criptografia, as informações confidenciais (chamadas de "texto simples") são enviadas com segurança a um destinatário pelo remetente, primeiro convertendo-as em um formato ilegível ("texto cifrado") usando um algoritmo de criptografia. O texto cifrado é enviado por meio de um canal inseguro para o destinatário. O destinatário descriptografa o texto cifrado aplicando um algoritmo de descriptografia inversa, recuperando o texto simples. Para descriptografar o texto cifrado, o destinatário requer um conhecimento secreto do remetente, geralmente uma sequência de letras, números ou bits, chamada de chave criptográfica. O conceito é que, mesmo que uma pessoa não autorizada obtenha acesso ao texto cifrado durante a transmissão, sem a chave secreta, ela não poderá convertê-lo de volta em texto simples.

A criptografia tem sido usada ao longo da história para enviar importantes mensagens militares, diplomáticas e comerciais, e hoje é amplamente utilizada em redes de computadores para proteger a comunicação por e-mail e pela Internet.

O objetivo da criptoanálise é que um terceiro, um criptoanalista, obtenha o máximo de informações possível sobre o original ("texto simples"), tentando “quebrar” o criptografia para ler o texto cifrado e aprender a chave secreta para que mensagens futuras possam ser descriptografadas e lidas. Uma técnica matemática para fazer isso é chamada de "''ataque criptográfico''"Os ataques criptográficos podem ser caracterizados de várias maneiras:

Quantidade de informação disponível para o invasor

Os ataques podem ser classificados com base no tipo de informação que o invasor tem disponível. Como ponto de partida básico, normalmente assume-se que, para fins de análise, o algoritmo geral é conhecido; esta é a máxima de Shannon "o inimigo conhece o sistema" – por sua vez, equivalente a Kerckhoffs' princípio. Esta é uma suposição razoável na prática – ao longo da história, existem inúmeros exemplos de algoritmos secretos caindo no conhecimento mais amplo, por meio de espionagem, traição e engenharia reversa. (E ocasionalmente cifras foram quebradas por pura dedução; por exemplo, a cifra de Lorenz alemã e o código roxo japonês, e uma variedade de esquemas clássicos):

• Só o Ciphertext: o cryptanalyst tem acesso apenas a uma coleção de cifratextos ou codetexts.
• Reclamação conhecida: o atacante tem um conjunto de cifratextos a que eles conhecem o texto liso correspondente.
• Reclamação de sentimentos (texto escolhido): o atacante pode obter os cifratextos (plaintextos) correspondentes a um conjunto arbitrário de texto liso (ciphertexts) de sua própria escolha.
• Adaptação do texto escolhido: como um ataque de texto escolhido, exceto o atacante pode escolher textos lisos subseqüentes com base em informações aprendidas com encriptações anteriores, da mesma forma que as Ataque de cifrado escolhido adaptativo.
• Ataque de teclas relacionadas: Como um ataque de texto escolhido, exceto o atacante pode obter cifratextos criptografados sob duas chaves diferentes. As chaves são desconhecidas, mas a relação entre elas é conhecida; por exemplo, duas chaves que diferem em um pouco.

Recursos computacionais necessários

Os ataques também podem ser caracterizados pelos recursos que requerem. Esses recursos incluem:

• Tempo – o número de etapas de computação (por exemplo, encriptações de teste) que devem ser executadas.
• Memória – a quantidade de armazenamento necessário para executar o ataque.
• Dados – a quantidade e tipo de texto simples e cifratextos necessário para uma abordagem específica.

Às vezes é difícil prever essas quantidades com precisão, especialmente quando o ataque não é prático de implementar para teste. Mas os criptoanalistas acadêmicos tendem a fornecer pelo menos a ordem de magnitude estimada de seus ataques' dificuldade, dizendo, por exemplo, "SHA-1 colisões agora 2⁵²."

Bruce Schneier observa que mesmo ataques computacionalmente impraticáveis podem ser considerados quebras: "Quebrar uma cifra significa simplesmente encontrar uma fraqueza na cifra que pode ser explorada com uma complexidade menor que a força bruta. Não importa que a força bruta possa exigir 2¹²⁸ criptografias; um ataque que exija 2¹¹⁰ criptografias seria considerado uma quebra...simplesmente, uma quebra pode ser apenas uma falha de certificação: evidência de que a cifra não funciona como anunciado."

Pausas parciais

Os resultados da criptoanálise também podem variar em utilidade. O criptógrafo Lars Knudsen (1998) classificou vários tipos de ataque a cifras de bloco de acordo com a quantidade e a qualidade das informações secretas que foram descobertas:

• Interrupção total – o atacante deduz a chave secreta.
• Redução global – o atacante descobre um algoritmo funcionalmente equivalente para criptografia e descriptografia, mas sem aprender a chave.
• Dedução de instância (local) – o atacante descobre textos lisos adicionais (ou cifratextos) não conhecidos anteriormente.
• Dedução da informação – o atacante ganha algumas informações de Shannon sobre textos simples (ou cifratextos) não conhecidos anteriormente.
• Algoritmo de extinção – o atacante pode distinguir a cifra de uma permutação aleatória.

Ataques acadêmicos geralmente são contra versões enfraquecidas de um sistema criptográfico, como uma cifra de bloco ou função de hash com algumas rodadas removidas. Muitos ataques, mas não todos, tornam-se exponencialmente mais difíceis de executar à medida que as rodadas são adicionadas a um sistema criptográfico, portanto, é possível que o sistema criptográfico completo seja forte, mesmo que as variantes de rodadas reduzidas sejam fracas. No entanto, quebras parciais que chegam perto de quebrar o sistema criptográfico original podem significar que uma quebra completa ocorrerá; os ataques bem-sucedidos a DES, MD5 e SHA-1 foram todos precedidos por ataques a versões enfraquecidas.

Na criptografia acadêmica, uma fraqueza ou uma quebra em um esquema geralmente é definida de forma bastante conservadora: pode exigir quantidades impraticáveis de tempo, memória ou textos simples conhecidos. Também pode exigir que o invasor seja capaz de fazer coisas que muitos invasores do mundo real não podem: por exemplo, o invasor pode precisar escolher determinados textos sem formatação para serem criptografados ou até mesmo solicitar que os textos sem formatação sejam criptografados usando várias chaves relacionadas a a chave secreta. Além disso, pode revelar apenas uma pequena quantidade de informações, o suficiente para provar que o sistema criptográfico é imperfeito, mas muito pouco para ser útil para invasores do mundo real. Por fim, um ataque pode se aplicar apenas a uma versão enfraquecida de ferramentas criptográficas, como uma cifra de bloco de rodada reduzida, como um passo para quebrar o sistema completo.

História

A criptoanálise coevoluiu junto com a criptografia, e o concurso pode ser rastreado através da história da criptografia - novas cifras sendo projetadas para substituir antigos designs quebrados e novas técnicas criptanalíticas inventadas para decifrar os esquemas aprimorados. Na prática, eles são vistos como dois lados da mesma moeda: criptografia segura requer design contra possível criptoanálise.

Cifras clássicas

Embora a palavra real "criptanálise" é relativamente recente (foi cunhado por William Friedman em 1920), os métodos para quebrar códigos e cifras são muito mais antigos. David Kahn observa em The Codebreakers que os estudiosos árabes foram as primeiras pessoas a documentar sistematicamente os métodos criptanalíticos.

A primeira explicação registrada conhecida da criptoanálise foi dada por Al-Kindi (c. 801–873, também conhecido como "Alkindus" na Europa), um polímata árabe do século IX, em Risalah fi Istikhraj al-Mu'amma (Um manuscrito sobre a decifração de mensagens criptográficas). Este tratado contém a primeira descrição do método de análise de frequência. Al-Kindi é, portanto, considerado o primeiro decifrador da história. Seu trabalho inovador foi influenciado por Al-Khalil (717–786), que escreveu o Livro das Mensagens Criptográficas, que contém o primeiro uso de permutações e combinações para listar todas as palavras árabes possíveis com e sem vogais.

A análise de frequência é a ferramenta básica para quebrar a maioria das cifras clássicas. Nas línguas naturais, certas letras do alfabeto aparecem com mais frequência do que outras; em inglês, "E" é provável que seja a letra mais comum em qualquer amostra de texto simples. Da mesma forma, o dígrafo "TH" é o par de letras mais provável em inglês e assim por diante. A análise de frequência depende de uma falha de cifra para ocultar essas estatísticas. Por exemplo, em uma cifra de substituição simples (onde cada letra é simplesmente substituída por outra), a letra mais frequente no texto cifrado seria uma provável candidata a "E". A análise de frequência de tal cifra é, portanto, relativamente fácil, desde que o texto cifrado seja longo o suficiente para fornecer uma contagem razoavelmente representativa das letras do alfabeto que ele contém.

A invenção de Al-Kindi da técnica de análise de frequência para quebrar cifras de substituição monoalfabética foi o avanço criptanalítico mais significativo até a Segunda Guerra Mundial. Al-Kindi's Risalah fi Istikhraj al-Mu'amma descreveu as primeiras técnicas criptanalíticas, incluindo algumas para cifras polialfabéticas, classificação de cifras, fonética e sintaxe árabe e, mais importante, deu a primeiras descrições sobre análise de frequência. Ele também abordou métodos de cifras, criptoanálise de certas cifras e análise estatística de letras e combinações de letras em árabe. Uma contribuição importante de Ibn Adlan (1187–1268) foi sobre o tamanho da amostra para uso da análise de frequência.

Na Europa, o estudioso italiano Giambattista della Porta (1535–1615) foi o autor de um trabalho seminal sobre criptoanálise, De Furtivis Literarum Notis.

A criptoanálise bem-sucedida indubitavelmente influenciou a história; a capacidade de ler os pensamentos e planos supostamente secretos dos outros pode ser uma vantagem decisiva. Por exemplo, na Inglaterra, em 1587, Maria, Rainha dos Escoceses, foi julgada e executada por traição como resultado de seu envolvimento em três conspirações para assassinar Elizabeth I da Inglaterra. Os planos vieram à tona depois que sua correspondência codificada com outros conspiradores foi decifrada por Thomas Phelippes.

Na Europa, durante os séculos XV e XVI, a ideia de uma cifra de substituição polialfabética foi desenvolvida, entre outros, pelo diplomata francês Blaise de Vigenère (1523–96). Por cerca de três séculos, a cifra de Vigenère, que usa uma chave repetida para selecionar diferentes alfabetos de criptografia em rotação, foi considerada completamente segura (le chiffre indéchiffrable—"a cifra indecifrável"). No entanto, Charles Babbage (1791-1871) e mais tarde, de forma independente, Friedrich Kasiski (1805-1881) conseguiram quebrar essa cifra. Durante a Primeira Guerra Mundial, inventores em vários países desenvolveram máquinas de cifra de rotor, como Arthur Scherbius'; Enigma, na tentativa de minimizar a repetição que havia sido explorada para quebrar o sistema de Vigenère.

Cifras da Primeira Guerra Mundial e da Segunda Guerra Mundial

Na Primeira Guerra Mundial, a quebra do Telegrama Zimmermann foi fundamental para trazer os Estados Unidos para a guerra. Na Segunda Guerra Mundial, os Aliados se beneficiaram enormemente de seu sucesso conjunto na criptoanálise das cifras alemãs – incluindo a máquina Enigma e a cifra de Lorenz – e cifras japonesas, particularmente 'Purple' e JN-25. 'Ultra' a inteligência foi creditada com tudo, desde encurtar o fim da guerra européia em até dois anos, até determinar o resultado final. A guerra no Pacífico foi igualmente ajudada por 'Magic' inteligência.

A criptoanálise de mensagens inimigas desempenhou um papel significativo na vitória dos Aliados na Segunda Guerra Mundial. F. W. Winterbotham, citou o Comandante Supremo Aliado ocidental, Dwight D. Eisenhower, no final da guerra, descrevendo a inteligência Ultra como tendo sido "decisiva". à vitória aliada. Sir Harry Hinsley, historiador oficial da inteligência britânica na Segunda Guerra Mundial, fez uma avaliação semelhante sobre o Ultra, dizendo que encurtou a guerra "em não menos de dois anos e provavelmente em quatro anos"; além disso, ele disse que na ausência do Ultra, é incerto como a guerra teria terminado.

Na prática, a análise de frequência depende tanto do conhecimento linguístico quanto da estatística, mas à medida que as cifras se tornaram mais complexas, a matemática tornou-se mais importante na criptoanálise. Essa mudança foi particularmente evidente antes e durante a Segunda Guerra Mundial, onde os esforços para decifrar as cifras do Eixo exigiam novos níveis de sofisticação matemática. Além disso, a automação foi aplicada pela primeira vez à criptoanálise naquela época com o dispositivo polonês Bomba, o britânico Bombe, o uso de equipamentos de cartões perfurados e nos computadores Colossus – os primeiros computadores digitais eletrônicos a serem controlados por um programa.

Indicador

Com cifras de máquina recíprocas, como a cifra de Lorenz e a máquina Enigma usada pela Alemanha nazista durante a Segunda Guerra Mundial, cada mensagem tinha sua própria chave. Normalmente, o operador transmissor informa o operador receptor desta chave de mensagem, transmitindo algum texto simples e/ou texto cifrado antes da mensagem cifrada. Isso é chamado de indicador, pois indica ao operador receptor como configurar sua máquina para decifrar a mensagem.

Sistemas de indicadores mal projetados e implementados permitiram que primeiro os criptógrafos poloneses e depois os criptógrafos britânicos em Bletchley Park quebrassem o sistema de cifras Enigma. Sistemas de indicadores ruins semelhantes permitiram aos britânicos identificar profundezas que levaram ao diagnóstico do sistema de cifras Lorenz SZ40/42 e à quebra abrangente de suas mensagens sem que os criptoanalistas vissem a máquina de cifras.

Profundidade

Enviar duas ou mais mensagens com a mesma chave é um processo inseguro. Para um criptoanalista, as mensagens são consideradas "em profundidade." Isso pode ser detectado pelas mensagens que têm o mesmo indicador pelo qual o remetente operador informa o operador receptor sobre as configurações iniciais do gerador de chaves para a mensagem.

Geralmente, o criptoanalista pode se beneficiar ao alinhar operações de codificação idênticas entre um conjunto de mensagens. Por exemplo, a cifra de Vernam codifica bit a bit combinando texto simples com uma chave longa usando o "exclusivo ou" operador, que também é conhecido como "adição de módulo-2" (simbolizado por ⊕):

Chave de texto: Cifrotexto

A decifração combina os mesmos bits de chave com o texto cifrado para reconstruir o texto simples:

Ciphertext = Key = Contexto

(Na aritmética do módulo 2, a adição é o mesmo que a subtração.) Quando dois desses textos cifrados estão alinhados em profundidade, combiná-los elimina a chave comum, deixando apenas uma combinação dos dois textos simples:

Ciphertext1 ⊕ Ciphertext2 = Plaintext1 ⊕ Plaintext2

Os textos simples individuais podem então ser trabalhados linguisticamente tentando palavras prováveis (ou frases), também conhecidas como "cribs," em vários Localizações; um palpite correto, quando combinado com o fluxo de texto simples mesclado, produz um texto inteligível do outro componente de texto simples:

(Plaintext1 ⊕ Plaintext2) text Plaintext1 = Plaintext2

O fragmento recuperado do segundo texto simples geralmente pode ser estendido em uma ou ambas as direções, e os caracteres extras podem ser combinados com o fluxo de texto simples mesclado para estender o primeiro texto simples. Trabalhando para frente e para trás entre os dois textos claros, usando o critério de inteligibilidade para verificar suposições, o analista pode recuperar muito ou todos os textos originais originais. (Com apenas dois textos simples em profundidade, o analista pode não saber qual deles corresponde a qual texto cifrado, mas na prática isso não é um grande problema.) Quando um texto simples recuperado é então combinado com seu texto cifrado, a chave é revelada:

Simpletext1 ⊕ Ciphertext1 = Chave

O conhecimento de uma chave permite que o analista leia outras mensagens criptografadas com a mesma chave, e o conhecimento de um conjunto de chaves relacionadas pode permitir que os criptoanalistas diagnostiquem o sistema usado para construí-las.

Desenvolvimento da criptografia moderna

Os governos há muito reconhecem os benefícios potenciais da criptoanálise para inteligência, tanto militar quanto diplomática, e estabeleceram organizações dedicadas a quebrar os códigos e cifras de outras nações, por exemplo, GCHQ e NSA, organizações que ainda são muito ativas hoje.

Embora a computação tenha sido usada com grande efeito na criptoanálise da cifra de Lorenz e outros sistemas durante a Segunda Guerra Mundial, ela também possibilitou novos métodos de criptografia ordens de magnitude mais complexas do que nunca. Tomado como um todo, a criptografia moderna tornou-se muito mais impermeável à criptoanálise do que os sistemas de papel e caneta do passado, e agora parece ter vantagem contra a criptoanálise pura. O historiador David Kahn observa:

Muitos são os criptosistemas oferecidos pelas centenas de fornecedores comerciais hoje que não podem ser quebrados por quaisquer métodos conhecidos de criptoanálise. De fato, em tais sistemas até mesmo um ataque de texto simples escolhido, em que um texto simples selecionado é combinado contra seu cifratexto, não pode produzir a chave que desbloquear[s] outras mensagens. Em certo sentido, então, a criptoanálise está morta. Mas isso não é o fim da história. Cryptanalysis pode estar morto, mas há – misturar minhas metáforas – mais de uma maneira de esfolar um gato.

Kahn continua mencionando maiores oportunidades de interceptação, escutas, ataques de canal lateral e computadores quânticos como substitutos dos meios tradicionais de criptoanálise. Em 2010, o ex-diretor técnico da NSA, Brian Snow, disse que tanto os criptógrafos acadêmicos quanto os do governo estão "avançando muito lentamente em um campo maduro".

No entanto, qualquer autópsia para criptoanálise pode ser prematura. Embora a eficácia dos métodos criptanalíticos empregados pelas agências de inteligência permaneça desconhecida, muitos ataques sérios contra primitivos criptográficos acadêmicos e práticos foram publicados na era moderna da criptografia de computador:

• A cifra de bloco Madryga, proposta em 1984, mas não amplamente utilizada, foi considerada suscetível a ataques somente de cifratexto em 1998.
• FEAL-4, proposto como um substituto para o algoritmo de criptografia padrão DES, mas não amplamente utilizado, foi demolido por um espate de ataques da comunidade acadêmica, muitos dos quais são totalmente práticos.
• Os sistemas A5/1, A5/2, CMEA e DECT usados em tecnologia de telefone móvel e sem fio podem ser quebrados em horas, minutos ou mesmo em tempo real usando equipamentos de computação amplamente disponíveis.
• Pesquisa de espaço-chave Brute-force quebrou algumas cifras e aplicações do mundo real, incluindo single-DES (veja EFF DES cracker), criptografia de 40 bits "export-strength" e o DVD Content Scrambling System.
• Em 2001, Wired Equivalent Privacy (WEP), um protocolo usado para proteger redes sem fio Wi-Fi, foi mostrado para ser quebradável na prática por causa de uma fraqueza na cifra RC4 e aspectos do projeto WEP que fez ataques relacionados-chave práticos. O WEP foi posteriormente substituído pelo Wi-Fi Protected Access.
• Em 2008, os pesquisadores realizaram uma quebra de prova de conceito de SSL usando fraquezas na função hash MD5 e práticas de emissor de certificados que permitiram explorar ataques de colisão em funções hash. Os emissores de certificados envolvidos mudaram suas práticas para evitar que o ataque seja repetido.

Assim, embora as melhores cifras modernas possam ser muito mais resistentes à criptoanálise do que a Enigma, a criptoanálise e o campo mais amplo da segurança da informação permanecem bastante ativos.

Cifras simétricas

• Ataque de Boomeran
• Ataque de força bruta
• Ataque de Davies
• Criptoanálise diferencial
• Criptoanálise diferencial impossível
• Criptoanálise diferencial improvável
• Criptoanálise Integral
• Criptoanálise linear
• Ataque médio
• Mod-n criptoanálise
• Ataque de teclas relacionadas
• Ataque de sanduíche
• Ataque de slides
• ataque XSL

Cifras assimétricas

Criptografia assimétrica (ou criptografia de chave pública) é a criptografia que depende do uso de duas chaves (matematicamente relacionadas); um privado e outro público. Essas cifras invariavelmente dependem de códigos "difíceis" problemas matemáticos como base de sua segurança, então um ponto de ataque óbvio é desenvolver métodos para resolver o problema. A segurança da criptografia de duas chaves depende de questões matemáticas de uma maneira que a criptografia de chave única geralmente não depende e, inversamente, vincula a criptoanálise a pesquisas matemáticas mais amplas de uma nova maneira.

Esquemas assimétricos são projetados em torno da dificuldade (conjecturada) de resolver vários problemas matemáticos. Se um algoritmo melhorado puder ser encontrado para resolver o problema, o sistema estará enfraquecido. Por exemplo, a segurança do esquema de troca de chaves 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 certos grupos) e, portanto, exigindo que os criptógrafos usassem grupos maiores (ou diferentes tipos de grupos). A segurança do RSA depende (em parte) da dificuldade da fatoração inteira – um avanço na fatoração afetaria a segurança do RSA.

Em 1980, era possível fatorar um número difícil de 50 dígitos à custa de 10¹² operações elementares de computador. Em 1984, o estado da arte em algoritmos de fatoração havia avançado a um ponto em que um número de 75 dígitos poderia ser fatorado em 10¹² operações. Os avanços na tecnologia de computação também significaram que as operações poderiam ser executadas muito mais rapidamente. A lei de Moore prevê que as velocidades dos computadores continuarão a aumentar. As técnicas de fatoração também podem continuar a fazê-lo, mas provavelmente dependerão da percepção matemática e da criatividade, nenhuma das quais jamais foi previsível com sucesso. Números de 150 dígitos do tipo usado uma vez no RSA foram fatorados. O esforço foi maior do que acima, mas não era irracional em computadores rápidos e modernos. No início do século 21, números de 150 dígitos não eram mais considerados um tamanho de chave grande o suficiente para RSA. Números com várias centenas de dígitos ainda eram considerados muito difíceis de fatorar em 2005, embora os métodos provavelmente continuem a melhorar com o tempo, exigindo o tamanho da chave para manter o ritmo ou outros métodos, como criptografia de curva elíptica, a serem usados.

Outra característica distintiva dos esquemas assimétricos é que, ao contrário dos ataques a sistemas criptográficos simétricos, qualquer criptoanálise tem a oportunidade de fazer uso do conhecimento obtido da chave pública.

Atacando sistemas criptográficos de hash

• Ataque de aniversário
• Resumo de segurança da função Hash
• Tabela de arco-íris

Ataques de canal lateral

• Criptoanálise de saco preto
• Ataque de homem no meio
• Análise do poder
• Replay ataque
• Criptoanálise de mangueira de borracha
• Análise de tempo

Aplicativos de computação quântica para criptoanálise

Computadores quânticos, que ainda estão nas fases iniciais de pesquisa, têm uso potencial em criptoanálise. Por exemplo, o Algoritmo de Shor poderia fatorar grandes números em tempo polinomial, efetivamente quebrando algumas formas comumente usadas de criptografia de chave pública.

Ao usar o algoritmo de Grover em um computador quântico, a pesquisa de chave de força bruta pode ser feita quadraticamente mais rápida. No entanto, isso pode ser combatido dobrando o comprimento da chave.