Criptografia - Faculdade Impacta

CriptografiaLuiz Rabelo

História da criptografia• A história da criptografia começa há milhares de anos. Até

décadas recentes, ela havia sido a história do que poderia ser chamado de criptografia clássica — isto é, de métodos de criptografia que usam caneta e papel, ou talvez auxílios mecânicos simples. No começo do século XX, a invenção de complexas máquinas mecânicas e electro-mecânicas, tais como a máquina com rotores Enigma, providenciou meios mais sofisticados e eficientes de encriptação; e a posterior introdução da eletrônica e computação permitiu elaborar esquemas de ainda maior complexidade, muitos completamente inadequáveis ao papel e caneta.

Enigma• Enigma é o nome por que é conhecida uma máquina electro-

mecânica de criptografia com rotores, utilizada tanto para criptografar como para descriptografar mensagens secretas, usada em várias formas na Europa a partir dos anos 1920. A sua fama vem de ter sido adaptada pela maior parte das forças militares alemãs a partir de cerca de 1930. A facilidade de uso e a suposta indecifrabilidade do código foram as principais razões para a sua popularidade. O código foi, no entanto, decifrado, e a informação contida nas mensagens que ele não protegeu é geralmente tida como responsável pelo fim da Segunda Guerra Mundial pelo menos um ano antes do que seria de prever.

Enigma - Funcionamento• Combinação de sistemas mecânicos e elétricos. O mecanismo

consiste num teclado, num conjunto de discos rotativos chamados rotores, dispostos em fila; e de um mecanismo de avanço que faz andar alguns rotores uma posição quando uma tecla é pressionada. O mecanismo varia entre diversas versões da máquina, mas o mais comum é o rotor colocado à direita avançar uma posição com cada tecla premida, e ocasionalmente despoletar o movimento rotativo dos restantes rotores, à sua esquerda, à semelhança do mecanismo conta-quilómetros de um automóvel. O movimento contínuo dos rotores provoca diferentes combinações na criptografia.

Enigma

Enigma

1. anel dentado (uma ranhura)2. ponto de marca do contacto "A"3. círculo com alfabeto4. contatos5. fios eléctricos6. pinos7. encaixe do eixo8. hub9. roda dentada movível com os dedos10. ratchet

Enigma

Enigma

História da criptografia• O desenvolvimento da criptografia foi acompanhado pelo

desenvolvimento da criptoanálise - a "quebra" de códigos e cifras. A descoberta e aplicação, desde cedo, de análise de frequência para a leitura de comunicações criptografadas, muitas vezes, alterou o curso da história. Portanto, o Telegrama Zimmermann que motivou a entrada dos Estados Unidos na Primeira Guerra Mundial e o fato de que os Aliados conseguiram decifrar as cifras da Alemanha Nazista, encurtou a Segunda Guerra Mundial, em algumas avaliações, em até dois anos.

História da criptografia• Até a década de 70, criptografia segura foi amplamente

utilizada para a proteção de governos. Dois eventos trouxeram-a diretamente para o domínio público: a criação de um padrão de criptografia de chave pública (DES), e a invenção da criptografia de chave pública.

ROT 13• Procedimento simples mas eficaz para garantir que textos

eletrônicos não sejam lidos por distração ou acidente. ROT-13 vem do inglês, ROTate by 13 places, "ROTacionar 13 posições".

• Como era de se esperar, o ROT-13 é usado principalmente em grupos de discussão como as dos Yahoo e Google.

• Um detalhe importante: não há qualquer diferença entre o procedimento para codificar um texto em ROT-13 e o procedimento para decodificá-lo; simplesmente aplicamos o mesmo procedimento uma segunda vez.

ROT 13

Cifra de César• Uma das mais simples e conhecidas técnicas de criptografia. É

um tipo de cifra de substituição na qual cada letra do texto é substituída por outra, que se apresenta no alfabeto abaixo dela um número fixo de vezes. Por exemplo, com uma troca de três posições, A seria substituído por D, B se tornaria E, e assim por diante. O nome do método é em homenagem a Júlio César, que o usou para se comunicar com os seus generais.

Cifra de César

Chave pública• A criptografia de chave pública ou criptografia assimétrica é

um método de criptografia que utiliza um par de chaves: uma chave pública e uma chave privada. A chave pública é distribuída livremente para todos os correspondentes via e-mail ou outras formas, enquanto a chave privada deve ser conhecida apenas pelo seu dono.

• Num algoritmo de criptografia assimétrica, uma mensagem cifrada com a chave pública pode somente ser decifrada pela sua chave privada correspondente.

Chave pública• Os algoritmos de chave pública podem ser utilizados para

autenticidade e confidencialidade:

• Confidencialidade: A chave pública é usada para cifrar mensagens, com isso apenas o dono da chave privada pode decifrá-la.

• Autenticidade: A chave privada é usada para cifrar mensagens, com isso garante-se que apenas o dono da chave privada poderia ter cifrado a mensagem que foi decifrada com a 'chave pública', e que a mensagem não foi forjada.

Chave pública

1º passo: o envio da chave pública

Chave pública

2º passo: o envio da mensagem cifrada, aberta com a chave privada

Chave públicaCada usuário possui um par de chaves (S, P) sendo S a sua chave particular, secreta, e P a sua chave pública. As chaves S e P são relacionadas matematicamente de tal forma que:• Se x denota um texto legível, e S() denota a aplicação da chave S,

transforma x em S(x) =y então P(y) =x onde P() denota a aplicação da chave P, ou seja, S é a chave inversa da chave P onde, P(S(x)) =x;

• O cálculo do par de chaves (S, P) é computacionalmente fácil.• É computacionalmente difícil calcular S a partir do conhecimento de P.• Os cálculos de P() e S() são computacionalmente fáceis para quem

conhece as chaves.• É computacionalmente difícil calcular S() sem conhecer a chave S.

Estas possibilidades levam ao seguinte cenário:• Cada usuário calcula o seu par de chaves (S, P) no seu computador.• A chave S é guardada de forma segura no seu computador.• A chave P é distribuída a todos de forma pública.

Criptoanálise• 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 descodificar 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.

Criptoanálise• 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, keylogging, 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.

Criptoanálise• 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”.

Criptoanálise• 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.

Criptoanálise• 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 – foi conhecido como o ponto decisivo para chegar ao fim da guerra.

Criptoanálise

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?

CriptoanáliseOs 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.

Força bruta• Wikipedia: Em ciência da computação, força bruta (ou busca

exaustiva) é uma algoritmo trivial mas de uso muito geral que consiste em enumerar todos os possíveis candidatos de uma solução e verificar se cada um satisfaz o problema.

• Por exemplo, um algoritmo para encontrar os divisores de um número natural n é enumerar todos os inteiros de 1 a n, e verificar para cada um se ele dividido por n resulta em resto 0.

Força bruta• Isto é uma estimativa de tempo requerido para um exaustivo

ataque de senha (força bruta), sendo que a senha é uma seqüencia aleatória de letras minúsculas latinas.

• Vamos supor que um usuário possa controlar 10 senhas por segundo e que uma organização com um orçamento de $1 bilhão (mil milhões) de dólares possa controlar 1 bilhão de senhas por segundo. Também supomos que o processador em uso duplica seu desempenho a cada dois anos, assim, cada letra latina que acrescentarmos será adicionada 9 anos de um exaustivo ataque de senha.

Força brutaTamanho da senha Ataque de um usuário comum Ataque da organização

1 letra minúscula latina 2 segundos 1 segundo

2 1 minuto 1s

3 30 min 1s

4 12 horas 1s

5 14 dias 1s

6 1 ano 1s

7 10 anos 1s

8 19 anos 20s

9 26 anos 9 min

10 37 anos 4 horas

11 46 anos 4 dias

12 55 anos 4 meses

13 64 anos 4 anos

14 73 anos 13 anos

15 82 anos 22 anos

16 91 anos 31 anos

17 100 anos 40 anos

Dicionário

Dicionário• Consiste em tentar descobrir uma senha utilizando todas as

possíveis combinações de um dicionário. Este tipo de ataque é mais eficiente que um ataque de força bruta, pois o conjunto de todas as combinações com as palavras do dicionário usado é muito menor que todas as combinações existentes, como no caso de força bruta.

• O fato deste conjunto ser menor, tem um motivo: o usuário sabe quais as palavras, letras, números que ele utilizou na confecção da senha.

Rainbow tables

Comparativos de ataques

Prática• Criptool