Criptografia. Aleatoriedad

La aleatoriedad se encuentra en todas partes en la criptografía: en la generación de
claves secretas, en esquemas de cifrado, e incluso en los ataques a criptosistemas. Sin aleatoriedad, la criptografía sería imposible porque todas las operaciones se volverían predecibles y, por lo tanto, inseguras. Este post le presenta el concepto de aleatoriedad en el contexto de la criptografía y sus aplicaciones. Exponemos los generadores de numeros pseudoaleatorios y cómo los sistemas operativos pueden producir aleatoriedad, y concluimos con ejemplos reales que muestran cuán defectuosa la aleatoriedad puede afectar a la seguridad.

aleatorio o no aleatorio

Probablemente ya haya escuchado la frase «bits aleatorios», pero estrictamente hablando, no existe una serie de bits aleatorios. Lo que es aleatorio es en realidad el algoritmo o proceso que produce una serie de bits aleatorios; por lo tanto, cuando decimos «bits aleatorios», en realidad queremos decir bits generados aleatoriamente.
¿Cómo se ven los bits aleatorios? Por ejemplo, para la mayoría de las personas, los 8 bits de la cadena 11010110 es más aleatoria que 00000000, aunque ambas tienen la misma posibilidad de ser generada (es decir, 1/256). El valor 11010110 parece más aleatorio que 00000000 porque tiene los signos típicos de un valor generado aleatoriamente. Es decir, 11010110 no tiene un patrón obvio. Cuando vemos la cadena 11010110, nuestro cerebro registra que tiene aproximadamente tantos ceros (tres) como unos (cinco), al igual que otras 55 cadenas de 8 bits (11111000, 11110100, 11110010, etc.), pero solo una cadena de 8 bits tiene ocho ceros. Porque el patrón tres-ceros-cinco-unos es más probable
que el patrón de ocho ceros, identificamos 11010110 como aleatorio y 00000000 como no aleatorio, y si un programa produce los bits 11010110, puede pensar que es aleatorio, incluso si no lo es. Por el contrario, si un programa aleatorio produce 00000000, probablemente dudará de que sea aleatorio.
Este ejemplo ilustra dos tipos de errores que las personas suelen cometer cuando
identifican la aleatoriedad:

Confundir la no aleatoriedad con la aleatoriedad Pensar que un objeto se genera aleatoriamente simplemente porque parece aleatorio.
Confundir aleatoriedad con no aleatoriedad Pensar que los patrones que aparecen por casualidad están ahí por una razón distinta a la casualidad.

La distinción entre apariencia aleatoria y realmente aleatoria es crucial. De hecho, en criptografía, la no aleatoriedad es a menudo sinónimo de inseguridad .

aleatoriedad como una distribucion de probabilidad

Cualquier proceso aleatorio se caracteriza por una distribución de probabilidad, que da todo lo que hay que saber sobre la aleatoriedad del proceso. Una distribución de probabilidad, o simplemente distribución, enumera los resultados de un proceso aleatorio donde a cada resultado se le asigna una probabilidad.
Una probabilidad mide la probabilidad de que ocurra un evento. Es expresada como un número real entre 0 y 1 donde una probabilidad 0 significa imposible y una probabilidad de 1 significa cierto. Por ejemplo, cuando alanzamos una moneda de dos caras, cada lado tiene una probabilidad de caer boca arriba de 1/2, y generalmente asumimos que aterrizar en el borde de la moneda tiene probabilidad cero.
Una distribución de probabilidad debe incluir todos los resultados posibles, de manera que la suma de todas las probabilidades es 1. Específicamente, si hay N eventos posibles,
hay N probabilidades:

p1, p2,. . . , pN con p1 + p2 +. . . + pN = 1

En el caso del lanzamiento de una moneda, la distribución es 1/2 para cara y 1/2 para cruz.

La suma de ambas probabilidades es igual a 1/2 + 1/2 = 1, porque la moneda caerá sobre una de sus dos caras. Una distribución uniforme ocurre cuando todas las probabilidades en la distribución son iguales, lo que significa que todos los resultados tienen la misma probabilidad de ocurrir. Sí hay N eventos, entonces cada evento tiene probabilidad 1/N. Por ejemplo, si una clave de 128 bits se elige uniformemente al azar, es decir, de acuerdo con una distribución uniforme, cada uno de los 2^128 claves posibles deben tener un
probabilidad de 1/(2^128). Por el contrario, cuando una distribución no es uniforme, las probabilidades no son todas iguales. Se dice que un lanzamiento de moneda con una distribución no uniforme está sesgado, y puede producir cara con probabilidad 1/4 y cruz con probabilidad 3/4, por ejemplo.

entropia. una medida de la incertidumbre

La entropía es la medida de incertidumbre o desorden en un sistema. Podrías ipensar en la entropía como la cantidad de sorpresa encontrada en el resultado de un proceso aleatorio: cuanto mayor es la entropía, menor es la certeza encontrada en el resultado.
Podemos calcular la entropía de una distribución de probabilidad. Si la distribución consiste en probabilidades p1, p2,. . . , pN, entonces su entropía es la suma negativa de todas las probabilidades multiplicada por su logaritmo, como se muestra
en esta expresión:

−p1 × log(p1) − p2 × log(p2) − … pN × log(pN)

Aquí, la función log es el logaritmo binario, o logaritmo en base dos. A diferencia del logaritmo natural, el logaritmo binario expresa la información en bits y produce valores enteros cuando las probabilidades son potencias de dos. Por ejemplo, log(1/2) = –1, log (1/4) = –2 y más generalmente log (1/2N) = –n. (Es por eso que en realidad tomamos la suma negativa para terminar con un número positivo). Las claves aleatorias de 128 bits producidas usando una distribución uniforme por lo tanto tienen la siguiente entropía:

2128 x (-2-128 x log(2-128)) = -log(2-128) = 128 bits

Si reemplaza 128 por cualquier número entero n, encontrará que la entropía de una cadena de n bits distribuida uniformemente será de n bits. La entropía se maximiza cuando la distribución es uniforme porque una distribución uniforme maximiza la incertidumbre: ningún resultado es más probable que los otros. Por lo tanto, los valores de n bits no pueden tener más de n bits de entropía.
Por la misma razón, cuando la distribución no es uniforme, la entropía es inferior. Considere el ejemplo del lanzamiento de una moneda. La entropía de un lanzamiento limpio es la siguiente:

-(1/2) x log(1/2) - (1/2) x log(1/2) = 1/2 + 1/2 = 1 bit

¿Qué pasa si una cara de la moneda tiene una mayor probabilidad de caer boca arriba?
Digamos que cara tiene una probabilidad de 1/4 y cruz de 3/4 (recuerde que la suma de todas las probabilidades debe ser 1). La entropía de un lanzamiento tan sesgado es la siguiente:

-(3/4) x log(3/4)-(1/4) x log(1/4) ≈ -(3/4) x (-0.415)-(1/4) x (-2) ≈ 0.81 bits

El hecho de que 0,81 sea menor que la entropía de 1 bit de un lanzamiento justo nos dice
que cuanto más sesgada es la moneda, menos uniforme es la distribución y la entropía es baja. Tomando este ejemplo más allá, si cara tiene una probabilidad de 1/10, la entropía es 0,469; si la probabilidad cae a 1/100, la la entropía cae a 0.081.

La entropía también puede verse como una medida de información. Por ejemplo, el resultado de un lanzamiento de moneda justo le da exactamente un bit de información: cara o cruz, y no puede predecir el resultado del lanzamiento de antemano. En el caso del lanzamiento injusto de una moneda, usted sabe de antemano que la cruz es más probable, por lo que normalmente puede predecir el resultado del sorteo. El resultado del lanzamiento de la moneda le brinda la información necesaria para predecir el resultado con certeza.

generadores de numeros aleatorios (rng) y generadores de numeros pseudoaleatorios (Prng)

Los criptosistemas necesitan aleatoriedad para ser seguros y, por lo tanto, necesitan un componente del cual obtener su aleatoriedad. El trabajo de este componente es devolver bits aleatorios cuando se le solicite. ¿Cómo hacer esta generación de aleatoriedad?Necesitarás dos cosas:
Una fuente de incertidumbre, o fuente de entropía, proporcionada por un generador de numeros aleatorio (RNG).
Un algoritmo criptográfico para producir bits aleatorios de alta calidad a partir de la fuente de la entropía. Esto se encuentra en los generadores de numeros pseudoaleatorios (PRNG). El uso de RNG y PRNG es la clave para hacer que la criptografía sea práctica y segura. Veamos brevemente cómo funcionan los RNG antes de explorar los PRNG en profundidad. La aleatoriedad proviene del entorno, que es analógico, caótico, incierto y, por tanto, impredecible. La aleatoriedad no puede ser generada solo por algoritmos basados ​​en computadora. En criptografía, la aleatoriedad suele proviene de generadores de números aleatorios (RNG), que son software o componentes de hardware que aprovechan la entropía en el mundo analógico para producir bits impredecibles en un sistema digital. Por ejemplo, un RNG podría muestrear directamente bits de mediciones de temperatura, acústica, turbulencia de aire o electricidad estática. Desafortunadamente, tales fuentes de entropía no siempre están disponibles y su entropía suele ser difícil de estimar. Los RNG también pueden recolectar la entropía en un sistema operativo en ejecución al obtener medidas de sensores conectados, dispositivos de E/S, red o actividad de disco, registros del sistema, procesos en ejecución y actividades del usuario, como pulsaciones de teclas y movimiento del mouse. Tales actividades generadas por el sistema y por el hombre pueden ser una buena fuente de entropía, pero pueden ser frágiles y manipuladas por un atacante. Además, son lentos para producir bits aleatorios. Los generadores cuánticos de números aleatorios (QRNG) son un tipo de RNG que se basan en la aleatoriedad que surge de los fenómenos de la mecánica cuántica como la desintegración radiactiva, las fluctuaciones del vacío y la observación de la polarizacion de fotones. Estos pueden proporcionar aleatoriedad real, en lugar de solo aleatoriedad aparente. Sin embargo, en la práctica, los QRNG pueden estar sesgados y no producen bits rápidamente; como las fuentes de entropía citadas anteriormente, necesitan un componente adicional para producir de forma fiable a alta velocidad. Los generadores de números pseudoaleatorios (PRNG) abordan el desafío que enfrentamos en generar aleatoriedad mediante la producción confiable de muchos bits de unos pocos bits aleatorios verdaderos. Por ejemplo, un RNG que se traduce los movimientos del mouse a bits aleatorios dejarían de funcionar si dejas de mover el mouse, mientras que un PRNG siempre devuelve bits pseudoaleatorios cuando se solicita hacerlo. Los PRNG se basan en los RNG pero se comportan de manera diferente: los RNG producen bits aleatorios de forma relativamente lenta de fuentes analógicas, en una manera no determinista, y sin garantía de alta entropía. Por el contrario, los PRNG producen bits de aspecto aleatorio rápidamente de fuentes digitales, de forma determinista, y con máxima entropía. Esencialmente, los PRNG transforman algunos bits aleatorios no confiables en un flujo largo de bits pseudoaleatorios confiables adecuadso para aplicaciones criptográficas, como se muestra aqui:

Como funcionan los prng

Un PRNG recibe bits aleatorios de un RNG a intervalos regulares y los utiliza para actualizar el contenido de un búfer de memoria grande, llamado pool de entropía . El pool de entropía es la fuente de entropía del PRNG, al igual que el entorno físico lo es para un RNG. Cuando el PRNG actualiza el pool de entropía, mezcla los bits del pool para ayudar a eliminar cualquier sesgo estadístico.

Para generar bits pseudoaleatorios, el PRNG ejecuta un algoritmo generador de bits aleatorios determinista (DRBG) que expande algunos bits del grupo de entropía en una secuencia mucho más larga. Como su nombre sugiere, un DRBG es determinista, no aleatorio: dada una entrada, siempre obtendrá el mismo resultado. El PRNG asegura que su DRBG nunca recibe la misma entrada dos veces, para generar una secuencia unica pseudoaleatoria. En el curso de su labor, el PRNG realiza tres operaciones, como sigue:

• init () Inicializa el poolde entropía y el estado interno del PRNG
• refresh (R) Actualiza el pool de entropía usando algunos datos, R, generalmente procedente de un RNG
• next (N) Devuelve N bits pseudoaleatorios y actualiza el pool de entropía

La operación init() restablece el PRNG a un estado nuevo, reinicia el
pool de entropía a algún valor predeterminado, e inicializa cualquier variable o
búferes de memoria utilizados por el PRNG para realizar la actualización y la siguientes
operaciones. La operación refresh(R) a menudo se denomina reseed y su argumento R es llamado semilla. Cuando no hay ningún RNG disponible, las semillas pueden ser valores únicos codificados en un sistema de codificacion. Normalmente, la operación de actualización la llama el sistema operativo, mientras que next() es normalmente llamado o solicitado por las aplicaciones. La operacion next() la ejecuta el DRBG y modifica el
pool de entropía para asegurar que next() producirá diferentes bits pseudoaleatorios.

preocupaciones de seguridad

Hablemos brevemente sobre la forma en que los PRNG abordan algunas preocupaciones de seguridad. Específicamente, los PRNG deben garantizar la resistencia backtracking y la resistencia a la predicción. Resistencia backtracking (también llamada fordward secrecy) significa que los bits generados previamente son imposibles de recuperar, mientras que la resistencia a la predicción (ordward secrecy) significa que en el futuro los bits deberían ser imposibles de predecir.

Para lograr la resistencia backtracking, el PRNG debe garantizar que las transformaciones realizadas al actualizar el estado a través de refresh() y las próximas operaciones son irreversibles, de modo que si un atacante compromete el sistema y obtiene el valor del pool de entropía, no pueden determinar los valores previos del pool o los bits generados previamente. Para lograr la resistencia a la predicción, el PRNG debe llamar a refresh()
regularmente con valores de R que son desconocidos para un atacante y que son difícil de adivinar, lo que evita que un atacante determine en el futuro valores del pool de entropía, incluso si todo el grupo está comprometido. (Incluso si se conociera la lista de valores de R utilizados, necesitaría conocer el orden en qué refresh() y next() se realizaron para reconstruir la pool).

el prng fortuna

Fortuna es una construcción PRNG utilizada en Windows y originalmente diseñada en 2003 de Niels Ferguson y Bruce Schneier. Fortuna reemplazó a Milenrama, un diseño de 1998 de Kelsey y Schneier que ahora se usa en macOS e iOS. No proporcionaremos la especificación de Fortuna aquí ni se mostrara cómo implementarlo, pero intentaremos explicar cómo funciona. La memoria interna de Fortuna incluye lo siguiente:

1. Treinta y dos pools de entropía, P₁, P₂,. . . , P₃₂, de modo que P_i se utiliza cada 2ⁱ reseeds.
2. Una clave, K, y un contador, C (ambos de 16 bytes). Estos forman el estado interno de la DRBG de Fortuna

En términos más simples, Fortuna funciona así:

1. init() establece K y C en cero y vacía los 32 grupos de entropía P_i, donde i = 1. . . 32.

2. refresh(R) agrega los datos, R, a uno de los pools de entropía. El sistema elige los RNG utilizados para producir valores R y debe llamar a refresh() con regularidad.

3. next (N) actualiza K usando datos de uno o más pools de entropía, donde la elección de los pools de entropía depende principalmente de cuántas actualizaciones de K ya se han realizado. Los N bits solicitados se producen luego cifrando C usando K como clave. Si cifrar C no es suficiente, Fortuna cifra C + 1, luego C + 2, y así sucesivamente, para obtener suficientes bits.

Aunque las operaciones de Fortuna parecen bastante simples, implementarlas correctamente es difícil. Por un lado, necesita obtener todos los detalles del algoritmo correctamente, es decir, cómo se eligen los pools de entropía, el tipo de cifrado que se usará en el siguiente, cómo comportarse cuando no se recibe entropía, etc. Aunque las especificaciones definen la mayoría de los detalles, no incluyen un conjunto de pruebas completo para verificar que una implementación sea correcta, lo que dificulta garantizar que su implementación de Fortuna se comporte como se esperaba.

Incluso si Fortuna se implementa correctamente, las fallas de seguridad pueden ocurrir por razones distintas al uso de un algoritmo incorrecto. Por ejemplo, Fortuna podría no darse cuenta que los RNG no producen suficientes bits aleatorios y, como resultado, Fortuna producirá bits pseudoaleatorios de menor calidad, o puede dejar de entregar bits pseudoaleatorios por completo.

Otro riesgo inherente a las implementaciones de Fortuna radica en la posibilidad de exponer los archivos seeds asociados a los atacantes. Los datos en los archivos seeds de Fortuna se utilizan para alimentar la entropía a Fortuna a través de llamadas refresh cuando un RNG no está disponible de inmediato, como inmediatamente después de reiniciar el sistema y antes de que los RNG del sistema hayan registrado eventos impredecibles. Sin embargo, si se usa dos veces un archivo seed idéntico, Fortuna producirá la misma secuencia de bits dos veces. Por lo tanto, los archivos seed deben borrarse después de usarse para asegurarse de que no se reutilicen.

Finalmente, si dos instancias de Fortuna están en el mismo estado porque comparten un archivo seed (lo que significa que comparten los mismos datos en los grupos de entropía, incluidos los mismos C y K), la siguiente operación devolverá los mismos bits en ambos instancias.

prng criptograficos Vs prng no criptograficos

Hay PRNG criptográficos y no criptográficos. Los PRNG no criptográficos están diseñados para producir distribuciones uniformes para aplicaciones como simulaciones científicas o videojuegos. Sin embargo, nunca debe usar PRNG que no sean criptográficos en aplicaciones criptográficas, porque son inseguras; solo les preocupa la calidad de la distribución de probabilidad de los bits y no su previsibilidad. Los PRNG criptográficos, por otro lado, son impredecibles, porque también están preocupados por la solidez de las operaciones subyacentes que se utilizan para entregar bits bien distribuidos.

Desafortunadamente, la mayoría de los PRNG expuestos por los lenguajes de programación, como libc’s rand y drand48, PHP’s rand y mt_rand, el módulo ramdom de Python, la clase random de Ruby, etc., no son criptográficos. La configuración predeterminada de un PRNG no criptográfico es una receta para el desastre porque a menudo termina usándose en aplicaciones criptográficas, así que asegúrese de usar solo PRNG criptográficos en aplicaciones criptográficas.

Un PRNG no criptográfico popular: Mersenne twister

El algoritmo Mersenne Twister (MT) es un PRNG no criptográfico que se utiliza (en el momento de escribir este post) en PHP, Python, R, Ruby y muchos otros sistemas. MT generará bits aleatorios distribuidos uniformemente sin sesgo estadístico, pero es predecible: dados algunos bits producidos por MT, es bastante fácil saber qué bits seguirán.

Miremos desde el punto de vista matemático para ver qué hace que Mersenne Twister sea inseguro. El algoritmo MT es mucho más simple que el de los PRNG criptográficos: su estado interno es una matriz, S, que consta de 624 palabras de 32 bits. Esta matriz se establece inicialmente en S1, S2,. . . , S624 y evoluciona a S2,. . . , S625, luego S3,. . . , S626, y así sucesivamente, de acuerdo con esta ecuación:

Sk + 624 = Sk + 397 ⊕ A((Sk ∧ 0x80000000) ∨ (Sk + 1 ∧ 0xfffffff))

Aquí, ⊕ denota el XOR bit a bit (^ en el lenguaje de programación C), ∧ denota el AND bit a bit (& en C), ∨ denota el OR bit a bit (| en C), y A es una función que transforma una palabra de 32 bits , x, a (x >> 1), si el bit más significativo de x es 0, o a (x >> 1) ⊕ 0x9908b0df en caso contrario.

Observe en esta ecuación que los bits de S interactúan entre sí solo a través de XOR. Los operadores ∧ y ∨ nunca combinan dos bits de S juntos, sino solo bits de S con bits de las constantes 0x80000000 y 0x7fffffff. De esta forma, cualquier bit de S625 puede expresarse como un XOR de bits de S398, S1 y S2, y cualquier bit de cualquier estado futuro puede expresarse como una combinación XOR de bits del estado inicial S1,. . . , S624. (Cuando expresas, digamos, S228 + 624 = S852 en función de S625, S228 y S229, puedes a su vez reemplazar S625 por su expresión en términos de S398, S1 y S2).

Debido a que hay exactamente 624 × 32 = 19,968 bits en el estado inicial (o 624 palabras de 32 bits), cualquier bit de salida puede expresarse como una ecuación con un máximo de 19,969 términos (19,968 bits más un bit constante). Eso es solo alrededor de 2.5 kilobytes de datos. Lo contrario también es cierto: los bits del estado inicial se pueden expresar como un XOR de bits de salida.

inseguridad por linealidad

A una combinación XOR de bits la llamamos combinación lineal. Por ejemplo, si X, Y y Z son bits, entonces la expresión X ⊕ Y ⊕ Z es una combinación lineal, mientras que (X ∧ Y) ⊕ Z no lo es porque hay un Y (∧). Si cambias un bit de X en X ⊕ Y ⊕ Z, entonces el resultado también cambia, independientemente del valor de Y y Z. Por el contrario, si cambias un bit de X en (X ∧ Y) ⊕ Z, el resultado cambia solo si el bit de Y en la misma posición es 1. El resultado es que las combinaciones lineales son predecibles, porque no es necesario conocer el valor de los bits para predecir cómo un cambio en su valor afectará el resultado .

A modo de comparación, si el algoritmo MT fuera criptográficamente fuerte, sus ecuaciones serían no lineales e involucrarían no solo bits individuales sino también combinaciones Y (productos) de bits, como S₁S₁₅S₁₈₂ o S₁₇S₂₅₆S₂₅₇S₃₅₄S₄₉₈S₆₀₁. Aunque las combinaciones lineales de esos bits incluyen como máximo 624 variables, las combinaciones no lineales permiten hasta 2624 variables. Sería imposible de resolver, y mucho menos escribir todas estas ecuaciones. (Tenga en cuenta que 2305, un número mucho menor, es la capacidad de información estimada del universo observable).

La clave aquí es que las transformaciones lineales dan lugar a ecuaciones cortas (comparables en tamaño al número de variables), que son fáciles de resolver, mientras que las transformaciones no lineales dan lugar a ecuaciones de tamaño exponencial, que son prácticamente irresolubles. Por tanto, el juego de los criptógrafos consiste en diseñar algoritmos PRNG que emulen transformaciones no lineales tan complejas utilizando solo un pequeño número de operaciones simples.

La linealidad es solo uno de los muchos criterios de seguridad. Aunque es necesario, la no linealidad por sí sola no hace que un PRNG sea criptográficamente seguro.

La inutilidad de las pruebas estadísticas

Los conjuntos de pruebas estadísticas como TestU01, Diehard o el conjunto de pruebas del Instituto Nacional de Estándares y Tecnología (NIST) son una forma de probar la calidad de bits pseudoaleatorios. Estas pruebas toman una muestra de bits pseudoaleatorios producidos por un PRNG (digamos, un megabyte de valor), calculan algunas estadísticas sobre la distribución de ciertos patrones en los bits y comparan los resultados con los resultados típicos obtenidos para una distribución perfecta y uniforme. Por ejemplo, algunas pruebas cuentan el número de 1 bits frente al número de 0 bits, o la distribución de patrones de 8 bits. Pero las pruebas estadísticas son en gran medida irrelevantes para la seguridad criptográfica, y es posible diseñar un PRNG criptográficamente débil que engañará a cualquier prueba estadística.

Cuando ejecuta pruebas estadísticas con datos generados aleatoriamente, normalmente verá un montón de indicadores estadísticos como resultado. Suelen ser valores p, un indicador estadístico común. Estos resultados no siempre son fáciles de interpretar porque rara vez son tan simples como aprobados o reprobados. Si sus primeros resultados parecen anormales, no se preocupe: pueden ser el resultado de alguna desviación accidental o puede que esté analizando muy pocas muestras. Para asegurarse de que los resultados que ve son normales, compárelos con los obtenidos para una muestra confiable de idéntico tamaño; por ejemplo, uno generado con el kit de herramientas OpenSSL usando el siguiente comando:

$ openssl rand <number of bytes> -out <output file>

prng en el mundo real

Dirijamos nuestra atención a cómo implementar PRNG en el mundo real. Encontrará PRNG criptográficas en los sistemas operativos de la mayoría de las plataformas, desde computadoras de escritorio y portátiles hasta sistemas integrados como enrutadores y decodificadores, así como máquinas virtuales, teléfonos móviles, etc. La mayoría de estos PRNG se basan en software, pero algunos son hardware puro. Esos PRNG son utilizados por aplicaciones que se ejecutan en el sistema operativo y, a veces, otros PRNG que se ejecutan sobre bibliotecas o aplicaciones criptográficas.

A continuación, veremos los PRNG más implementados: el de Linux, Android y muchos otros sistemas basados en Unix; el de Windows; y el de los microprocesadores Intel recientes, que se basa en hardware.

generando bits aleatorios en sistemas basados en unix

El archivo de dispositivo /dev/urandom es la interfaz de usuario para el PRNG criptográfico de los sistemas unix comunes, y es lo que normalmente utilizará para generar bits aleatorios fiables. Debido a que es un archivo de dispositivo, la solicitud de bits aleatorios de /dev/urandom se realiza leyéndolo como un archivo. Por ejemplo, el siguiente comando usa /dev/urandom para escribir 10 MB de bits aleatorios en un archivo:

 $ dd if=/dev/urandom of=<output file> bs=1M count=10

manera erronea de usar /dev/urandom

Podría escribir un programa C inseguro como el que se muestra abajo para leer bits aleatorios y esperar lo mejor, pero eso sería una mala idea.

int random_bytes_insecure(void *buf, size_t len)
{
    int fd = open("/dev/urandom", O_RDONLY);
    read(fd, buf, len);
    close(fd);
    return 0;
}

Este código es inseguro; ni siquiera comprueba los valores de retorno de open () y read (), lo que significa que su búfer aleatorio esperado podría terminar lleno de ceros o dejarse sin cambios.

manera segura de usar /dev/urandom

int random_bytes_safer(void *buf, size_t len)
{
    struct stat st;
    size_t i;
    int fd, cnt, flags;
    int save_errno = errno;

start:
    flags = O_RDONLY;
#ifdef O_NOFOLLOW
    flags |= O_NOFOLLOW;
#endif
#ifdef O_CLOEXEC
    flags |= O_CLOEXEC;
#endif
    fd = ❶open("/dev/urandom", flags, 0);
    if (fd == -1) {
        if (errno == EINTR)
            goto start;
        goto nodevrandom;
    }
#ifndef O_CLOEXEC
    fcntl(fd, F_SETFD, fcntl(fd, F_GETFD) | FD_CLOEXEC);
#endif
    /* Lightly verify that the device node looks sane */
    if (fstat(fd, &st) == -1 || !S_ISCHR(st.st_mode)) {
        close(fd);
        goto nodevrandom;
    }
    if (ioctl(fd, RNDGETENTCNT, &cnt) == -1) {
        close(fd);
        goto nodevrandom;
    }
    for (i = 0; i < len; ) {
        size_t wanted = len - i;
        ssize_t ret = ❷read(fd, (char *)buf + i, wanted);
        if (ret == -1) {
            if (errno == EAGAIN || errno == EINTR)
                continue;
            close(fd);
            goto nodevrandom;
        }
        i += ret;
    }
    close(fd);
    if (gotdata(buf, len) == 0) {
        errno = save_errno;
        return 0;                 /* satisfied */
    }
nodevrandom:
    errno = EIO;
    return -1;
}

A diferencia del listado anterior, este listado realiza varias comprobaciones. Compare, por ejemplo, la llamada a open () en ❶ y la llamada a read () en ❷ con las del anterior listado: notará que el código más seguro verifica los valores de retorno de esas funciones y, en caso de falla, se cierra el descriptor de archivo y devuelve –1

Diferencias entre /dev/urandom y /dev/random en Linux

Las diferentes versiones de Unix usan diferentes PRNG. El PRNG de Linux, definido en drivers/char/random.c en el kernel de Linux, utiliza principalmente la función hash SHA-1 para convertir bits de entropía sin procesar en bits pseudoaleatorios confiables. El PRNG recolecta entropía de varias fuentes (incluido el teclado, el mouse, el disco y los tiempos de interrupción) y tiene un grupo de entropía principal de 512 bytes, así como un grupo de no bloqueo para /dev/urandom y un grupo de bloqueo para /dev/random.

¿Cuál es la diferencia entre /dev/urandom y /dev/random? La historia corta es que /dev/random intenta estimar la cantidad de entropía y se niega a devolver bits si el nivel de entropía es demasiado bajo. Aunque esto puede parecer una buena idea, no lo es. Por un lado, los estimadores de entropía son notoriamente poco fiables y pueden ser engañados por los atacantes (que es una de las razones por las que Fortuna abandonó la estimación de entropía de Yarrow). Además, /dev/random se queda sin entropía estimada con bastante rapidez, lo que puede producir una condición de denegación de servicio, lo que ralentiza las aplicaciones que se ven obligadas a esperar más entropía. El resultado es que, en la práctica, /dev/random no es mejor que /dev/urandom y crea más problemas de los que resuelve.

Estimando la entropía de /dev /random

Puede observar cómo evoluciona la estimación de entropía de /dev/random leyendo su valor actual en bits en /proc/sys/kernel /random/entropy_avail en Linux. Por ejemplo, el script de shell que se muestra en el listado de abajo primero minimiza la estimación de entropía leyendo 4 KB de /dev/random, espera hasta que alcanza una estimación de 128 bits, lee 64 bits de /dev/random y luego muestra la nueva estimar. Al ejecutar el script, observe cómo la actividad del usuario acelera la recuperación de la entropía (los bytes leídos se imprimen en la salida estándar codificada en base64).

#!/bin/sh
ESTIMATE=/proc/sys/kernel/random/entropy_avail
timeout 3s dd if=/dev/random bs=4k count=1 2> /dev/null | base64
ent=`cat $ESTIMATE`
while [ $ent -lt 128 ]
do
    sleep 3
    ent=`cat $ESTIMATE`
    echo $ent
done
dd if=/dev/random bs=8 count=1 2> /dev/null | base64
cat $ESTIMATE

Una ejecución de muestra del listado anterior dio el resultado que se muestra en abajo (Adivina cuándo comencé a mover el mouse al azar y presionar el teclado para acumular entropía).

xFNX/f2R87/zrrNJ6Ibr5R1L913tl+F4GNzKb60BC+qQnHQcyA==
2
18
19
27
28
72
124
193
jq8XWCt8
129

Como puede ver en arriba, tenemos 193 – 64 = 129 bits de entropía restantes en el pool, según el estimador de /dev /random. ¿Tiene sentido considerar que un PRNG tiene N bits menos de entropía solo porque se leyeron N bits del PRNG? (Spoiler: no es así).

Como /dev/random, la llamada al sistema getrandom() de Linux se bloquea si no ha reunido suficiente entropía inicial. Sin embargo, a diferencia de /dev/random, no intentará estimar la entropía en el sistema y nunca se bloqueará después de su etapa de inicialización.

La función CryptGenRandom en Windows

En Windows, la interfaz de área de usuario heredada para el PRNG del sistema es la función CryptGenRandom() de la interfaz de programación de aplicaciones (API) de criptografía. La función CryptGenRandom() se ha reemplazado en versiones recientes de Windows con la función BcryptGenRandom() en la API de criptografía, API de próxima generación (CNG). El PRNG de Windows toma la entropía del controlador en modo kernel cng.sys (anteriormente ksecdd.sys), cuyo colector de entropía se basa libremente en Fortuna. Como suele ocurrir en Windows, el proceso es complicado.

El Listado de abajo muestra una invocación típica de C ++ de CryptGenRandom() con las comprobaciones necesarias.

int random_bytes(unsigned char *out, size_t outlen)
{
    static HCRYPTPROV handle = 0; /* only freed when the program ends */
    if(!handle) {
        if(!CryptAcquireContext(&handle, 0, 0, PROV_RSA_FULL,
                            CRYPT_VERIFYCONTEXT | CRYPT_SILENT)) {
            return -1;
        }
    }
    while(outlen > 0) {
        const DWORD len = outlen > 1048576UL ? 1048576UL : outlen;
        if(!CryptGenRandom(handle, len, out)) {
            return -2;
        }
        out    += len;
        outlen -= len;
    }
    return 0;
}

Observe en el Listado de arriba que antes de llamar al PRNG real, debe declarar un proveedor de servicios criptográficos (HCRYPTPROV) y luego adquirir un contexto criptográfico con CryptAcquireContext(), lo que aumenta las posibilidades de que las cosas salgan mal. Por ejemplo, se descubrió que la versión final del software de cifrado TrueCrypt llamaba a CryptAcquireContext() de una manera que podía fallar silenciosamente, lo que provocaba una aleatoriedad subóptima sin notificar al usuario. Afortunadamente, la interfaz BCryptGenRandom() más nueva para Windows es mucho más simple y no requiere que el código abra explícitamente un identificador (o al menos hace que sea mucho más fácil de usar sin un identificador).

Un PRNG basado en hardware: RDRAND en microprocesadores Intel

Hasta ahora solo hemos hablado de los PRNG de software, así que echemos un vistazo a uno de hardware. El Generador de números aleatorios digitales de Intel es un PRNG de hardware introducido en 2012 en la microarquitectura Ivy Bridge de Intel, y se basa en las pautas SP 800-90 de NIST con el Estándar de cifrado avanzado (AES) en modo CTR_DRBG. Se accede al PRNG de Intel a través de la instrucción en ensamblador RDRAND, que ofrece una interfaz independiente del sistema operativo y, en principio, es más rápida que los PRNG de software.

Mientras que los PRNG de software intentan recopilar entropía de fuentes impredecibles, RDRAND tiene una única fuente de entropía que proporciona un flujo en serie de datos de entropía como ceros y unos. En términos de ingeniería de hardware, esta fuente de entropía es un latch diferencial doble con retroalimentación; esencialmente, un pequeño circuito de hardware que salta entre dos estados (0 o 1) dependiendo de las fluctuaciones del ruido térmico, a una frecuencia de 800 MHz. Este tipo de cosas suele ser bastante confiable.

La instrucción de ensamblaje RDRAND toma como argumento un registro de 16, 32 o 64 bits y luego escribe un valor aleatorio. Cuando se invoca, RDRAND establece el indicador de acarreo en 1 si el conjunto de datos en el registro de destino es un valor aleatorio válido, y en 0 en caso contrario, lo que significa que debe asegurarse de verificar el indicador CF si escribe código ensamblador directamente.

El framework PRNG de Intel proporciona una instrucción ensamblador distinta de RDRAND: la instrucción de ensamblador RDSEED devuelve bits aleatorios directamente de la fuente de entropía, después de algún acondicionamiento o procesamiento criptográfico. Está destinado a poder alimentar a otros PRNG.

El PRNG de Intel está solo parcialmente documentado, pero se basa en estándares conocidos y ha sido auditado por la reconocida empresa Cryptography Research (consulte su informe titulado «Análisis del generador de números aleatorios digitales Ivy Bridge de Intel»). No obstante, ha habido algunas preocupaciones sobre su seguridad, especialmente después de las revelaciones de Snowden sobre las puertas traseras criptográficas, y los PRNG son de hecho el objetivo perfecto para el sabotaje. Si está preocupado pero aún desea usar RDRAND o RDSEED, simplemente mézclelos con otras fuentes de entropía. Hacerlo evitará la explotación efectiva de una puerta trasera hipotética en el hardware de Intel o en el microcódigo asociado en todos los escenarios excepto en los más inverosímiles.

cosas que pueden ir mal

Para concluir, presentaré algunos ejemplos de fallas de aleatoriedad. Hay innumerables ejemplos para elegir, pero he elegido cuatro que son lo suficientemente simples como para comprender e ilustrar diferentes problemas.

fuentes de entropia pobres

En 1996, la implementación SSL del navegador Netscape estaba computando seeds PRNG de 128 bits de acuerdo con el pseudocódigo que se muestra en el Listado de abajo , copiado de la página de Goldberg y Wagner en http://www.cs.berkeley.edu/~daw/papers/ddj-netscape.html.

global variable seed;

   RNG_CreateContext()
       (seconds, microseconds) = time of day; /* Time elapsed since 1970 */
       pid = process ID;  ppid = parent process ID;
       a = mklcpr(microseconds);
    ➊ b = mklcpr(pid + seconds + (ppid << 12));
      seed = MD5(a, b); /* Derivation of a 128-bit value using the hash MD5 */

   mklcpr(x) /* not cryptographically significant; shown for completeness */
       return ((0xDEECE66D * x + 0x2BBB62DC) >> 1);

   MD5() /* a very good standard mixing function, source omitted */

El problema aquí es que los PID y los microsegundos son valores adivinables. Suponiendo que puede adivinar el valor de los segundos, microsegundos tiene solo 106 valores posibles y, por lo tanto, una entropía de log (106), o aproximadamente 20 bits. El ID de proceso (PID) y el ID de proceso principal (PPID) son valores de 15 bits, por lo que esperaría 15 + 15 = 30 bits de entropía adicionales. Pero si observa cómo se calcula b en ❶, verá que la superposición de tres bits produce una entropía de solo 15 + 12 = 27 bits, para una entropía total de solo 47 bits, mientras que una seed de 128 bits debe tener 128 bits de entropía.

insificiente entropia en tiempo de arranque

En 2012, los investigadores analizaron todo Internet y recopilaron claves públicas de certificados TLS y hosts SSH. Descubrieron que un puñado de sistemas tenían claves públicas idénticas y, en algunos casos, claves muy similares (a saber, claves RSA con factores primos compartidos): en resumen, dos números, n = pq y n ′ = p′q ′, con p = p ′, mientras que normalmente todos los ps y qs deberían ser diferentes en valores de módulo distintos.

Después de una mayor investigación, resultó que muchos dispositivos generaban su clave pública temprana, en el primer arranque, antes de haber recolectado suficiente entropía, a pesar de usar un PRNG decente (típicamente /dev/urandom). Los PRNG en diferentes sistemas terminaron produciendo bits aleatorios idénticos debido a una misma fuente de entropía base (por ejemplo, una seed codificada).

En un nivel alto, la presencia de claves idénticas se debe a esquemas de generación de claves como el siguiente, en pseudocódigo:

prng.seed(seed)
p = prng.generate_random_prime()
q = prng.generate_random_prime()
n = p*q

Si dos sistemas ejecutan este código con una semilla idéntica, producirán la misma p, la misma q y, por lo tanto, la misma n.

La presencia de primos compartidos en diferentes claves se debe a esquemas de generación de claves donde se inyecta entropía adicional durante el proceso, como se muestra aquí:

prng.seed(seed)
p = prng.generate_random_prime()
prng.add_entropy()
q = prng.generate_random_prime()
n = p*q

Si dos sistemas ejecutan este código con la misma semilla, producirán la misma p, pero la inyección de entropía a través de prng.add_entropy() asegurará qs distintas.

El problema con los factores primos compartidos es que, dado n = pq y n ′ = pq ′, es trivial recuperar el p compartido calculando el máximo común divisor (MCD) de n y n ′. Para obtener más información, consulte el artículo «Mining Your Ps and Qs» de Heninger, Durumeric, Wustrow y Halderman, disponible en https://factorable.net/.

prng no criptograficos

Anteriormente discutimos la diferencia entre los PRNG criptográficos y no criptográficos y por qué estos últimos nunca deberían usarse para aplicaciones criptográficas. Por desgracia, muchos sistemas pasan por alto ese detalle, así que pensé que debería darte al menos uno de esos ejemplos.

La popular aplicación MediaWiki se ejecuta en Wikipedia y muchas otras wikis. Utiliza la aleatoriedad para generar elementos como tokens de seguridad y contraseñas temporales, que por supuesto deberían ser impredecibles. Desafortunadamente, una versión ahora obsoleta de MediaWiki utilizó un PRNG no criptográfico, el Mersenne Twister, para generar estos tokens y contraseñas. Aquí hay un fragmento del código fuente vulnerable de MediaWiki. Busque la función llamada para obtener un bit aleatorio y asegúrese de leer los comentarios.

/**
         * Generate a hex-y looking random token for various uses.
         * Could be made more cryptographically sure if someone cares.
         * @return string
         */
function generateToken( $salt = '' ) {
    $token = dechex(mt_rand()).dechex(mt_rand());
    return md5( $token . $salt );
}

¿Advirtió mt_rand() en el código anterior? Aquí, mt significa Mersenne Twister, el PRNG no criptográfico discutido anteriormente. En 2012, los investigadores mostraron cómo explotar la predictibilidad de Mersenne Twister para predecir tokens futuros y contraseñas temporales, con un par de tokens de seguridad. MediaWiki fue parcheado para usar un PRNG criptográfico.

Error de muestreo con fuerte aleatoriedad

El siguiente error muestra cómo incluso un PRNG criptográfico fuerte con suficiente entropía puede producir una distribución sesgada. El programa de chat Cryptocat fue diseñado para ofrecer una comunicación segura. Utilizaba una función que intentaba crear una cadena distribuida uniformemente de dígitos decimales, es decir, números en el rango de 0 a 9. Sin embargo, simplemente tomar bytes aleatorios módulo 10 no produce una distribución uniforme, porque cuando se toman todos los números entre 0 y 255 y reduciéndolos módulo 10, no obtienes un número igual de valores de 0 a 9.

Cryptocat hizo lo siguiente para abordar ese problema y obtener una distribución uniforme:

Cryptocat.random = function() {
    var x, o = '';
    while (o.length < 16) {
         x = state.getBytes(1);
         if (x[0] <= 250) {
             o += x[0] % 10;
         }
     }
    return parseFloat('0.' + o)
}

Y eso fue casi perfecto. Al tomar solo los números hasta un múltiplo de 10 y descartar otros, esperaría una distribución uniforme de los dígitos del 0 al 9. Desafortunadamente, hubo un error de uno por uno en la condición if. Te dejaré los detalles como ejercicio. Debería encontrar que los valores generados tenían una entropía de 45 en lugar de aproximadamente 53 bits (pista: <= debería haber sido < en su lugar).

mas alla

En este pots, acabo de arañar la superficie de la aleatoriedad en la criptografía. Hay mucho más que aprender sobre la teoría de la aleatoriedad, incluidos temas como diferentes nociones de entropía, extractores de aleatoriedad e incluso el poder de la aleatorización y la desaleatorización en la teoría de la complejidad. Para obtener más información sobre los PRNG y su seguridad, lea el artículo clásico de 1998 «Ataques criptoanalíticos en generadores de números pseudoaleatorios» de Kelsey, Schneier, Wagner y Hall. Luego mire la implementación de PRNG en sus aplicaciones favoritas e intente encontrar sus debilidades. (Busque en línea «error generador aleatorio» para encontrar muchos ejemplos).

Sin embargo, no hemos terminado con la aleatoriedad. Lo encontraremos una y otra vez a lo largo de los posts, y descubrirá las muchas formas en que ayuda a construir sistemas seguros.