¿Podría generarse un número verdaderamente aleatorio utilizando pings para direcciones IP seleccionadas seudoaleatoriamente?
https://stackoverflow.com/questions/137340
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianPregunta
La pregunta planteada surgió durante una conferencia de segundo año de Comp Science mientras se discutía la imposibilidad de generar números en un dispositivo computacional determinista.
Esta fue la única sugerencia que no dependía de un hardware que no fuera de clase de producto.
Posteriormente, nadie pondría su reputación en la línea para argumentar definitivamente a favor o en contra.
A cualquiera le importa hacer una posición a favor o en contra. Si es así, ¿qué tal una mención sobre una posible implementación?
Solución
No.
Una máquina maliciosa en su red podría usar la falsificación de ARP (o varias otras técnicas) para interceptar sus pings y responderlos después de ciertos períodos. Entonces no solo sabrían cuáles son sus números aleatorios, sino que también los controlarían.
Por supuesto, aún queda la pregunta de cuán determinista es su red local, por lo que podría no ser tan fácil como todo eso en la práctica. Pero como no obtiene ningún beneficio al hacer ping a direcciones IP aleatorias en Internet, también podría obtener la entropía del tráfico de Ethernet.
Dibujar entropía desde dispositivos conectados a su máquina es un principio bien estudiado, y las ventajas y desventajas de varios tipos de dispositivos y métodos de medición pueden ser, por ejemplo. robado de la implementación de / dev / random.
[ Editar : como principio general, al trabajar con los fundamentos de la seguridad (y las únicas necesidades prácticas para cantidades significativas de datos verdaderamente aleatorios están relacionados con la seguridad), DEBES suponer que es increíblemente bueno El atacante determinado y determinado hará todo lo que esté a su alcance para romper tu sistema.
Para seguridad práctica, puede asumir que nadie quiere su clave PGP tan mal y se conforma con una compensación de seguridad contra el costo. Pero cuando invente algoritmos y técnicas, debe darles las garantías de seguridad más sólidas que puedan tener. Ya que puedo creer que alguien, en algún lugar, podría querer la clave privada de otra persona lo suficiente como para crear este kit para derrotar su propuesta, no puedo aceptarlo como un avance sobre las mejores prácticas actuales. AFAIK / dev / random sigue bastante cerca de las mejores prácticas para generar datos verdaderamente aleatorios en una PC doméstica barata]
[ Otra edición : ha sugerido en los comentarios que (1) es cierto en cualquier TRNG que el proceso físico podría verse afectado, y (2) que las preocupaciones de seguridad no se aplican aquí de todos modos .
La respuesta a (1) es que es posible en cualquier hardware real hacerlo mucho mejor que los tiempos de respuesta de ping, y reunir más entropía más rápido, de que esta propuesta no es una solución. En términos de CS, obviamente, no puede generar números aleatorios en una máquina determinista, que es lo que provocó la pregunta. Pero luego, en términos de CS, una máquina con un flujo de entrada externo no es determinista por definición, por lo que si estamos hablando de ping, no estamos hablando de máquinas deterministas. Por lo tanto, tiene sentido observar los datos reales que tienen las máquinas reales y considerarlos como fuentes de aleatoriedad. No importa cuál sea su máquina, los tiempos de ping en bruto no son altos en la lista de fuentes disponibles, por lo que se pueden descartar antes de preocuparse por lo bueno que son los mejores. Suponer que una red no está subvertida es una suposición mucho mayor (e innecesaria) que suponer que su propio hardware no está subvertido.
La respuesta a (2) es filosófica. Si no le importa que sus números aleatorios tengan la propiedad de que pueden ser elegidos por capricho en lugar de por casualidad, entonces esta propuesta está bien. Pero eso no es lo que entiendo por el término 'aleatorio'. El hecho de que algo sea inconsistente no significa que sea necesariamente aleatorio.
Finalmente, para abordar los detalles de implementación de la propuesta según lo solicitado: asumiendo que acepta los tiempos de ping como aleatorios, aún no puede usar los tiempos de ping sin procesar como salida de RNG. Usted no conoce su distribución de probabilidad, y ciertamente no están distribuidas uniformemente (que normalmente es lo que la gente quiere de un RNG).
Por lo tanto, debe decidir cuántos bits de entropía por ping está dispuesto a confiar. La entropía es una propiedad matemática definida con precisión de una variable aleatoria que puede considerarse razonablemente una medida de qué tan "aleatoria" es en realidad. En la práctica, encuentras un límite inferior con el que estás contento. Luego junte un número de entradas y conviértalo en un número de bits de salida menor o igual que la entropía total de las entradas. 'Total' no significa necesariamente suma: si las entradas son estadísticamente independientes, entonces es la suma, pero es poco probable que este sea el caso de pings, por lo que parte de su estimación de entropía será la cuenta de la correlación. La hermana mayor sofisticada de esta operación de hash se llama "recolector de entropía", y todos los sistemas operativos buenos tienen uno.
Sin embargo, si está utilizando los datos para generar un PRNG, y el PRNG puede usar datos de entrada arbitrariamente grandes, no tiene que hacer hash porque lo hará por usted. Aún debe estimar la entropía si quiere saber qué tan aleatorio fue el valor de su semilla. Puede usar el mejor PRNG del mundo, pero su entropía aún está limitada por la entropía de la semilla.]
Otros consejos
Los números aleatorios son demasiado importantes para dejarlos al azar.
O influencia externa / manipulación.
Respuesta corta
El uso de los datos de tiempo de ping por sí solo no sería realmente aleatorio, pero se puede usar como fuente de entropía que luego puede usarse para generar datos verdaderamente aleatorios.
Versión más larga
¿Qué tan aleatorios son los tiempos de ping?
Por sí mismo, los datos de tiempo de las operaciones de la red (como ping) no se distribuirán de manera uniforme. (Y la idea de seleccionar hosts aleatorios no es práctica: muchos no responderán en absoluto, y las diferencias entre los hosts pueden ser enormes, con brechas entre rangos de tiempo de respuesta, piense en las conexiones satelitales).
Sin embargo, aunque el tiempo no estará bien distribuido, habrá algún nivel de aleatoriedad en los datos. O, dicho de otra forma, está presente un nivel de entropía de información . Es una buena idea introducir los datos de tiempo en un generador de números aleatorios para sembrarlos. Entonces, ¿qué nivel de entropía está presente?
Para datos de temporización de red, por ejemplo, alrededor de 50 ms, medidos a los 0.1 ms más cercanos, con una distribución de valores de 2 ms, tiene aproximadamente 20 valores. Redondeando a la potencia más cercana de 2 (16 = 2 ^ 4) tiene 4 bits de entropía por valor de tiempo. Si es para cualquier tipo de aplicación segura (como generar claves criptográficas), sería conservador y diría que solo fueron 2 o 3 bits de entropía por lectura. (Tenga en cuenta que he hecho una estimación muy aproximada aquí, e ignoré la posibilidad de un ataque).
Cómo generar datos verdaderamente aleatorios
Para los verdaderos números aleatorios, debe enviar los datos a algo diseñado siguiendo las líneas de / dev / random que recopilará la entropía, distribuyéndola dentro de un almacén de datos (utilizando algún tipo de función hash , generalmente una secure ). Al mismo tiempo, se incrementa la estimación de entropía. Por lo tanto, para una clave AES de 128 bits, se necesitarían 64 temporizaciones de ping antes de que el grupo de entropía tuviera suficiente entropía.
Para ser más robusto, podría agregar datos de tiempo del uso del teclado y el mouse, tiempos de respuesta del disco duro, datos del sensor de la placa base (por ejemplo, temperatura), etc. Aumenta la tasa de recolección de entropía y hace que sea más difícil para un atacante. Para controlar todas las fuentes de entropía. Y de hecho esto es lo que se hace con los sistemas modernos. La lista completa de fuentes de entropía de MS Windows se encuentra en Segundo comentario de esta publicación .
Más lecturas
Para una discusión de los ataques (de seguridad informática) en generadores de números aleatorios, y el diseño de un generador de números aleatorios criptográficamente seguro, podría hacer algo peor que leer milenrama por Bruce Schneier y John Kelsey. (Los sistemas BSD y Mac OS X utilizan la milenrama).
No.
Desconecte el cable de red (o /etc/init.d/networking stop ) y la entropía básicamente se reduce a cero.
Realice un ataque de denegación de servicio en la máquina que está haciendo ping y también obtendrá resultados predecibles (el valor de tiempo de espera de ping)
Supongo que podrías. Un par de cosas a tener en cuenta:
- Incluso si se hacen ping a direcciones IP aleatorias, los primeros saltos (de usted al primer enrutador L3 real en la red del ISP) serán los mismos para cada paquete. Esto pone un límite inferior en el tiempo de ida y vuelta, incluso si hace ping a algo en un centro de datos en ese primer Punto de Presencia. Por lo tanto, debe tener cuidado al normalizar el tiempo, hay un límite inferior en el viaje de ida y vuelta.
- También debería tener cuidado con la configuración del tráfico en la red. Una implementación típica de un grupo con pérdidas en un enrutador libera N bytes cada M microsegundos, lo que efectivamente perturba su tiempo en intervalos de tiempo específicos en lugar de un rango continuo de veces. Por lo tanto, es posible que deba descartar los bits de orden inferior de su marca de tiempo.
Sin embargo, no estoy de acuerdo con la premisa de que no hay buenas fuentes de entropía en el hardware de los productos básicos. Muchos conjuntos de chips x86 de los últimos años han incluido generadores de números aleatorios. Los que estoy familiarizado con el uso de ADCs relativamente sensibles para medir la temperatura en dos ubicaciones diferentes en el dado y restarlos. Se puede demostrar que los bits de bajo orden de este diferencial de temperatura (a través del análisis de Chi cuadrado) son fuertemente aleatorios. A medida que aumenta la carga de procesamiento en el sistema, la temperatura general aumenta, pero el diferencial entre dos áreas de la matriz permanece sin correlación e impredecible.
La mejor fuente de aleatoriedad en el hardware básico que he visto, fue un tipo que quitó un filtro o algo de su cámara web, puso pegamento opaco en la lente y luego pudo detectar fácilmente píxeles blancos individuales de rayos cósmicos impactantes El CCD. Estos son lo más cerca posible de ser lo más aleatorios posibles, y están protegidos de la inspección externa por los efectos cuánticos.
Parte de un buen generador de números aleatorios es la misma probabilidad de todos los números como n - > infinito.
Entonces, si planea generar bytes aleatorios, entonces, con suficientes datos de un buen rng, cada byte debería tener la misma probabilidad de ser devuelto. Además, no debe haber ningún patrón o previsibilidad (picos de probabilidad durante ciertos períodos de tiempo) de ciertos números que se devuelven.
No estoy muy seguro de usar ping lo que medirías para obtener la variable aleatoria, ¿es el tiempo de respuesta? Si es así, puede estar bastante seguro de que algunos tiempos de respuesta, o rangos de tiempos de respuesta, serán más frecuentes que otros y, por lo tanto, sería un generador de números aleatorios potencialmente inseguro.
Si desea hardware básico, su tarjeta de sonido debería hacerlo. Simplemente suba el volumen en una entrada analógica y tendrá una fuente de ruido blanco barata. Aleatoriedad barata sin la necesidad de una red.
El enfoque de medir algo para generar una semilla aleatoria parece ser bastante bueno. El libro de O'Reilly Unix práctico y seguridad en Internet da una pocos métodos adicionales similares para determinar una semilla aleatoria, como pedirle al usuario que escriba algunas pulsaciones de teclas y luego medir el tiempo entre pulsaciones de teclas. (El libro señala que esta técnica es utilizada por PGP como fuente de su aleatoriedad).
Me pregunto si la temperatura actual de la CPU de un sistema (medida con muchos decimales) podría ser un componente viable de una semilla aleatoria. Este enfoque tendría la ventaja de no tener que acceder a la red (por lo que el generador aleatorio no estará disponible cuando la conexión de red se caiga).
Sin embargo, es probable que no sea probable que el sensor interno de una CPU pueda medir con precisión la temperatura de la CPU con suficientes decimales para que el valor sea realmente viable como una semilla de números aleatorios; al menos, no con " hardware de clase de producto, " como se menciona en la pregunta!
No es tan bueno como el uso del ruido atmosférico, pero sigue siendo verdaderamente aleatorio, ya que depende de las características de la red, que es notoria por el comportamiento aleatorio no repetible.
Consulte Random.org para obtener más información sobre la aleatoriedad.
Aquí hay un intento de implementación:
@ips : list = getIpAddresses();
@rnd = PseudorandomNumberGenerator(0 to (ips.count - 1));
@getTrueRandomNumber() { ping(ips[rnd.nextNumber()]).averageTime }
Preferiría usar algo como ISAAC como un PRNG más fuerte antes de confiar en el viaje de ida y vuelta Pings como entropía. Como han dicho otros, sería demasiado fácil para alguien no solo adivinar sus números, sino también posiblemente controlarlos en diversos grados.
Existen otras grandes fuentes de entropía, que otros han mencionado. Uno de los que no se mencionó (lo que podría no ser práctico) es el ruido de muestreo del dispositivo de audio incorporado, que suele ser un poco ruidoso incluso si no hay un micrófono conectado.
Fui a 9 rondas tratando de encontrar un PRNG fuerte (y rápido) para un mecanismo RPC cliente / servidor que estaba escribiendo. Ambos lados tenían una clave idéntica, que consiste en 1024 líneas de cifrados de 32 caracteres. El cliente enviaría AUTH xx, el servidor devolvería AUTH yy ... y ambas partes sabían qué dos líneas de la clave utilizar para producir el secreto del pez globo (+ sal). El servidor luego enviaría un resumen SHA-256 de la clave completa (encriptada), el cliente sabía que estaba hablando con algo que tenía la clave correcta ... la sesión continuó. Sí, muy débil protección para el hombre en el medio, pero una clave pública estaba fuera de la cuestión de cómo se estaba utilizando el dispositivo.
Entonces, tenías un servidor no bloqueante que tenía que manejar hasta 256 conexiones ... no solo el PRNG tenía que ser fuerte, tenía que ser rápido. No fue tan difícil utilizar métodos más lentos para recopilar entropía en el cliente, pero eso no se podía permitir en el servidor.
Entonces, tengo que preguntar sobre tu idea ... ¿qué tan práctico sería?
Ningún cálculo matemático puede producir un resultado aleatorio, pero en el " mundo real " las computadoras no solo hacen números precisos ... Con un poco de creatividad debería ser posible producir resultados aleatorios del tipo donde no se conoce un método para reproducir o predecir resultados exactos.
Una de las ideas más fáciles de implementar que he visto y que funciona universalmente en todos los sistemas es usar la estática de la línea de la tarjeta de sonido de la computadora en el puerto / mic.
Otras ideas incluyen el ruido térmico y la sincronización de bajo nivel de las líneas de caché. Muchas PC modernas con chips TPM tienen hardware de encriptación con generadores de números aleatorios ya incorporados.
Mi reacción instintiva al ping (especialmente si se usa ICMP) es que estás haciendo trampas demasiado descaradamente. En ese momento, también podrías sacar un contador de Giger y usar radiación de fondo como fuente aleatoria.
Sí, es posible, pero ... el diablo está en los detalles.
Si va a generar un número entero de 32 bits, debe reunir > 32 bits de entropía (y usar una función de mezcla suficiente para hacer que esa entropía se extienda, pero eso es conocido y factible). La gran pregunta que es:
¿Cuánta entropía tienen los tiempos de ping?
La respuesta a esta pregunta depende de todo tipo de suposiciones sobre la red y su modelo de ataque, y hay diferentes respuestas en diferentes circunstancias.
Si los atacantes son capaces de controlar totalmente los tiempos de ping, obtienes 0 bits de entropía por ping y nunca puedes sumar 32 bits de entropía, sin importar cuánto mezcles. Si tienen un control menos que perfecto sobre los tiempos de ping, obtendrás algo de entropía y (si no sobrestimas la cantidad de entropía que estás reuniendo) obtendrás números de 32 bits perfectamente aleatorios.
YouTube muestra un dispositivo en acción: http://www.youtube.com/watch? v = 7n8LNxGbZbs
Aleatorio es, si nadie puede predecir el siguiente estado.
Aunque no puedo ubicar definitivamente un sitio a favor o en contra, esta implementación tiene sus problemas.
¿De dónde provienen estas direcciones IP? Si se seleccionan al azar, lo que sucede cuando no responden o se demoran en responder, significa que el número aleatorio será más lento en aparecer.
Además, incluso si hiciera un gráfico visual de 100.000 resultados y calculara que no hay o hay pocas correlaciones entre los números, no significa que sea realmente aleatorio. Tal como se explica en dilbert :)
No me parece una buena fuente de aleatoriedad.
¿Qué métrica usaría? la obvia es el tiempo de respuesta, pero el rango de valores que razonablemente puede esperar es pequeño: de unas pocas decenas de milisegundos a unos pocos miles. Los tiempos de respuesta seguirán una curva de campana y no se distribuirán al azar en ningún intervalo (¿cómo elegiría el intervalo?), Por lo que tendría que intentar seleccionar algunos bits "aleatorios" de los números.
El LSB podría proporcionarle un flujo de bits aleatorio, pero debería tener en cuenta los problemas de granularidad del reloj, tal vez debido a la forma en que funcionan las interrupciones siempre obtendrá múltiplos de 2 ms en algunos sistemas.
Probablemente hay formas mucho mejores y 'interesantes' de obtener bits aleatorios, tal vez buscar una palabra al azar en Google, tome la primera página y elija el bit Nth de la página.
Eh, encuentro que este tipo de pregunta conduce a discusiones sobre el significado de 'verdaderamente aleatorio' con bastante rapidez.
Creo que la medición de pings produciría bits aleatorios de calidad decente, pero a una tasa insuficiente para ser de mucha utilidad (a menos que estuvieras dispuesto a hacer algo de DDOS grave).
Y no veo que sea más aleatorio que medir las propiedades analógicas / mecánicas de la computadora, o el comportamiento de la bolsa de carne que la opera.
(editar) En una nota práctica, este enfoque le abre la posibilidad de que alguien en su red manipule su generador de números "aleatorios".
Me parece que la verdadera aleatoriedad es inefable; no hay manera de saber si una secuencia es aleatoria, ya que por definición puede contener cualquier cosa sin importar cuán improbable sea. Garantizar un patrón de distribución particular reduce la aleatoriedad. La palabra " patrón " Es un poco un regalo.
I MADE U A RANDOM NUMBER
BUT I EATED IT
La aleatoriedad no es una propiedad binaria, es un valor entre 0 y 1 que describe lo difícil que es predecir el siguiente valor en una secuencia.
Preguntando " ¿qué tan aleatorios pueden ser mis valores si los baso en pings? " en realidad está preguntando "¿qué aleatorios son los pings?". Puede estimar eso reuniendo un conjunto suficientemente grande de datos (por ejemplo, 1 millón de pings) y mapeando su curva de distribución y comportamiento en el tiempo. Si la distribución es plana y el comportamiento es difícil de predecir, los datos parecen más aleatorios. La distribución más desigual o el comportamiento predecible sugieren una aleatoriedad menor.
También debe considerar la resolución de muestra. Podría imaginar que los resultados se redondearían de alguna manera a un milisegundo, por lo que con pings podría tener valores enteros entre 0 y 500. Eso no es mucha resolución.
En el aspecto práctico, lo recomendaría, ya que los pings se pueden predecir y manipular, lo que reduce aún más su aleatoriedad.
En general, sugiero en contra de " rodar tus propios " Generadores de aleatoriedad, métodos de encriptación y algoritmos de hash. Por más divertido que parezca, es sobre todo una matemática muy intimidante.
En cuanto a cómo construir un generador de entropía realmente bueno, creo que probablemente tendrá que ser una caja sellada que genere algún tipo de resultado de interacciones en el nivel atómico o subatómico. Quiero decir, si estás usando una fuente de entropía que el enemigo también puede leer fácilmente, solo necesita descubrir tu algoritmo. Cualquier forma de conexión es un posible vector de ataque, por lo que debe colocar la fuente de entropía lo más cerca posible del servicio que la consume.
Puedes usar el método XKCD:
Tengo un código que crea números aleatorios con traceroute. También tengo un programa que lo hace usando ping. Lo hice hace más de un año para un proyecto de clase. Todo lo que hace es ejecutar traceroute on y address y toma el dígito mínimo de las ms veces. Funciona bastante bien para obtener números aleatorios, pero realmente no sé qué tan cerca está del verdadero azar.
Aquí hay una lista de 8 números que obtuve cuando lo ejecuté.
455298558263758292242406192
506117668905625112192115962
805206848215780261837105742
095116658289968138760389050
465024754117025737211084163
995116659108459780006127281
814216734206691405380713492
124216749135482109975241865
#include <iostream>
#include <string>
#include <stdio.h>
#include <cstdio>
#include <stdlib.h>
#include <vector>
#include <fstream>
using namespace std;
int main()
{
system("traceroute -w 5 www.google.com >> trace.txt");
string fname = "trace.txt";
ifstream in;
string temp;
vector<string> tracer;
vector<string> numbers;
in.open(fname.c_str());
while(in>>temp)
tracer.push_back(temp);
system("rm trace.txt");
unsigned index = 0;
string a = "ms";
while(index<tracer.size())
{
if(tracer[index]== a)
numbers.push_back(tracer[index-1]);
++index;
}
std::string rand;
for(unsigned i = 0 ; i < numbers.size() ; ++i)
{
std::string temp = numbers[i];
int index = temp.size();
rand += temp[index - 1];
}
cout<<rand<<endl;
return 0;
}
Muy simple, ya que las redes obedecen las reglas prescritas, los resultados no son aleatorios.
La idea de la webcam suena (ligeramente) razonable. La gente de Linux a menudo recomienda simplemente usar el ruido aleatorio de una tarjeta de sonido que no tiene un micrófono conectado.
Aquí está mi sugerencia:
1- Elija un puñado de sitios web que estén lo más lejos posible de su ubicación. p.ej. Si se encuentra en EE. UU., pruebe algunos sitios web que tengan sus IP de servidor en malasia, China, Rusia, India ... etc. Los servidores con alto tráfico son mejores.
2- durante las horas de alto tráfico de Internet en su país (en mi país es de 7 a 11 pm) haga ping a esos sitios web muchas veces, tome cada resultado de ping (use solo el valor entero) y calcule el módulo 2 de es (es decir, de cada operación de ping se obtiene un bit: 0 o 1).
3- Repita el proceso durante varios días, registrando los resultados.
4- recopila todos los bits que obtuviste de todos tus pings (probablemente obtendrás cientos de miles de bits) y elige entre ellos tus bits. (quizás quieras elegir tus bits utilizando algunos datos del mismo método mencionado anteriormente :))
TENGA CUIDADO: en su código debe verificar el tiempo de espera ... etc.
