La aleatoriedad es un factor importante en muchos elementos de la informática, sobre todo a la hora de generar claves criptográficas seguras para protocolos criptográficos. Un elemento criptográfico generado a partir de una semilla que no sea suficientemente aleatoria, puede convertirse en un blanco fácil para un criptoanálisis por comparación de frecuencias, por ejemplo. ¿Cómo se consigue aleatoriedad en un sistema?
Se han dado casos en los que, por diferentes razones, se han utilizado generadores vulnerables en diferentes plataformas. Fueron importantes problemas derivados de un mal uso de la aleatoriedad, que tuvieron graves consecuencias.
Malas experiencias
- OpenSSL en Debian. En 2008 se encontró un error en la implementación. Se eliminaron dos líneas críticas en la generación de números aleatorios para usar en la creación de las claves. Esto dejó la función devolviendo números cuyo único factor para alimentar la aleatoriedad era solamente el PID del proceso (entre 1 y 32768). Estas líneas fueron eliminadas por sugerencia de Valgrind (un software que busca fugas de memoria en códigos C) mientras se depuraba el código de OpenSSL.
- Otro caso sonado fue el de Windows 2000 y XP. A finales de 2007, se descubrió una debilidad en su código de generación de números pseudoaleatorios. Aunque sin disponer del algoritmo, se consiguió llegar a un punto en el que un posible atacante podría predecir los números que habían sido generados previamente y podrían ser generados en un futuro.
- En 2010, la Play Station 3 sufrió también las consecuencias de una mala implementación en la generación de números pseudoaleatorios. En realidad, ni siquiera había aleatoriedad. La generación de claves privadas ocurría siempre a partir del mismo número, por lo que cualquier persona podía firmar una aplicación para PS3.
- En agosto de 2013, se supo que la función SecureRandom que usa Android no accedía a /dev/urandom (cuando debería). Cualquier software que usara esa función se veía afectado, por ejemplo, las carteras de bitcoins.
- Hace muy poco, durante la CanSecWest, se descubrió que en la versión 7 de iOS se introdujeron problemas en su generador de números.
Mejor entropía, mejor seguridad
¿Qué significa que algo sea aleatorio? En teoría, que no hay forma de predecirlo. Pensando en números, es aleatorio el que no hay forma de averiguar su valor hasta que se genera. Algo parecido a la paradoja del gato de Schrödinger. Todos los sistemas operativos necesitan generar números aleatorios para diversos usos pero, generar aleatoriedad en algo tan determinista por definición como un ordenador, no es trivial.
Y este es uno de los problemas de los RNG (Random Number Generator), que en realidad son PRNG (Pseudo Random Number Generator) porque es imposible conseguir una aleatoriedad del 100%. El sistema debe conformarse con acumular cierta cantidad de entropía para poder simular la creación de algo aleatorio, aun sufriendo una componente determinista. Veamos esto con más detalle:
La entropía (en este contexto) no es más que bytes de aleatoriedad añadidos de algunas fuentes pseudoaleatorias, como por ejemplo: drivers de dispositivos, algunos elementos en la secuencia de arranque de la máquina, audio o vídeo capturado desde el micrófono/cámara, movimientos del ratón, tiempo entre presionar una tecla u otra en el teclado…
Existen otras formas de añadir más bytes pseudoaleatorios, por ejemplo con dispositivos que, midiendo el ruido que se genera en el salto de electrones en una unión PN, añaden mucha entropía al sistema.
¿Dónde se añade toda esta entropía y qué se hace con ella? Esto varía entre sistemas operativos, aunque muchos se basan en la implementación que usa el kernel de Linux, que funciona más o menos así:
La entropía (en este contexto) no es más que bytes de aleatoriedad añadidos de algunas fuentes pseudoaleatorias, como por ejemplo: drivers de dispositivos, algunos elementos en la secuencia de arranque de la máquina, audio o vídeo capturado desde el micrófono/cámara, movimientos del ratón, tiempo entre presionar una tecla u otra en el teclado…
Existen otras formas de añadir más bytes pseudoaleatorios, por ejemplo con dispositivos que, midiendo el ruido que se genera en el salto de electrones en una unión PN, añaden mucha entropía al sistema.
¿Dónde se añade toda esta entropía y qué se hace con ella? Esto varía entre sistemas operativos, aunque muchos se basan en la implementación que usa el kernel de Linux, que funciona más o menos así:
/dev/random y /dev/urandom
/dev/random y /dev/urandom son dos archivos especiales en el Kernel de Linux cuya función es mantener una fuente de entropía (como una especie de almacén) que consigue de diferentes fuentes (como las mencionadas anteriormente). Desde esa fuente selecciona algunos bytes de entropía y genera un número aleatorio cuando se le llama.
No se suele hacer una llamada directa de sistema a /dev/random y a /dev/urandom en busca de números aleatorios, sino que se consiguen una serie de bytes de cualquiera de las dos fuentes y se usan como semillas para métodos/funciones implementadas en el programa que las necesite, a modo de PRNG. Cada programa podrá tener su PRNG.
Veámoslo con un pequeño diagrama:
No se suele hacer una llamada directa de sistema a /dev/random y a /dev/urandom en busca de números aleatorios, sino que se consiguen una serie de bytes de cualquiera de las dos fuentes y se usan como semillas para métodos/funciones implementadas en el programa que las necesite, a modo de PRNG. Cada programa podrá tener su PRNG.
Veámoslo con un pequeño diagrama:
 |
| Esquema básico de funcionamiento de /dev/random y /dev/urandom |
En él se observa cómo se «rellenan» (de forma simplificada) /dev/random y /dev/urandom. Del colector de entropía (de las fuentes que hemos mencionado antes) se estima la cantidad útil y se suma al contador de entropía. A esta entropía se le quita parte del bias (eliminación de muestras no válidas por diversas razones) y después de pasar por el generador de números pseudoaleatorios es añadido a la fuente de aleatoriedad.
La gran diferencia entre los dos es la comprobación de entropía: mientras una petición a /dev/urandom devolverá un valor aunque no quede mucha entropía en la fuente, /dev/random comprobará antes si la cantidad de entropía en el sistema es suficiente para llegar al mínimo especificado y bloqueará la petición hasta que ese mínimo se satisfaga, momento en el que se restará del contador de entropia.
Aquí podemos ver el resultado de pedir datos constantemente a /dev/random. Se puede observar que se genera muy poca información. Tras el primer «parón», se comienza a mover el ratón del sistema. Esto genera la entropía necesaria para que el proceso siga adelante.
 |
| Volcado directo de /dev/random |
Por el contrario, en la siguiente animación, se comprueba que /dev/urandom devuelve tanto como se le pida, sin bloqueos, puesto que no espera a que la entropía sea suficiente.
 |
| Volcado directo de /dev/urandom |
.
Esta diferencia ha llevado a problemas y discusiones a la hora de decidir cuál de los dos archivos usar para la generación de números pseudoaleatorios. En realidad, se resume en que:
- /dev/random ofrece números con aleatoriedad “de mayor calidad”, pero el bloqueo puede ser un problema si se encuentra bajo gran demanda.
- /dev/urandom ofrece números con aleatoriedad «menor» pero sin bloqueos ni «esperas».
Existen muchos puntos de vista al respecto sobre cuál usar para qué, pero está relativamente establecido que para generar claves criptográficas que vayan a tener una larga duración, como las usadas en SSH o SSL se debe usar /dev/random. Para prácticamente todos los demás usos, es más rápido y menos «arriesgado» utilizar /dev/urandom.
Juan Luis Sanz
juanluis.sanz@11paths.com
Interesante… hasta yo lo he entendido
Muy buen artículo Juan Luis.
Interesante y bien explicado.