Técnicas de criptografiatele.sj.ifsc.edu.br/~msobral/rmu/intro-seguranca2.pdf · Técnicas de criptografia Criptografia Cifra de César • O método pode ser expresso por: c = E(p)

1

Técnicas de criptografiaTécnicas de criptografia

• Funções Hash • Criptografia com chave secreta• Criptografia com chave pública• Assinatura digital• Protocolos

2


Criptografia• Estudo de ferramentas e técnicas matemáticas

relacionadas com aspectos relativos a segurança da informação, tais como privacidade, integridade, autenticação de entidade e autenticação da origem dos dados.

• É amplamente reconhecido que criptografia é uma tecnologia crucial para segurança em redes."Necessidade é a mão das invenções, e redes de computadores

são as mães da criptografia moderna."Ronald L. Rivest, 1997.

3


Criptografia– Transformação de uma mensagem segundo um

método (encriptação)– A mensagem é encriptada antes de ser enviada– Ao ser recebida, a mensagem encriptada é

revertida à mensagem original (decriptação)– Para dificultar a descoberta do método de

encriptação, este é dividido em duas partes• Um procedimento, ou algoritmo, de encriptação• Uma chave de codificação

– Assim, o algoritmo de encriptação pode ser conhecido publicamente, resguardando-se a chave

4


CriptografiaModelo de encriptação convencional

5


CriptografiaTerminologia

Parâmetro de codificação do algoritmo de encriptação

Chave

Análise da cifra, visando desvendar o texto plano

Criptanálise

O texto encriptadoCifra

O texto originalTexto plano

6


CriptografiaCifra de César

• Cada letra do alfabeto é substituída por outra letra três posições adiante:

Texto: meet me after the toga partyCifra: phhw ph diwhu wkh wrjd sduwb• A criptanálise para desvendar o texto original é

de grande simplicidadeTexto: a b c d e f g h i j k l m n o p q r s t u v w x y

zCifra: d e f g h i j k l m n o p q r s t u v w x y z a b c

7



• O método pode ser expresso por:c = E(p) = (p + 3) mod (26)p = D(c) = (c - 3) mod (26)

• Se for generalizado o número de posições de deslocamento das letras:

c = E(p) = (p + k) mod (26)p = D(c) = (c - k) mod (26) • Para se quebrar este código, basta tentar todas

as 25 possibilidades para k

8



Quebrando o código na força bruta ...

9


CriptografiaUma boa técnica deve ter propriedades:– Segurança depender da chave permanecer secreta, e não o algoritmo– Alta entropia– Resistência a criptanálise– Espaço de chaves amplo– Alta variabilidade em função da chave e do texto plano– Resistência a colisões

10


CriptografiaTécnicas modernas incluem:– Hashes– Encriptação com chave simétrica (chave secreta)– Encriptação com chaves assimétricas (chave pública)

11


Hashes– Uma função hash h recebe como entrada uma

string x de comprimento arbitrário.

– A saída h(x) é uma string de comprimento fixo.• Ex: cálculo de dígito verificador do CPF,CRC

– Uma função hash é dita somente-ida (one-way) se for computacionalmente inviável invertê-la

• Deve ser muito difícil encontrar x, dado h(x)

– Além disto, uma função hash é dita fortemente resistente a colisão se for também muito difícil encontrar duas strings x e x' tais que h(x) = h(x').

12


Hashes (algoritmos mais conhecidos):– MD4 (128 bits): desenvolvido em 1990 pela RSA,

sendo atualmente considerado frágil. Usado para senhas NTLM.

– MD5 (128 bits): desenvolvido em 1991 pela RSA. Há técnicas para gerar colisões. Muito usado para verificação de integridade de arquivos e armazenamento de senhas.

– SHA (160 a 512 bits): desenvolvidos a partir de 1993 pelo NIST e NSA. Há técnicas para gerar colisões para SHA-0 e SHA-1 (ambos com 160 bits).

– Whirlpool (512 bits): criado em 2004 e parte do padrão ISO 10118-3.

13


Hashes– Ex: Algoritmo MD5, que gera hashes de 128 bits:

Entrada: abcdefghijHash: a925576942e94b2ef57a066101b48876

Entrada: abcdefghiHash: 8aa99b1f439ff71293e95357bac6fd94

14


Hashes– Ex: Algoritmo SHA, que gera hashes de 160 bits:

Entrada: abcdefghijHash:

d68c19a0a345b7eab78d5e11e991c026ec60db63

Entrada: abcdefghiHash:

c63b19f1e4c8b5f76b25c49b8b87f57d8e4872a1

15


HashesUtilidade de hashes

– Verificação de integridade de mensagens• Deteccção de erros• Detecção de adulteração

– Representação compacta de mensagens (fingerprint, ou impressão digital)

• Podem-se comparar os hashes de duas mensagens, ao invés das mensagens em si.

• Usados em aplicações P2P e de cópias de arquivos (rsync)

– Armazenamento de senhas• Amplamente usado por sistemas operacionais e

aplicativos

16


HashesUtilidade de hashes – exemploMensagem original:

Hash MD5 da mensagem:

17


HashesUtilidade de hashes – exemploModificando a mensagem original:

Hash MD5 da mensagem modificada:

18


HashesUtilidade de hashes – exemploComparando os dois hashes MD5:

... Pode-se concluir que:1. As mensagens são diferentes.2. Se deveriam ser iguais, a mensagem original foi alterada

(a alteração pode ter sido um erro durante a transmissão, ou uma modificação intencional).

19


HashesUtilidade de hashes – exemploSe o hash MD5 da mensagem for enviado a ela anexado,

pode-se fazer uma verificação de integridade na recepção:

20


Criptografia com chave secreta– Transforma uma string:c = E(p, k)p = D(c, k)– Comumente c e p têm mesmo tamanho– Ideal para proteger (encriptar) informação– Chamados de algoritmos de criptografia simétricos

• Usa-se a mesma chave k para encriptar e para decriptar

• A chave deve ser do conhecimento apenas dos pares envolvidos na troca de informação

21


Criptografia com chave secreta

22


Criptografia com chave secreta (algoritmos):– DES (Data Encryption Standard): padrão do

governo americano a partir de 1976. Considerado fraco, por usar chaves pequenas (40 ou 56 bits).

– 3DES (Triple DES): desenvolvido pela IBM em 1978, usa DES três vezes, com duas ou três chaves distintas de 56 bits.

– AES (Advanced Encryption Standard): desenvolvido em 1998, e sucessor do DES como padrão do governo americano em 2002. Usa chaves de 128, 192 ou 256 bits.

23


Criptografia com chave secreta (algoritmos):– RC4 (Ron's Code): desenvolvido em 1987 pela

RSA. Cifra para streams bastante usada em protocolos de comunicação (SSL, WEP), apesar de fraquezas conhecidas. Usa chaves entre 40 e 256 bits.

– Blowfish: desenvolvido em 1993 por Bruce Schneier. Tem boa taxa de encriptação, e não há fraquezas conhecidas. Usa chaves de 128 bits.

– Twofish: desenvolvido em 1998 por Bruce Schneier e outros, sendo sucessor do Blowfish. Usa chaves de 256 bits. Disputou com AES para ser novo padrão do governo americano.

24



Usando criptografia simétrica para encriptar o hash MD5 da mensagem mostrada anteriormente:

25



Para fazer a verificação da mensagem, quem a receber deve antes decriptar o hash

– Implica então que a chave simétrica deve ser de seu conhecimento

– Caso a possua, a verificação da mensagem se dará pelas etapas:

• Decripta o hash• Calcula o hash da mensagem recebida• Compara os hashes

– Para implementar essa verificação, faz-se necessário um mecanismo seguro de distribuição de chaves

26


Criptografia com chave secretaEncriptando um valor com GnuPG:

Decriptando o texto cifrado acima:

27


Criptografia com chave secreta• Algoritmos com chave simétrica são apropriados para encriptar informação• Há uma dificuldade quanto ao gerenciamento das chaves secretas

– Como chaves secretas podem ser compartilhadas ?– Se a chave secreta for enviada pela rede, um terceiro

usuário poderia interceptá-la !

Vejam o filme “The Imitation Game”, de 2014.

28


Criptografia com chave pública– Algoritmos de criptografia com chaves assimétricas– Cada par da comunicação possui duas chaves

• Uma cifra gerada com uma das chaves somente pode ser decriptada com a outra chave.

– Com este método, pode-se tornar pública uma das chaves, e manter a outra secreta (privada)

• A chave pública de uma entidade da rede será usada por quem desejar lhe enviar uma mensagem

• Somente o possuidor da correspondente chave privada conseguirá decodificar a mensagem

29


Criptografia com chave públicac = F(p, kp) c = F(p, ks)p = F(c, ks) p = F(p, kp)

30


Criptografia de chave pública (algoritmos):– RSA (Rivest-Shamir-Adleman): desenvolvido em

1977 no MIT. Primeiro algoritmo de chave pública, e usa dificuldade de fatoração de grandes números como princípio. Usa chaves de 512, 1024, 2048 ou 4096 bytes.

– DSA (Digital Signature Algorithm): desenvolvido em 1991 pelo NIST, tornando-se padrão do governo americano. Usado somente para assinaturas digitais. Usa chaves de 1024, 2048 ou 3072 bits.

– Elgamal: desenvolvido em 1984 por Taher Elgamal. Possui fraquezas conhecidas.

31


Criptografia com chave públicaO algoritmo RSA se baseia em teoria dos números (fatoração de números):

Chave pública:n = p.q (p e q são números primos)e relativamente primo de (p - 1).(q - 1)Chave secreta:d = e-1 mod [(p - 1).(q - 1)]Encriptação:c = me mod nDecriptação:m = cd mod n

32


Criptografia com chave públicaExemplo de criação de chaves para RSA:

Se p = 47 e q = 71:n = p.q = 3337(p - 1).(q - 1) = 3220Escolhe-se e aleatoriamente, de forma que seja primo e não tenha fatores em comum com 3220:e = 79d = 79-1 mod 3220 = 1019Publiquem-se e e n, mantendo-se d secreta.Encriptando m = 688:68879 mod 3337 = 1570 = cDecriptando c:15701019 mod 3337 = 688 = m

33


Assinatura digitalUma forma de garantir que uma mensagem foi gerada de fato por uma determinada entidade da rede

– O remetente calcula um hash da mensagem, que a ela é anexado

– Hash é encriptado com a chave privada do remetente

– Mensagem + hash encriptado são enviados para o destinatário

– O destinatário decripta o hash com a chave pública do remetente

– O destinatário confere se o hash corresponde à mensagem

34


Assinatura digitalExemplo de assinatura digital da mensagem vista anteriormente,usando o software GnuPG (uma variação do famoso PGP):

35


Assinatura digital– Inserindo uma pequena alteração na mensagem.

– Verificando a mensagem:

36


ProtocolosTroca de chave• Criptografia com chave pública é muito mais pesada

computacionalmente que criptografia simétrica.– Segundo Bruce Schneier, em seu livro “Applied

Cryptography”, o algoritmo RSA é cerca de 100 vezes mais lento que DES se implementado em software, e 1000 vezes mais lento se implementado em hardware.

– Não se considera viável usar criptografia de chave pública para manter sigilo (confidencialidade) de informação.

– Sigilo pode ser implantado de forma mais eficiente com criptografia simétrica.

– Isto leva ao problema de troca de chaves entre pares de uma comunicação, pois ambos precisarão conhecer a chave secreta usada por tal tipo de algoritmo.

37


ProtocolosIntercâmbio de chave

– Com criptografia simétrica• a chave de sessão deve ser do conhecimento dos pares

antes da comunicação• Uma entidade confiável pode gerar uma chave de sessão,

e enviá-la para os pares que desejam se comunicar com sigilo.

• Cada par deve possuir uma chave simétrica previamente fornecida pela entidade confiável, para poder se comunicar com esta também com sigilo.

– Com criptografia assimétrica• a chave de sessão é gerada aleatoriamente por um dos

pares • usa-se a chave pública do outro par para lhe transmitir a

chave de sessão

38


Protocolos Autenticação• Com funções somente-ida (one-way hash)

– Uma senha é armazenada criptografada– Para conferir a autenticidade de um usuário, solicita-se a

senha– A senha fornecida é criptografada e então comparada

com aquela armazenada

39


Protocolos Autenticação• Com criptografia de chave pública

– Armazena-se a chave pública de um usuário A– Para B autenticar este usuário, gera-se uma string

aleatória e encripta-se a chave pública de A– Envia-se a string ao usuário A, que deve decriptá-la com

sua chave privada, encriptá-la com a chave pública de B e remetê-la de volta

– B decripta esta mensagem com sua chave privada, e compara-a com a string original

40


Protocolos Autenticação

– Com credenciais únicas• Recebe-se uma semente da entidade que exige

autenticação (isto é feito num momento de cadastro).• A cada autenticação a ser realizada, computa-se um

valor que servirá de credencial.• Esta credencial é calculada com uma função a partir

da semente.• A cada autenticação, a nova credencial é calculada

em função da credencial anterior.• A função deve ser tal que seja computacionalmente

inviável determinar a semente a partir das credenciais calculadas.

Documents

Técnicas de criptografiatele.sj.ifsc.edu.br/~msobral/rmu/intro-seguranca2.pdf · Técnicas de criptografia Criptografia Cifra de César • O método pode ser expresso por: c = E(p)