Hackeando a la suerte (Historias de funciones pseudo aleatorias).

Ganar la lotería es difícil. Existen millones de posibilidades en contra. Pero cuando ocurre, el o los afortunados recibirán premios millonarios. Ganar más de una vez, parece inalcanzable. Pero no es imposible. Existen casos de agraciados que triunfaron en múltiples ocasiones. Por citar algunos ejemplos un francés 2 veces con una separación de 15 años, o una pareja en Virginia USA 3 premios en un mes.

El caso de Eddie Tipton podría agregarse a la lista de multiganadores. Ganó al menos seis grandes premios de lotería. "Al menos" porque no hay certeza de que haya ganado más. Tipton no dio precisiones, porque lo llevaría a autoincriminarse. Estamos hablando de un ex empleado de la Multi-State Lottery Association (MUSL) que nuclea al menos 36 loterías de diferentes estados de USA. Las normas prohiben que trabajadores en relación con la empresa o sus familiares más cercanos puedan participar en un sorteo. En este caso no es cualquier empleado de bajo rango, sino del mismísimo director de seguridad de la asociación. Y tampoco es únicamente una violación de la norma. Eddie está acusado de modificar el proceso del sorteo mediante el hackeo de la función generadora del número aleatorio.

Los investigadores realizaron análisis forenses en una de las computadoras que realizaba el sorteo y encontraron evidencias de que ciertos días del año y en ciertas condiciones los números que se debían generar al azar eran producidos con un algoritmo que emitía un número predecible. Cómplices del estafador eran encargados de comprar o cobrar los premios recibidos. El caso se conoció como "Hot Lotto fraud scandal" y estalló públicamente en 2015, Aun el proceso judicial y de investigación sigue ramificándose.

Las loterías que fueron víctimas utilizaban un generador de números aleatorios que se conectaba a una computadora. La lotería de Idaho - una de las afectadas - explica en su sitio web que utiliza el decaimiento radioactivo del plutonio para generar un número completamente aleatorio. Este método, es indudablemente un buen generador de un valor random. El problema vino, evidantemente, en el hackeo de la interface.

Hackear una función aleatoria, en el sentido de predecir el próximo número a salir, no es posible (más información en "Las computadoras no juegan a los dados"). Si la función es realmente no-determínistica la opciones son reemplazarla o intermediarla por otro proceso del que se tenga control. Pero, la realidad es que una gran cantidad de procesos que utilizan computadoras para generar valores aleatorios no usan generadores randoms. Utilizan funciones pseudo-aleatorios.


Una función pseudo aleatoria es un algoritmo computacional que genera una sucesión de números que 'parece' aleatoria. Intentan emitir resultados que sean uniformemente distribuidos y "aparentemente" estadísticamente independientes. La uniformidad intenta que todos los valores tengan la misma probabilidad de ocurrencia. La independencia que la ocurrencia de un valor en un determinado momento sea independiente de los valores anteriores.  

¿Cuál es el motivo por el que se utilizan las funciones pseudo y no los métodos verdaderamente aleatorios? En primer lugar la mayoría de las computadoras hasta fechas recientes no tenían un mecanismo integrado de generación de números random. Luego, hay pocos lenguajes de programación que integran a estos mecanismos verdaderamente random en su set de instrucciones. Además, aún venciendo estos dos escollos, la generación tiene una limitación en la cantidad de valores por segundo que pueden emitir. Por último nada garantiza que no puedan ser "intervenidos" externamente.

John von Neumann

John von Neumann, unos de los padres de la informática, inventor junto a Stanislaw Ulam del método Monte Carlo, fue unos de los primeros en utilizar una función pseudo-aleatorio. Sin esta las simulaciones con su método no podían resolverse en un tiempo razonable. Von Neumann consciente de las limitaciones de la pseudo aleatoriedad afirma en la publicación "Various techniques used in connection with random digits":

"Any one who considers arithmetical methods of producing random digits is, of course, in a state of sin. For, as has been pointed out several times, there is no such thing as a random number — there are only methods to produce random numbers, and a strict arithmetic procedure of course is not such a method."

Los generadores pseudo aleatorios son algoritmos basados en funciones matemáticas. Por lo tanto, son funciones determinísticas. Requieren valores iniciales que reciben el nombre de "semilla". Para el mismo valor inicial, se emitirán consistentemente la misma sucesión de números. Conocida la semilla los resultados se vuelven totalmente predecibles. Además son cíclicos: luego de una cantidad de resultados producidos vuelve a repetir desde el inicio los valores ya producidos.

Von Neumann propone uno de los primeros métodos pseudo aleatorios en 1951. El método "Middle-Square" iniciaba con un número de longitud "n" (la semilla). Para emitir el valor siguiente lo elevaba al cuadrado y tomaba los "n" dígitos del medio del valor resultante. El proceso se repetía tomando el valor calculado como la entrada del próximo cálculo y al mismo tiempo emitiéndolo como el valor aleatorio. Midle-Square no es muy buena. Ciertos valores hacen que la salida se vuelva monótona. Si la semilla es 0 o 1, o en algún paso se llega a esos valores, las salidas siguientes siempre serán las mismas.

Una familia de funciones aleatorias un poco más robusta es la conocida como generadores congruenciales lineales (LCG). Gran cantidad de lenguajes de programación incluyen este tipo de generador como su función standard de valores random (C, Java, pascal, entre otros). Comparados con el método anterior tienen ciclos de repetición más grandes. Además es un método ágil para calcular y sencillo de implementar. No es muy seguro, no se recomienda en aplicaciones criptográficos o que requieran seguridad. A pesar de distribuir bastante bien los valores, no es ni muy estadísticamente independiente ni uniformemente distribuido. Pero para aplicaciones simples se "defiende" bastante bien.

Sin embargo, los LCG tienen historias nefastas en cuanto a su utilización en procesos de seguridad. Sea por desconocimiento o negligencia, los resultados son igualmente problemáticos. En primer lugar, la aparente aleatoriedad se destruye conociendo la semilla seleccionada. Una selección previsible de la misma o calculable es el peor escenario. Este problema se repitió varias veces. Tal vez el caso más resonante se remonta a los primeros años de la word web wide. En 1994 las primeras alarmas se disparaban dentro del CERN: la capa de seguridad de las comunicaciones web del servidor de Netscape (en ese momento el más popular) era insegura. El investigador  Phillip Hallam-Baker reportó el problema por canales privados a los desarrolladores del servidor. La alerta no impidió que el producto sea lanzado. Netscape requería un mecanismo seguro para transportar información sensible por la web y es por eso que desarrolló e implemento el SSL. Tal vez inconscientes de la gravedad o pendientes que no se divulgue públicamente el problema hasta poder solucionarlo, el producto fue distribuido.

En 1995 - y publicado en enero de 1996 - dos estudiantes de doctorado de la universidad de Berkeley, Ian Goldberg y David Wagner, descubrieron el problema y lo difundieron al público. Un poco de ingenieria inversa y paciencia para analizar las instrucciones del programa dieron frutos. Dentro de proceso de creación de canales de comunicaciones seguros, Netscape utilizaba una función LCG para crear un valor único en cada conexión establecida. Para definir la semilla del método utilizaban identificadores del proceso de ejecución (algo sencillo de obtener) y la hora de inicio del servidor. Conocidos estos valores, se podía escuchar cualquier comunicación que se estaba realizando (obteniendo de esa forma entre otras cosas claves de acceso o datos de tarjetas de crédito). Para obtener la hora de inicio existen diversas maneras, tal vez la más sencilla es realizar un reinicio controlado. Cuando uno no es dueño del servidor, la manera de reiniciarlo es "volteándolo" (forzar el reinicio de manera non-sancta).

Como suele suceder, la dolorosa experiencia de algunos, muchas veces no sirve de aprendizaje a otros que vuelven a cometer el mismo error. En 2009 se publicó en el sitio Hacker News, el hackeo exitoso del mismo sitio. El post titulado "How I Hacked Hacker News (with arc security advisory)" aun sigue disponible y explica detalladamente y paso a paso como llegó a realizarse. En rigor, tenía exactamente el mismo problema que Netscape del 94.

El problema de la selección segura de la semilla puede ser resuelto de diferentes maneras. Una forma es utilizar una variable sin inicializar en el programa (no todos los lenguajes de programación lo permiten). La misma tendrá almacenado un valor que no depende del programa y que puede tener cualquier contenido (la variable contendrá un conjunto de bits de la memoria que pueden haber sido usados anteriormente para almacenar cualquier cosa por cualquier programa). Esta aproximación la utilizó la distribución Debian de Linux para diferentes procesos para generar números aleatorios. En 2008 se desató lo que se conoció como "Debian/OpenSSL Fiasco". Un colaborador de mantenimiento del código core de Debian encontró que la herramienta de profiling y debugging Valgrind daba errores por variables no inicializadas. Es generalmente un error de programación no inicializar las variables que puede ocasionar resultados inesperados en los procesos (justamente lo que en este caso se estaba buscando). De la comunicación con los desarrolladores entendió que podía "solucionar" el problema poniendo un valor a las variables. Por ese pequeño cambio, entre 2006 y 2008 Debian presentó un error tan grosero en su capa de seguridad SSL que únicamente se podían generar 32.767 valores para identificar las comunicaciones. Ese número podía ser procesado mediante fuerza bruta y de esa forma toda la seguridad se desmoronaba.

Otra forma de generar la semilla es utilizar un generador aleatorio real para definirla. De esa manera un proceso "lento" inicial se utiliza solo para el setup del proceso de generación aleatorio más veloz. Luego con la semilla definida se procede a generar los valores pseudo aleatorios.

Pero aún sin saber la semilla es posible predecir los próximos valores de un LCG conociendo una secuencia de números que se emitieron anteriormente. Teniendo los parámetros lineales alcanza con observar 2 valores consecutivos para poder calcular los próximos (acá una explicación detallada). Y sin tenerlos, con 6 números consecutivos se los puede reconstruir y predecir todos los siguientes números (véase acá). También acá una demostración más general y profunda de como es que funciona este "hack".

Es evidente que utilizar un Generador congruencial lineal para una aplicación que requiere seguridad no es una buena elección (Se pueden leer otros ejemplos de problemas de seguridad utilizando incorrectamente generadores aleatorios en la publicación "The Sad History of Random Bits"). En su lugar se podría utilizar Blum Blum Shub propuesto en 1986 por Lenore Blum, Manuel Blum, y Michael Shub.

Cabe entonces, mantener los LCG en aplicaciones que no tengan que ver con seguridad. Pero, para desgracia de quien los utiliza, tampoco son utiles para simulaciones de Monte Carlo. En su publicación "Random numbers fall mainly in the planes", George Marsaglia demostró que cualquiera sean los parámetros iniciales seleccionados, se puede ver que los puntos seleccionados caen siempre en un conjunto reducido de hiperplanos. Lo que convierte a esta familia de generadores random en pobres con respecto a la uniformidad de distribución. Al respecto, con preocupación, se preguntaba:

"[...] more disturbing is the possibility that for the past 20 years such regularity might have produced bad, but unrecognized, results in Monte Carlo studies which have used multiplicative generators"

Una prueba visual del problema de distribución puede obervarse en la pagina de Bo Allen. Esta prueba realiza un rectángulo y pinta un bit de blanco o negro de acuerdo a si el valor obtenido de la función random esta en la mitad superior o inferior de los valores posibles (>0,5). Si el generador fuese realmente aleatorio no deberían verse patrones (otras pruebas de calidad estadística de funciones aleatorias acá).

Una alternativa para utilizar en simulaciones de Monte Carlo es Mersenne Twister creado en 1997 por Makoto Matsumoto y Takuji Nishimura.

Entonces, para que utilizar un LCG? O es mejor no utilizarlo? LGC sigue siendo el método más rápido de calcular y requiere poco procesamiento y almacenamiento para funcionar. Para ciertos juegos de computadoras o por ejemplo para hacer un random de ejecución de una lista de videos o canciones sigue siendo una buena elección.