Inicio / Blog / Comprobando la aleatoriedad

Comprobando la aleatoriedad

Publicado el 05/11/2015, por Miguel Herrero (INCIBE)
aleatoriedad

Anteriormente habíamos hablado de la importancia de lo aleatorio en el mundo de la seguridad de la información. Sabemos que es importante tener un buen generador de números aleatorios para multitud de aplicaciones como generar OTP, nonces... , pero, ¿cómo se puede comprobar que la secuencia de números que se está generando es aleatoria?

Ilustración 1: Tira cómica de Dilbert (Fuente Dilbert.com)

Este problema no tiene fácil solución. Al fin y al cabo lo aleatorio es aleatorio. Si conocéis el teorema del mono infinito sabréis que cualquier secuencia que elijáis (al azar), puede encontrarse dentro de una secuencia infinita de un generador de números aleatorios.

Los generadores de números pseudoaleatorios (PRNG) son capaces de generar secuencias de números con una buena aleatoriedad basándose en un algoritmo predeterminado. Sin embargo, si la secuencia es suficientemente larga, no se cambia el estado inicial y se realimenta la semilla, la entropía del sistema se va reduciendo hasta cero, convirtiéndose en predecibles y, por tanto, inútiles.

El mal uso de los PRNG ha provocado varios incidentes de seguridad en los últimos tiempos. Sirva de ejemplo esta vulnerabilidad en un software comercial de 2013 o alguno de los problemas de OpenSSL y OpenSSH en Debian hace algunos años (CVE-2008-0166).

De hecho, la mala implementación de los PRNG por parte de algunos desarrolladores han motivado la creación a través de GitHub de algún proyecto con el cual se puede intentar obtener la semilla con la que se generó la secuencia aleatoria y por tanto predecir el siguiente número de la secuencia, comprometiendo la seguridad de la aplicación

Por ello, antes de utilizar un PRNG para generar números aleatorios y que otros procesos dependan de él, es recomendable realizar una serie de pruebas previas a su implantación, para comprobar que la secuencia de bits y el funcionamiento del PRNG son, al menos aparentemente, correctos.

Para este fin se diseñaron una serie de análisis estadísticos que permiten medir la aparente aleatoriedad de una secuencia. Una de las pruebas más conocidas es la que lanzó el Instituto Nacional de Estándares y Tecnología (NIST) americano en 2010. Se compone de un conjunto de test para la validación de los RNG y PRNG.

La suite del NIST se compone de 15 pruebas estadísticas que se ejecutan de forma sucesiva sobre la secuencia de bits. Si el resultado de cualquiera de estas pruebas supera el umbral del 1%, la secuencia se descarta como no aleatoria y no se ejecuta ningún otro test. De lo contrario, se deduce que la secuencia es aleatoria y se realiza el siguiente test de la lista.

Los test comprueban diferentes aspectos de la secuencia de bits. Por ejemplo, el primero, llamado "el test de frecuencia monobit", calcula la relación entre unos y ceros de la secuencia entera. Si la secuencia es lo suficientemente larga, ambos valores deberían ser equiprobables, por lo que cualquier desviación en este cálculo provoca el descarte de la secuencia. Este test podría fallar en caso de que se intentara ejecutar sobre una cadena aleatoria que no fuera lo suficientemente larga, pero cualquier secuencia aleatoria lo suficientemente larga debería de pasar este test sin problemas.

Otros conjuntos de test ampliamente utilizados para medir la aleatoriedad de una secuencia es el conjunto Diehard, creado por la Universidad de Florida y el Dieharder, de la Universidad de Duke, ambos utilizados ampliamente junto con el del NIST.

El uso conjunto de estas suites de test sirve para depurar la calidad de los generadores de números aleatorios. Si en alguno de los test (NIST, Diehard, Dieharder) se determina que la secuencia no parece aleatoria es necesario volver a analizar al generador y comprobar su calidad.

Tanto los generadores de números aleatorios basados en fenómenos físicos como los PRNG suelen tener sesgos que hacen que, en determinadas condiciones, la secuencia generada sea más sencilla de predecir. Antes de poder utilizar los números obtenidos mediante estos generadores es convenientes someter a las secuencias a un proceso de post procesado de forma que esos sesgos se eliminen, mejorando la calidad de la secuencia.

Es conveniente tener en cuenta que estos análisis son meramente estadísticos, por lo que puede darse el caso de que existan falsos negativos. Puede haber secuencias totalmente predecibles que, al someterse a este tipo de análisis, su resultado sea que parecen aleatorias. Por ejemplo, analicemos una secuencia formada por los decimales del número Pi, algo parecido a 314159265358979323846264338327950288419716939937510… A simple vista la cadena podría parecer aleatoria e impredecible (especialmente si obviamos los 3 o 4 primeros números). Este tipo de cadenas suelen pasar los análisis estadísticos si son lo suficientemente largas, sin embargo, como generador de números aleatorios no tiene ningún valor por ser totalmente predecible.

De hecho, la suite del NIST dispone de una secuencia compuesta de los decimales del número pi a fin de jugar con la herramienta. El resultado de analizar los datos correspondientes a pi con la suite es el siguiente (se muestra sólo la primera parte de los resultados por cuestión de espacio).

 

Al final del informe de resultados se indica que, para considerar que la secuencia es aleatoria en las condiciones en las que se ha ejecutado, la "nota" remarcada en rojo debería ser al menos de 8. Por tanto, el test considera que la secuencia de entrada es aleatoria, a pesar de ser determinista.

Por tanto, si no vamos a usar el PRNG por excelencia en computación, el Mersenne Twister y apostamos por crear uno propio, para dar soporte a cualquier aplicación que estemos creando, lo recomendable sería que, antes de ponerla en producción, comprobaras que la secuencia que generas sea como la mujer del César, que además de ser aleatoria, lo parezca.

Etiquetas: