33C3: ¿Cómo puede confiar en sus números aleatorios?

Gloria Vega
Gloria Vega

Una de las charlas destacadas en el 33 ° Congreso de Comunicación del Caos se refería a los generadores de números pseudoaleatorios (PRNG). [Vladimir Klebanov] (Derecha y [Felix Dörre] (izquierda) proporcionó un marco para garantizar que los PRNG hagan lo que se supone que deben hacer. En el camino, descubrieron una falla en Libgcrypt / GNUPG, que arreglaron. Vut.

Los números aleatorios criptográficamente seguros realmente importan. Si tiene la edad suficiente para recordar la falla de debia OpenSSL de 2008, básicamente todos los servicios de Internet fueron de puerta trasera debido a números aleatorios incorrectos. Entonces importan. [Vladimir] asume que escribir buenos generadores de números aleatorios es muy, muy difícil. Por lo tanto, es muy importante que su salida se pruebe muy, muy bien.

Entonces, ¿cómo podemos probarlos? [Vladimir] advierte contra nuestro primer instinto, administrar un conjunto de pruebas estadísticas como DIEHARD. Señala (correctamente) que ejecutar cualquier algoritmo con una función hash bastante buena pasará las pruebas estadísticas, pero eso no significa que sea adecuado para la criptografía.

En cambio, hay dos formas de probar PRNG. Primero, si está utilizando una función estándar y tiene un conjunto de semillas y resultados de referencia, compruébelos. Al menos, se asegurará de que su código haga lo que se supone que debe hacer. En segundo lugar, y de manera más general, desea asegurarse de que el algoritmo no pierda entropía: los PRNG no crean posibilidades, por lo que lo mejor que pueden hacer es no perderlas.

Aquí hay algunas cosas que puede consultar. Si parte de la semilla no afecta el rendimiento, o si dos semillas producen el mismo rendimiento, o de manera equivalente, si hay menos rendimientos posibles que semillas, el algoritmo pierde entropía. Si puede pasar por una cantidad arbitrariamente grande de semillas y resultados, es posible que pueda aplicar la fuerza bruta a esta prueba (con suerte antes de que el universo muera su inevitable muerte caliente).

O podrías hacerlo analíticamente. Ellos prueban seis implementaciones de PRNG utilizando los analizadores estáticos CBMC y Minisat para probar estos requisitos. Al hacerlo, se detectaron todos los problemas que esperaban y uno que no. Usando su “entroposcopio”, rastrean la pérdida de entropía a través del flujo del programa, encuentran el error y salvan el día.

Esta no es una charla incipiente sobre PRNG criptográficas, pero es muy buena. Los PRNG que parecen aleatorios y pasan pruebas estadísticas, aún pueden perder entropía. Como la pareja mostró en la pregunta y respuesta, el solo La forma de estar seguro en un período de tiempo razonable es revisar el código y verificar que no lo esté. La implicación de esto es que el único PRNG seguro es el PRNG de código abierto. Pero eso ya lo sabías, ¿no?


  • Jaime dice:

    Siempre quise construir un generador de ruido blanco e integrarlo en un convertidor de analógico a digital.

    • zambullirse dice:

      Creo que así es como ET realmente llamó a casa …

      • TheRegnirps. dice:

        ¿A diferencia del ruido rosa?

        • Iw2 dice:

          ¿No debería Trump hacer un ruido naranja?

    • Germanio SynthiMuse dice:

      Autopromoción descarada aquí, pero el producto que acabo de lanzar utiliza un generador de ruido blanco para crear notas MIDI aleatorias para componer música.
      Piense en ello como Triadex Muse se encuentra con una máquina Enigma, excepto que no se repite. Estoy.
      http://www.synthimuse.com

      • Internet dice:

        ¿Le gusta a un oyente humano? La mayor parte de la generación actual de “música generada por CPU” carece de algo parecido a cómo se sentiría tener sexo con un amante de la silicona en comparación con la intimidad con un ser humano real. Simplemente carece de ese elemento especial. Además, la falta total de movimiento o voz o intimidad o compartir los deseos o la posibilidad de un embarazo en encuentros del sexo opuesto, menos el gasto en una situación en la que eso aún podría dar sus frutos, y así sucesivamente. En otras palabras, no es * malo * pero tampoco es exactamente bueno o completamente correcto.

        Dicho esto, hay algunos paquetes de software de producción de música artificial que en realidad son bastante decentes. Como Jukedeck o Computoser. DeepBeat también está en esa área.

      • ROBÓ dice:

        @[Internet]

        ¡No suena a música de mierda de “computadora”!

        Ve a verlo –
        https://synthimuse.wordpress.com/samples/

        Me gusta “tocar la batería”

        @[Germanium SynthiMuse]

        ¡Ama a tu trabajador!

        Estoy buscando un esquema para ver cómo usas tantas macetas con uC.

        Quería jugar con sonido en CPLD / FPGA para agregar la capacidad de dar la ubicación, vector, arco, velocidad y fase de la fuente de sonido. Como una extensión de MIDI, que tiene estas características adicionales. Algo que tiene que ver con el sonido está en la naturaleza, como cuando un automóvil pasa a gran velocidad y tiene cambios de frecuencia, amplitud, fase y tono.

        ¡Espero recibir más información sobre su proyecto!

        • Germanio SynthiMuse dice:

          Gracias por las palabras amables. No puedo obtener crédito por “Drumming”, que fue creado por mi colega, quien también animó el sitio web de wordpress.
          La palabra de los pocos probadores beta es que SynthiMuse no suena como un compositor de computadora. Principalmente porque no tiene algoritmos como tal. Solo toma la configuración y bombea notas MIDI.
          Si escuchas algo que te guste, tómate una foto y guárdalo en una de sus 4 memorias de bucle.
          Es interesante que cuando tomas una frase al azar y la repites, adquiere un significado musical.
          El SynthiMuse puede tomar disparadores del micrófono incorporado, entrada de un midi externo, así como del generador de ruido y LFO incorporado.
          Siento que tengo que limitar mi autopromoción aquí, porque SynthiMuse es un producto comercial autofinanciado que, aunque creado por un hacker, es un intento de casi intentar alcanzar el punto de equilibrio a costa del desarrollo.
          Estoy contento y agradecido por cualquier comentario, bueno o malo.

        • sintetizar dice:

          Hola rob
          No puedo publicar los esquemas, pero me complace decirles la forma más eficaz que conozco de escanear muchas macetas.
          Utilizo moscas analógicas con sus líneas seleccionadas y habilitadas impulsadas por la uC. Nada especial aqui.
          El truco principal es que tengo un tiempo de espera que se ejecuta:
          1. Lee el valor del bote seleccionado actualmente en una matriz.
          2. Seleccione la siguiente entrada de potenciómetro
          3. Inicie el muestreo de ADC
          4. Salir de la interrupción
          La clave es que no espero que termine el ADC. Simplemente me alejo y hago otras cosas hasta que el punto de tiempo se interrumpe nuevamente y sé que el ADC tendrá un nuevo valor transferible.

          Así que no es original en absoluto, pero es una técnica que mucha gente extraña.

          http://www.synthimuse.com

  • DV82XL dice:

    Lavarand era un generador de números aleatorios por hardware diseñado por Silicon Graphics que funcionaba tomando imágenes del material flotante en lámparas de lava, extrayendo datos aleatorios de las imágenes y usando el resultado para sembrar un generador de números pseudoaleatorios. Aunque la parte secundaria de la generación de números aleatorios utiliza un generador de números pseudoaleatorios, el proceso completo esencialmente califica como un generador de números aleatorios “verdadero” debido a la semilla aleatoria utilizada. Sin embargo, su aplicabilidad está limitada por su reducido ancho de banda.

    • copa de corona dice:

      Lo que da miedo de la madriguera del conejo “al azar real” es que con las variables correctas, incluso el estado de una lámpara de lava se puede predecir. es difícil definitivamente. pero la VERDADERA posibilidad es definitivamente algo que no puede existir dentro de un “sistema”. de alguna manera se parece a todo el experimento de pensamiento cuántico. lastiman el cerebro

      • DV82XL dice:

        La madriguera del conejo a la que te refieres es objeto del determinismo en todas sus diversas manifestaciones. El indeterminismo adecuado es suficiente y puede provenir de cualquier generador de números aleatorios práctico que pueda vincularse a una propiedad irreductible del indeterminismo cuántico.

        • copa de corona dice:

          bien, tenemos que caminar hasta uno lo suficientemente grande. Como la “esfera perfecta” o el “peso adecuado”. Lo mío era que “verdadero aleatorio” es (con la tecnología actual) poco probable, por lo que el ejemplo de la lámpara de lavado estaría mal etiquetado. De lo contrario, deberíamos asumir que siempre será imposible modelar con precisión las interacciones de flujo / térmicas que ocurren dentro de esa extraña burbuja de vidrio.
          http://demonstrations.wolfram.com/LavaLamp/

        • Elliot Williams dice:

          @ DV82XL: “vinculado a una propiedad irreductible del indeterminismo cuántico” es el camino correcto. Y para eso: ruido de diodo genérico, ruido destructivo de avalancha de transistores, ruido de Johnson en resistencias si no te importa la blancura, etc. No es dificil.

          Hice algunas basadas en la falla del transistor y para anchos de banda en el rango de 100 kHz, por lo que tal vez 10K bits / seg. – Es fácil. Úselos como semilla para un buen PRNG y tendrá un buen diseño. Lo difícil es si necesita testificar que el dispositivo funciona en sentido antihorario y siempre funciona como debería. Pero esa es la diferencia entre un aficionado de $ 2 y una unidad profesional.

          De todos modos, cualquier PRNG necesita buenos datos semanales. La incertidumbre cuantitativa es una excelente fuente de estos datos de semillas. Este artículo trata sobre no estropear el siguiente paso.

          • Artenz dice:

            Si tiene 10k bits aleatorios, tiene suficientes posibilidades para el resto de su vida. El dispositivo tampoco tiene que ser antidetonante, ya que nadie sabe que ha estado funcionando durante un segundo. Lo único es que necesita mantener sus 10k piezas aleatorias almacenadas de forma segura.

        • Elliot Williams dice:

          Si. Y: https://la-tecnologia.com/2014/12/19/nist-randomness-beacon/

          Estos gatos apuntan al paradójico RNG cuántico de Bell, que lo lleva al siguiente nivel: el RNG cuántico, que tampoco se ve afectado por a) la distancia yb) la velocidad de la luz. ¡Profundiza en eso si quieres que te duela el cerebro!

        • Linterna mágica dice:

          como una buena taza de té caliente …

          • DV82XL dice:

            Los discos infinitos improbables parecen ser menos difíciles sobre el origen de las semillas iniciales que la mayoría de los generadores de números pseudoaleatorios.

      • Dax dice:

        > VERDADERO aleatorio es definitivamente algo que no puede existir dentro de un “sistema”

        Claro, hay una posibilidad limitada, de modo que un pez no pueda convertirse en una roca, sino que simplemente exista como un pez, pero eso no significa que la elección de estados dentro de la opción no sea realmente aleatoria.

        Al contrario, es cierto. Si argumenta que no es accidental, entonces debe señalar qué lo está causando, y no hay nada; no hay “variable oculta” para explicar el progreso de los estados de uno a otro que tendría algún tipo físico o teórico sentido.

      • Steven Gann dice:

        No soy un experto en matemáticas, pero ¿el concepto detrás de la “teoría del caos” es que algunas cosas son simplemente impredecibles, como las vibraciones de los átomos y como resultado del movimiento marrón en los fluidos? Luego está todo el Principio de Incertidumbre de Heisenberg, que, en mi crudo entendimiento, dice que no se puede medir realmente la posición y la inercia de cada partícula, y sin esa información no se pueden predecir con precisión sus movimientos.

        • DV82XL dice:

          El determinismo adecuado es el tipo de determinismo que tenemos en el mundo. Es el determinismo estadístico, donde las estadísticas son casi seguras para grandes objetos macroscópicos. El determinismo apropiado también incluye el no determinismo, una propiedad irreducible del mundo cuántico microscópico. Esto debe distinguirse del predeterminismo, la idea de que todo el pasado (así como el futuro) se determinó en el origen del universo. La predeterminación implica que toda la información del universo actual estaba implícita en los primeros momentos del universo y que esta información se conserva. El Principio de Incertidumbre de Heisenberg establece que este no puede ser el caso, pero no implica que todo evento no sea la consecuencia inevitable y necesaria de un estado previo, solo que no pueden ser perfectamente conocidos.

          • Dax dice:

            Luego está también el superdeterminismo, que es la idea de que en realidad no hay eventos, sino que el mundo se reproduce como si se proyectara desde una bobina de película.

            De tal manera que en cualquier punto del espacio y del tiempo, la realidad es exactamente la información que está allí, y si das un paso hacia la izquierda, el mundo es completamente diferente, por lo que no puedes decir en absoluto que algo está sucediendo; al momento siguiente, Contendré diversa información, que no necesita tener nada que ver con lo que vino antes.

      • Artenz dice:

        La forma más realista de conocer el estado de la lámpara de lavado es entrar en la habitación donde está almacenada. Pero entonces será más fácil simplemente tomar el número aleatorio que se genera.

        • Elliot Williams dice:

          Especialmente con lavarand, también se mezclan en radio estática por algunas radios FM.
          Sé lo que piensas …

  • Ricardo de Azambuja dice:

    Los enlaces a CBMC y Minisat están rotos (rutas relativas …)

    • Mike Szczys dice:

      Gracias, debería arreglarse ahora.

  • Unferio dice:

    Cualquier mejora en la seguridad de código abierto del sistema operativo y Userland siempre es buena.
    Aunque con algo de estandarización y hojas de ruta definidas a largo plazo para las principales distribuciones de GNU Linux.

    Al igual que mi pensamiento:
    A medida que sysvinit se introduce en todo, debe desarrollarse como si fuera una parte integral a largo plazo del subsistema de arranque y servicio GNU.
    Su objetivo es ejecutar servicios de terceros (es decir, realizados por otro proyecto de código abierto) comunicándose a través de un bus API común como módulos / aplicaciones y ya no entrar en la experiencia del usuario como obtener un terminal o una pantalla gráfica en blanco (es decir, configurada) a través de bandera de inicio)

    Solo mi opinión, por favor tómalo con un poco de sal (o pimienta si quieres)

  • ian dice:

    Sería interesante ver este enfoque aplicado al generador de números aleatorios de hardware 8266, la mayoría de las personas que lo revisan hasta ahora parecen pensar que es bueno, y es el generador de números aleatorios de dispositivos más barato y fácil de usar que existe (que yo sepa. .).
    Utiliza wifi para la fuente aleatoria, o eso nos dicen, porque no es de código abierto.

    • Koplin dice:

      Por lo tanto, solo tiene que “confiar” en algo que no puede verificar por seguridad, ciertamente parece legítimo.

      • ian dice:

        Estoy de acuerdo con su punto, es decir, aunque muchas personas prueban los números aleatorios 8266, algún día el chip puede despertar y hacer algo más y no al azar …

        Aunque esto, como se comenta a menudo en este sitio, es el problema de cualquier cosa que se ejecute en un chip que usted mismo no haya creado … O transmitir los datos a través de cualquier cosa que usted mismo no haya hecho …

        Adoptar ese enfoque es bueno si solo necesita unos pocos números aleatorios; escribo un artículo para un cliente en el medio y les digo que tiren los dados por algo que quieren que sea demostrablemente aleatorio … sin embargo, si necesita millones, casi no es posible hacer esto y usarlos con hardware confiable …

  • Tic dice:

    ¿No sería completamente trivial crear semillas basadas en la latencia y el contenido de la página que a menudo cambia el contenido entre muchas otras fuentes de condiciones fuera del procesador?

    • Máximo dice:

      Uno de los requisitos básicos de cualquier cripto RNG es que ningún atacante pueda influir en él de alguna manera. Si pueden, les será más fácil romper su criptografía. De eso se trata todo este artículo: ni siquiera necesitan _influenciar_ su RNG, el simple hecho de saber que es imperfecto de una manera específica les da demasiada ventaja. Y creo que es obvio cómo alguien está engañando tu conexión a Internet. podría engañarte por completo …

    • Elliot Williams dice:

      Regla general: no hagas nada con el tiempo a menos que tengas suficiente resolución y haya muchas variaciones impredecibles en el tiempo.

      Si fijo ahora, obtengo números en el rango de 30-45 ms, por lo que puede fortalecer estos 15 valores probables con bastante rapidez. Si mido los pines en microsegundos, ¿quizás los últimos tres dígitos son aleatorios? Entonces eso es 8-10 bits.

      Puede continuar subdividiendo, pero si desea 128 o 256 bits aleatorios, tiene escalas de tiempo que no puede medir y debe resumir muchas observaciones. Esto puede exponer alguna estructura en la “aleatoriedad” que esperaba evitar; el promedio es una excelente manera de mejorar la relación señal / ruido, exactamente lo que no queremos. Las computadoras pueden actuar fácilmente de forma repetida en una escala de tiempo de microsegundos.

      Haz … meh. Múltiples fuentes (no correlacionadas) siempre que sea posible, y lidiar con tiempos derivados de sistemas informáticos con severo escepticismo. (En mi opinión, no es un experto. Sepa algo sobre probabilidad).

  • Ralph Doncaster (Nerdo Ralph) dice:

    Generador de números aleatorios por hardware de $ 10.
    https://github.com/pwarren/rtl-entropy

    • ian dice:

      sí, puesto como comenté anteriormente,

  • TheRegnirps. dice:

    ¿Con qué frecuencia necesitan nuevos números? Utilizo un contador Geiger y se necesita un intervalo lo suficientemente largo para tener un número razonable de estados.

    • Steven Gann dice:

      Recuerdo haber leído algo sobre las CPU Intel más antiguas que tienen un circuito que se dejó flotando intencionalmente y descartaron su entrada en un registro. Cualquier cosa, desde EMI hasta rayos cósmicos, podría impactar en una puerta de bajo voltaje con entrada flotante, por lo que teóricamente era tan aleatorio como un contador Geiger.

      • TheRegnirps. dice:

        Debería ver el análisis 😉

        La desintegración radiactiva no se ve afectada por la temperatura, la gravedad, la luz, los campos eléctricos o magnéticos ni ningún blindaje. La calculadora Geiger con algo de radio será aleatoria. En lugar de recopilar cálculos que tendrán una distribución estrecha en intervalos largos, calcule el tiempo entre eventos.

  • Etienne dice:

    El video es demasiado grande para el módem de su teléfono. Pero también está en YouTube:

    • ian dice:

      No es necesario señalar una copia encubierta del video. Todos los discursos están disponibles en el canal de youtube CCC – https://youtu.be/C6JKQbOvkgI

      • tmxod dice:

        Este video ya no está disponible porque la cuenta de YouTube asociada con este video venció.
        Lo siento por eso.

        🙁

  • Artenz dice:

    Tome una secuencia de números aleatorios mediocre y cifre la transmisión con AES-256 para obtener una buena.

    • Máximo dice:

      Felicitaciones, se te ocurrió el equivalente críptico de la unidad excesiva …

      • Unferio dice:

        Demonios, ahora los locos de las unidades superiores (a menos que alguna vez tengan éxito) entregarán ese flujo a los devanados y cosas que afirman generar una crisis de electricidad de unidades superiores.

    • Elliot Williams dice:

      “Tome una secuencia de números aleatorios mediocre y encripte la transmisión con AES-256 para obtener una buena”.

      Sin embargo, aquí está el experimento. Mi secuencia de números aleatorios promedio es 7, siempre. Ningún trozo de entropía ingresa al AES-256. ¿Cuántos bits salen?

      Sobre eso vienen los comentarios sobre la “unidad excesiva”, y ese es el verdadero caballo de Troya en esta idea. Digamos que ingresó 10 bits de entropía. Obtienes algo que parece aleatorio, pasa (tal vez) algunas pruebas de rastreo estadístico, pero está sucio en milisegundos. Esto es lo que le sucedió a OpenSSL.

      • Artenz dice:

        Obviamente, no es necesario que ingrese un flujo de séptimo. Pero podría cifrar una secuencia de 0, 1, 2, 3, 4 … etc.

        Obtenga 256 bits de entropía y utilícelo como clave. La única forma de adivinar el siguiente número aleatorio es romper AES.

  • Iw2 dice:

    Me quedé mirando la imagen de arriba durante un rato tratando de averiguar qué se suponía que significaba “em rof skrow”. A veces es realmente molesto si su cerebro refleja automáticamente el texto, porque las letras se reflejan …

  • nsayer dice:

    No hace mucho tuve un problema ligeramente diferente. Necesitaba números aleatorios para mi Crazy Clock, pero debido a que el controlador funcionaba a 32 kHz, la función aleatoria en AVR-libc era demasiado lenta. No necesitaba nada de calidad críptica, pero no quería que el comportamiento del reloj siguiera patrones. Terminé encontrando un buen reemplazo en una publicación del foro en algún lugar, pero lo que estoy escribiendo aquí es el método que usé para probarlo: generé un millón de bits de salida y lo transformé en un archivo PBM de 1024 × 1024 y miré el resultado. Si hace esto con algo con un patrón repetitivo corto, se vuelve bastante fácilmente visible en la pantalla. En este caso, parecía un fotograma de un viejo televisor Snow analógico.

    No estoy afirmando en este momento que esto sea lo suficientemente riguroso para los criptógrafos, pero es una buena “prueba de rastreo” si estás escribiendo un juego integrado o algo así que necesita ser rápido, pero no quieres para ser patrones fáciles de encontrar.

    • Steven Gann dice:

      Yo ya vi esta prueba. Aquí está el PRNG incorporado de PHP:
      https://i.stack.imgur.com/uzSyZ.png

      Obtenido de aquí: http://stackoverflow.com/questions/8838413/php-rand-is-it-possible-to-guess-the-next-number-in-a-sequence-and-generatin

      El mismo método se utilizó para evaluar el PRNG de Javascipt aquí en La-Tecnologia: https://la-tecnologia.com/2015/12/28/v8-javascript-fixes-horrible-random-number-generator/

Deja una respuesta

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *