Effects of inadequate randomness in information security

If I were in charge of weakening cryptosystems in the real world, the first thing I would target is random number generators.

Bruce Schneier [1]

Introduction

     When we talk about cryptosystems, one of the first things we need to think is: "random numbers". Because in these kind of systems, random numbers are necessary.
     Usually in this area, randomness is used to generate session keys, encryption keys (for example: One time pad requires random keys), to generate primes numbers, etc. We must ensure quality of each key, it needs to have the characteristics of a succession of random numbers, because the quality of system depends in a part of the quality of the key.
      If we have a simple generator of pseudorandom numbers ( simple, in this case, it means it will be able to break easily), it will be able to become in the "Achilles' heel" in our cryptosystems.

Random numbers

      They are a succession of numbers, it hasn't have a define patron, because numbers are chosen randomly, each number has the same probability to be chosen between the set of numbers, it means the succession has a uniform distribution.  [David Ríos, et al. Simulación. Métodos y aplicaciones. 2ª Edición. pp. 12 – 14]

      Some sources produce randomness are radioactive decay, but this source has a problem: how get radioactive material? how store it safely? and in some places need a permission to have this material. So another good option is the thermal noise of a resistor, an advantage it is required a minimal power requirements. There are chips that use thermal noise of a resistor, for example:

• Intel RNG (random number generator Intel), some characteristics are: high performance and low cost. Intel RNG uses thermal noise of a resistor with this option makes truly random numbers, because don't exist an algorithm to determinate a sequence, in that way the data-flow is non-deterministic unpredictable. It provides: authentication, integrity and data security.
• ComScire QNG hardware. It connect to a computer through a parallel port, it generates 10 to 20 kilo-bits per second. The principal advantage: ease of use, because we only need to plug into parallel port and install some drivers.

Pseudo-random numbers

     These numbers are generated in a predictable way through mathematical function [4]. Some good pseudorandom number generators are: 

• PRNG Yarrow
• Fortuna,  it is an improvement of PRNG Yarrow.
• Blum blum shub
• Dual EC ERBG
• X9.17-1985
• X9.31-1998

     The strongest generator is: Blum blum shub, for that reason I want to explain a how works:

Choose two large prime number (p and q). These numbers need to have a remainder of 3 when divided by 4.

Then generate n = p * q

Choose a random number (x), this number is relatively prime to n.

For calculate initial seed use the next function:

s₀ = (x²) mod n

Don't take the result of this operation, only use a few bits from the bottom of each s.

For generate the next numbers use:

s _{i + 1} = (s₁²) mod n

Características

     Para saber si una sucesión de números presenta una adecuada aleatoriedad es necesario que cumpla con ciertos requisitos: [Tomados de la presentación de la clase de criptografía, de la Dra. Elisa Schaeffer]

• Necesitan pasar test estadísticos.

“Formalmente, cualquier contraste aplicado a una parte finita de (un = sucesión) que intentase detectar desviaciones relevantes de la aleatoriedad no ha de rechazar la hipótesis nula de que los números son aleatorios.” [David Ríos, et al. Simulación. Métodos y aplicaciones. 2ª Edición. pp. 14]

Hay que poner a prueba la sucesión de números. Algunas pruebas, también llamados contrastes empíricos [David Ríos, et al. Simulación. Métodos y aplicaciones. 2ª Edición. pp. 14-18] son los siguientes:

1. Contraste x² (uniformidad)
2. Contraste de Kolmogorov-Smirnov (uniformidad)
3. Contraste de rachas (aleatoriedad)

• Impredecibles [BitMap, en esta web muestra como se verían los números si los pusieramos en un plano, contrastando uno de random.org vs pseudorandom number PHP (Windows).]
• Incompresibilidad computacional
• No reproducibles

Al cumplir con estas características nos aseguramos que los números son pseudoaleatorios.

Aplicaciones

     Los números aleatorios tienen diversas áreas aplicación, por mencionar algunas:

• Criptografía
• Juegos de azar
• Videojuegos
• Simulación

Efectos...

    Como mencionaba al inicio, actualmente los sistemas criptográficos si los números aleatorios o pseudoaleatorios no son generados en realidad al azar las claves a generar serán muy vulnerables.

     Generar números aleatorios es tan importante que existen organizaciones que se dedican a generar tests estadísticos. Un ejemplo es el NIST.

   Un ejemplo de esto es el fallo del navegador Netscape Navigator 1.1, en el cual la implementación del protocolo HTTPS, el cual sirve para establecer una comunicación segura, podía ser descifrada en segundos. El porqué de este problema es que sus números aleatorios, resultaron no ser tan aleatorios.[5,6]

Todavía hay más...[7,8,9]

Conclusión

     En resumen uno de los efectos de usar inadecuados números pseudoaleatorios es que si el criptoanalista pudiera encontrar la función que se usa, el sistema estara en un estado vulnerable.

Referencias

1. SCHNEIER, Bruce. Schneier on Security [en línea] Actualizada: 16 febrero 2012. [Fecha de consulta: 11 septiembre 2014]. Disponible en: https://www.schneier.com/blog/archives/2012/02/lousy_random_nu.html
2. BELLONE, Matías Agustín. En Español Tecnología con acento [en línea] Actualizada: 15 noviembre 2007. [Fecha de consulta: 11 septiembre 2014]. Disponible en: http://www.enespanol.com.ar/2007/11/15/%C2%BFla-nsa-puso-una-puerta-trasera-en-el-nuevo-estandar-de-encriptacion/
3. QUIRANTES, Arturo. Taller de Criptografía [en línea] Actualizada: 2005. [Fecha de consulta: 11 septiembre 2014]. Disponible en: http://www.ugr.es/~aquiran/cripto/informes/info002.htm
4. RANDOM.ORG [en línea] Actualizada: 2014. [Fecha de consulta: 11 septiembre 2014]. Disponible en: http://www.random.org/
5. Guillermo Julian. Genbeta [en línea] Actualizada: 10 septiembre 2013. [Fecha de consulta: 11 septiembre 2014]. Disponible en: http://www.genbeta.com/seguridad/rdrand-intel-y-la-poco-probable-puerta-trasera-de-la-nsa-en-linux
6. QUIRANTES, Arturo. Taller de Criptografía [en línea] Actualizada: 2005. [Fecha de consulta: 11 septiembre 2014]. Disponible en: http://www.ugr.es/~aquiran/cripto/informes/info002.htm
7. BENDEL Mike. Exophase [en línea] Actualizada: 29 diciembre 2010. [Fecha de consulta: 11 septiembre 2014]. Disponible en: http://www.exophase.com/20540/hackers-describe-ps3-security-as-epic-fail-gain-unrestricted-access/
8. KLYUBIN, Alex. Android Developers Blog [en línea] Actualizada: 14 agosto 2013. [Fecha de consulta: 11 septiembre 2014]. Disponible en: http://android-developers.blogspot.ro/2013/08/some-securerandom-thoughts.html
9. S/A. Seguridad apple[en línea] Actualizada: 17 marzo 2014. [Fecha de consulta: 11 septiembre 2014]. Disponible en: http://www.seguridadapple.com/2014/03/ios-7-generador-de-numeros-pseudo.html
10. S/A. Segu.Info [en línea] Actualizada: 2009. [Fecha de consulta: 11 septiembre 2014]. Disponible en: http://www.segu-info.com.ar/proyectos/p1_generador-numeros.htm