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 habitualmente. Es justo cuando estoy leyendo sobre GC, al menos en Java, parece aceptado que el daemon de recolección de basura se ejecuta. no deterministicamente Si esto es cierto, ¿por qué no usamos el tiempo de la recolección de basura como fuente de entropía en lugar de la variable / dev / random?

    
pregunta edthethird 03.11.2013 - 22:19

2 respuestas

58

"Sin especificar" 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 VM de tipo, pero no necesariamente).

Por lo tanto, no tiene un tiempo específico (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 descubriendo qué partes puede realmente usar como entropía sé complicado).

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

    
respondido por el Joachim Sauer 03.11.2013 - 22:26
8

En primer lugar, debemos tener cuidado de no caer en la trampa del razonamiento mediante la manipulación de meras palabras. Por ejemplo, podríamos preguntar, ya que una NFA es un "autómata finito no determinístico", ¿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 una NFA, en una entrada dada, el comportamiento de la simulación es perfectamente determinista.

"Determinista" es una frase cargada. Para un programador informático o científico informático, el comportamiento no determinista simplemente significa que "determinar el comportamiento exacto es complicado de considerar" y depende de muchos factores, incluida la información 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 ser determinados, y los patrones repetibles emergen de un comportamiento "no determinista".

    
respondido por el Kaz 04.11.2013 - 05:47

Lea otras preguntas en las etiquetas