ProtocolosCriptográficos

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

Criptografia simétrica

• Chave única Ke = Kd

• Extremamente rápida

Método decifragem EMétodo decifragem E

Método dedecifragem D

Método dedecifragem D

Ke Kd

M M

C

E(M,Ke) = C D(C,Kd) = M

AA

+dOJJVEqkmDJZ1S+X8UzGNN+uLDy6aheTS2tiOF7VW5IT+/8Ace4tG2shAHLnXCwpdPggMAhj8qsB90R3uLkuhvYumU/xn5zuFHnMAJ76R6J6dnx

Criptografia Assimétrica

PubPub Priv

Esta mensagem é secreta, pois contém dados da mais alta importância para a nossa empresa.

+dOJJVEqkmDJZ1S+X8UzGNN+uLDy6aheTS2tiOF7VW5IT+/8Ace4tG2shAHLnXCwpdPggMAhj8qsB90R3uLkuhvYumU/xn5zuFHnMAJ76R6J6dnx

CIFRAGEM

Esta mensagem é secreta, pois contém dados da mais alta importância para a nossa empresa.

DECIFRAGEM TRANSMISSÃO

Alice Bob

AA Pub+dOJJVEqkmDJZ1S+X8UzGNN+uLDy6aheTS2tiOF7VW5IT+/8Ace4tG2shAHLnXCwpdPggMAhj8qsB90R3uLkuhvYumU/xn5zuFHnMAJ76R6J6dnx

Funções Unidirecionais (Hash)

• Resumo matemático de tamanho fixo– 128, 160, 256,... Bits

• M pode ter qualquer tamanho

• Detecta alterações intencionais

• Resistência a colisões

Função deHash H

Função deHash HM

H(M) = h

538294DF1EC334CCF2A8

K H(M,K) = h

hAHLnXCwpdPggMAhj8qsB9+dOJJVEqkmDJZ1S+X8UzGNN+uLDy6aheTS2tiOF7VW5IT+/8n5zuFHAce4tG2shAHLnXCwpdPggMAhj8qsB90R3uLkuhvYumU/xn5zuFHnMAJ76R6J6dnxB9+dOwpdPgg8UzGG2shAHjsGshdsS

hAHLnXCwpdPggMAhj8qsB9+dOJJVEqkmDJZ1S+X8UzGNN+uLDy6aheTS2tiOF7VW5IT+/8n5zuFHAce4tG2shAHLnXCwpdPggMAhj8qsB90R3uLkuhvYumU/xn5zuFHnMAJ76R6J6dnxB9+dOwpdPgg8UzGG2shAHjsGshdsS

Assinatura Digital

Pub Pub Priv

Esta mensagem é secreta, pois contém dados da mais alta importância para a nossa empresa.

h25c924fed23

Pub PrivPub

Esta mensagem é secreta, pois contém dados da mais alta importância para a nossa empresa.

4932uvf9vbd8bbfgbfg 4932uvf9vbd8bbfgbfgh25c924fed23

CIFRAGEM +ASSINATURA

DECIFRAGEM +verificação da ASSINATURA

Alice Bob

Protocolos Criptográficos

• Segurança não depende só do algoritmo de criptografia

• Exemplo: HTTPS (SSL)

Site.comSite.com

CACA

ClienteCliente

CA

Site

Site

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

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

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

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

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

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

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

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

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

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

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

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

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 :-)

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

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

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

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

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

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

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

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 = 0

F(2) = 28 + 16 + 11 mod 13 = 3

F(3) = 63 + 24 + 11 mod 13 = 7

F(4) = 112 + 32 + 11 mod 13 = 12

F(5) = 175 + 40 + 11 mod 13 = 5