algorithm - sostenido - tipos de ping
¿Se podría generar un número verdaderamente aleatorio utilizando pings para direcciones IP seleccionadas de forma pseudoaleatoria? (23)
Respuesta corta
El uso de datos de temporización de ping por sí solo no sería realmente aleatorio, pero puede usarse como una fuente de entropy que luego puede usarse para generar datos verdaderamente aleatorios.
Versión más larga
¿Cuán aleatorios son los tiempos de ping?
Por sí solo, los datos de tiempo de las operaciones de red (como el ping) no se distribuirán uniformemente. (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 conexiones satelitales).
Sin embargo, aunque el tiempo no estará bien distribuido, habrá un cierto nivel de aleatoriedad en los datos. O para decirlo de otra manera, hay un nivel de entropy de la entropy presente. Es una buena idea alimentar los datos de tiempo en un generador de números aleatorios para sembrarlo. Entonces, ¿qué nivel de entropía está presente?
Para datos de temporización de red de, digamos, alrededor de 50 ms, medidos al 0.1 ms cercano, con una dispersión de valores de 2 ms, tiene alrededor de 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 la generación de claves criptográficas), entonces sería conservador y diría que fueron solo 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 números aleatorios verdaderos, debe enviar los datos a algo diseñado en la línea de /dev/random que recolectará la entropía, distribuyéndola dentro de un data store (usando algún tipo de función hash , generalmente una segura ). Al mismo tiempo, la estimación de la entropía aumenta. Por lo tanto, para una clave AES de 128 bits, se necesitarían 64 sincronizaciones de ping antes de que el grupo de entropía tuviera suficiente entropía.
Para ser más robusto, podría agregar datos de temporización del uso del teclado y del mouse, tiempos de respuesta del disco duro, datos del sensor de la placa base (p. Ej. Temperatura). Aumenta la tasa de recolección de entropía y dificulta que un atacante controle 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 enumera en el segundo comentario de esta publicación .
Más lectura
Para una discusión sobre 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 el papel milenrama de Bruce Schneier y John Kelsey. (Yarrow es utilizado por los sistemas BSD y Mac OS X).
La pregunta que se planteó surgió durante una conferencia de Ciencias de la Computación del 2º año mientras se discutía la imposibilidad de generar números en un dispositivo computacional determinista.
Esta fue la única sugerencia que no dependía del hardware de clase no comercial.
Posteriormente, nadie pondría su reputación en la línea para discutir definitivamente a favor o en contra.
A cualquiera le importa defenderse o estar en contra. Si es así, ¿qué tal una mención sobre una posible implementación?
Antes utilizaría algo así como ISAAC como un PRNG más fuerte antes de confiar en pings de ida y vuelta como la 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 varios grados.
Existen otras grandes fuentes de entropía, que otros han mencionado. Uno que no se mencionó (que podría no ser práctico) es el ruido de muestreo del dispositivo de audio a bordo ... que generalmente va a ser un poco ruidoso incluso si no hay un micrófono conectado a él.
Pasé 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 consta de 1024 líneas de cifras de 32 caracteres. El cliente enviará AUTH xx, el servidor devolverá AUTH yy ... y ambas partes sabrán qué dos líneas de la clave usar para producir el secreto blowfish (+ salt). 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í, una protección muy débil para el hombre en el medio, pero una clave pública estaba fuera de discusión sobre cómo se usaba el dispositivo.
Entonces, usted tenía un servidor que no bloqueaba y tenía que manejar hasta 256 conexiones ... no solo el PRNG tenía que ser fuerte, tenía que ser rápido. No era tan difícil utilizar métodos más lentos para reunir entropía en el cliente, pero eso no se podía permitir en el servidor.
Entonces, tengo que preguntarle sobre su idea ... ¿Qué tan práctico sería?
Aunque no puedo ubicarme definitivamente a favor o en contra, esta implementación tiene sus problemas.
¿De dónde provienen estas direcciones IP, si se seleccionan al azar, qué sucede cuando no responden o llegan tarde para responder, significa que el número aleatorio será más lento para aparecer.
Además, incluso si hace un gráfico visual de 100.000 resultados y calcula que no hay o hay pocas correlaciones entre los números, no significa que sea verdaderamente aleatorio. Como lo explica dilbert :)
Eh, encuentro que este tipo de preguntas conducen a discusiones sobre el significado de ''verdaderamente aleatorio'' bastante rápido.
Creo que la medición de pings arrojaría bits aleatorios de calidad decente, pero a un ritmo insuficiente para ser de mucha utilidad (a menos que estuvieras dispuesto a hacer un DDOSing serio).
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.
(edit) En una nota práctica, este enfoque te abre a la posibilidad de que alguien en tu red manipule tu generador de números "aleatorio".
El enfoque de medir algo para generar una semilla aleatoria parece ser bastante bueno. El libro de O''Reilly Practical Unix e Internet Security ofrece algunos métodos adicionales similares para determinar una semilla aleatoria, como pedirle al usuario que escriba unas pocas teclas y luego medir el tiempo entre las 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 necesitar acceder a la red (por lo que el generador aleatorio no estaría disponible cuando la conexión de red se desactiva).
Sin embargo, probablemente no sea probable que el sensor interno de una CPU pueda medir con precisión la temperatura de la CPU a un número de decimales suficiente como para que el valor sea realmente viable como una semilla de número aleatorio; al menos, no con "hardware de clase económica", como se menciona en la pregunta.
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.
Preguntar "¿qué tan aleatorios pueden ser mis valores si los base en pings?" en realidad está preguntando "¿qué tan aleatorio son los pings?". Puede estimar eso reuniendo un conjunto de datos lo suficientemente grande (pings de 1 mln por ejemplo) y mapeando su curva de distribución y comportamiento a 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 accidentada o el comportamiento predecible sugieren una menor aleatoriedad.
También debes considerar la resolución de la muestra. Me imagino que los resultados se redondean de alguna manera a un milisegundo, por lo que con los pings se pueden tener valores enteros entre 0 y 500. Esa no es mucha resolución.
En el aspecto práctico, recomendaría no hacerlo, ya que los pings pueden predecirse y manipularse, reduciendo aún más su aleatoriedad.
En general, sugiero que no se generen los propios generadores de aleatoriedad, los métodos de cifrado y los algoritmos hash. Por divertido que parezca, es en su mayoría un montón de matemáticas muy intimidantes.
En cuanto a cómo construir un generador de entropía realmente bueno, creo que probablemente tenga que ser una caja sellada que produzca algún tipo de resultado de interacciones a 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 averiguar 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.
La mejor fuente de aleatoriedad en hardware básico que he visto, fue un tipo que eliminó un filtro o algo de su cámara web, puso pegamento opaco en la lente y luego pudo detectar fácilmente los píxeles blancos individuales de los rayos cósmicos que golpean la CCD. Estos son lo más aleatorios posible y están protegidos de la intromisión externa por efectos cuánticos.
Los números aleatorios son demasiado importantes para dejarlos al azar.
O influencia / manipulación externa.
Me parece que la verdadera aleatoriedad es inefable: no hay forma de saber si una secuencia es aleatoria, ya que por definición puede contener cualquier cosa, por improbable que sea. Garantizar un patrón de distribución particular reduce la aleatoriedad. La palabra "patrón" es un poco entregada.
I MADE U A RANDOM NUMBER
BUT I EATED IT
Muy simplemente, dado que las redes obedecen las reglas prescritas, los resultados no son aleatorios.
La idea de la cámara web suena (un poco) razonable. La gente de Linux a menudo recomienda simplemente usar el ruido aleatorio de una tarjeta de sonido que no tiene micrófono conectado.
Ningún cálculo matemático puede producir un resultado aleatorio, pero en el "mundo real" las computadoras no hacen exactamente números crujientes ... Con un poco de creatividad debería ser posible producir resultados aleatorios del tipo donde no hay un método conocido de reproduciendo o prediciendo 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 estática de la línea de la tarjeta de sonido de la computadora en / mic port.
Otras ideas incluyen el ruido térmico y el bajo nivel de sincronización de las líneas de caché. Muchas PC modernas con chips TPM tienen generadores de números aleatorios de calidad de encriptación ya a bordo.
Mi reacción de kneejerk al ping (especialmente si se usa ICMP) es que tu trampa es demasiado falsa. En ese punto, también podría sacar un contador giger y usar radiación de fondo como fuente aleatoria.
No es tan bueno como usar ruido atmosférico, pero sigue siendo realmente aleatorio ya que depende de las características de la red que es notoria para el comportamiento aleatorio no repetible.
Vea Random.org para 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 }
No me parece una buena fuente de aleatoriedad.
¿Qué medida usaría? La más obvia es el tiempo de respuesta, pero el rango de valores que puede razonablemente esperar es pequeño: algunas decenas de milisegundos a algunos miles. Los tiempos de respuesta en sí seguirán una curva de campana y no se distribuirán aleatoriamente en ningún intervalo (¿cómo elegirías el intervalo?) Por lo que tendrías que intentar seleccionar algunos bits "aleatorios" de los números.
El LSB podría darle un flujo de bits aleatorio, pero tendría que considerar los problemas de granularidad del reloj; tal vez debido a cómo funcionan las interrupciones, siempre obtendrá múltiplos de 2 ms en algunos sistemas.
Probablemente haya formas mucho mejores "interesantes" de obtener bits aleatorios, tal vez google por una palabra al azar, agarrar la primera página y elegir la enésima parte de la página.
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 ping-timeout)
Parte de un buen generador de números aleatorios es igual a las probabilidades de todos los números como n -> infinito.
Entonces, si está planeando 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 predictibilidad (picos de probabilidad durante ciertos períodos de tiempo) de que se devuelvan ciertos números.
No estoy muy seguro con el uso del ping de lo que mediría 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, crearían un generador de números aleatorios potencialmente inseguro.
Pondré mi representante en la línea (al menos, 2 puntos por voto negativo).
No.
Una máquina maliciosa en su red podría usar suplantación de ARP (o una serie de otras técnicas) para interceptar sus ping y responder a ellos después de ciertos períodos. Entonces no solo sabrían cuáles son sus números aleatorios, sino que los controlarían.
Por supuesto, aún existe la cuestión 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 dado que no obtiene ningún beneficio al hacer ping a direcciones IP aleatorias en Internet, también puede extraer entropía del tráfico de ethernet.
Dibujar entropía desde dispositivos conectados a su máquina es un principio bien estudiado, y los pros y los contras de varios tipos de dispositivos y métodos de medición pueden ser robados, por ejemplo, de la implementación de / dev / random.
[ Editar : como principio general, cuando se trabaja en los fundamentos de la seguridad (y las únicas necesidades prácticas para cantidades significativas de datos verdaderamente aleatorios están relacionadas con la seguridad) DEBE asumir que un atacante con recursos fantásticos y con recursos suficientes hará todo lo posible en su poder para romper tu sistema
Para la seguridad práctica, puede suponer que nadie quiere su clave PGP tan mal, y conformarse con una compensación de seguridad contra el costo. Pero cuando inventa algoritmos y técnicas, debe brindarles las garantías de seguridad más sólidas que puedan enfrentar. Como puedo creer que alguien, en algún lugar, puede querer la clave privada de otra persona lo suficiente como para construir 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 de casa barata]
[ Otra edición : ha sugerido en comentarios que (1) es cierto de 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 realista hacer mucho mejor que los tiempos de respuesta de ping, y reunir más entropía más rápido, que esta propuesta no es una solución. En términos CS, obviamente no se pueden 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 cualquier flujo de entrada externo no es determinista por definición, así que si estamos hablando de ping, entonces no estamos hablando de máquinas deterministas. Por lo tanto, tiene sentido mirar las entradas reales que tienen las máquinas reales y considerarlas como fuentes de aleatoriedad. No importa cuál sea su máquina, los tiempos de ping en bruto no ocupan un lugar destacado en la lista de fuentes disponibles, por lo que pueden descartarse antes de preocuparse por lo bueno que son los mejores. Asumir que una red no está subvertida es una suposición mucho más grande (e innecesaria) que suponer que su propio hardware no está subvertido.
La respuesta a (2) es filosófica. Si no te importa que tus números aleatorios tengan la propiedad de que pueden elegirse por capricho y no 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 no procesados como salida de RNG. No conoce su distribución de probabilidad, y ciertamente no están distribuidos uniformemente (lo que normalmente es lo que la gente quiere de un RNG).
Por lo tanto, debe decidir en 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 se puede considerar razonablemente como una medida "aleatoria" de la realidad. En la práctica, encuentras un límite inferior con el que estás satisfecho. A continuación, agrupe varias entradas y conviértalas en una cantidad de bits de salida inferior o igual a la entropía total confiada de las entradas. ''Total'' no necesariamente significa suma: si las entradas son estadísticamente independientes, entonces es la suma, pero es poco probable que este sea el caso para los pings, por lo que parte de su estimación de entropía será para tener en cuenta la correlación. La hermana mayor sofisticada de esta operación hash se llama un ''colector de entropía'', y todos los buenos sistemas operativos tienen uno.
Sin embargo, si está usando los datos para sembrar un PRNG, y el PRNG puede usar una cantidad de semillas arbitrariamente grande, entonces no tiene que hacer hash porque lo hará por usted. Aún debe estimar la entropía si desea 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.]
Puedes usar el método XKCD:
Sí, es posible, pero ... el diablo está en los detalles.
Si vas a generar un número entero de 32 bits, necesitas reunir más de 32 bits de entropía (y usar una función de mezcla suficiente para extender esa entropía, pero eso es conocido y factible). La gran pregunta 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 pueden controlar por completo los tiempos de ping, obtienes 0 bits de entropía por ping, y nunca puedes totalizar 32 bits de entropía, sin importar cuánto mezclas. Si tienen un control menos que perfecto sobre los tiempos de ping, obtendrás algo de entropía, y (si no sobreestimas la cantidad de entropía que estás reuniendo) obtendrás números de 32 bits perfectamente aleatorios.
Si quieres hardware básico, tu tarjeta de sonido debería hacerlo. Simplemente suba el volumen de una entrada analógica y tendrá una fuente barata de ruido blanco. Aleatoriedad barata sin la necesidad de una red.
Supongo que podrías. Un par de cosas para tener en cuenta:
- Incluso si hace 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. Entonces debes tener cuidado con la normalización del 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 cubo con fugas en un enrutador libera N bytes cada M microsegundos, lo que interrumpe efectivamente el tiempo en intervalos de tiempo específicos en lugar de un intervalo continuo de veces. Por lo tanto, es posible que deba descartar los bits de orden inferior de su marca de tiempo.
Sin embargo, estoy en desacuerdo con la premisa de que no hay buenas fuentes de entropía en el hardware básico. Muchos conjuntos de chips x86 de los últimos años incluyen generadores de números aleatorios. Con los que estoy familiarizado utilizo ADCs relativamente sensibles para medir la temperatura en dos ubicaciones diferentes en el dado y restarlos. Los bits de orden bajo de esta diferencia de temperatura pueden mostrarse (mediante análisis Chi-cuadrado) como fuertemente aleatorios. A medida que aumenta la carga de procesamiento en el sistema, la temperatura general aumenta, pero la diferencia entre las dos áreas de la matriz permanece sin correlación e imprevisible.
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 el trazado de ruta y la dirección y toma el dígito menos sig de los tiempos ms. 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;
}
YouTube muestra un dispositivo en acción: http://www.youtube.com/watch?v=7n8LNxGbZbs
Aleatorio es, si nadie puede predecir el siguiente estado.
aquí está mi sugerencia:
1- Elija un puñado de sitios web que estén lo más lejos posible de su ubicación. por ejemplo, si se encuentra en los Estados Unidos, pruebe algunos sitios web que tienen sus direcciones IP de servidor en malasia, china, rusia, india ... etc. los servidores con mucho tráfico son mejores
2- en tiempos de alto tráfico de Internet en tu país (en mi país son como 7 a 11 p. M.), Haz ping a esos sitios muchas veces, toma cada resultado de ping (usa solo el valor entero) y calcula el módulo 2 (es decir, de cada operación de ping obtienes un bit: 0 o 1).
3- repite el proceso por varios días, registrando los resultados.
4- recoge todos los bits que obtuviste de todos tus ping (probablemente obtendrás cientos de miles de bits) y elije de ellos tus bits. (Quizás quieras elegir tus bits usando algunos datos del mismo método mencionado anteriormente :))
TENGA CUIDADO: en su código debe verificar el tiempo de espera ..etc