¿Se utilizan teóricamente generadores pseudoaleatorios sólidos en la práctica?

17

Hasta donde yo sé, la mayoría de las implementaciones de generación de números pseudoaleatorios en la práctica utilizan métodos como los registros de retroalimentación de desplazamiento lineal (LSFR) o estos algoritmos "Mersenne Twister". Si bien pasan muchas pruebas estadísticas (heurísticas), no hay garantías teóricas de que parezcan pseudoaleatorias para, por ejemplo, todas las pruebas estadísticas computables de manera eficiente. Sin embargo, estos métodos se usan indiscriminadamente en todo tipo de aplicaciones, desde protocolos criptográficos hasta computación científica y banca (probablemente). Me parece un poco preocupante que tengamos poca o ninguna garantía sobre si estas aplicaciones funcionan según lo previsto (porque cualquier tipo de análisis probablemente habría asumido una aleatoriedad verdadera como entrada).

Por otro lado, la teoría de la complejidad y la criptografía proporcionan una teoría muy rica de pseudoaleatoriedad, e incluso tenemos construcciones candidatas de generadores pseudoaleatorios que engañarían CUALQUIER prueba estadística eficiente que se te ocurra, utilizando funciones candidatas de una vía.

Mi pregunta es: ¿esta teoría ha llegado a la práctica? Espero que para usos importantes de la aleatoriedad, como la criptografía o la computación científica, se utilicen PRG teóricamente sólidos.

Por otro lado, pude encontrar un análisis limitado de qué tan bien funcionan los algoritmos populares, como el método de clasificación rápida, cuando se usan LSFR como fuente de aleatoriedad, y aparentemente funcionan bien. Ver "Algoritmos aleatorios y números pseudoaleatorios" de Karloff y Raghavan .

Henry Yuen
fuente
3
Incluso hay un PRG universal: es seguro si existen PRG seguros.
¿Te refieres a los PRG criptográficos? Si es así, ¿no sabemos que los PRG (criptográficos) son equivalentes a los OWF?
Henry Yuen
2
Si. Dividir la semilla bits en aproximadamente k bloques de aproximadamentek bits cada uno, correklas primeras [número de bloques] máquinas de Turing en los bloques correspondientes para hasta pasos,k2 rellenar las salidas a k+1 bits, y genera el xor de esas salidas de TM. (Al igual que la búsqueda universal de Levin, esto no se puede usar en la práctica).
1
quizás más relevantes para la práctica son los resultados relacionados con la aleatoriedad requerida para el hash: desde las familias de independencia limitadas clásicas hasta resultados más recientes como Mitzenmacher-Vadhan (la independencia por pares + alguna entropía en la entrada proporciona pseudoaleatoriedad suficiente para sondeo lineal y filtros de floración) o el Patrascu -Thorup resultados en tabulación hash.
Sasho Nikolov
1
"Sin embargo, estos métodos se usan indiscriminadamente en todo tipo de aplicaciones, desde protocolos criptográficos ...". Espero que no. Los Twers de Mersenne no deben usarse para la criptografía, ya que no son criptográficamente fuertes, aunque pueden existir variantes .
Mike Samuel

Respuestas:

13

La noción de generadores pseudoaleatorios "teóricamente sólidos" no está realmente bien definida. Después de todo, ningún generador pseudoaleatorio tiene una prueba de seguridad. No sé si podemos decir que un generador pseudoaleatorio basado en la dureza de factorizar enteros grandes es "más seguro" que, por ejemplo, usar AES como un generador pseudoaleatorio. (De hecho, existe la sensación de que es menos seguro, ya que conocemos algoritmos de factorización cuántica pero no algoritmos cuánticos para romper AES).

De lo que sí tenemos pruebas matemáticas es de varios resultados de composición, que dicen que si compones cifrados de bloque o funciones hash de ciertas maneras, puedes obtener generadores pseudoaleatorios o función pseudoaleatoria. Algunos de estos resultados se usan ampliamente en la práctica, por ejemplo, HMAC . Pero es cierto que los resultados que alcanzan un PRG y comienzan con solo suponer que el componente básico es una función unidireccional simple no son lo suficientemente eficientes para usar en aplicaciones (y esto es al menos en parte inherente) Por lo tanto, normalmente tenemos que asumir una función PRG / stream cipher / block-cipher / hash como primitiva básica, y comenzar a construir otras cosas a partir de ella. El problema no es realmente sobre el análisis asintótico, ya que esencialmente todas las reducciones criptográficas (excepto quizás el PRG universal de Levin) pueden hacerse concretas y, por lo tanto, otorgar garantías concretas bajo supuestos concretos.

Pero aunque no se basan en funciones unidireccionales, hay un sentido en el cual las construcciones como AES son "teóricamente sólidas" porque: (1) Hay conjeturas formales sobre su seguridad. (2) Hay trabajo para tratar de refutar estas conjeturas, y también derivar implicaciones de ellas.

Y, de hecho, las personas son conscientes de que para muchas aplicaciones, no sería inteligente utilizar PRG como LSFR que no satisfacen (1) y (2) anteriores.

Boaz Barak
fuente
1
Supongo que querías vincular uno de los documentos de Jonathan Katz a su página web. Por cierto, ¿quieres que combinemos esto con tu otra cuenta ?
Kaveh
9

Parece confundir la teoría con la práctica. Un generador pseudoaleatorio teóricamente adecuado encaja mal para un uso práctico por varias razones:

  • Probablemente sea muy ineficiente.
  • La prueba de seguridad es solo asintótica, por lo que para el parámetro de seguridad particular utilizado, el generador pseudoaleatorio puede ser fácil de romper.
  • Todas las pruebas de seguridad son condicionales, por lo que en cierto sentido ni siquiera satisface la noción de seguridad teórica.

En contraste con esto, los generadores pseudoaleatorios reales son rápidos y vienen en diferentes sabores dependiendo de su uso. Para uso no criptográfico, casi cualquier cosa que no sea un LFSR simple hará el trabajo, no de manera demostrable, pero en la práctica (lo que es más importante para las personas que usan cosas en realidad).

Para uso criptográfico, las personas intentan ser más inteligentes. En este punto, su crítica tiene sentido: no podemos saber si un generador pseudoaleatorio en particular utilizado es "seguro", y de hecho algunos viejos se han roto, por ejemplo RC4 como se usa en WEP. Sin embargo, por las razones indicadas anteriormente, el uso de un generador pseudoaleatorio teóricamente (condicionalmente) no es una solución realista. En cambio, la comunidad criptológica se basa en la "revisión por pares": otros investigadores que intentan "romper" el sistema (su definición de cuándo se rompe un cifrado es muy amplia).

Finalmente, en las aplicaciones en las que se puede invertir el dinero y la seguridad es lo suficientemente importante, digamos códigos nucleares, las personas usan ruido generado físicamente (pasado por un extractor de aleatoriedad), aunque incluso eso no está más allá de la crítica teórica.


Cuando los investigadores escriben propuestas de subvención o presentaciones de artículos, a menudo afirman que su investigación pertenece e informa a la práctica. No sé si creen en él o es solo un servicio de labios (y puede depender del investigador), pero debes tener en cuenta que la conexión es muy exagerada en los círculos académicos, por razones obvias.

Una cosa que nos limita como investigadores matemáticos es nuestro apego dogmático a la prueba formal. Usted menciona el análisis de algoritmos aleatorios alimentados por generadores pseudoaleatorios simples. Este tipo de análisis no puede extenderse a problemas del mundo real, ya que simplemente son demasiado complicados. Y, sin embargo, en la práctica, las personas resuelven incluso problemas NP difíciles todo el tiempo, con métodos informados.

Los problemas del mundo real se entienden mejor con un ojo más científico y experimental. Se resuelven mejor desde una perspectiva de ingeniería. Inspiran la investigación teórica, y ocasionalmente son informados por ella. Como dijo Dijsktra, la informática (teórica) no se trata realmente de computadoras, ya no.

Yuval Filmus
fuente
Gracias por tu respuesta, Yuval. Sin embargo, no creo totalmente que las construcciones de generador pseudoaleatorio de la criptografía sean prácticamente ineficaces. Hasta donde puedo ver, nadie ha estudiado esto.
Henry Yuen
2
También estoy en desacuerdo con la afirmación general de que los generadores pseudoaleatorios estándar son suficientes para "fines cotidianos". Como mostró el reciente documento "Ron estaba equivocado, Whit tenía razón", la generación pseudoaleatoria defectuosa ha generado vulnerabilidades embarazosas para una cantidad no despreciable de personas. Ese análisis particular fue bastante simple; ¿Cuántas aplicaciones del "mundo real" pueden sufrir vulnerabilidades más sutiles porque los LSFR no son adecuados? Si la sobrecarga computacional adicional necesaria para los PRG teóricamente sólidos no es tanto, ¿por qué no usarlos?
Henry Yuen
1
@HenryYuen LSFR no se utilizan para aplicaciones criptográficas en ningún sistema moderno y decente. (Por supuesto, existen sistemas mal diseñados, como GSM que se enseña en cursos introductorios como cómo no hacerlo.) Los problemas encontrados en el documento "Ron estaba equivocado, Whit tiene razón" no estaban con la calidad de PRNG, pero con la calidad de la recolección de entropía.
Gilles 'SO- deja de ser malvado'