Probando un generador de números aleatorios de hardware

13

La Raspberry Pi tiene un generador de números aleatorios de hardware incorporado, pero no parece haber ninguna documentación pública en el hardware, e incluso si la hubiera, sería cuestionable (qué compañía va a admitir públicamente que podría haber ¿Problemas con su propio hardware si pueden salirse con la suya?).

Entonces, ¿cuál es el mejor método para probar un generador de números aleatorios de hardware? Si llené un archivo de 10 GB con números aleatorios generados con el generador de números aleatorios de hardware, ¿hay alguna herramienta en mi computadora principal que pueda usar para ver si hay algún patrón en los números producidos?

Me cuesta creer que no haya una forma de terceros para verificar si es seguro usar un generador de números aleatorios (ya sea software o hardware). De lo contrario, ¿por qué alguien confiaría en un generador de números aleatorios que no fuera de código abierto y que no pudiera ser auditado independientemente?

Me gustaría usar la Raspberry Pi para generar algunas claves privadas, pero el generador de números aleatorios de software normal no obtiene la entropía suficiente para que sea viable (se demora en generarlas) pero con el generador de números aleatorios de hardware es mucho más viable. Simplemente no sé si puedo confiar en el generador de números aleatorios de hardware o no.

    
pregunta Cromulent 22.12.2013 - 01:59
fuente

7 respuestas

11

Hay varios factores en juego aquí:

  • El mecanismo físico de HRNG utilizado dentro del microprocesador ARM.
  • La lógica de soporte en el silicio dentro del microprocesador.
  • El microcódigo implementado en el microprocesador.
  • La implementación del RNG dentro de Linux.

Según el fabricante, ese chip en particular utiliza el ruido de un transistor de polarización inversa, en un diseño HRNG de colector abierto. Este es precisamente el hardware que estoy usando en mi proyecto HRNG actual, pero mucho más pequeño. Es una de las formas más baratas de implementar un HRNG directamente en silicio; mientras que estoy usando transistores discretos, el procesador ARM simplemente reduce esto a unas pocas señales de silicio en el chip chip.

Sabemos que este mecanismo es una fuente importante de aleatoriedad, porque se basa en un fenómeno llamado túnel cuántico , que se sabe que es probabilístico y aleatorio. La idea básica es que los electrones "saltan" al azar sobre el intervalo de banda dentro del transistor, lo que lleva a una señal fluctuante al azar. Luego podemos amplificar esto (el amplificador de transistor PNP simple funcionará) e interpretar la salida como un 1 o un 0 muestreando el resultado a una frecuencia fija: si supera un cierto umbral, es un 1, de lo contrario es un 0.

Una ligera deficiencia de este mecanismo es que cualquier fuga de CC provocará un sesgo hacia 1s que aparece más a menudo que 0s. Para solucionar esto, podemos usar un simple truco llamado descorrelación de von Neumann, que esencialmente implica codificar los pares de bits 01 y 10 a 0 y 1 respectivamente, e ignorar todos los 00 y 11 pares. Esto produce un flujo estadísticamente imparcial.

Es casi seguro que puedo garantizar que este es el mecanismo por el cual produce números aleatorios. Hay una alternativa importante (dos puertas NOT con polarización inversa en paralelo) pero está cubierta por una patente de Intel, así que dudo que ARM esté usando eso. Desafortunadamente, la única forma de saberlo con certeza es tomar un poco de ácido y destapar un chip, luego tomar un microscopio y comenzar a aplicar ingeniería inversa al silicio. No tengo el equipo de repuesto disponible para esto.

La vulnerabilidad potencial que puede encontrar en dicha exploración es que las señales del reloj de alta frecuencia u otras líneas de datos de HF se enrutan muy cerca del HRNG o su lógica de soporte, lo que lleva a un potencial de interferencia. Esto suele ser poco probable en los circuitos integrados, pero estamos hablando de aplicaciones de alta sensibilidad aquí, por lo que vale la pena buscarlo. Sin embargo, incluso si fuera el caso, no veo que ofrezca un sesgo útil desde una perspectiva criptoanalítica.

El siguiente potencial de explotación es microcódigo. Recientemente, un investigador demostró que era posible parchear el microcódigo para que los procesadores Intel buscaran patrones únicos en el búfer de instrucciones y detectar cuándo se estaba utilizando la instrucción RDRAND para completar el conjunto /dev/random . Luego identificaría la posición de ese búfer de agrupación en el caché del procesador y efectivamente la pondría a cero, haciendo que la agrupación de cero se vuelva a copiar en la memoria del sistema. Esto significaba que /dev/random emitiría constantemente el mismo valor controlado por el atacante, con resultados obviamente devastadores. Si se empleara un truco similar pero más sutil en el microcódigo ARM, podría ser posible reducir masivamente la entropía del HRNG de una manera que solo sea conocida por el creador del parche. Detectar tales trucos sería difícil, pero podría hacerse extrayendo el microcódigo y analizándolo.

Finalmente, el último problema es el diseño RNG dentro del kernel de Linux. La agrupación /dev/random generalmente se alimenta de un grupo de fuentes basadas en estado, utilizando un algoritmo de mezcla que se basa en una función criptográfica. Sin embargo, cuando RDRAND o instrucciones similares están disponibles, el motor simplemente almacena los datos en la agrupación. Esto no es exactamente una buena idea, ya que facilita la conexión de los datos de la agrupación de manera significativa mediante la producción de ciertos valores. Si se usara la función de mezcla más fuerte, el atacante tendría que romper eso (o hacer algo más visible) para obtener un control significativo sobre la piscina.

No hay una respuesta obvia a tu pregunta. Los generadores de números aleatorios de hardware pueden ser de muy alta calidad, pero es difícil analizar su implementación dado solo un dispositivo de consumidor. Dicho esto, si vas a desconfiar de tu hardware, no puedes hacer ninguna garantía en primer lugar. Si desea limitar el alcance de la desconfianza por completo a la calidad de los números aleatorios producidos, entonces diseñe su sistema de soporte alrededor de ese hecho.

    
respondido por el Polynomial 22.12.2013 - 04:29
fuente
6

He tenido el mismo problema en el pasado. El Instituto Nacional de Estándares y Tecnología (NIST) de los Estados Unidos ha preparado una suite llena de un montón de pruebas . Contiene todo tipo de pruebas estadísticas e informa un valor de p para cada prueba. Incluye pruebas simples como solo contar ceros y unos para ver si están cerca del 50% y pruebas sofisticadas como el análisis de espectro. Hay un manual muy extenso, fácil de leer y entender, que explica toda la teoría y cómo usar correctamente las pruebas e interpretar sus resultados.

    
respondido por el Fixed Point 22.12.2013 - 10:30
fuente
5
  

Me cuesta creer que no haya una forma de terceros para verificar si es seguro usar un generador de números aleatorios (ya sea software o hardware).

Lamentablemente, este es el caso. A menos que el RNG sea terriblemente malo porque hay un sesgo visible en la salida, es muy difícil detectar si un RNG contiene debilidades sutiles que pueden considerarse backdoors sin mirar la fuente.

    
respondido por el Ayrx 22.12.2013 - 03:32
fuente
3

Con respecto a las herramientas que se utilizan para probar la previsibilidad de sus datos aleatorios, el estándar de la industria es el conjunto de intemperie, que se encuentra aquí .
Ejemplo específico de RaspberryPi, que se lanzará después de instalando el módulo del kernel y las herramientas rng :

apt-get install dieharder
cat /dev/hwrng | dieharder -d 0 -vv  

# Verbose is now 0
#=============================================================================#
#            dieharder version 3.31.1 Copyright 2003 Robert G. Brown          #
#=============================================================================#
   rng_name|rands/second|   Seed   |
    mt19937|  1.34e+06  |2497347415|
#=============================================================================#
    test_name       |ntup| tsamples |psamples|  p-value |Assessment
#=============================================================================#
   diehard_birthdays|   0|       100|     100|0.79423698|  PASSED  
    
respondido por el Cyryl Płotnicki 08.03.2014 - 12:09
fuente
2

Bueno, hay algunas cosas que puedes probar que te señalaría a esta página: enlace

Comprueba tu nivel de aleatoriedad

Puedes probar el nivel de entropía / aleatoriedad en tu archivo externo usando ent. "Ent puede usarse contra cualquier archivo que contenga datos y probará la aleatoriedad de esos datos"

Aumenta tu entropía

Incrementa la entropía. Hay un demonio llamado "rngd" que puedes usar. Se ejecuta en segundo plano y aumenta significativamente la cantidad de entropía en el sistema. La calidad de los datos es casi la misma que la que produciría / dev / random, simplemente hace más por segundo.

Vale la pena tener en cuenta el siguiente artículo: enlace

  

El cambio principal que esto ha forzado es la visualización de hardware al azar.   generadores de números como generadores de números psudo-aleatorios. Tratándolos como   eso significa que se pueden tomar precauciones para hacer los números generados   más aleatorio (como pasarlo como una semilla a un segundo aleatorio   generador de números).

Podrías hacer tu propio generador de números aleatorios. Hay muchos proyectos interesantes que te mostrarán cómo hacerlo.

    
respondido por el DevilCode 22.12.2013 - 06:07
fuente
1

Una computadora es una máquina determinista y siempre debe realizar los pasos sanos en el mismo orden. Un generador de números pseudoaleatorios es un algoritmo de software que produce números "impredecibles" en ciertas condiciones: conocer cualquier salida del generador no lo ayudará a determinar los números que se generaron antes de la secuencia que conoce, y conocer cualquier salida no lo ayudará a determinar el futuro salida. Por supuesto, conocer el estado interno le permite predecir resultados futuros. El estado inicial se llama la semilla.

Para producir números realmente impredecibles, el estado del algoritmo debe ser sembrado con un valor incognoscible. Pero un algoritmo matemático no puede producir uno. Así que los diseñadores de hardware crean hardware que ofrece una medida de imprevisibilidad.

Si no confía en el hardware, aún puede reunir tantas fuentes de información desconocida como sea posible y mezclarlas. Si una fuente está sesgada, simplemente contribuirá menos al estado general desconocido. Estos algoritmos son conocidos como recolectores de entropía. La salida se ejecuta a través de una función de esponja criptográfica, que absorbe datos desconocidos a la velocidad a la que llega, y luego emite bytes pseudoaleatorios a pedido.

    
respondido por el John Deters 22.12.2013 - 04:13
fuente
1

La prueba de un generador físico de números aleatorios es similar a la prueba de los generadores de números aleatorios (funciones matemáticas) de buena calidad y puede hacer uso de las mismas herramientas desarrolladas para ellos; FIPS 140, STS 1.2.1, diehard, dieharder, Test U01, etc ...

La interpretación de los resultados de estas pruebas es algo diferente cuando se trata de un verdadero generador de números aleatorios. Cuando se prueba un generador basado en una función matemática, una falla de prueba revela una falla en el diseño básico del generador; sin embargo, con un generador físico, esperamos que las pruebas falle ocasionalmente en cualquier muestra. Y mientras estas pruebas fallidas no se repitan con frecuencia con muestras diferentes , el generador sigue produciendo lo que esperamos que deba.

Otra diferencia es que al probar un generador de base matemática solo necesitamos probarlo una vez para determinar su validez; sin embargo, un generador físico debe probarse regularmente ya que los cambios en las propiedades físicas del hardware que recopila la aleatoriedad (entropía) pueden afectar la validez de su salida.

He creado un sitio web que detalla mis exploraciones en curso relacionadas con el diseño, implementación, uso y prueba de estos generadores físicos que contienen más información si está interesado, incluidos cuatro conjuntos de pruebas ejecutadas en cuatro muestras diferentes de cuatro gigabytes recopiladas del generador de números aleatorios de hardware interno de la Pi:

Vista general de los verdaderos generadores de números aleatorios

Pruebas de Raspberry Pi

    
respondido por el Walter Anderson 19.04.2014 - 14:43
fuente

Lea otras preguntas en las etiquetas