Troca de chave

Na ciência da computação , e mais particularmente na criptologia , um protocolo de troca de chave (ou negociação de chave , ou estabelecimento de chave , ou distribuição de chave ) é um mecanismo pelo qual vários participantes concordam com uma chave criptográfica . A invenção da criptografia de chave pública na década de 1970 produziu o primeiro protocolo de troca de chave que pode ser demonstrado ser seguro, embora as comunicações sejam feitas por um canal desprotegido, sem o uso de um terceiro confiável . Um dos primeiros protocolos desse tipo, devido a Whitfield Diffie e Martin Hellman , é hoje o mais utilizado na Internet , por meio do protocolo TLS . Por esta invenção, Diffie e Hellman receberam o prestigioso Prêmio Turing em 2016.

História

Antes de 1970

Antes da descoberta da criptografia de chave pública, nenhum método matemático era conhecido para realizar a troca de chaves, que dependia inteiramente da segurança operacional: a chave precisava ser comunicada por meio de um canal já seguro. Para o telefone vermelho , que usava criptografia de máscara descartável , isso envolvia o transporte físico de malas diplomáticas contendo as chaves (na forma de cartões perfurados ) dos Estados Unidos para a Rússia e vice-versa.

Mas o caso mais conhecido é certamente o da máquina Enigma , usada durante a Segunda Guerra Mundial pelas forças do Eixo para criptografar comunicações de rádio. As chaves de criptografia, que para o Enigma correspondem aos parâmetros de conexão e escolha dos rotores, eram alteradas diariamente pelo exército alemão. Ainda antes da guerra, em 1932, o espião francês Hans-Thilo Schmidt conseguiu obter as chaves dos meses de setembro e outubro do mesmo ano. É em particular com esta informação que a equipa polaca de Marian Rejewski conseguiu desenvolver um método de desencriptação, automatizado a partir de 1938. Mudando a chave apenas uma vez por dia, todas as mensagens interceptadas no mesmo dia eram interrompidas simultaneamente. É refinando o trabalho de Rejewski e contando com outros erros operacionais das forças alemãs que Alan Turing conseguirá organizar a descriptografia das comunicações da Enigma.

Quebra-cabeça Merkle

O primeiro mecanismo de troca de chaves é de Ralph Merkle , que o descreveu em 1974 e publicou em 1976. A ideia é fazer uma lista pública de problemas, os "quebra-cabeças", que requerem algum esforço para serem resolvidos e que revelam dois segredos uma vez resolvidos. Para estabelecer uma chave, escolhemos aleatoriamente um desses quebra-cabeças que resolvemos. O primeiro segredo é passado para o dono do quebra-cabeça e informa qual quebra-cabeça foi resolvido, e o segundo segredo serve como uma chave criptográfica.

Um oponente que está ouvindo a conversa não sabe, a priori, qual quebra-cabeça foi selecionado. Para encontrar a chave escolhida pelos dois participantes, o oponente deve, na pior das hipóteses, resolver todos os quebra-cabeças propostos. Portanto, ele enfrenta um problema de complexidade quadrática.

No modelo de oráculo aleatório , podemos mostrar que a segurança desse protocolo é efetivamente quadrática no número de quebra-cabeças. Essa complexidade não é considerada suficiente na criptografia moderna, mas um resultado de Boaz Barak e Mohammad Mahmoody-Ghidary mostra que não é possível fazer melhor neste modelo.

Em 1976, apoiando-se na construção de Merkle, Whitfield Diffie e Martin Hellman propõem usar o problema do logaritmo discreto em um corpo finito , um problema computacional considerado difícil, como base para a construção de um protocolo de troca de chaves.

O princípio de operação é o seguinte: para estabelecer uma chave, Alice e Bob escolhem secretamente um inteiro e, respectivamente. Alice calcula e Bob calcula , onde é um gerador de um subgrupo bastante grande e pré-negociado. Alice manda para Bob e Bob manda para Alice. Finalmente, Alice calcula e Bob calcula ; essas duas quantidades são de fato iguais, como pode ser visto em um cálculo rápido. $x_ {A}$ $x_ {B}$ ${\ displaystyle y_ {A} = g ^ {x_ {A}}}$ ${\ displaystyle y_ {B} = g ^ {x_ {B}}}$ $g$ $y_ {A}$ $y_ {B}$ ${\ displaystyle y_ {B} ^ {x_ {A}}}$ ${\ displaystyle y_ {A} ^ {x_ {B}}}$

Um oponente ouvindo a conversa enfrenta o seguinte problema: dado , calcular . Este problema é denominado problema computacional Diffie-Hellman . Em 2018, o método mais conhecido para atacá-lo é calcular logaritmos discretos. ${\ displaystyle g, g ^ {x_ {A}}, g ^ {x_ {B}}}$ ${\ displaystyle g ^ {x_ {A} x_ {B}}}$

Resolver o logaritmo discreto em um grupo genérico de primeira ordem requer esforço , ou seja, o adversário enfrenta um problema exponencialmente mais difícil do que os usuários do protocolo. Nos subgrupos multiplicativos de campo finito inicialmente usados por Diffie e Hellman, existem algoritmos mais eficientes, notavelmente variantes da peneira de campo numérico generalizado . Em 1984, Neal Koblitz e Victor S. Miller propõem usar o grupo de pontos racionais de uma curva elíptica . Para curvas bem escolhidas, nenhum ataque clássico é mais eficaz do que os ataques genéricos. $p$ ${\ displaystyle O ({\ sqrt {p}})}$

Na prática, não é o resultado direto do protocolo Diffie-Hellman que é usado como uma chave: é antes usado como uma fonte de entropia , fornecida a uma função de derivação chave .

Troca de chave autenticada

O protocolo Diffie-Hellman, conforme descrito acima, só garante a segurança contra um adversário passivo, capaz de escutar a conversa, mas não interferir nela. Se o oponente é capaz de interceptar comunicações, então é possível montar um ataque man-in-the-middle . Para isso, o oponente só precisa fingir ser Alice com Bob e Bob com Alice. Ele estabelecerá uma chave com cada um, podendo assim decifrar as mensagens enviadas por Alice (e, se desejar, transmiti-las a Bob, potencialmente após tê-las modificado).

Para se proteger contra tal cenário, um protocolo de troca deve ser autenticado. Para isso, podemos utilizar um esquema de assinatura , e garantir que cada mensagem enviada seja assinada por seu autor e verificada por seu destinatário. Por motivos de desempenho, apenas uma assinatura cobrindo toda a conversa pode ser produzida: esta é a abordagem adotada pelo TLS . No entanto, essa simplificação enfraquece a troca de chaves na prática, já que um invasor tem até o final da conversa para forjar uma assinatura: é um dos componentes do ataque Logjam .

Para poder verificar a validade de uma assinatura digital, o destinatário deve estar ciente da chave de verificação correspondente. É uma chave pública de longo prazo, que pode ser certificada para garantir sua procedência. Uma troca de chave autenticada, portanto, depende da disponibilidade de uma infraestrutura de chave pública . A segurança da assinatura digital usada pode ser baseada em outras suposições além do problema Diffie-Hellman, como a dificuldade de fatorar números inteiros grandes para RSA .

A quantidade (ou ) usada pode, portanto, ser calculada em cada sessão com um novo (resp. ). O uso de uma chave de sessão "efêmera" oferece a seguinte garantia: se uma chave de sessão é descoberta pelo adversário, este não tem informações sobre sessões passadas ou futuras. Diz-se que tal mecanismo garante perfeitamente a confidencialidade persistente . $y_ {A}$ $y_ {B}$ $x_ {A}$ $x_ {B}$

Por outro lado, a chave de longo prazo utilizada para assinar as mensagens, se for descoberta pelo adversário, permite-lhe usurpar a identidade de um dos participantes. Para certos esquemas de assinatura, em particular as assinaturas de Schnorr e suas variantes DSA , ECDSA , EdDSA , os pontos fracos do gerador de números aleatórios podem revelar a chave secreta. Em 2004, o algoritmo Dual_EC_DRBG foi padronizado pelo NIST , como um gerador de números pseudo-aleatórios destinado ao uso em particular para assinaturas digitais. Em 2013, as revelações de Edward Snowden confirmaram que esta era uma tentativa de enfraquecer a criptografia (como parte do programa Bullrun da NSA ), permitindo aos seus autores prever a geração de números aleatórios através de uma porta dos fundos . Dual_EC_DRBG foi removido em 2014 da lista oficial do NIST.

Encapsulamento e troca de chave autenticada por senha

Em vez de um protocolo em que ambas as partes obtêm uma chave, é possível que uma das partes decida sobre uma chave, que é passada para a outra. Para que essa transmissão seja segura, a chave enviada é criptografada: isso é chamado de encapsulamento de chave .

Um mecanismo de encapsulamento de chave pode usar qualquer criptografia de chave pública, por exemplo RSA : Alice publica sua chave pública, Bob escolhe dados aleatórios que ele criptografa com a chave de Alice. Esses dados serão usados para derivar uma chave por ambas as partes.

Um caso extremo de encapsulamento consiste no uso de criptografia simétrica para enviar uma chave, o que requer que as duas partes tenham se coordenado previamente em um segredo. Este segredo pode ser por exemplo uma senha : fala-se em troca de chave autenticada por senha (PAKE), cujas primeiras versões foram propostas em 1992, as quais foram rapidamente quebradas. As primeiras construções com prova de segurança foram obtidas em 2000, no modelo do oráculo aleatório . A primeira evidência no Modelo Padrão data de 2001.

Troca de chave multi-partidária

Em 2002, Antoine Joux mostra como usar os acoplamentos Weil em curvas elípticas para realizar, em um turno, uma troca de chave de três vias. O protocolo Diffie-Hellman, se usado, exigiria o estabelecimento de um canal de segurança entre cada par.

Em 2003, Dan Boneh e Alice Silverberg propuseram generalizar esta construção, a fim de trocar uma chave entre um número arbitrário de participantes, por meio de uma aplicação criptográfica multilinear. Este é um algoritmo efetivamente computável que satisfaz em particular que, para todos os inteiros e todos , temos , que verifica uma extensão das propriedades de segurança dos acoplamentos. Não foi até 2013 para ver os primeiros candidatos aparecerem, que desde então foram quebrados. ${\ displaystyle e: G_ {1} \ times \ cdots \ times G_ {n} \ rightarrow G_ {T}}$ ${\ displaystyle a_ {1}, \ dotsc, a_ {n}}$ ${\ displaystyle g_ {i} \ in G_ {i}}$ ${\ displaystyle e (g_ {1} ^ {a_ {1}}, \ ldots, g_ {n} ^ {a_ {n}}) = e (g_ {1}, \ ldots, g_ {n}) ^ { \ prod _ {i = 1} ^ {n} a_ {i}}}$

A construção de um protocolo de troca de chaves multipartidário eficiente e o projeto de uma aplicação criptográfica multilinear ainda são questões de pesquisa em aberto em 2018.

O problema do logaritmo discreto, no qual o protocolo Diffie-Hellman é baseado, pode ser resolvido de forma eficiente em um computador quântico usando o algoritmo de Shor . Além disso, a assinatura usada para autenticar uma sessão também está em risco.

Vários protocolos de substituição foram, portanto, propostos, os quais não sofrem de tais deficiências. Dentre as propostas, destacamos o algoritmo Jao-De Feo, baseado em isogenias de curvas elípticas supersingulares, e o algoritmo New Hope, baseado em problemas de vetores curtos em redes euclidianas. New Hope foi implementado e usado experimentalmente no navegador Google Chrome em 2016.

Não relacionado à seção anterior, foi proposto usar, em vez de garantias matemáticas e computacionais, as propriedades da física para garantir a segurança da troca de chaves. Mais especificamente, a observação das propriedades estatísticas de um fluxo de partículas emaranhadas , associadas ao teorema da não clonagem, permite detectar um adversário que está ouvindo e "jogar" uma parte dos bits assim revelados, corrigindo o ruído (que corrige também erros inerentes às medições). Esta etapa de reconciliação resulta em uma sequência de bits comum às duas partes que desejam trocar uma chave. Uma etapa de amplificação adicional é necessária para ser capaz de derivar uma chave da sequência comum.

Vários desses protocolos foram implementados e validados experimentalmente, em distâncias que cobrem várias centenas de quilômetros.

No entanto, a troca de chaves quânticas apresenta uma série de desafios tecnológicos e operacionais, que atualmente limitam sua implantação: em particular, um canal de comunicação específico deve ser estabelecido entre os participantes. Por exemplo, para os protocolos BB84 , B92 ou SARG04 , é necessário ser capaz de garantir o transporte de fótons de baixa energia enquanto conserva sua polarização, apesar dos fenômenos de decoerência em todo o comprimento do canal.

Notas e referências

Notas

Como se trata de uma única chave, falamos de troca de chave, no singular, e não de troca de chave.

Referências

(em) " Pioneiros da criptografia recebem prêmio ACM AM Turing " em www.acm.org (acessado em 20 de setembro de 2018 )
Consulte http://www.merkle.com/1974/ e http://www.merkle.com/1974/Puzzles1975.12.07.pdf .
(em) RC Merkle, "Secure Communications over Insecure Channels", Communications of the ACM 21 (4), p. 294--299 (abril de 1978).
(in) Boaz Barak e Mohammad Mahmoody-Ghidary , Merkle Puzzles Are Optimal - Um O (n ²) -Query Attack on Any Key Exchange from a Random Oracle, Advances in Cryptology - CRYPTO 2009 , Springer, Berlin, Heidelberg, al. "Notas de aula em ciência da computação",2009( ISBN 9783642033551 e 9783642033568 , DOI 10.1007 / 978-3-642-03356-8_22 , leitura online ) , p. 374-390
(em) Steven M. Bellovin e Michael Merritt , " Encrypted Key Exchange: password-based protocol secure contre dictionary attack " , Proceedings 1992 IEEE Computer Society Symposium on Research in Security and Privacy ,Maio de 1992, p. 72–84 ( DOI 10.1109 / risp.1992.213269 , ler online , acessado em 17 de março de 2018 )
(in) Steven M. Bellovin e Michael Merritt , " Troca de chave criptografada aumentada: um protocolo seguro baseado em senha contra ataques de dicionário e arquivo de senha comprometidos " , Proceedings of the 1st ACM Conference on Computer and Communications Security (CCS '93) , ACM,1 r dezembro 1993, p. 244–250 ( ISBN 0897916298 , DOI 10.1145 / 168588.168618 , lido online , acessado em 17 de março de 2018 )
(in) Mihir Bellare David Pointcheval e Phillip Rogaway , " Authenticated Key Exchange Secure contre Dictionary Attacks " , Advances in Cryptology - EUROCRYPT 2000 , Springer, Berlin, Heidelberg, ler Notes in Computer Science,14 de maio de 2000, p. 139–155 ( ISBN 3540455396 , DOI 10.1007 / 3-540-45539-6_11 , lido online , acessado em 17 de março de 2018 )
(in) Victor Boyko , Philip MacKenzie e Sarvar Patel , " Provably Secure Password-Authenticated Key Exchange Using Diffie-Hellman " , Advances in Cryptology - EUROCRYPT 2000 , Springer, Berlin, Heidelberg, leia Notes in Computer Science,14 de maio de 2000, p. 156–171 ( ISBN 3540455396 , DOI 10.1007 / 3-540-45539-6_12 , lido online , acessado em 17 de março de 2018 )
(em) Oded Goldreich e Yehuda Lindell , " Session-Key Generation Using Only Human Passwords " , Journal of Cryptology , vol. 19, n o 3,1 ° de julho de 2006, p. 241-340 ( ISSN 0933-2790 e 1432-1378 , DOI 10.1007 / s00145-006-0233-z , ler online , acessado em 17 de março de 2018 )
(in) Jonathan Katz , Rafail Ostrovsky e Moti Yung , " Efficient Password-Authenticated Key Exchange Using Human-Memorable Passwords " , Advances in Cryptology - EUROCRYPT 2001 , Springer, Berlin, Heidelberg, leia Notes in Computer Science,6 de maio de 2001, p. 475-494 ( ISBN 3540449876 , DOI 10.1007 / 3-540-44987-6_29 , lido online , acessado em 17 de março de 2018 )
(em) Antoine Joux , " The Weil and Tate Pairings as Building Blocks for Public Key Cryptosystems " , Algorithmic Number Theory , Springer, Berlin, Heidelberg, leia Notes in Computer Science,7 de julho de 2002, p. 20–32 ( ISBN 3540454551 , DOI 10.1007 / 3-540-45455-1_3 , lido online , acessado em 17 de março de 2018 )
(em) Dan Boneh e Alice Silverberg, "Applications of Multilinear Forms to Cryptography" Contemporary Mathematics Vol. 324, American Mathematical Society, pp. 71-90, 2003
(em) Sanjam Garg , Craig Gentry e Shai Halevi , " Candidate Multilinear Maps from Ideal Lattices " , Advances in Cryptology - EUROCRYPT 2013 , Springer, Berlin, Heidelberg, leia Notes in Computer Science,26 de maio de 2013, p. 1-17 ( ISBN 9783642383472 , DOI 10.1007 / 978-3-642-38348-9_1 , lido online , acessado em 17 de março de 2018 )
(en) Jean-Sébastien Coron , Tancred Lepoint e Mehdi Tibouchi , Advances in Cryptology - CRYPTO 2013 , Springer, Berlin, Heidelberg, al. "Notas de aula em ciência da computação",2013( ISBN 9783642400407 e 9783642400414 , DOI 10.1007 / 978-3-642-40041-4_26 , leitura online ) , p. 476-493
(en) Jung Hee Cheon , Kyoohyung Han , Changmin Lee e Hansol Ryu , " Cryptanalysis of the over-the Multilinear Map Integers " , Advances in Cryptology - EUROCRYPT 2015 , Springer, Berlin, Heidelberg, leia Notes in Computer Science,26 de abril de 2015, p. 3-12 ( ISBN 9783662467992 , DOI 10.1007 / 978-3-662-46800-5_1 , lido online , acessado em 17 de março de 2018 )
(en) Jung Hee Cheon , Pierre-Alain Fouque , Changmin Lee e Brice Minaud , " Cryptanalysis of the New CLT Multilinear Map over the Integers " , Advances in Cryptology - EUROCRYPT 2016 , Springer, Berlin, Heidelberg, leia Notes in Computer Science ,8 de maio de 2016, p. 509-536 ( ISBN 9783662498897 , DOI 10.1007 / 978-3-662-49890-3_20 , lido online , acessado em 17 de março de 2018 )
(em) Eric Miles , Amit Sahai e Mark Zhandry , " Annihilation Attacks for Multilinear Maps: Cryptanalysis of indistinguishability Ofuscation over GGH13 " , Advances in Cryptology - CRYPTO 2016 , Springer, Berlin, Heidelberg, read Notes in Computer Science,14 de agosto de 2016, p. 629-658 ( ISBN 9783662530078 , DOI 10.1007 / 978-3-662-53008-5_22 , lido online , acessado em 17 de março de 2018 )
(en) Jean-Sébastien Coron , Moon Sung Lee , Tancred Lepoint e Mehdi Tibouchi , " Cryptanalysis of GGH15 Multilinear Maps " , Advances in Cryptology - CRYPTO 2016 , Springer, Berlin, Heidelberg, leia Notes in Computer Science,14 de agosto de 2016, p. 607-628 ( ISBN 9783662530078 , DOI 10.1007 / 978-3-662-53008-5_21 , lido online , acessado em 17 de março de 2018 )
(em) David Jao e Luca De Feo , " Towards Quantum-Resistant Cryptosystems from Supersingular isogenies Elliptic Curve " , Post-Quantum Cryptography , Springer, Berlin, Heidelberg, ler Notes in Computer Science,29 de novembro de 2011, p. 19–34 ( ISBN 9783642254048 , DOI 10.1007 / 978-3-642-25405-5_2 , lido online , acessado em 17 de março de 2018 )
(em) Erdem Alkim Leo Ducas, Pöppelmann Thomas e Peter Schwabe, "Post-Quantum Key Exchange - A New Hope," USENIX Security Symposium , 2016, p. 327-343
(em) Matt Braithwaite, " Experimenting with Post-Quantum Cryptography " on security.googleblog.com ,7 de julho de 2016
(em) Boris Korzh , Charles Ci Wen Lim , Raphael Houlmann e Nicolas Gisin , " distribuição de chave quântica comprovadamente segura e prática com mais de 307 km de fibra óptica " , Nature Photonics , Vol. 9, n o 3,março de 2015, p. 163-168 ( ISSN 1749-4893 , DOI 10.1038 / nphoton.2014.327 , ler online , acessado em 17 de março de 2018 )
(em) Charles H. Bennett , " Quantum cryptography using any two nonorthogonal states " , Physical Review Letters , vol. 68, n o 21,25 de maio de 1992, p. 3121-3124 ( DOI 10.1103 / PhysRevLett.68.3121 , ler online , acessado em 17 de março de 2018 )
(em) Valerio Scarani , Antonio Acín Grégoire Ribordy e Nicolas Gisin , " Quantum Cryptography Protocolos Robust contre Photon Número ataques de divisão para implementações de pulso de laser fracos " , Physical Review Letters , vol. 92, n o 5,6 de fevereiro de 2004, p. 057901 ( DOI 10.1103 / PhysRevLett.92.057901 , ler online , acessado em 17 de março de 2018 )