Dado que la recolección de basura no es determinista, ¿por qué no se usa para la generación segura de números aleatorios?

13

Entiendo que / dev / random es una buena fuente de entropía, y es lo que se usa generalmente: es justo cuando estoy leyendo sobre GC, al menos en Java, parece aceptado que el demonio de recolección de basura se ejecuta de manera no determinista . Si esto es cierto, ¿por qué no usamos el tiempo de recolección de basura como fuente de entropía en lugar de la variable / dev / random?

random garbage-collection edthethird
fuente
77
Eche un vistazo a algunos de los documentos para las funciones rand () en la biblioteca C estándar. Expresan específicamente que, si bien le dan lo que parecen números aleatorios, no pueden usarse para seguridad. Su recolector de basura típico probablemente caería en la misma categoría. Si va a usar uno por seguridad, debe asegurarse de usar un recolector de basura criptográficamente seguro.
DXM
15
algo no determinista aún puede ser altamente predecible
fanático del trinquete el
77
En este caso, "no determinista" es una descripción pobre. Un recolector de basura es un sistema completamente determinista y si tiene pleno conocimiento de su estado y del estado del programa que lo utiliza, puede predecir de manera determinista los resultados.
Gort the Robot el
44
@DXM, ¿conoce una buena implementación para un recolector de basura criptográficamente seguro? ;)
AJMansfield
77
"Cualquiera que considere métodos aritméticos para producir dígitos aleatorios está, por supuesto, en un estado de pecado". - John von Neumann
Mark Adler

Respuestas:

58

"No especificado" y "aleatorio" son dos conceptos completamente diferentes.

El funcionamiento exacto de un recolector de basura no se especifica y depende del recolector de basura (generalmente implementado por una máquina virtual, pero no necesariamente).

Por lo tanto, no tiene un tiempo especificado (es decir, determinista) en el que se recolectará la basura.

Sin embargo, cualquier implementación dada seguirá algunas reglas y existe una alta probabilidad de que dos ejecuciones posteriores del mismo programa tengan patrones de recolección de basura muy similares.

Por lo tanto, la entropía real proporcionada por un recolector de basura sería muy baja (y descubrir qué partes puede usar realmente como entropía será complicado).

Como comparación: A HashMapen Java no garantiza ningún orden de recuperación para sus miembros (básicamente porque garantiza que agregaría una sobrecarga que no vale la pena pagar, la mayoría de las veces). Sin embargo, para una implementación dada y un conjunto dado de inserciones / eliminaciones, definitivamente puede calcular el orden resultante. El hecho de que no haya garantía para un pedido dado, no significa que el pedido sea aleatorio.

Joachim Sauer
fuente
20
Creo que sería una afirmación justa decir que si una computadora alguna vez hace algo que en realidad no es determinista, esa computadora está averiada.
Schilcote
No determinista también podría significar que depende de algún estado externo al programa en cuestión, que en sí mismo puede ser determinista, pero no tendrá ninguna relación con el programa en sí mismo y, por lo tanto, puede ser diferente cada vez que el programa se ejecute.
asmeurer el
@asmeurer No creo haber escuchado estos términos en ningún contexto. De hecho, ni siquiera estoy seguro de lo que quiere decir: cada programa que toma entrada externa (es decir, la mayoría de los programas útiles) "depende de algún estado externo", pero eso no lo hace no determinista.
us2012
2
@Schilcote: algunas CPU modernas tienen RNG no deterministas (verdaderos) implementados en hardware. Estos son realmente no deterministas hasta la física de nivel cuántico.
MSalters el
2
@Schilcote Incluso sin instrucciones especializadas de RNG (RDRAND y RDSEED de Intel) una computadora no es completamente determinista. Algunos tiempos no están completamente especificados y pueden depender de factores externos como la temperatura.
CodesInChaos
8

En primer lugar, debemos tener cuidado de no caer en la trampa del razonamiento mediante la manipulación de simples palabras. Por ejemplo, podríamos preguntar, dado que un NFA es un "autómata finito no determinista", ¿por qué no lo usamos para obtener números aleatorios? En ese caso, sería porque eso no es lo que significa "no determinista" en una NFA; de hecho, cuando simulamos un NFA, en una entrada dada, el comportamiento de la simulación es perfectamente determinista.

"Determinista" es una frase cargada. Para un programador de computadoras o un científico de la computación, el comportamiento no determinista solo significa "determinar el comportamiento exacto es complicado de pensar", y depende de demasiados factores, incluida la entrada del programa.

Sin embargo, eso no significa que no sea determinista para alguien motivado para atacar un sistema criptográfico. A veces, los factores e insumos ambientales pueden precisarse, y los patrones repetibles surgen del comportamiento "no determinista".

Kaz
fuente