NIST SP 800-90A

Dual_EC_DBRG no se presentó al público por primera vez en NIST SP 800-90 de 2006. Se observó en un borrador de 2004 de ANSI X9.82-3, así como en la versión oficial de ISO/IEC 18031:2005. ^{[ 1 ]} Sus fallos se demostraron por primera vez en marzo de 2006, cuando Kristian Gjøsteen publicó un método para predecir el sesgo en la versión que se encuentra en el borrador de diciembre de 2015 de NIST SP 800-90. Sin embargo, la publicación posterior de junio de 2006 no abordó este fallo. ^{[ 2 ]}

En 2007, Dan Shumow y Niels Ferguson presentaron un ataque mucho más potente, capaz de recuperar todo el estado interno con tan solo 32 bytes de salida, prediciendo así toda su salida futura. Se planteó la hipótesis de que las constantes no explicadas en Dual_EC_DRBG actuaban como una clave pública ; un atacante utilizaría un conjunto diferente de números (análogo a una clave privada) para llevar a cabo el ataque. Shumow y Ferguson no lograron recuperar la clave de la NSA, pero sí pudieron construir su propio par de claves para una demostración. En noviembre de 2007, Bruce Schneier comentó la naturaleza "extraña" de la historia de este generador de números aleatorios y describió la presentación de Shumow y Ferguson en términos más accesibles. ^{[ 3 ]}

La atención sobre Dual_EC_DRBG se volvió a plantear en septiembre de 2013 a raíz de un memorando de la Agencia de Seguridad Nacional hallado en la filtración de Edward Snowden que afirmaba la existencia de una puerta trasera cleptográfica . ^{[ 4 ] [ 5 ]} Una búsqueda retrospectiva de patentes y documentos relacionados con este DRBG reveló que la técnica general utilizada ya se había descrito en dos documentos de 1997. ^{[ 6 ]} Además, una patente de 2005 describe la técnica exacta utilizada en la puerta trasera, así como un método para neutralizarla. ^{[ 7 ] [ 1 ]} Sin embargo, la formulación sutil utilizada en el estándar implicaba que el cumplimiento de FIPS 140-2 impediría el uso de cualquier técnica de neutralización. ^{[ 8 ]}

El NIST desautorizó el uso de Dual_EC_DRBG para RSA algún tiempo antes del 26 de febrero de 2014. ^{[ 9 ]} El 21 de abril de 2014, el NIST retiró Dual_EC_DRBG de su guía preliminar sobre generadores de números aleatorios, recomendando que "los usuarios actuales de Dual_EC_DRBG transiten a uno de los tres algoritmos aprobados restantes lo antes posible". ^{[ 10 ]} Este borrador se formalizaría como NIST SP 800-90A Revisión 1 en junio de 2015.

Un intento de prueba de seguridad para Dual_EC_DRBG afirma que se requieren tres problemas matemáticamente difíciles para que Dual_EC_DRBG sea seguro: el problema de decisión de Diffie-Hellman , el problema del x-logaritmo y el problema del punto truncado . ^{[ 12 ]} El problema de decisión de Diffie-Hellman es ampliamente aceptado como difícil. ^{[ 12 ]} El problema del x-logaritmo no es ampliamente aceptado como difícil. Se muestra cierta evidencia de que este problema es difícil, pero esa evidencia no es concluyente. ^{[ 12 ]} Por lo tanto, la prueba de seguridad es cuestionable y se demostraría inválida si se demuestra que el problema del x-logaritmo es eficientemente resoluble. El problema del punto truncado requiere que se trunquen suficientes bits del punto seleccionado por Dual_EC_DRBG para que sea indistinguible de un número verdaderamente aleatorio. ^{[ 12 ]} Sin embargo, se ha demostrado que el truncamiento de 16 bits, el valor predeterminado especificado por el estándar Dual_EC_DRBG, es insuficiente para que la salida sea indistinguible de un verdadero generador de números aleatorios ^{[ 13 ]} y, por lo tanto, invalida la prueba de seguridad de Dual_EC_DRBG cuando se utiliza el valor de truncamiento predeterminado.

Hash_DRBG y HMAC_DRBG cuentan con pruebas de seguridad para una sola llamada que genera números pseudoaleatorios. ^{[ 21 ]} El documento que demuestra la seguridad de Hash_DRBG y HMAC_DRBG cita la prueba de seguridad intentada para Dual_EC_DRBG utilizada en el párrafo anterior como prueba de seguridad para afirmar que no se debe usar CTR_DRBG porque es el único DRBG en NIST SP 800-90A que carece de una prueba de seguridad. ^{[ 21 ]}

HMAC_DRBG también cuenta con una prueba de seguridad verificada por máquina. ^{[ 22 ]} La tesis que contiene dicha prueba de seguridad también demuestra que una vulneración de una instancia de HMAC_DRBG implementada correctamente no compromete la seguridad de los números generados antes de la vulneración. ^{[ 22 ]}

Woodage y Shumow (2019) analizan los esquemas del NIST con mayor detalle; específicamente, proporcionan pruebas de seguridad que tienen en cuenta la generación inicial de semillas y la resiembra, que no se habían analizado en absoluto antes. Bajo el modelo de oráculo aleatorio y asumiendo una fuente de entropía independiente del oráculo: ^{[ 11 ]}

• Hash_DBRG es robusto en el sentido de Dodis et al., es decir, cumple con ambos requisitos de seguridad del NIST.
• HMAC_DBRG es robusto si se cumplen dos condiciones: debe invocarse con entropía de entrada adicional, y dicha entropía debe satisfacer condiciones adicionales. Todas las fuentes de entropía aprobadas por el NIST satisfacen estas "condiciones adicionales".
• HMAC_DBRG no es seguro hacia adelante cuando se llama sin entrada adicional.

Se ha demostrado que CTR_DRBG tiene una imperfección teórica cuando se usa con ciertos parámetros porque los criptógrafos no consideraron el tamaño del bloque del cifrado al diseñar este generador de números pseudoaleatorios. ^{[ 23 ]} CTR_DRBG parece seguro e indistinguible de una fuente verdaderamente aleatoria cuando se usa AES como cifrado de bloques subyacente y se toman 112 bits de este generador de números pseudoaleatorios . ^{[ 23 ]} Cuando se usa AES como cifrado de bloques subyacente y se toman 128 bits de cada instancia, se proporciona el nivel de seguridad requerido con la salvedad de que la salida de un cifrado de 128 bits en modo contador se puede distinguir de un generador de números verdaderamente aleatorios. ^{[ 23 ]} Cuando se usa AES como cifrado de bloques subyacente y se toman más de 128 bits de este generador de números pseudoaleatorios, entonces el nivel de seguridad resultante está limitado por el tamaño del bloque en lugar del tamaño de la clave y, por lo tanto, el nivel de seguridad real es mucho menor que el nivel de seguridad implícito por el tamaño de la clave. ^{[ 23 ]} También se ha demostrado que CTR_DRBG no ofrece el nivel de seguridad esperado cuando se utiliza Triple DES porque su tamaño de bloque de 64 bits es mucho menor que el tamaño de clave de 112 bits utilizado para Triple DES. ^{[ 23 ]}

Actualmente no se conoce ningún método para explotar esta vulnerabilidad cuando se utiliza AES.