Troca de chaves Diffie-Hellman - Diffie–Hellman key exchange

No esquema de troca de chaves Diffie – Hellman, cada parte gera um par de chaves pública / privada e distribui a chave pública. Depois de obter uma cópia autêntica das chaves públicas um do outro, Alice e Bob podem calcular um segredo compartilhado offline. O segredo compartilhado pode ser usado, por exemplo, como a chave para uma cifra simétrica .

A troca de chaves Diffie – Hellman é um método de troca segura de chaves criptográficas em um canal público e foi um dos primeiros protocolos de chave pública concebidos por Ralph Merkle e nomeados em homenagem a Whitfield Diffie e Martin Hellman . DH é um dos primeiros exemplos práticos de troca de chave pública implementada no campo da criptografia . Publicado em 1976 por Diffie e Hellman, este é o primeiro trabalho conhecido publicamente que propôs a ideia de uma chave privada e uma chave pública correspondente.

Tradicionalmente, a comunicação criptografada segura entre duas partes exigia que primeiro trocassem as chaves por algum meio físico seguro, como listas de chaves em papel transportadas por um correio confiável . O método de troca de chaves Diffie – Hellman permite que duas partes que não têm conhecimento prévio uma da outra estabeleçam em conjunto uma chave secreta compartilhada em um canal inseguro . Essa chave pode então ser usada para criptografar comunicações subsequentes usando uma cifra de chave simétrica .

Diffie – Hellman é usado para proteger uma variedade de serviços de Internet . No entanto, uma pesquisa publicada em outubro de 2015 sugere que os parâmetros em uso para muitos aplicativos DH Internet naquele momento não são fortes o suficiente para impedir o comprometimento por invasores bem financiados, como os serviços de segurança de alguns países.

O esquema foi publicado por Whitfield Diffie e Martin Hellman em 1976, mas em 1997 foi revelado que James H. Ellis , Clifford Cocks e Malcolm J. Williamson do GCHQ , a agência britânica de inteligência de sinais, haviam mostrado anteriormente em 1969 como criptografia de chave pode ser alcançada.

Apesar de acordo de chaves Diffie-Hellman em si é um não-autenticada protocolo-chave acordo , ele fornece a base para uma variedade de protocolos autenticados, e é usado para fornecer frente sigilo em Transport Layer Security 's efêmeras modos (referidos como EDH ou DHE dependendo do pacote de criptografia ).

O método foi seguido logo depois pelo RSA , uma implementação de criptografia de chave pública usando algoritmos assimétricos.

A patente US 4.200.770 expirada de 1977 descreve o agora algoritmo de domínio público . Ele credita Hellman, Diffie e Merkle como inventores.

Nome

Em 2002, Hellman sugeriu que o algoritmo fosse chamado de troca de chave Diffie – Hellman – Merkle em reconhecimento à contribuição de Ralph Merkle para a invenção da criptografia de chave pública (Hellman, 2002), escrevendo:

O sistema ... desde então se tornou conhecido como troca de chaves Diffie – Hellman. Embora esse sistema tenha sido descrito pela primeira vez em um artigo por Diffie e eu, é um sistema de distribuição de chave pública, um conceito desenvolvido por Merkle e, portanto, deve ser chamado de 'troca de chave Diffie-Hellman-Merkle' se nomes forem associados a ele . Espero que este pequeno púlpito possa ajudar nesse esforço de reconhecer a contribuição igual de Merkle para a invenção da criptografia de chave pública.

Descrição

Visao geral

Ilustração do conceito por trás da troca de chaves Diffie – Hellman

A troca de chaves Diffie – Hellman estabelece um segredo compartilhado entre duas partes que pode ser usado para comunicação secreta para troca de dados em uma rede pública. Uma analogia ilustra o conceito de troca de chave pública usando cores em vez de números muito grandes:

O processo começa com as duas partes, Alice e Bob , concordando publicamente sobre uma cor inicial arbitrária que não precisa ser mantida em segredo (mas deve ser diferente a cada vez). Neste exemplo, a cor é amarela. Cada pessoa também seleciona uma cor secreta que guarda para si - neste caso, vermelho e verde-azulado. A parte crucial do processo é que Alice e Bob misturem cada um sua própria cor secreta com sua cor mutuamente compartilhada, resultando em misturas de laranja-tan e azul-claro, respectivamente, e, em seguida, troquem publicamente as duas cores misturadas. Por fim, cada um mistura a cor que recebeu do parceiro com sua cor particular. O resultado é uma mistura de cores final (amarelo-marrom, neste caso) que é idêntica à mistura de cores final do parceiro.

Se um terceiro ouvisse a troca, ele saberia apenas a cor comum (amarelo) e as primeiras cores mistas (laranja-castanho e azul-claro), mas seria difícil para essa parte determinar a cor secreta final (amarelo -marrom). Trazendo a analogia de volta para uma troca da vida real usando grandes números em vez de cores, essa determinação é computacionalmente cara. É impossível calcular em uma quantidade prática de tempo, mesmo para supercomputadores modernos .

Explicação criptográfica

O mais simples e a implementação original do protocolo utiliza o grupo multiplicativo de números inteiros modulo p , onde p é primordial , e g é um primitivo módulo raiz p . Esses dois valores são escolhidos dessa maneira para garantir que o segredo compartilhado resultante possa assumir qualquer valor de 1 a p –1. Aqui está um exemplo do protocolo, com valores não secretos em azul e valores secretos em vermelho .

  1. Alice e Bob concordam publicamente em usar um módulo p = 23 e uma base g = 5 (que é uma raiz primitiva módulo 23).
  2. Alice escolhe um inteiro secreto a = 4 e envia a Bob A = g um mod p
    • A = 5 4 mod 23 = 4
  3. Bob escolhe um inteiro secreto b = 3 e, em seguida, envia Alice B = g b mod p
    • B = 5 3 mod 23 = 10
  4. Alice calcula s = B a mod p
    • s =10 4 mod23=18
  5. Bob calcula s = A b mod p
    • s =4 3 mod23=18
  6. Alice e Bob agora compartilham um segredo (o número 18).

Alice e Bob chegaram aos mesmos valores porque no mod p,

Mais especificamente,

Apenas um e b são mantidos em segredo. Todos os outros valores - p , g , g um mod p e g b mod p - são enviados em claro. A força do esquema vem do fato de que g ab mod p = g ba mod p leva tempos extremamente longos para computar por qualquer algoritmo conhecido apenas a partir do conhecimento de p , g , g a mod p e g b mod p . Depois que Alice e Bob calculam o segredo compartilhado, eles podem usá-lo como uma chave de criptografia, conhecida apenas por eles, para enviar mensagens pelo mesmo canal de comunicação aberto.

Claro, valores muito maiores de a , b e p seriam necessários para tornar este exemplo seguro, uma vez que existem apenas 23 resultados possíveis de n mod 23. No entanto, se p é um primo de pelo menos 600 dígitos, então mesmo o os computadores modernos mais rápidos que usam o algoritmo conhecido mais rápido não conseguem encontrar um dado apenas g , p e g a mod p . Esse problema é chamado de problema do logaritmo discreto . O cálculo de g a mod p é conhecido como exponenciação modular e pode ser feito de forma eficiente mesmo para números grandes. Observe que g não precisa ser grande e, na prática, geralmente é um número inteiro pequeno (como 2, 3, ...).

Gráfico de sigilo

O gráfico abaixo mostra quem sabe o quê, novamente com valores não secretos em azul e valores secretos em vermelho . Aqui, Eva é uma bisbilhoteira - ela observa o que é enviado entre Alice e Bob, mas não altera o conteúdo de suas comunicações.

  • g = base pública (principal), conhecida por Alice, Bob e Eva. g = 5
  • p = módulo público (primo), conhecido por Alice, Bob e Eva. p = 23
  • a = chave privada de Alice, conhecida apenas por Alice. a = 6
  • b = chave privada de Bob conhecida apenas por Bob. b = 15
  • A = chave pública de Alice, conhecida por Alice, Bob e Eve. A = g a mod p = 8
  • B = chave pública de Bob, conhecida por Alice, Bob e Eve. B = g b mod p = 19
Alice
Conhecido Desconhecido
p = 23
g = 5
a = 6 b
A = 5 a mod 23
A = 5 6 mod 23 = 8
B = 19
s =B a mod23
s =19 6 mod23= 2
Prumo
Conhecido Desconhecido
p = 23
g = 5
b = 15 uma
B = 5 b mod 23
B = 5 15 mod 23 = 19
A = 8
s =A b mod23
s =8 15 mod23= 2
véspera
Conhecido Desconhecido
p = 23
g = 5
a , b
   
   
A = 8 , B = 19
   
s

Agora s é a chave secreta compartilhada e é conhecida por Alice e Bob, mas não por Eve. Observe que não é útil para Eva calcular AB , que é igual a g a + b mod p .

Observação: deve ser difícil para Alice resolver a chave privada de Bob ou para Bob resolver a chave privada de Alice. Se não for difícil para Alice resolver a chave privada de Bob (ou vice-versa), Eva pode simplesmente substituir seu próprio par de chave privada / pública, conectar a chave pública de Bob em sua chave privada, produzir uma chave secreta compartilhada falsa e resolver A chave privada de Bob (e use-a para resolver a chave secreta compartilhada. Eve pode tentar escolher um par de chaves pública / privada que tornará mais fácil para ela resolver a chave privada de Bob).

Outra demonstração de Diffie – Hellman (também usando números muito pequenos para uso prático) é fornecida aqui .

Generalização para grupos cíclicos finitos

Aqui está uma descrição mais geral do protocolo:

  1. Alice e Bob concordar com um finito grupo cíclico L de ordem n e um gerador elemento g em L . (Isso geralmente é feito muito antes do resto do protocolo; presume-se que g seja conhecido por todos os invasores.) O grupo G é escrito multiplicativamente.
  2. Alice escolhe um número natural aleatório a , onde 1 < a < n , e envia g a mod n para Bob.
  3. Bob escolhe um número natural aleatório b , que também é 1 < b < n , e envia g b mod n para Alice.
  4. Alice calcula ( g b mod n ) a mod n .
  5. Bob calcula ( g a mod n ) b mod n .

Alice e Bob agora possuem o elemento de grupo g ab , que pode servir como a chave secreta compartilhada. O grupo G satisfaz a condição de requisito para comunicação segura se não houver um algoritmo eficiente para determinar g ab dados g , g a e g b .

Por exemplo, o protocolo de curva elíptica Diffie – Hellman é uma variante que usa curvas elípticas em vez do grupo multiplicativo de inteiros módulo n. Variantes usando curvas hiperelípticas também foram propostas. A troca de chave de isogenia supersingular é uma variante Diffie – Hellman que foi projetada para ser segura contra computadores quânticos .

Operação com mais de duas partes

O acordo de chave Diffie – Hellman não se limita a negociar uma chave compartilhada por apenas dois participantes. Qualquer número de usuários pode participar de um acordo executando iterações do protocolo do acordo e trocando dados intermediários (que não precisam ser mantidos em segredo). Por exemplo, Alice, Bob e Carol podem participar de um acordo Diffie-Hellman da seguinte forma, com todas as operações consideradas como módulo p :

  1. As partes concordam com os parâmetros p e g do algoritmo .
  2. As partes geram suas chaves privadas, denominadas a , b e c .
  3. Alice calcula g a e o envia para Bob.
  4. Bob calcula ( g a ) b = g ab e o envia para Carol.
  5. Carol calcula ( g ab ) c = g abc e usa-o como seu segredo.
  6. Bob calcula g b e o envia para Carol.
  7. Carol calcula ( g b ) c = g bc e o envia para Alice.
  8. Alice calcula ( g bc ) a = g bca = g abc e usa-o como seu segredo.
  9. Carol calcula g c e o envia para Alice.
  10. Alice calcula ( g c ) a = g ca e o envia para Bob.
  11. Bob calcula ( g ca ) b = g cab = g abc e usa-o como seu segredo.

Um bisbilhoteiro foi capaz de ver g a , g b , g c , g ab , g ac e g bc , mas não pode usar nenhuma combinação deles para reproduzir com eficiência g abc .

Para estender este mecanismo a grupos maiores, dois princípios básicos devem ser seguidos:

  • Começando com uma chave "vazia" consistindo apenas em g , o segredo é feito aumentando o valor atual para o expoente privado de cada participante uma vez, em qualquer ordem (a primeira dessas exponenciações produz a própria chave pública do participante).
  • Qualquer valor intermediário (tendo até N -1 expoentes aplicados, onde N é o número de participantes no grupo) pode ser revelado publicamente, mas o valor final (tendo todos os N expoentes aplicados) constitui o segredo compartilhado e, portanto, nunca deve ser revelado publicamente. Assim, cada usuário deve obter sua cópia do segredo aplicando sua própria chave privada por último (caso contrário, não haveria como o último contribuidor comunicar a chave final ao seu destinatário, já que o último contribuidor teria transformado a chave no próprio segredo que o grupo deseja proteger).

Esses princípios deixam em aberto várias opções para escolher em que ordem os participantes contribuem para as chaves. A solução mais simples e óbvia é organizar os N participantes em um círculo e fazer com que N chaves girem ao redor do círculo, até que, eventualmente, todas as chaves tenham sido contribuídas por todos os N participantes (terminando com seu proprietário) e cada participante tenha contribuído com N chaves (terminando com os seus próprios). No entanto, isso requer que cada participante execute N exponenciações modulares.

Ao escolher uma ordem mais ideal, e contando com o fato de que as chaves podem ser duplicadas, é possível reduzir o número de exponenciações modulares realizadas por cada participante para log 2 ( N ) + 1 usando uma abordagem do estilo dividir e conquistar , fornecido aqui para oito participantes:

  1. Cada participante A, B, C e D realiza uma exponenciação, produzindo g abcd ; esse valor é enviado para E, F, G e H. Em troca, os participantes A, B, C e D recebem g efgh .
  2. Os participantes A e B cada executar uma exponenciação, obtendo-se g efghab , que eles enviam para C e D, enquanto que C e D fazer o mesmo, obtendo-se g efghcd , que eles enviam para A e B.
  3. O participante A realiza uma exponenciação, produzindo g efghcda , que ele envia para B; da mesma forma, B envia g efghcdb para A. C e D fazem o mesmo.
  4. O participante A executa uma exponenciação final, produzindo o segredo g efghcdba = g abcdefgh , enquanto B faz o mesmo para obter g efghcdab = g abcdefgh ; novamente, C e D fazem de forma semelhante.
  5. Os participantes de E a H executam simultaneamente as mesmas operações usando o g abcd como ponto de partida.

Uma vez que esta operação tenha sido completada, todos os participantes possuirão o segredo g abcdefgh , mas cada participante terá realizado apenas quatro exponenciações modulares, ao invés das oito implícitas por um simples arranjo circular.

Segurança

O protocolo é considerado seguro contra bisbilhoteiros se G e g forem escolhidos corretamente. Em particular, a ordem do grupo G deve ser grande, principalmente se o mesmo grupo for usado para grandes quantidades de tráfego. O bisbilhoteiro precisa resolver o problema Diffie – Hellman para obter g ab . Atualmente, isso é considerado difícil para grupos cuja ordem é grande o suficiente. Um algoritmo eficiente para resolver o problema do logaritmo discreto tornaria mais fácil calcular a ou b e resolver o problema Diffie-Hellman, tornando este e muitos outros sistemas de criptografia de chave pública inseguros. Campos de pequenas características podem ser menos seguros.

A ordem de G deve ter um grande fator primo para evitar o uso do algoritmo Pohlig – Hellman para obter a ou b . Por essa razão, um primo de Sophie Germain q às vezes é usado para calcular p = 2 q + 1 , chamado de primo seguro , uma vez que a ordem de G só é divisível por 2 e q . g é então às vezes escolhido para gerar o subgrupo de ordem q de G , em vez de G , de modo que o símbolo de Legendre de g a nunca revele o bit de ordem inferior de a . Um protocolo que usa essa escolha é, por exemplo, IKEv2 .

g é frequentemente um número inteiro pequeno, como 2. Por causa da autorredutibilidade aleatória do problema do logaritmo discreto, um pequeno g é tão seguro quanto qualquer outro gerador do mesmo grupo.

Se Alice e Bob usam geradores de números aleatórios cujas saídas não são completamente aleatórias e podem ser previstas até certo ponto, então é muito mais fácil espionar.

Na descrição original, a troca Diffie-Hellman por si só não fornece autenticação das partes comunicantes e, portanto, é vulnerável a um ataque man-in-the-middle . Mallory (um atacante ativo executando o ataque man-in-the-middle) pode estabelecer duas trocas de chaves distintas, uma com Alice e a outra com Bob, efetivamente mascarando-se como Alice para Bob e vice-versa, permitindo que ela descriptografe e depois volte a -encrypt, as mensagens passadas entre eles. Observe que Mallory deve continuar no meio, descriptografando e criptografando ativamente as mensagens sempre que Alice e Bob se comunicam. Se ela estiver ausente, sua presença anterior será então revelada a Alice e Bob. Eles saberão que todas as suas conversas privadas foram interceptadas e decodificadas por alguém no canal. Na maioria dos casos, isso não os ajudará a obter a chave privada de Mallory, mesmo que ela tenha usado a mesma chave para ambas as trocas.

Geralmente, é necessário um método para autenticar as partes que se comunicam entre si para evitar esse tipo de ataque. Variantes de Diffie – Hellman, como o protocolo STS , podem ser usadas para evitar esses tipos de ataques.

Ataques práticos ao tráfego da Internet

O algoritmo de peneira de campo numérico , que geralmente é o mais eficaz para resolver o problema de logaritmo discreto , consiste em quatro etapas computacionais. As três primeiras etapas dependem apenas da ordem do grupo G, não do número específico cujo log finito é desejado. Acontece que grande parte do tráfego da Internet usa um de um punhado de grupos da ordem de 1024 bits ou menos. Ao pré - calcular as três primeiras etapas da peneira de campo numérico para os grupos mais comuns, um invasor precisa apenas realizar a última etapa, que é muito menos dispendiosa em termos computacionais do que as três primeiras etapas, para obter um logaritmo específico. O ataque Logjam usou essa vulnerabilidade para comprometer uma variedade de serviços de Internet que permitiam o uso de grupos cuja ordem era um número primo de 512 bits, denominado grau de exportação . Os autores precisaram de vários milhares de núcleos de CPU por uma semana para pré-calcular os dados para um único primo de 512 bits. Feito isso, os logaritmos individuais poderiam ser resolvidos em cerca de um minuto usando duas CPUs Intel Xeon de 18 núcleos.

Conforme estimado pelos autores por trás do ataque Logjam, a pré-computação muito mais difícil necessária para resolver o problema de log discreto para um prime de 1024 bits custaria na ordem de US $ 100 milhões, bem dentro do orçamento de uma grande agência de inteligência nacional como a US National Security Agency (NSA). Os autores do Logjam especulam que a pré-computação contra primos DH de 1024 bits amplamente reutilizados está por trás das alegações em documentos vazados da NSA de que a NSA é capaz de quebrar grande parte da criptografia atual.

Para evitar essas vulnerabilidades, os autores do Logjam recomendam o uso de criptografia de curva elíptica , para a qual nenhum ataque semelhante é conhecido. Caso contrário, eles recomendam que a ordem, p , do grupo Diffie – Hellman deve ser de pelo menos 2048 bits. Eles estimam que a pré-computação necessário para uma de 2048 bits principal é 10 9 vezes mais difícil do que para primos de 1024 bits.

Outros usos

Encriptação

Esquemas de criptografia de chave pública com base na troca de chaves Diffie – Hellman foram propostos. O primeiro desses esquemas é a criptografia ElGamal . Uma variante mais moderna é o Esquema de criptografia integrado .

Encaminhamento de sigilo

Os protocolos que alcançam o sigilo direto geram novos pares de chaves para cada sessão e os descartam no final da sessão. A troca de chaves Diffie – Hellman é uma escolha frequente para esses protocolos, devido à sua geração rápida de chaves.

Acordo de chave autenticado por senha

Quando Alice e Bob compartilham uma senha, eles podem usar uma forma de contrato de chave autenticada por senha (PK) de Diffie – Hellman para evitar ataques man-in-the-middle. Um esquema simples é comparar o hash de s concatenado com a senha calculada independentemente em ambas as extremidades do canal. Uma característica desses esquemas é que um invasor só pode testar uma senha específica em cada iteração com a outra parte e, portanto, o sistema oferece boa segurança com senhas relativamente fracas. Esta abordagem é descrita em ITU-T Recomendação X.1035 , que é usado pelo G.hn padrão de rede doméstica.

Um exemplo de tal protocolo é o protocolo Secure Remote Password .

Chave pública

Também é possível usar Diffie – Hellman como parte de uma infraestrutura de chave pública , permitindo que Bob criptografe uma mensagem para que apenas Alice seja capaz de descriptografá-la, sem comunicação anterior entre eles, exceto Bob por ter conhecimento confiável da chave pública de Alice . A chave pública de Alice é . Para enviar uma mensagem a ela, Bob escolhe um b aleatório e, em seguida, envia Alice (não criptografada) junto com a mensagem criptografada com chave simétrica . Apenas Alice pode determinar a chave simétrica e, portanto, descriptografar a mensagem, porque somente ela tem uma (a chave privada). Uma chave pública pré-compartilhada também evita ataques man-in-the-middle.

Na prática, Diffie – Hellman não é usado dessa maneira, com RSA sendo o algoritmo de chave pública dominante. Em grande parte, isso se deve a razões históricas e comerciais, principalmente porque a RSA Security criou uma autoridade de certificação para assinatura de chave que se tornou a Verisign . Diffie – Hellman, conforme elaborado acima, não pode ser usado diretamente para assinar certificados. No entanto, os algoritmos de assinatura ElGamal e DSA estão matematicamente relacionados a ele, bem como MQV , STS e o componente IKE do conjunto de protocolos IPsec para proteger as comunicações do protocolo da Internet .

Veja também

Notas

  1. ^ Sinônimos de troca de chave Diffie – Hellman incluem:
    • Troca de chaves Diffie-Hellman-Merkle
    • Acordo de chave Diffie-Hellman
    • Estabelecimento-chave de Diffie-Hellman
    • Negociação de chave Diffie-Hellman
    • Troca de chave exponencial
    • Protocolo Diffie-Hellman
    • Aperto de mão Diffie-Hellman

Referências

Referências gerais

links externos