1 La importancia de los números aleatorios en la generación de claves criptográficasEmmanuel Byrd Suárez | José de Jesús Ángel Ángel Instituto Tecnológico y de Estudios Superiores de Monterrey México, Junio 2017

2 Esta ponencia Objetivo: remarcar la relación entre los números aleatorios y las claves criptográficas Uso de los números aleatorios. Ataques a generadores de números aleatorios. Definición de número aleatorio y generador de números aleatorios. Cómo evaluar un generador de números aleatorios. Ejemplo práctico para generar y evaluar números aleatorios. El Dual_EC_DRBG: historia y vulnerabilidad Conclusiones Objetivo: Remarcar la relación entre los números aleatorios y las claves criptográficas.

3 Uso de los números aleatoriosDES Aproximaciones de radiación de Monte Carlo Triple DES RSA Juegos AES Algoritmos de identificación usados en bancos. DH ECDH ECDSA Estos algoritmos necesitan la generación de un número aleatorio en alguna parte (dentro de un proceso o como llave). Seguros: dificultad de obtener esa llave. Otras aplicaciones: Simulaciones donde controlar millones de elementos es difícil, genera errores y es muy tardado: probabilidades, las cuales producen resultados certeros.

4 Rusia y casinos: Junio 2014 [Schn17] [Koer17]En 2014 algunos casinos empezaron a ver que ciertas máquinas estaban dando más dinero de lo que las probabilidades predecían. Un grupo de rusos con conocimiento del generador de números aleatorios de ciertas máquinas y retroalimentación de un cómplice jugando podía predecir en qué segundo el cómplice debía operar la máquina para ganar. [Schn17] [Koer17]

5 Windows PRNG Windows 2000 y Windows XP.Ataque Forward Security: Un adversario podría calcular las salidas anteriores dado el estado del WRNG con un costo de cálculos (cuestión de segundos en una computadora de escritorio). Ataque Backward Security: Dado el estado del WRNG, un atacante puede calcular las siguientes salidas de forma inmediata. [Dorr09] Microsoft modificó su RNG para eliminar este problema desde Windows Vista, Windows Server y Windows Server [Keiz07] Forward Security: Conocer los estados anteriores del sistema. Backward Security: Replicar los siguientes estados del sistema.

6 Números aleatorios Hablando de números individuales: un número aleatorio es aquél obtenido de un grupo de posibles valores, todos con la misma probabilidad de ser seleccionados. Significa que provienen de una distribución uniforme de probabilidad. Hablando de una secuencia de números: cada número obtenido debe ser estadísticamente independiente de los demás. Seleccionar un número dentro de un grupo con una distribución uniforme de probabilidad. Cada número obtenido debe ser estadísticamente independiente de los demás. Cadenas binarias: cada 1 y 0 debe tener idealmente un 50% de probabilidades de generarse. [RAND]

7 Generadores de números aleatoriosVerdaderos generadores de números aleatorios Basados en un fenómeno físico inalterado por el humano RANDOM.ORG crea números aleatorios desde 1998 para el público en internet utilizando ruido atmosférico. Medir datos externos El movimiento del mouse o el tiempo en que una persona presiona las teclas. Un PRNG (Pseudo Random Number Generator) es un algoritmo determinista y eficiente que transforma un número inicial aleatorio (semilla) en una larga secuencia pseudoaleatoria. Deben tener “algunas” propiedades estadísticas presentes en secuencias verdaderamente aleatorias. [RAND], [Gold86]

8 CSB Generator 𝑝 𝑘 𝑖 − 1 2 < 1 𝑄 𝑘 2Cryptographically Strong Pseudorandom Bit Generator Let 𝑃 be a polynomial. A CSB generator G is a deterministic poly(k)-time program that stretches a k-bit-long randomly selected seed into a P(k)-bit-long sequence that passes all next-bit-test: Let 𝑃 be a polynomial, 𝑆 𝑘 a multiset consisting of P(k)-bit sequences and 𝑆= 𝑈 𝑘 𝑆 𝑘 . A next-bit-test for 𝑆 is a probabilistic polynomial-time algorithm 𝑇 that on input 𝑘 and the first 𝑖 bits in a string 𝑠 ∈ 𝑟 𝑆 𝑘 outputs a bit 𝑏. Let 𝑝 𝑘 𝑖 denote the probability that 𝑏 equals the 𝑖+1𝑠𝑡 bit of 𝑠. We say that 𝑆 passes the next-bit-test 𝑇 if, for all polynomials 𝑄, for all sufficiently large 𝑘, and for all integers 𝑖∈[0,𝑃 𝑘 ]; 𝑝 𝑘 𝑖 − 1 2 < 1 𝑄 𝑘 2 La prueba del siguiente bit es aprobada si no hay un algoritmo eficiente, esto es en tiempo polinomial, que pueda predecir el valor del siguiente bit con un nivel de certeza significativamente más alto que Podría decir siempre: “el siguiente va a ser 1”, si le atino a la mitad no lo estoy prediciendo. Goldwasser How to Construct Random Functions 1986. [Gold86]

9 Propósito final de las pruebas del NISTLa aleatoriedad es una propiedad probabilística. Se predicen con anticipación los resultados de aplicar estas pruebas a secuencias verdaderamente aleatorias y son descritos en términos probabilísticos. 𝐻0:𝑙𝑎 𝑠𝑒𝑐𝑢𝑒𝑛𝑐𝑖𝑎 𝑒𝑠 𝑎𝑙𝑒𝑎𝑡𝑜𝑟𝑖𝑎 El error peligroso es el de tipo II. Los generadores aprobados pueden ser utilizados en aplicaciones que requieran mucha seguridad. [NIST10]

10 Propósito final de las pruebas del NISTMinimizar los Errores de tipo II: Minimizar la probabilidad de aceptar una secuencia como producida por un buen generador cuando en realidad fue producida por un mal generador. Falso positivo. Es probable y aceptado decidir que un mal generador produjo la secuencia cuando en realidad era un buen generador. Falso negativo. P 𝑣𝑎𝑙𝑢𝑒 : la probabilidad de que un generador de números aleatorios perfecto haya producido una secuencia menos aleatoria que la secuencia evaluada. Por defecto se compara el P 𝑣𝑎𝑙𝑢𝑒 de cada prueba con el valor crítico 0.01 para obtener un nivel de certeza del 99%. El objetivo es minimizar los errores de tipo II: los falsos positivos. Habrá un nivel relativamente alto de errores de tipo I: falsos negativos, pero podemos vivir con eso. Las pruebas de NIST son comparadas con los resultados estadísticos que se esperarían de una secuencia verdaderamente aleatoria. [NIST10]

11 Las pruebas de NIST [NIST10] Frequency (Monobit) TestLinear Complexity Test Frequency Test Within a Block Serial Test Runs Test Approximate Entropy Test Longest Run on Ones in a Block Cumulative Sums Test Binary Matrix Rank Test Random Excursions Test Discrete Fourier Transform Test Random Excursions Variant Test Non-overlapping Template Matching Test Overlapping Template Matching Test Maurer’s “Universal Statistical” Test Esta herramienta es la que utilizamos en nuestro ejemplo práctico, se puede descargar gratuitamente por internet. [NIST10]

12 Frequency Monobit TestObjetivo: que exista aproximadamente el mismo número de 1 que de 0. Ninguna secuencia debe ser rechazada por esta prueba. Secuencia de bits: 𝜀= 𝜀 1 , 𝜀 2 ,…, 𝜀 𝑛 𝑆 𝑛 = 𝑋 1 + 𝑋 2 +…+ 𝑋 𝑛 , donde 𝑋 𝑖 =2 𝜀 𝑖 −1 𝑆 𝑜𝑏𝑠 = | 𝑆 𝑛 | 𝑛 P-value = erfc 𝑆 𝑜𝑏𝑠 2 Si P-value <0.01 concluimos que la secuencia es no-aleatoria [NIST10]

13 Maurier’s “Universal” Statistical TestQué tanto puede comprimirse una secuencia de bits. Una secuencia que puede comprimirse mucho sin perder información es considerada no- aleatoria. Se requieren secuencias de bits grandes para poder evaluar con precisión si se puede comprimir mucho o no. Una secuencia que se pueda comprimir significa que tiene muchos patrones repetidos, lo cual nos da un indicativo de que puede ser no aleatoria. [NIST10]

14 Generadores comunes Java C++ Python PHP random() rand()Estos generadores están a la mano de cualquiera. Sumergiéndonos en la documentación vemos las advertencias de su uso en aplicaciones criptográficas. Con esta información invito al público a investigar a fondo aquellas funciones que vayan a utilizar, así sean las recomendadas para aplicaciones cripográficas como SecureRandom de Java. [ORACLE], [CPPR], [PYTHON], [PHP]

15 El código fuente que utilicé para crear las cadenas de números aleatorios que evaluamos. La clase SecureRandom de Java permite escoger entre diferentes algoritmos generadores de números aleatorios, el default es SHA1 y por estar usando Windows pude acceder al algoritmo del sistema operativo mediante Windows-PRNG. Los usuarios de Linux no podrían acceder a este algoritmo pero sí a otro como NativePRNG. Creé 20 archivos con 14 millones de bits cada uno, se cambia la semilla del algoritmo al inicio de cada archivo y se vuelve a cambiar otras tres veces.

16 Podemos ver en la línea 37 cómo se genera una semilla y se utiliza para iniciar el algoritmo. La entropía del número generado depende de la entropía de la semilla, existen algunos algoritmos que si no encuentran suficiente caos en el sistema bloquean el avance del código hasta encontrarlo. Una vez generada la semilla el algoritmo se llama un número grande de veces y se concatena un byte a la secuencia que será almacenada en el archivo. Cada archivo tiene el nombre del algoritmo y el número del archivo.

17 Esta es la información que utilizó mi implementaciónEsta es la información que utilizó mi implementación. Estos datos se obtuvieron con llamadas a la clase SecureRandom, es decir: no escribí explícitamente: “print(Java versión: 1.0.8_51)”, sino más bien algo como “getVersion”, “getAlgorithm” y “getProvider”. Esta información es importante para conocer con detalle qué es lo que está sucediendo dentro del código y poder compararlo con otras investigaciones: podemos saber si SHA1 es seguro, qué defectos tiene esta versión de Java y demás. Este análisis debería ser realizado con mucho más vigor en aplicaciones robustas.

18 Análisis de algunos generadoresNota: Secuencias de más de 20,000 bits. Con un nivel significativo 𝛼=0.01, deberían evaluarse al menos 100 secuencias. Una evaluación exhaustiva para fines criptográficas puede tener niveles significativos 𝛼 de al menos y hasta Evaluar 100GB. Si el tamaño de cada secuencia es de 20,000 bits entonces pruebas como la “universal” tendrá problemas: no habrá una buena forma de saber si se puede comprimir. Nuestro ejemplo utilizó un nivel significativo de 0.01, pero aplicaciones serias deberían tener un nivel mucho más preciso. [NIST10], [Sýs15]

19 Análisis de algunos generadoresJava 1.8.0_51 Windows 8.1 SHA1 100 cadenas de un millón de bits Windows-PRNG

20 SHA1PRNG C1 C2 C3 C4 C5 C6 C7 C8 C9 C10 P-Value ProporcionalSTATISTICAL TEST 5 8 11 14 12 9 13 98/100 Frequency 7 15 10 96/100 BlockFrequency 16 97/100 CumulativeSums Runs 100/100 LongestRun of Ones 6 Rank 99/100 FFT NonOverlappingTemplate 95/100 OverlappingTemplate Universal Statical ApproximateEntropy RandomExcursions RandomExcursionsVariant Serial Linear Complexity

21 Windows-PRNG C1 C2 C3 C4 C5 C6 C7 C8 C9 C10 P-Value Proporcional STATISTICAL TEST 13 9 8 10 12 7 11 98/100 Frequency 15 17 99/100 BlockFrequency 2 19 95/100 CumulativeSums 16 5 Runs 6 LongestRun of Ones Rank FFT 21 * NonOverlappingTemplate 4 OverlappingTemplate 97/100 Universal Statical 14 ApproximateEntropy RandomExcursions 96/100 RandomExcursionsVariant Serial Linear Complexity El generador de Windows falla la prueba de NonOverlappingTemplate, pero al ser probabilístico se espera que los generadores fallen algunas de ellas.

22 Resultados obtenidos SHA1PRNG: Windows-PRNG: Aprobó todas las pruebas.Los P−𝑣𝑎𝑙𝑢𝑒 son uniformes. No es: no pseudoaleatorio. Se deben evaluar otras muestras, obtenidas bajo otras plataformas para concluir que es pseudoaleatorio. Windows-PRNG: Aprobó la mayoría de las pruebas. Los P−𝑣𝑎𝑙𝑢𝑒 no son uniformes, tienen un sesgo. No es no pseudoaleatorio. Debido al documento de NIST podemos considerarla pseudoaleatoria y proceder al siguiente paso. Debido al fallo de una prueba determinamos la evaluación no concluyente. José de Jesús Ángel Ángel

23 Dual_EC_DRBG 2004: Publicado en el ANSIX9.82 y NIST SP 800 90.2004: RSA coloca Dual_EC_DRBG como default en principal librería de criptografía BSAFE. 2005: ISO-IEC publican Dual_EC_DRBG. 2013: RSA niega trato con NSA para promover Dual_EC_DRBG 2014: NIST retira del documento SP el algoritmo Dual_EC_DRBG. ¿Qué sucedió con este algoritmo?

24 Curvas elípticas 𝑦 2 = 𝑥 3 +𝑎𝑥+𝑏 Elegidos! [Groo15]Debe haber una elección en los valores que generan la curva, así como las coordenadas del par de puntos que se utilizarán (más adelante explico cómo funciona) y el número primo con el que se realizarán las operaciones de módulo. Es importante recalcar que alguien debe escoger estos valores. [Groo15]

25 Suma de puntos Q P P+Q [Groo15]

26 Multiplicación 5P P 3P 6P 4P P+P = 2P [Groo15]

27 Problema de Logaritmo DiscretoFuerza bruta Baby step-Giant step Algoritmo del canguro de Pollard Algoritmo de Silver-Pohlig-Hellman Index-Calculus Algoritmo ρ de Pollard: El más utilizado Si tenemos un número P, podemos duplicarlo y sumarle P de manera que obtengamos el número 100P. Estas operaciones son rápidas y en este caso (100) solo se requieren 8 movimientos entre sumarle 1P y doblar el número actual. Dado el punto Q y el punto P, si nosotros sabemos que Q es el resultado de multiplicar P un número de veces, encontrar ese número de veces es realmente complicado. Es el problema del logaritmo discreto, el cual podría llevar años si se intenta para números grandes. [Sant13]

28 Como generador de números aleatoriosDual_EC_DRBG Dual, Elliptic Curve, Deterministic Random Bit Generator Discrete Logarithm Problem Produce puntos (números) “aleatorios” Es pseudoaleatorio porque es impredecible de forma eficiente y es impredecible porque es difícil resolver el problema del logaritmo discreto.

29 Semilla Función Nueva cadena Nueva cadena Función Otra nueva cadena 1 1 1 1 Secuencia aleatoria generada

30 𝑃=𝑑∗𝑄 𝑆 1 ∗𝑃 𝑆 0 ∗𝑃 𝑆 2 ∗𝑃 𝑆 0 𝑆 1 𝑆 2 32-bytes 𝑆 1 ∗𝑄 𝑆 2 ∗𝑄 𝑅 1 ∗𝑑𝑆 1 ∗𝑃 𝑆 0 ∗𝑃 𝑆 2 ∗𝑃 𝑆 0 𝑆 1 𝑆 2 32-bytes 𝑆 1 ∗𝑄 𝑆 2 ∗𝑄 𝑅 1 ∗𝑑 𝑅 1 𝑅 2 2 bytes concatenados 30 bytes descartados 𝑆 1 ∗𝑃= 𝑆 2 = 𝑆 1 ∗ 𝑑∗𝑄 =𝑑∗ 𝑆 1 ∗𝑄 =𝑑∗ 𝑅 1 Las personas que dieron la estandarización de los puntos P y Q tuvieron la oportunidad de hacer lo siguiente: voy a generar un punto P, un punto D y los voy a multiplicar para obtener el punto Q. Pero me guardaré por siempre el valor del punto D, al fin y al cabo nadie podrá encontrarlo a menos que resuelva el problema del logaritmo discreto.

31 La estandarización de NIST (retirada en 2015)NIST A: El apéndice A del documento de NIST donde especifican sus recomendaciones para generadores determinísticos de números aleatorios menciona que deberían usarse las curvas que NIST aprueba. ¿Recuerdan que diferentes valores de la ecuación generan diferentes curvas? [NIST12]

32 NIST incluso les puso nombreNIST incluso les puso nombre. En esta pantalla NIST nos da los valores de la curva, el número primo sobre el cual hacer las operaciones de módulo y las coordenadas X y Y de los dos puntos P y Q. ¿De dónde salieron estos valores? ¿Por qué escogieron estos valores? [NIST12]

33 RSA introdujo el algoritmo a su librería BSAFE y negó saber que existía una posible vulnerabilidad.[Arth13]

34 Muchos expertos han estado en contra de seguir promoviendo este algoritmo.[Pete14]

35 Principio de KerckhoffsLa efectividad de un sistema criptográfico no debe depender de que su diseño permanezca en secreto Sin respuestas claras de cómo se obtuvieron estos números estaríamos trabajando bajo la suposición de que nadie conoce la llave a la puerta trasera. Como es muy sabido en criptografía, la efectividad de un algoritmo no debe depender de que éste sea guardado en secreto. La realidad es que nadie sabe si este número escondido se conoce, el número existe, eso es un hecho matemático, pero nadie puede probar que se conoce. Tampoco se puede probar que se desconozca. Mejor no lo utilicemos (al menos para generar números aleatorios) como decidieron NIST, RSA y demás.

36 Conclusión Mientras más claves criptográficas sean generadas por verdaderas funciones pseudoaleatorias entonces el espacio de claves es más grande y menos vulnerable al ataque de fuerza bruta u oportunistas.

37 Referencias [Arth13] Arthur, Charles. (Diciembre 2013). Security Company RSA denies knowingly installing NSA ‘back door’. The Guardian. Recuperado de https://www.theguardian.com/technology/2013/dec/23/security-company-rsa-denies-installing-nsa-back-door [Dorr09] Dorrendorf, Leo. Gutterman, Zvi. Pinkas, Benny. (Octubre 2009). Cryptanalysis of the random number generator of the Windows operating system (PDF). ACM Transactions on Information and System Security. Recuperado de [Gold86] Goldreich, Oded. Goldwasser, Shafi. Micali, Silvio. (1986) How to Construct Random Functions. Journal of the Association for Computing Machinery, Vol. 33, No. 4. Recuperado de https://people.csail.mit.edu/silvio/Selected%20Scientific%20Papers/Pseudo%20Randomness/How%20To%20Construct%20Random%20Functions.pdf [Groo15] Grooten, Martinj. (BSides London, Junio 2015). Elliptic Curve Cryptography for those who are afraid of math. Recuperado de https://www.youtube.com/watch?v=yBr3Q6xiTw4&feature=share

38 Referencias [Keiz07] Keizer, Gregg. (Noviembre 2007). Microsoft confirms that XP contains random number generator bug. Recuperado de [Kels98] Kelsey, John. Schneier, Bruce. Wagner, David. Hall, Chris. (1998) Cryptanalitic Attacks on Pseudorandom Number Generators. Fast Software Encryption, Fifth International Workshop Proceedings (March 1998), Springer-Verlag, 1998, pp Recuperado de https://www.schneier.com/academic/paperfiles/paper-prngs.pdf [Koer17] Koerner, Brendan. (Junio 2017). Russians engineer a brilliant slot machine cheat – and casinos have no fix. WIRED. Recuperado de https://www.wired.com/2017/02/russians-engineer-brilliant-slot-machine-cheat-casinos-no-fix/ [Mene96] Menezes, A. van Oorschot, P. Vanstone, S. (1996). Pseudorandom Bits and Sequences. Handbook of Applied Criptography. CRC Press. Capítulo 5. p

39 Referencias [NIST12] Kelsey, John. Barker, Elaine. (2012) Recommendation for Random Number Generation Using Deterministic Random Bit Generators. NIST Special Publication A. Recuperado de [NIST94] NIST (1994). Security Requirements for Cryptographic Modules. Recuperado de [Pete14] Peterson, Andrea. (Enero 2014). At least eight security experts boycott prominent security conference over NSA ties. The Washington Post. Recuperado de https://www.washingtonpost.com/news/the-switch/wp/2014/01/07/at-least-six-security-experts-boycott-prominent-security-conference-over-nsa-ties/?utm_term=.a8930d63f998 [RAND] RANDOM.ORG. Are the Numbers Really Random? Recuperado de https://www.random.org/analysis/

40 Referencias [NIST10] Rukhin, Andrew. Soto, Juan. Nechvatal, James. et.al. (2010). A Statistical Test Suite for Random and Pseudorandom Number Generators for Cryptographic Applications. NIST. Recuperado de [Sant13] Santamaría, Jennifer. Sadornil, Daniel. (España, 2013) El algoritmo discreto y sus aplicaciones en Criptografía. Recuperado de https://repositorio.unican.es/xmlui/bitstream/handle/10902/3101/Jennifer%20Santamaria%20Fernandez.pdf?sequence=1 [Schn17] Schneier, Bruce. (Febrero 2017). Predicting a Slot’s Machine PRNG. Recuperado de https://www.schneier.com/blog/archives/2017/02/predicting_a_sl.html [Sýs15] Sýs, Marek. Ríha, Zdenek. Matyás, Vashek. et.al. (2015) On the Interpretation of Results from the NIST Statistical Test Suite. Romanian Journal of Information Science and Technology, Vol. 18, Number 1, 2015,

41 Referencias Documentación sobre lenguajes de programación[ORACLE] Oracle. Class Random. Java Platform Standard Ed. 7. Recuperado de https://docs.oracle.com/javase/7/docs/api/java/util/Random.html [CPPR] cppreference.com. std::rand. Recuperado de [PYTHON] Python Software Foundation. random – Generate pseudo-random numbers. Recuperado de https://docs.python.org/2/library/random.html [PHP] The PHP Group. rand. Recuperado de