Dual EC DRBG
Gerador pseudorrandômico controverso
Dual_EC_DRBG (sigla de Dual Elliptic Curve Deterministic Random Bit Generator) é um algoritmo proposto como gerador de números pseudoaleatórios criptograficamente seguro (CSPRNG), baseado em técnicas de criptografia de curva elíptica. Apesar de críticas públicas significativas — incluindo suspeitas de que a National Security Agency (NSA) tivesse introduzido uma porta dos fundos em sua padronização — o algoritmo figurou durante vários anos entre os geradores aprovados no NIST SP 800-90A, até ser retirado em 2014.
Fraqueza: uma potencial porta dos fundos
Problemas na solidez criptográfica do algoritmo já eram conhecidos e criticados publicamente antes de sua incorporação formal a padrões apoiados pelo ANSI, pela ISO e pelo National Institute of Standards and Technology (NIST). Entre as principais preocupações estava a possibilidade de o algoritmo conter uma porta dos fundos criptográfica explorável por quem conhecesse certos parâmetros secretos — hipótese frequentemente associada à National Security Agency.
Em 2013, reportagens do The New York Times sustentaram, com base em documentos vazados por Edward Snowden, que a NSA havia atuado no processo de padronização de modo a favorecer a adoção do Dual_EC_DRBG e que o algoritmo continha, de fato, uma porta dos fundos útil ao programa Bullrun. No mesmo período, uma reportagem da Reuters afirmou que, em 2004, a NSA teria pago 10 milhões de dólares à RSA Security para que o Dual_EC_DRBG fosse usado por padrão na biblioteca criptográfica RSA BSAFE. A RSA negou ter adotado conscientemente um algoritmo que soubesse ser defeituoso.
Antes mesmo de sua primeira publicação conhecida, já havia sido observado que o desenho do Dual_EC_DRBG permitia a existência de uma porta dos fundos kleptográfica. O aspecto incomum do projeto era que apenas quem tivesse participado de sua construção — ou conhecesse a relação secreta entre certos parâmetros — poderia verificar ou explorar plenamente essa fragilidade. Bruce Schneier observou, pouco depois da padronização, que essa porta dos fundos “bastante óbvia”, somada a outras deficiências, tornava improvável sua adoção ampla.
A exploração da fragilidade permitiria, em tese, a reconstrução do estado interno do gerador a partir de uma pequena quantidade de saída observada. Com isso, um atacante poderia prever saídas futuras do gerador e comprometer protocolos como SSL/TLS quando dependessem dele para gerar valores aleatórios críticos.
Membros do grupo de padronização do ANSI que primeiro analisou o Dual_EC_DRBG tinham conhecimento do mecanismo pelo qual a porta dos fundos poderia surgir e também sabiam como neutralizá-la, mas não tornaram esse risco amplamente público. A comunidade criptográfica em geral só passou a discutir o problema de forma aberta depois da apresentação de Dan Shumow e Niels Ferguson em 2007 e da divulgação de documentos e análises posteriores.
Em setembro de 2013, após novas revelações associadas aos documentos de Snowden, o NIST declarou que não enfraqueceria deliberadamente um padrão criptográfico. Mesmo assim, a confiança no algoritmo já estava seriamente abalada. Em abril de 2014, o NIST removeu o Dual_EC_DRBG de sua orientação preliminar sobre geradores aleatórios e recomendou que os usuários migrassem o mais rapidamente possível para um dos outros algoritmos aprovados.
Cronologia
| Data |
Evento |
|---|
| Maio de 1997 |
Adam L. Young e Moti Yung apresentam, na Eurocrypt 1997, o trabalho Kleptography: Using Cryptography Against Cryptography, mostrando como mecanismos criptográficos podem embutir canais secretos e portas dos fundos assimétricas. |
| Agosto de 1997 |
Young e Yung apresentam, na Crypto 1997, o artigo The Prevalence of Kleptographic Attacks on Discrete-Log Based Cryptosystems, generalizando ataques kleptográficos em sistemas baseados em logaritmo discreto. |
| Início dos anos 2000 |
A NSA impulsiona a inclusão do Dual_EC_DRBG no processo de padronização do ANSI X9.82. |
| 2004 |
Surge uma versão preliminar do padrão ANSI X9.82 Parte 3 contendo o Dual_EC_DRBG. No mesmo ano, a RSA Security passa a usar o algoritmo como CSPRNG padrão em produtos da linha BSAFE. |
| 21 de janeiro de 2005 |
É registrada uma patente por Daniel R. L. Brown e Scott Vanstone descrevendo o funcionamento de uma porta dos fundos em um gerador pseudoaleatório de curva elíptica e formas de mitigá-la. |
| Dezembro de 2005 |
O primeiro rascunho público do NIST SP 800-90 inclui o Dual_EC_DRBG. |
| 16 de março de 2006 |
Kristian Gjøsteen publica uma análise mostrando que parte do Dual_EC_DRBG não é criptograficamente sólida e que o algoritmo apresenta previsibilidade inaceitável para um CSPRNG. |
| 29 de maio de 2006 |
Berry Schoenmakers e Andrey Sidorenko publicam uma criptoanálise concluindo que a saída do Dual_EC_DRBG pode ser distinguida empiricamente de bits aleatórios. |
| Junho de 2006 |
O NIST publica o SP 800-90 incluindo o Dual_EC_DRBG, apesar das críticas já levantadas. |
| Agosto de 2007 |
Dan Shumow e Niels Ferguson apresentam informalmente um ataque mostrando que, com a porta dos fundos e pequena quantidade de saída, é possível recuperar completamente o estado interno do gerador. |
| Novembro de 2007 |
Bruce Schneier publica artigo no Wired chamando atenção para a possibilidade de a NSA ter inserido uma porta dos fundos no padrão. |
| Janeiro de 2012 |
É publicada a versão SP 800-90A, mantendo o Dual_EC_DRBG. |
| Setembro de 2013 |
Reportagens baseadas nos documentos de Edward Snowden associam o algoritmo ao programa Bullrun e reforçam a acusação de porta dos fundos. |
| 19 de setembro de 2013 |
A RSA Security recomenda que seus clientes parem de usar Dual_EC_DRBG em seus produtos. |
| 20 de dezembro de 2013 |
A Reuters noticia a existência de um acordo secreto de 10 milhões de dólares entre a NSA e a RSA para tornar o Dual_EC_DRBG o padrão em certos produtos BSAFE. |
| 21 de abril de 2014 |
O NIST remove formalmente o Dual_EC_DRBG de suas recomendações preliminares e aconselha a migração para outros algoritmos aprovados. |
| Junho de 2015 |
A revisão 1 do NIST SP 800-90A consolida formalmente a remoção do Dual_EC_DRBG. |
Descrição
Visão geral
O algoritmo usa um único inteiro, denotado por s, como estado interno. Sempre que um novo valor aleatório é solicitado, esse estado é atualizado. O estado na iteração k é dado por:
O valor pseudoaleatório devolvido também é função do estado. O valor produzido na iteração k é:
As funções 
e 
dependem de dois pontos fixos, P e Q, sobre uma curva elíptica. Esses pontos permanecem constantes em uma dada implementação do algoritmo.
Detalhes
O algoritmo admite diferentes conjuntos de constantes, comprimentos de saída e outras opções de parametrização. Em uma descrição simplificada, pode-se considerar o conjunto de parâmetros da curva P-256.
O algoritmo opera sobre um corpo finito primo 
, onde p é primo. O estado interno, a semente e os números produzidos pertencem a esse corpo.
Uma curva elíptica sobre é dada por:
onde b é uma constante fixa. Os pontos P e Q pertencem ao conjunto de pontos da curva, 
.
Usa-se ainda a função que extrai a coordenada x de um ponto:
Antes de ser devolvida, a saída passa por truncamento:
As funções principais do gerador são então definidas por:
A partir de uma semente inicial, o gerador calcula sucessivamente os estados internos e os valores de saída:
produzindo assim a sequência:
Segurança
A justificativa teórica para a inclusão do Dual_EC_DRBG no NIST SP 800-90A era a ideia de que sua segurança poderia ser reduzida a hipóteses de dificuldade computacional oriundas da teoria dos números. Em princípio, isso permitiria uma prova de segurança: se certos problemas matemáticos forem difíceis, então o gerador também seria seguro.
Contudo, os propositores do algoritmo não apresentaram inicialmente uma redução de segurança satisfatória, e análises publicadas pouco depois mostraram que o esquema, tal como especificado, revelava bits demais em cada rodada. Isso tornava a saída distinguível de aleatoriedade ideal e abria espaço para reconstrução do estado interno. Essa característica, combinada com a escolha apropriada dos pontos P e Q, é justamente o que viabilizaria a alegada porta dos fundos.
Ao contrário de outros padrões criptográficos, o Dual_EC_DRBG não explicou de modo convincente como seus parâmetros públicos padrão haviam sido escolhidos. Em muitos casos, constantes aparentemente arbitrárias são derivadas de valores conhecidos — como π — segundo o princípio do nothing up my sleeve number, para reduzir suspeitas de manipulação. No caso do Dual_EC_DRBG, a ausência dessa transparência fortaleceu as suspeitas de que os parâmetros pudessem ter sido construídos de forma maliciosa.
Posteriormente, Daniel R. L. Brown e Kristian Gjøsteen publicaram uma análise de segurança mostrando que o algoritmo poderia ser defendido teoricamente sob hipóteses adicionais, desde que os pontos P e Q fossem independentes e que a truncagem da saída fosse substancialmente maior do que a realmente adotada no padrão. Na forma padronizada, porém, essas condições protetivas não estavam satisfeitas.
A alegada porta dos fundos permitiria a um atacante determinar o estado interno do gerador a partir da saída observada em uma única rodada. Uma vez recuperado esse estado, torna-se possível prever todas as saídas futuras até que o CSPRNG seja reinicializado com nova entropia externa. Isso afetaria, por exemplo, protocolos como SSL/TLS, que dependem da geração correta de nonces e outros valores aleatórios.
Padronização e implementações
A NSA introduziu o Dual_EC_DRBG no processo do ANSI X9.82 DRBG no início dos anos 2000, com os mesmos parâmetros posteriormente apontados como problemáticos. O algoritmo também foi incluído no padrão ISO/IEC 18031.
Segundo John Kelsey, a possibilidade de uma porta dos fundos por meio da escolha cuidadosa de P e Q foi discutida em reuniões do grupo ANSI X9F1. Em resposta, o padrão passou a permitir que implementadores escolhessem seus próprios parâmetros. Na prática, contudo, a formulação adotada tornava muito difícil obter validação FIPS 140-2 sem recorrer precisamente aos parâmetros suspeitos.
Ao menos dois membros do grupo de padronização ligados à Certicom, Daniel R. L. Brown e Scott Vanstone, conheciam de perto o mecanismo da porta dos fundos, como sugere a patente registrada em 2005 sobre exatamente esse tipo de inserção e mitigação.
A RSA Security teve papel central na disseminação do algoritmo ao adotá-lo por padrão em produtos da linha RSA BSAFE. Mais tarde, após as revelações de 2013, a empresa aconselhou clientes a deixarem de utilizá-lo.
O projeto OpenSSL também implementou o Dual_EC_DRBG a pedido de um cliente, embora seus desenvolvedores estivessem cientes das suspeitas. O algoritmo, porém, não foi ativado por padrão, e descobriu-se em 2013 que a implementação continha um erro que a tornava inoperante fora do modo de teste.
A Microsoft adicionou suporte ao Dual_EC_DRBG no Windows Vista, sem ativá-lo por padrão. Em versões posteriores do Windows, chamadas a esse gerador passaram a ser redirecionadas silenciosamente para o CTR_DRBG baseado em AES.
Em 2013, após o vazamento dos documentos de Snowden e a repercussão do caso, o NIST reabriu a discussão pública em torno da família SP 800-90 e passou a recomendar explicitamente que o Dual_EC_DRBG não fosse mais usado.
Software e hardware que continham a possível porta dos fundos
Implementações do Dual_EC_DRBG normalmente chegavam aos produtos por meio de bibliotecas criptográficas. Entre as plataformas e fornecedores associados ao algoritmo estão a RSA Security, o OpenSSL, a Microsoft e a Cisco. Dentre esses, o caso mais significativo foi o da RSA, cujo BSAFE o utilizava por padrão.
A BlackBerry também ofereceu suporte ao algoritmo em sua plataforma criptográfica, embora não como configuração padrão. A empresa afirmou não considerar a provável porta dos fundos uma vulnerabilidade suficiente para justificar um aviso amplo a clientes.
Em dezembro de 2013, foi publicada uma prova de conceito demonstrando a viabilidade prática de prever saídas subsequentes do gerador a partir de estado interno recuperado.
Em dezembro de 2015, a Juniper Networks anunciou que certas versões do firmware ScreenOS usavam o Dual_EC_DRBG com os pontos suspeitos P e Q, o que criava uma porta dos fundos em seus firewalls. Nesse caso, uma modificação adicional feita por terceiros alterou os parâmetros e acabou introduzindo uma nova camada de comprometimento no mecanismo já suspeito.