Protocolos Básicos
Troca de Chaves
Autenticação
Autenticação e Troca de Chaves
Protocolos Básicos
Troca de Chaves
• Uma técnica de criptografia é uso de chave de sessão.
• Chave de sessão é assim chamada por ser utilizada uma única vez para uma comunicação particular.
• Chave de sessão somente existe durante a comunicação.
Protocolos BásicosTroca de chaves com criptografia simétrica
A deseja se comunicar com B e recebe uma chave de
sessão KS .
A → T : Requisição KS , IDB
T → A : EKA ( KS ) || EKB ( KS )
A : DKA ( KS )
A → B : EKB ( KS )
B : DKB ( KS )
A EKS ( m ) B
Protocolos Básicos
Troca de chaves com criptografia assimétrica
A deseja se comunicar com B e recebe uma chave de
sessão KS .
A → T : Requisição KUB, IDB
T → A : KUB
A : Gera KS
A → B : EKUB ( KS )
B : DKRB ( KS )
A EKS ( m ) B
Protocolos Básicos Man-in-the-Middle Attack A → B : KUA
M : KUA ; M → B : KUM
B → A : KUB
M : KUB ; M → B : KUM
A → B : EKUM (m) Alice pensa que tem uma KUB
M : EKUM (m) ; M : DKUM (m) ; M : m ; M :> m’
M : EKUB (m’) ; M → B : EKUB (m’) ; B : DKRB(m’) ; B : m’
B → A : EKUM (m”) Bob pensa que tem uma KUA
M : EKUM (m”) ; M : DKRM
(m”) ; M : m”
M : EKUA (m”) ; M → A : EKUA (m”)
Man-in-the-Middle Attack
• Mesmo que as chaves públicas de Alice e Bob estejam armazenadas em uma base de dados, este ataque funcionará.
• Mallory pode interceptar a consulta de Alice na base de dados e substituir sua própria chave-pública para Bob.
Man-in-the-Middle Attack
• Mallory pode interceptar a consulta de Bob na base de dados e substituir sua própria chave-pública para Alice.
• Ou melhor ainda, Mallory pode invadir a base de dados e substituir as chaves de Alice e Bob, pela chave dele.
Man-in-the-Middle Attack
• Então, Mallory simplesmente espera Alice e Bob se comunicarem, intercepta e modifica mensagens capturadas de forma bem sucedida.
• Este Man-in-the-Middle Attack funciona bem porque Alice e Bob não tem nenhum meio para verificar que eles estão se comunicando entre eles mesmo.
Man-in-the-Middle Attack
• Assumindo que Mallory não causa nenhum atraso de rede notável, Alice e Bob não tem ideia que alguém situado entre eles está lendo tudo de sua supostamente comunicação secreta.
Protocolos Básicos
Interlock Protocol, Ron Rivest and Adi Shamir
A → B : KUA
B → A : KUB A : EKUB ( MA )
A → B : { EKUB ( MA ) } / 2 B : EKUA ( MB )
B → A : { EKUA ( MB ) } / 2
A → B : { EKUB ( MA ) } / 2´ B : DKRB ( 1 / 2 || 1 / 2´ )
B → A : { EKUB ( MB ) } / 2´ A : DKRA ( 1 / 2 || 1 / 2´ )
Interlock Protocol
• Este protocolo criado por Ron Rivest, Adi Shamir tem uma boa chance de frustar o Man-in-the-Middle Attack.
Interlock Protocol
• O importante ponto aqui é que metade de mensagens não tem nenhuma utilidade sem a outra metade, ela não pode ser descriptada. Bob não pode ler qualquer parte da mensagem de Alice até a etapa (6) de concatenação de duas metades.
Interlock Protocol
• Alice não pode ler qualquer parte da mensagem de Bob até a etapa (7), ou seja, até que Alice junte as duas metades e descriptografe com sua chave privada.
Interlock Protocol
• Este causa um problema para Mallory.
• Quando ele intercepta metade da mensagem de Alice em (3), ele não pode decriptá-la com sua chave privada e re-encriptá-la com a chave pública de Bob.
• Quando ele intercepta metade da mensagem de Bob em (4), ele tem o mesmo problema.
Protocolos Básicos
Troca de chaves e Transmissão de Mensagens
B → A : KUB (ou A obtém KUB de
uma base de dados de chaves)
A : Gera KS
A : EKS ( M )
A → B : EKS ( M ) || EKUB (KS )
B : DKRB ( KS )
B : DKS ( M )
Protocolos Básicos
Troca de chaves de sessão e Mensagens Compartilhadas
A : Gera KS
A : EKS ( M )
A → B,C,D : EKS (M) || EKUB (KS) || EKUC (KS) || EKUD (KS)
B : DKRB ( KS ) B : DKS ( M )
C : DKRC ( KS ) C : DKS ( M )
D : DKRD ( KS ) D : DKS ( M )
Protocolos Básicos
Particionamento de Segredos
T : Gera R (random bit string do tamanho de M)
T : S = M R
T → A : R
T → B : S
Para reconstruir a mensagem M:
A ^ B : M = R S Problema: perda de R ou S
Protocolos Básicos
Particionamento de Segredos entre N Pessoas
T : Gera R, S, T (random bit string tamanho de M)
T : U = M R S T
T → A : R
T → B : S
T → C : T
T → D : U
A ^ B ^ C ^ D : M = R S T U
Protocolos Básicos
Compartilhamento de Segredos
• Com simples uso de criptotografia assimétrica
T : Gera KS
T : EKS ( M )
T : M1 = EKUA ( EKUB (KS) )
: M2 = EKUA ( EKUC (KS) )
: . . . .
: Mn = EKUn-1 ( EKUn (KS) )
T → A,B,C,D : EKS (M) || M1 || M2 || . . . || Mn
Compartilhamento de Segredos
A,B,C,D : EKS (M) || M1 || M2 || . . . || Mn
de modo que quaisquer três deles podem por seus pedaços juntos e reconstruir a mensagem M (segredo)
Se C está de férias, A, B e D podem reconstruir M.
Se B estiver de férias, A, C e D podem obter M.
Mas, se B e C estiverem de férias, A e D não podem reconstruir M.
Protocolos Básicos
Esquemas de autenticação
São métodos através dos quais alguém pode provar sua identidade, sem revelar conhecimentos importantes e que possam ser usados de forma maliciosa no futuro.
Protocolos Básicos
Autenticação usando Hash
A → S : senha Alice envia sua senha para um servidor S.
S : Hash (senha) S calcula o Hash da senha recebida.
S : Compara com valor Hash da senha, previamente armazenado.
A lista de hash de senhas é sem utilidade, porque uma função Hash
não pode ter inversa para recuperar senhas.
Ataque do Dicionário e Salt
• Um arquivo de senhas cifrado com uma função Hash é ainda vulnerável.
• Em seu tempo livre, Mallory gera 1000.000 de senhas mais comuns. Ele opera sobre todas 1000.000 destas com uma função Hash e armazena os hashes resultantes.
• Se cada senha tem 8 bytes, o arquivo resultante será não mais do que 8 Megabytes.
Ataque do Dicionário e Salt
• Mas, se Mallory furta, em um host, um arquivo de senhas criptografadas (por Hash), ele compara esse arquivo com seu arquivo de senhas possíveis criptografadas, e vê o que corresponde.
• Este é o ataque do dicionário que pode ser realizado.
• Um salt é uma string aleatória, que dificulta este ataque.
• Salts são concatenados com senhas, antes de serem operados com uma função Hash.
Ataque do Dicionário e Salt
• Então, ambos, o valor salt e o resultado da função Hash são armazenados numa base de dados no host.
• Se o número de valores salt é bastante grande, isto praticamente elimina o ataque do dicionário contra senhas usadas comumente, porque Mallory tem de gerar um hash para cada valor salt possivel.
Problemas de segurança
• Mesmo com salt, o protocolo de autenticação usando hash tem problema de segurança: quando Alice envia sua senha à S, qualquer um que tenha acesso ao caminho dos dados de Alice, poderá ler sua senha.
• A senha não pode ser lida antes de S calcular o hash dessa.
• Criptografia de chave pública pode resolver este problema.
Protocolos Básicos
Autenticação com chave compartilhada “K” entre A e B
A → B : NA
B → A : NB || V = EK ( NA || NB || IDB )
A : DK ( V ) == NA || NB || IDB
A → B : Q = EK ( NB || IDA )
B : DK ( Q ) == NB || IDA
Autenticação com chave compartilhada “K” entre A e B
• Criptografia simétrica provê alguma autenticação. Quando Bob recebe uma mensagem de Alice, criptografada com a chave compartilhada, Bob sabe que a mensagem veio de Alice.
• É assumido que ninguém mais conhece tal chave. Contudo, Bob não tem nenhum modo de convencer uma terceira parte (Trent). Bob não pode mostrar a mensagem a Trent e convencê-lo de que veio de Alice.
• Trent pode estar convencido de que a mensagem veio de Alice ou de Bob, e não tem nenhum modo para saber que veio de qual deles.
Autenticação com criptografa de chave pública
(1) S A : N N é uma string aleatória
(2) A S : EKRA(N) || IDA
(3) S procura a chave pública de Alice, KUA , correspondente à chave privada KRA , em sua base de dados de chaves públicas.
(4) S decripta com essa chave pública DKUA(N) obtendo N.
(5) Se N corresponde ao que S enviou à A (Alice) em (1), S permitirá que Alice acesse ao sistema. A : N == DKUA ( EKRA ( N ) ) ?
Se ninguém mais tem acesso à chave privada de Alice, ninguém poderá se passar por Alice.
Protocolos Básicos
Autenticação e Troca de Chave
Estes protocolos combinam autenticação e troca de chave para resolver um problema geral: Alice e Bob
estão nas extremidades opostas de uma rede e desejam se comunicar com segurança. Como pode
Alice e Bob trocarem uma chave secreta e ter certeza que ele e ela estão falando entre eles, e não com o
atacante Mallory ? A maioria dos protocolos assumem que Trent compartilha uma diferente chave secreta com cada participante, e que todas essas chaves estão em algum lugar antes do protocolo iniciar.
Protocolos Básicos
Autenticação arbitrada “T” : Wide-Mouth-Frog Protocol
A → T : IDA || EKA ( TA || KS || IDB )
T → B : EKB ( TB || KS || IDA )
T é um servidor confiável.
KA e KB são chaves compartilhadas com T que só servem para distribuição e não para encriptar mensagens.
TA e TB são rótulos de tempo
Protocolos BásicosYahalom
A → B : IDA || NA
B → T : IDB || EKB ( IDA,NA,NB )
T → A : EKA ( IDB,KS,NA,NB) || EKB ( IDA,KS )
A → B : EKB ( IDA,KS ) || EKS ( NB )
B : DKB ( EKB ( IDA,KS ) )
DKS ( EKS (NB) )
A e B ficam convencidos que estão falando entre eles e não com
uma terceira parte, o atacante Mallory.
Protocolos Básicos
Needham-Schroeder
A → T : IDA || IDB || NA
T → A : [ EKA ( NA || IDB || KS ) || EKB ( KS || IDA ) ] (2)
A → B : EKB ( KS,IDA )
B → A : EKS ( NB )
A → B : EKS ( NB -1 ) (5)
Needham-Schroeder Protocol
• Tudo em torno de NA , NB , NB-1 é evitar ataques de repetição.
• Nestes ataques, Mallory pode registrar mensagens já transmitidas e então usá-las mais tarde em uma tentativa de subverter o protocolo.
Needham-Schroeder Protocol
• A presença de NA em (2) assegura a Alice que a mensagem de Trent é legítima e não uma repetição de uma resposta de uma execução prévia do protocolo.
• Quando Alice decifra NB e envia (NB – 1) em (5), Bob é garantido que as mensagens de Alice não são repetições de execuções prévias do protocolo.
Protocolos Básicos
Kerberos
A → T : IDA, IDB
T → A : EKA ( t || L || KS || IDB ) || EKB ( t || L || KS || IDA )
A → B : EKS ( IDA, t ) || EKB ( t || L || KS || IDA )
B → A : EKS ( t+1 )
Kerberos
• Variante de Needham-Schroeder. Alice e Bob compartilham chaves com Trent (KDC)
• Alice deseja gerar uma chave de sessão para conversação com Bob.
• O protocolo funciona, mas assume que todos os clocks estão sincronizados com o clock de Trent (KDC).
• Na prática, o efeito é obtido por sincronizar cloks dentro de poucos minutos de um servidor de tempo seguro e detectar repetições dentro de um intervalo de tempo.