23
Protocolos Criptográficos

Protocolos Criptográficos. Comunicação Alice Bob Características desejadas –Privacidade: Alice e Bob usam uma chave simétrica secreta comum (“chave de

Embed Size (px)

Citation preview

Page 1: Protocolos Criptográficos. Comunicação Alice Bob Características desejadas –Privacidade: Alice e Bob usam uma chave simétrica secreta comum (“chave de

ProtocolosCriptográficos

Page 2: Protocolos Criptográficos. Comunicação Alice Bob Características desejadas –Privacidade: Alice e Bob usam uma chave simétrica secreta comum (“chave de

Comunicação

• Alice Bob

• Características desejadas– Privacidade: Alice e Bob usam uma chave simétrica secreta comum (“chave de

sessão”)» chaves assimétricas são muito lentas

– Autenticidade: Alice e Bob assinam as mensagens com suas chaves assimétricas secretas

– Integridade: Alice e Bob utilizam funções de hash (com chave)» Função de hash sem chave pode ser manipulada, se transmitida junto com a mensagem

M

Page 3: Protocolos Criptográficos. Comunicação Alice Bob Características desejadas –Privacidade: Alice e Bob usam uma chave simétrica secreta comum (“chave de

Chave de sessão

• Alice Bob

• Como gerar?– Transmissão em claro

» Eve pode estar escutando – Alice gera a chave

» Como enviar para Bob?» Como saber se Alice gera boas chaves?

M

Eve

Page 4: Protocolos Criptográficos. Comunicação Alice Bob Características desejadas –Privacidade: Alice e Bob usam uma chave simétrica secreta comum (“chave de

Chave de sessão

• Alice Bob

• Alice conhece a chave pública de Bob (e vice-versa)– Alice gera uma chave: Ka– Alice envia para Bob cifrando com a chave pública de Bob

» E(Ka,KPubB)– Bob decifra com sua chave secreta

» Ka = D(E(Ka, KPubB),KSecB)– Bob repete os passos, enviando para Alice sua chave Kb

» Kb = D(E(Kb, KPubA),KSecA)– Alice e Bob fazem uma operação comum sobre as chaves

» Chave de sessão: K = Ka xor Kb

M

Eve KPubAKPubB

Page 5: Protocolos Criptográficos. Comunicação Alice Bob Características desejadas –Privacidade: Alice e Bob usam uma chave simétrica secreta comum (“chave de

Prova de identidade

• Alice Bob

• Como Alice pode se autenticar com Bob?– Alice e Bob nunca se encontraram antes– Eve pode estar escutando, gravando a conversa e depois fazer

um ataque de repetição de bloco

M

Eve

Page 6: Protocolos Criptográficos. Comunicação Alice Bob Características desejadas –Privacidade: Alice e Bob usam uma chave simétrica secreta comum (“chave de

Prova de identidade

• Alice Bob

• Alice conhece a chave pública de Bob (e vice-versa)– Bob gera um desafio Rb e envia para Alive– Alice assina o desafio, cifrando com sua chave secreta

» E(Rb,KsecA)– Bob decifra com a chave pública de Alice

» Rb = D(E(Rb, KsecA),KPubA)– Alice repete os passos, enviando para Bob seu desafio Ra

» Ra = D(E(Ra, KsecB),KPubB)– Alice e Bob nunca devem reutilizar o desafio!

» Senão Eve pode fazer o ataque de repetição de bloco

M

Eve KPubAKPubB

Page 7: Protocolos Criptográficos. Comunicação Alice Bob Características desejadas –Privacidade: Alice e Bob usam uma chave simétrica secreta comum (“chave de

Ataque do homem-no-meio

• Alice Bob

• Alice Mallory Bob

• Se Alice e Bob conhecem a chave pública um do outro, Mallory não tem chances!

– Mallory não pode obter a chave de sessão, mesmo observando todo tráfego, pois não pode decifrar as mensagens (chaves secretas de Alice e Bob são necessárias)

– Mallory não pode responder a um desafio da Alice, personificando Bob, porque não conhece a chave secreta de Bob (e vice-versa

M

M N

Page 8: Protocolos Criptográficos. Comunicação Alice Bob Características desejadas –Privacidade: Alice e Bob usam uma chave simétrica secreta comum (“chave de

Ataque do homem-no-meio

• Alice Bob

• Alice Mallory Bob

• Mas e se Alice e Bob não possuem a chave pública do outro?• Soluções:

– Enviar “metade” da mensagem de cada vez– Enviar Hash da mensagem antes– Enviar Mensagem cifrada antes e Chave depois– Usar um “Terceiro Confiável” (Trent)

M

M N

Page 9: Protocolos Criptográficos. Comunicação Alice Bob Características desejadas –Privacidade: Alice e Bob usam uma chave simétrica secreta comum (“chave de

Autenticação

• (1) Alice envia ao computador sua senha (S)• (2) O computador calcula um hash desta senha: H(S)• (3) O computador calcula este hash com o valor previamente

armazenado

• Problema:– Senha S enviada em claro– Sujeito ao ataque ativo (Mallory) ou passivo (Eve)

• Vantagem:– Senha não é armazenada no computador– Somente H(S) é armazenado

Page 10: Protocolos Criptográficos. Comunicação Alice Bob Características desejadas –Privacidade: Alice e Bob usam uma chave simétrica secreta comum (“chave de

Chave de sessão

• Protocolo de três passos• Utiliza uma função Ou-exclusivo

– (1) Alice escolhe uma chave K, cifra com uma chave randômica A (C1 = K exor A), e envia para Bob

– (2) Bob cifra a mensagem recebida com uma chave randômica B (C2 = C1 exor B), e envia para Alice

– (3) Alice cifra novamente com a chave A (C3 = C2 exor A = K exor A exor B exor A = K exor B) e envia o resultado para Bob

– (4) Bob cifra novamente com sua chave B e obtém C3 exor B = K exor B exor B = K

Page 11: Protocolos Criptográficos. Comunicação Alice Bob Características desejadas –Privacidade: Alice e Bob usam uma chave simétrica secreta comum (“chave de

Chave de sessão

• Problema: Atacante que intercepta as três mensagens recupera a chave:

• C1 exor C2 exor C3 =• (K exor A) exor (K exor A exor B) exor (K exor B) =• K exor K exor K exor A exor A exor B exor B =• K exor K exor K =• K

Page 12: Protocolos Criptográficos. Comunicação Alice Bob Características desejadas –Privacidade: Alice e Bob usam uma chave simétrica secreta comum (“chave de

Chave de sessão

Troca de chave via Diffie-Hellman• É o protocolo mais antigo (1977), e permite que Alice e Bob gerem

uma chave secreta K sem a necessidade de intermediários– (1) Alice e Bob escolhem um número primo n e um número g. Estes números não

necessitam ser secretos, e podem ser trocados através de um canal inseguro– (2) Alice escolhe um número x qualquer e envia para Bob o número X = f(x,n,g)– (3) Bob escolhe um número y qualquer e envia para Alice o número Y = f(y,n,g)– (4) Alice calcula Ka = g(x,Y,n,g)– (5) Bob calcula Kb = g(y,X,n,g)

Funciona se g(x,Y,n,g) = g(y,X,n,g), pois então Ka = Kb = K

Page 13: Protocolos Criptográficos. Comunicação Alice Bob Características desejadas –Privacidade: Alice e Bob usam uma chave simétrica secreta comum (“chave de

Chave de sessão

Diffie-Hellman aditivo– (1) Alice e Bob escolhem um número primo n e um número g. Estes números são

trocados através de um canal inseguro– (2) Alice escolhe um número x qualquer e envia para Bob o número X = x + g mod n– (3) Bob escolhe um número y qualquer e envia para Alice o número Y = y + g mod n– (4) Alice calcula K = x + Y mod n = x + y +g mod n– (5) Bob calcula K = y + X mod n = y + x + g mod n– Mas Eve conhece n, g, X e Y:

» Eve calcula o inverso aditivo de g: (n - g)» Eve calcula X + Y + (n - g) mod n = x + g + y + g + n - g mod n» Eve obtém x + y + g + n mod n = x + y + g mod n

Page 14: Protocolos Criptográficos. Comunicação Alice Bob Características desejadas –Privacidade: Alice e Bob usam uma chave simétrica secreta comum (“chave de

Chave de sessão

Diffie-Hellman multiplicativo– (1) Alice e Bob escolhem um número primo n e um número g. Estes números são

trocados através de um canal inseguro– (2) Alice escolhe um número x qualquer e envia para Bob o número X = x * g mod n– (3) Bob escolhe um número y qualquer e envia para Alice o número Y = y * g mod n– (4) Alice calcula K = x * Y mod n = x * y * g mod n– (5) Bob calcula K = y * X mod n = y * x * g mod n– Mas Eve conhece n, g, X e Y:

» Eve calcula o inverso multiplicativo de g: g-1 mod n» Eve calcula X * Y * g-1 mod n = x * g * y * g * g-1 mod n» Eve obtém x * y * g * 1 mod n = x * y * g mod n

Page 15: Protocolos Criptográficos. Comunicação Alice Bob Características desejadas –Privacidade: Alice e Bob usam uma chave simétrica secreta comum (“chave de

Chave de sessão

Diffie-Hellman exponencial– (1) Alice e Bob escolhem um número primo n e um número g. Estes números são

trocados através de um canal inseguro– (2) Alice escolhe um número x qualquer e envia para Bob o número X = gx mod n– (3) Bob escolhe um número y qualquer e envia para Alice o número Y = gy mod n– (4) Alice calcula K = Yx mod n = (gy mod n)x mod n = gxy mod n– (5) Bob calcula K = Xy mod n = (gx mod n)y mod n = gxy mod n

– Mas Eve conhece n, g, X e Y:» Eve deve resolver x = logg X mod n» ou Eve deve resolver y = logg Y mod n» (Eve vai demorar um pouco :-)

Page 16: Protocolos Criptográficos. Comunicação Alice Bob Características desejadas –Privacidade: Alice e Bob usam uma chave simétrica secreta comum (“chave de

Chave de sessão

Diffie-Hellman modificado• Cada usuário possui uma chave secreta S e uma chave pública (n,g,T),

onde T = gS mod n(1) Alice calcula K1=(gB)SA mod nB e K2=(TB)SA mod nB(2) Alice escolhe uma chave de sessão K, e cifra esta chave

com o valor K2: X = E(K,K2)(3) Alice envia K1 e X para Bob(4) Bob calcula (K1)SB mod nB= ((gB)SA mod nB)SB mod nB =

(gBSA)SB mod nB) = TBSA mod nB = K2(5) Bob decifra X usando K2 e obtém K

Page 17: Protocolos Criptográficos. Comunicação Alice Bob Características desejadas –Privacidade: Alice e Bob usam uma chave simétrica secreta comum (“chave de

Chave de sessão

Wide-Mouth Frog

(1) Alice cifra o nome de Bob, uma chave randômica de sessão e um carimbo de tempo, e envia para Trent junto com seu nome: A,EA(B,K,Ta)

(2) Trent decifra a mensagem, e cifra uma mensagem para Bob com o nome de Alice, a chave K e outro carimbo de tempo: EB(A,K,Tb)

• O protocolo é simples• Assume que Alice é capaz de gerar boas chaves

Page 18: Protocolos Criptográficos. Comunicação Alice Bob Características desejadas –Privacidade: Alice e Bob usam uma chave simétrica secreta comum (“chave de

Chave de sessão

Kerberos(1) Alice para Trent o seu nome e o de Bob: A,B(2) Trent gera uma chave de sessão, um tempo de validade, um carimbo de tempo

e prepara duas mensagens, que ele envia para Alice: EA(K,L,T,B),EB(K,L,T,A)(3) Alice decifra sua mensagem, obtém K e envia para Bob: EB(K,L,T,A), EK(A,T)(4) Bob decifra sua mensagem, obtém K, decifra a mensagem de Alice e envia

para ela: EK(T+1)

• Kerberos assume que os relógios de Trent, Alice e Bob estão sincronizados

Page 19: Protocolos Criptográficos. Comunicação Alice Bob Características desejadas –Privacidade: Alice e Bob usam uma chave simétrica secreta comum (“chave de

One-Time Password

(1) Alice, através de um canal seguro, envia ao computador uma senha S

(2) O computador calcula h[1]=H(S), h[2]=H(h[1]), h[3]=H(h[2]), ...., h[n]=H(h[n-1]), h[n+1]=H(h[n]) e armazena somente h[n+1]

(3) Da primeira vez que se autenticar, Alice envia h[n]. O computador calcula h[n+1]=H(h[n]). Ele então descarta h[n+1] e substitui por h[n]. De uma maneira genérica, Alice envia h[i]; o computador calcula H(h[i]) e compara com h[i+1]; o computador armazena h[i] no lugar de h[i+1]

(4)Quando Alice utilizar toda a seqüência, ela deve reinicializar o protocolo

Page 20: Protocolos Criptográficos. Comunicação Alice Bob Características desejadas –Privacidade: Alice e Bob usam uma chave simétrica secreta comum (“chave de

Divisão de segredo

– Dividir um segredo S entre várias pessoas– Todas as pessoas devem se reunir para recompor o segredo– Uso do ou-exclusivo (xor)– Para dividir um segredo S entre duas pessoas escolhe-se um randômico R e calcula-se:

S xor R = Rr– Alice recebe R e Bob recebe Rr. Eles devem se reunir para restaurar M:

R xor Rr = S– Para dividir entre n pessoas, escolhe-se n-1 randômicos e faz-se o ou-exclusivo de

todos eles com a mensagem M. Distribui-se o resultado e os n-1 randômicos entre as n pessoas:

R1 xor R2 xor …. xor Rn-1 xor S = Rr

Page 21: Protocolos Criptográficos. Comunicação Alice Bob Características desejadas –Privacidade: Alice e Bob usam uma chave simétrica secreta comum (“chave de

Compartilhamento de segredo

• Compartilhar um segredo entre n pessoas, de tal forma que no mínimo m destas pessoas (m<n) devam se reunir para restaurar o segredo

• Um método para implementar este compartilhamento utiliza polinômios

• Escolhe-se um número primo p e um polinômio de grau m-1• Por exemplo, para compartilhar M de tal forma que três pessoas

possam restaurá-lo, escolhe-se um polinômio do segundo grau:a.x2 + b.x + M mod p

Page 22: Protocolos Criptográficos. Comunicação Alice Bob Características desejadas –Privacidade: Alice e Bob usam uma chave simétrica secreta comum (“chave de

Compartilhamento de segredo

• Por exemplo, para compartilhar M de tal forma que três pessoas possam restaurá-lo, escolhe-se um polinômio do segundo grau:a.x2 + b.x + M mod p

• Os coeficientes a e b podem ser quaisquer; p deve ser primo e maior que qualquer um dos coeficientes. A seguir calculam-se os valores desta equação para diversos pontos:ki = F(xi) = a.i2 + b.i + M mod p

• Cada pessoa recebe um deste valores. Como existem três incógnitas (a, b e M), são necessários no mínimo três pontos para resolver a equação

• Observe-se que a e b devem ser mantidos em segredo

Page 23: Protocolos Criptográficos. Comunicação Alice Bob Características desejadas –Privacidade: Alice e Bob usam uma chave simétrica secreta comum (“chave de

Compartilhamento de segredo

• Por exemplo, seja M=11. Escolhe-se aleatoriamente a=7 e b=8, assim como p=13. Então a equação fica:F(x) = 7.x2 + 8.x + 11 mod 13

• Se o segredo deve ser compartilhado entre cinco pessoas, basta calcular cinco pontos:F(1) = 7 + 8 + 11 mod 13 = 0F(2) = 28 + 16 + 11 mod 13 = 3F(3) = 63 + 24 + 11 mod 13 = 7F(4) = 112 + 32 + 11 mod 13 = 12F(5) = 175 + 40 + 11 mod 13 = 5