Может ли действительно случайное число быть сгенерировано с помощью пингов на псевдослучайно выбранные IP-адреса?
https://stackoverflow.com/questions/137340
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianВопрос
Поставленный вопрос возник во время лекции по информатике на 2 курсе, когда обсуждалась невозможность генерации чисел в детерминированном вычислительном устройстве.
Это было единственное предложение, которое не зависело от оборудования не товарного класса.
Впоследствии никто не стал бы рисковать своей репутацией, чтобы окончательно аргументировать за или против этого.
Любой желающий может высказаться за или против.Если да, то как насчет упоминания о возможной реализации?
Решение
Нет.
Вредоносная машина в вашей сети может использовать ARP-подмену (или ряд других методов), чтобы перехватывать ваши запросы и отвечать на них через определенные промежутки времени.Тогда они не только знали бы, что такое ваши случайные числа, но и контролировали бы их.
Конечно, все еще остается вопрос о том, насколько детерминирована ваша локальная сеть, так что на практике это может быть не так просто.Но поскольку вы не получаете никакой выгоды от пинга случайных IP-адресов в Интернете, вы могли бы с таким же успехом извлекать энтропию из трафика ethernet.
Извлечение энтропии из устройств, подключенных к вашей машине, является хорошо изученным принципом, и плюсами и минусами различных типов устройств и методов измерения могут быть, напримерукрадено из реализации /dev/random.
[Редактировать:в качестве общего принципа, при работе с основами безопасности (а единственные практические потребности в значительных объемах действительно случайных данных связаны с безопасностью) вы ДОЛЖНЫ исходить из того, что фантастически хорошо оснащенный, решительный злоумышленник сделает все, что в его силах, чтобы взломать вашу систему.
Для практической безопасности вы можете предположить, что ваш ключ PGP никому так сильно не нужен, и согласиться на компромисс между безопасностью и стоимостью.Но когда вы изобретаете алгоритмы и методы, вам нужно предоставить им самые надежные гарантии безопасности, с которыми они когда-либо могли столкнуться.Поскольку я могу поверить, что кому-то где-то может понадобиться чужой закрытый ключ настолько сильно, чтобы создать этот набор, который опровергнет ваше предложение, я не могу принять это как шаг вперед по сравнению с текущей передовой практикой.AFAIK / dev /random довольно близко соответствует передовой практике генерации действительно случайных данных на дешевом домашнем ПК]
[Еще одна правка:в комментариях было высказано предположение, что (1) для любого TRNG верно, что на физический процесс можно повлиять, и (2) что соображения безопасности здесь в любом случае неприменимы.
Ответ на (1) заключается в том, что на любом реальном оборудовании можно работать намного лучше, чем время отклика на ping, и быстрее собирать больше энтропии, что это предложение не является решением.В терминах CS, очевидно, что вы не можете генерировать случайные числа на детерминированной машине, что и спровоцировало этот вопрос.Но тогда в терминах CS машина с внешним входным потоком недетерминирована по определению, так что если мы говорим о ping, то мы не говорим о детерминированных машинах.Поэтому имеет смысл взглянуть на реальные входные данные, которыми располагают реальные машины, и рассматривать их как источники случайности.Независимо от того, на какой машине вы работаете, необработанное время пинга невелико в списке доступных источников, поэтому их можно исключить, прежде чем беспокоиться о том, что хорошо, а что лучше.Предположение, что сеть не нарушена, является гораздо большим (и ненужным) предположением, чем предположение, что ваше собственное оборудование не нарушено.
Ответ на (2) носит философский характер.Если вы не возражаете против того, что ваши случайные числа обладают тем свойством, что их можно выбирать по прихоти, а не случайно, то это предложение подходит.Но это не то, что я понимаю под термином "случайный".Просто потому, что что-то противоречиво, не означает, что это обязательно случайно.
Наконец, рассмотреть детали реализации предложения в соответствии с запросом:предполагая, что вы принимаете время пинга как случайное, вы все равно не можете использовать необработанное время пинга в качестве выходных данных RNG.Вы не знаете их распределения вероятностей, и они, конечно же, распределены неравномерно (чего обычно люди хотят от ГСЧ).
Итак, вам нужно решить, на сколько бит энтропии за пинг вы готовы положиться.Энтропия - это точно определенное математическое свойство случайной величины, которое обоснованно можно считать мерой того, насколько "случайной" она является на самом деле.На практике вы находите нижнюю границу, которая вас устраивает.Затем хэшируйте вместе несколько входных данных и преобразуйте это в количество бит выходных данных, меньшее или равное общей полагающейся энтропии входных данных."Итого" не обязательно означает сумму:если входные данные статистически независимы, то это сумма, но это вряд ли относится к пингам, поэтому частью вашей оценки энтропии будет учет корреляции.Сложная старшая сестра этой операции хеширования называется "сборщиком энтропии", и она есть у всех хороших операционных систем.
Однако, если вы используете данные для заполнения PRNG, и PRNG может использовать сколь угодно большие начальные входные данные, тогда вам не нужно хэшировать, потому что он сделает это за вас.Вам все равно придется оценить энтропию, если вы хотите знать, насколько "случайным" было ваше начальное значение - вы можете использовать лучший PRNG в мире, но его энтропия по-прежнему ограничена энтропией начального значения.]
Другие советы
Случайные числа слишком важны, чтобы их можно было оставлять на волю случая.
Или внешнее влияние/манипуляция.
Краткий ответ
Использование данных синхронизации ping само по себе не было бы по-настоящему случайным, но их можно использовать в качестве источника энтропия которые затем могут быть использованы для генерации действительно случайных данных.
Более длинная версия
Насколько случайным является время пинга?
Сами по себе временные данные от сетевых операций (такие как ping) распределялись бы неравномерно.(И идея выбора случайных хостов непрактична - многие из них вообще не будут отвечать, а различия между хостами могут быть огромными, с разрывами между диапазонами времени отклика - подумайте о спутниковых соединениях).
Однако, хотя хронометраж не будет распределен должным образом, в данных будет присутствовать некоторый уровень случайности.Или, другими словами, уровень информационная энтропия присутствует.Это прекрасная идея - передать временные данные в генератор случайных чисел, чтобы заполнить их.Итак, какой уровень энтропии присутствует?
Для данных синхронизации сети, скажем, около 50 мс, измеренных с точностью до 0,1 мс, с разбросом значений в 2 мс, у вас есть около 20 значений.Округляя в меньшую сторону до ближайшей степени 2 (16 = 2 ^ 4), вы получаете 4 бита энтропии на значение синхронизации.Если это для любого вида защищенного приложения (например, для генерации криптографических ключей), то я бы был консервативен и сказал, что это было всего 2 или 3 бита энтропии на чтение. (Обратите внимание, что я сделал здесь очень приблизительную оценку и проигнорировал возможность атаки).
Как генерировать действительно случайные данные
Для получения истинных случайных чисел вам нужно отправить данные во что-то, разработанное в соответствии с /dev/случайный это позволит собирать энтропию, распределяя ее внутри хранилища данных (используя какой-то хэш-функция, обычно это безопасный один из них).В то же время оценка энтропии увеличивается.Таким образом, для 128-битного ключа AES потребуется 64 времени пинга, прежде чем пул энтропии наберет достаточно энтропии.
Для большей надежности вы могли бы затем добавить временные данные об использовании клавиатуры и мыши, время отклика жесткого диска, данные датчиков материнской платы (например, температуры) и т.д.Это увеличивает скорость сбора энтропии и затрудняет злоумышленнику отслеживание всех источников энтропии.И действительно, именно это делается с помощью современных систем.Полный список источников энтропии MS Windows приведен в второй комментарий к этому сообщению.
Больше чтения
Для обсуждения атак (компьютерной безопасности) на генераторы случайных чисел и разработки криптографически защищенного генератора случайных чисел вы могли бы сделать кое-что похуже, чем прочитать бумага из тысячелистника Автор: Bruce Schneier и Джон Келси.(Yarrow используется в системах BSD и Mac OS X).
Нет.
Отсоедините сетевой кабель (или /etc/init.d/networking stop) и энтропия в основном падает до нуля.
Выполните атаку типа "Отказ в обслуживании" на компьютер, на котором выполняется пинг, и вы также получите предсказуемые результаты (значение времени ожидания пинга).
Я думаю, ты мог бы.Пара вещей, на которые следует обратить внимание:
- Даже при пинге случайных IP-адресов первые несколько переходов (от вас к первому реальному маршрутизатору L3 в сети интернет-провайдера) будут одинаковыми для каждого пакета.Это накладывает нижнюю границу на время прохождения туда и обратно, даже если вы пингуете что-либо в центре обработки данных в этой первой точке присутствия.Таким образом, вы должны быть осторожны при нормализации времени, поскольку существует нижняя граница для поездки туда и обратно.
- Вам также следует быть осторожным при формировании трафика в сети.Типичная реализация с утечкой данных в маршрутизаторе высвобождает N байт каждые M микросекунд, что эффективно нарушает вашу синхронизацию в определенных временных интервалах, а не в непрерывном диапазоне времен.Таким образом, вам, возможно, придется отказаться от младших разрядов вашей временной метки.
Однако я бы не согласился с предположением, что в обычном оборудовании нет хороших источников энтропии.Многие чипсеты x86 за последние несколько лет включили генераторы случайных чисел.Те, с которыми я знаком, используют относительно чувствительные АЦП для измерения температуры в двух разных местах матрицы и их вычитания.Можно показать (с помощью анализа Хи-квадрат), что биты младшего порядка этой разницы температур являются сильно случайными.По мере увеличения рабочей нагрузки на систему общая температура повышается, но разница между двумя участками матрицы остается некоррелированной и непредсказуемой.
Лучшим источником случайности на обычном оборудовании, который я видел, был парень, который снял фильтр или что-то в этом роде со своей веб-камеры, нанес непрозрачный клей на объектив, а затем смог легко обнаружить отдельные белые пиксели от космических лучей, попадающих на ПЗС-матрицу.Они настолько близки к идеально случайным, насколько это возможно, и защищены от внешнего слежения квантовыми эффектами.
Частью хорошего генератора случайных чисел является равенство вероятностей всех чисел как n -> бесконечность.
Итак, если вы планируете генерировать случайные байты, то при достаточном количестве данных из хорошего ГСЧ каждый байт должен иметь равную вероятность возврата.Кроме того, не должно быть никакой закономерности или предсказуемости (всплесков вероятности в течение определенных периодов времени) возврата определенных чисел.
Я не слишком уверен в использовании ping, что бы вы измеряли, чтобы получить случайную величину, это время отклика?Если это так, вы можете быть почти уверены, что некоторые времена отклика или диапазоны времени отклика будут более частыми, чем другие, и, следовательно, создадут потенциально небезопасный генератор случайных чисел.
Если вам нужно обычное оборудование, ваша звуковая карта должна в значительной степени справляться с этой задачей.Просто увеличьте громкость аналогового входа, и у вас будет дешевый источник белого шума.Дешевая случайность без необходимости в сети.
Подход к измерение чего-либо сгенерировать случайное начальное значение, по-видимому, довольно хороший способ.Книга О'Рейли Практическая безопасность Unix и Интернета предоставляет несколько аналогичных дополнительных методов определения случайного начального значения, таких как просьба к пользователю ввести несколько нажатий клавиш, а затем измерение времени между нажатиями клавиш.(В книге отмечается, что этот метод используется PGP как источник его случайности.)
Интересно , если текущая температура процессора системы (измеряется со многими десятичными знаками) может быть жизнеспособным компонентом случайного начального числа.Преимущество такого подхода заключалось бы в отсутствии необходимости доступа к сети (таким образом, генератор случайных чисел не стал бы недоступен при отключении сетевого соединения).
Однако, вероятно, маловероятно, что внутренний датчик процессора сможет точно измерить температуру процессора с точностью до достаточного количества знаков после запятой, чтобы сделать значение действительно жизнеспособным в качестве начального значения случайного числа;по крайней мере, не с "оборудованием товарного класса", как упоминалось в вопросе!
Это не так хорошо, как использование атмосферного шума, но все равно по-настоящему случайно, поскольку зависит от характеристик сети, которая печально известна своим случайным неповторяемым поведением.
Видишь Random.org подробнее о случайности.
Вот попытка реализации:
@ips : list = getIpAddresses();
@rnd = PseudorandomNumberGenerator(0 to (ips.count - 1));
@getTrueRandomNumber() { ping(ips[rnd.nextNumber()]).averageTime }
Я бы предпочел использовать что-то вроде ИСААК как более сильный PRNG перед тем, как доверять пингам туда и обратно как энтропии.Как уже говорили другие, кому-то было бы слишком легко не только угадать ваши цифры, но и, возможно, в той или иной степени контролировать их.
Существуют и другие великие источники энтропии, о которых упоминали другие.Один из них, который не был упомянут (что может оказаться непрактичным), - это дискретизация шума от встроенного аудиоустройства..который обычно будет немного шумным, даже если к нему не подключен микрофон.
Я прошел 9 раундов, пытаясь создать надежный (и быстрый) PRNG для клиент-серверного механизма RPC, который я писал.Обе стороны имели идентичный ключ, состоящий из 1024 строк 32-символьных шифров.Клиент отправил бы AUTH xx, сервер вернул бы AUTH yy ..и обе стороны знали, какие две строки ключа использовать для получения секрета иглобрюха (+ соль).Затем сервер отправлял дайджест всего ключа SHA-256 (зашифрованный), клиент знал, что он разговаривает с чем-то, у чего есть правильный ключ..сеанс продолжался.Да, очень слабая защита для человека посередине, но об открытом ключе не могло быть и речи для того, как использовалось устройство.
Итак, у вас был неблокирующий сервер, который должен был обрабатывать до 256 подключений..PRNG должен был быть не только сильным, но и быстрым.Использовать более медленные методы для сбора энтропии в клиенте было не так уж сложно, но на сервере это было невозможно.
Итак, я должен спросить относительно вашей идеи..насколько это было бы практично?
Никакие математические вычисления не могут привести к случайному результату, но в "реальном мире" компьютеры не просто вычисляют числа...Проявив немного креативности, можно было бы получать случайные результаты такого рода, когда не существует известного метода воспроизведения или прогнозирования точных результатов.
Одна из самых простых в реализации идей, которые я видел и которые универсально работают на всех системах, - это использовать статику от линии ввода / вывода звуковой карты компьютера.
Другие идеи включают тепловой шум и низкий уровень синхронизации строк кэша.Многие современные КОМПЬЮТЕРЫ с чипами TPM уже оснащены аппаратными генераторами случайных чисел с качеством шифрования.
Моя дерзкая реакция на ping (особенно при использовании ICMP) заключается в том, что вы слишком откровенно жульничаете.В этот момент вы могли бы с таким же успехом установить счетчик гигера и использовать фоновое излучение в качестве случайного источника.
Да, это возможно, но...дьявол кроется в деталях.
Если вы собираетесь сгенерировать 32-битное целое число, вам нужно собрать > 32 бит энтропии (и использовать функцию микширования, достаточную для распределения этой энтропии, но это известно и выполнимо).Главный вопрос в том, что:
сколько энтропии имеет время пинга?
Ответ на этот вопрос зависит от всевозможных предположений о сети и вашей модели атаки, и в разных обстоятельствах возможны разные ответы.
Если злоумышленники могут полностью контролировать время пинга, вы получаете 0 бит энтропии за пинг, и вы никогда не сможете получить 32 бита энтропии, независимо от того, сколько вы смешиваете.Если у них менее совершенный контроль над временем пинга, вы получите некоторую энтропию и (если вы не переоцениваете количество собираемой энтропии) получите совершенно случайные 32-битные числа.
YouTube показывает устройство в действии: http://www.youtube.com/watch?v=7n8LNxGbZbs
Случайное - это, если никто не может предсказать следующее состояние.
Хотя я не могу однозначно сказать "за" или "против", у этой реализации есть свои проблемы.
Откуда берутся эти IP-адреса, выбираются ли они случайным образом, что происходит, когда они не отвечают или запаздывают с ответом, означает ли это, что случайное число будет отображаться медленнее?
Кроме того, даже если вы составили бы визуальный график из 100 000 результатов и вычислили, что корреляций между числами нет или их немного, это не означает, что они действительно случайны.Как объяснено дилберт :)
Мне это не кажется хорошим источником случайности.
Какую метрику вы бы использовали - очевидной является время отклика, но диапазон значений, которые вы можете разумно ожидать, невелик:от нескольких десятков миллисекунд до нескольких тысяч.Само время отклика будет следовать колоколообразной кривой и не будет случайным образом распределено по какому-либо интервалу (как бы вы выбрали интервал?), Поэтому вам придется попытаться выбрать несколько "случайных" битов из чисел.
LSB может выдавать вам случайный битовый поток, но вам придется учитывать проблемы с детализацией синхронизации - возможно, из-за того, как работают прерывания, вы всегда будете получать значения, кратные 2 мс в некоторых системах.
Вероятно, есть гораздо лучшие "интересные" способы получения случайных битов - возможно, поискав в Google случайное слово, перейдите на первую страницу и выберите N-й бит со страницы.
Эх, я нахожу, что такого рода вопросы довольно быстро приводят к дискуссиям о значении термина "по-настоящему случайный".
Я думаю, что измерение пингов дало бы случайные биты приличного качества, но с недостаточной скоростью, чтобы от них была большая польза (если только вы не были готовы провести серьезную DDoS-атаку).
И я не вижу, чтобы это было более случайным, чем измерение аналоговых / механических свойств компьютера или поведение пакета с мясом, управляющего им.
(редактировать) С практической точки зрения, такой подход открывает вам возможность того, что кто-то в вашей сети манипулирует вашим генератором "случайных" чисел.
Мне кажется, что истинная случайность невыразима - нет способа узнать, является ли последовательность случайной, поскольку по определению она может содержать что угодно неважно, насколько это невероятно.Гарантирование определенной схемы распределения уменьшает случайность.Слово "паттерн" немного выдает меня с головой.
I MADE U A RANDOM NUMBER
BUT I EATED IT
Случайность - это не двоичное свойство - это значение между 0 и 1, которое описывает, насколько сложно предсказать следующее значение в потоке.
Спрашивать "насколько случайными могут быть мои значения, если я основываю их на пингах?" на самом деле означает спрашивать "насколько случайными являются пинги?".Вы можете оценить это, собрав достаточно большой набор данных (например, 1 миллион пингов) и составив карту их кривой распределения и поведения во времени.Если распределение равномерное и поведение трудно предсказать, данные кажутся более случайными.Более неровное распределение или предсказуемое поведение предполагают меньшую случайность.
Вам также следует рассмотреть пример разрешения.Я мог бы представить, что результаты каким-то образом округляются до миллисекунды, поэтому при пинге вы могли бы иметь целочисленные значения от 0 до 500.Это не такое уж большое разрешение.
С практической стороны, я бы не рекомендовал этого делать, поскольку пинги можно предсказывать и манипулировать ими, что еще больше снижает их случайность.
Как правило, я предлагаю не "внедрять свои собственные" генераторы случайности, методы шифрования и алгоритмы хеширования.Каким бы забавным это ни казалось, в основном это очень пугающая математика.
Что касается того, как построить действительно хороший генератор энтропии - я думаю, что это, вероятно, должна быть запечатанная коробка, которая выдает какой-то результат взаимодействий на атомном или субатомном уровне.Я имею в виду, что если вы используете источник энтропии, который враг тоже может легко прочитать, ему нужно только узнать ваш алгоритм.Любая форма соединения является возможным вектором атаки, поэтому вы должны разместить источник энтропии как можно ближе к службе, которая ее потребляет.
Вы можете использовать метод XKCD:
У меня есть некоторый код, который создает случайные числа с помощью traceroute.У меня также есть программа, которая делает это с помощью ping.Я сделал это больше года назад для классного проекта.Все, что он делает, это запускает traceroute on и address, и он принимает наименьшую цифру в мс раз.Это довольно хорошо работает при получении случайных чисел, но я действительно не знаю, насколько это близко к истинному рандому.
Вот список из 8 номеров, которые я получил, когда запустил его.
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;
}
Очень просто, поскольку сети подчиняются предписанным правилам, результаты не являются случайными.
Идея веб-камеры звучит (слегка) разумно.Пользователи Linux часто рекомендуют просто использовать случайный шум от звуковой карты, к которой не подключен микрофон.
вот мое предложение :
1. выберите несколько веб-сайтов, которые находятся как можно дальше от вашего местоположения.например ,если вы находитесь в США , попробуйте некоторые веб - сайты , IP - адреса серверов которых находятся в Малайзии, Китае , России , Индии .. и т.д.серверы с высоким трафиком лучше.
2- во время высокого интернет-трафика в вашей стране (в моей стране это примерно с 7 до 11 часов вечера) пропингуйте эти веб-сайты много-много раз, возьмите каждый результат ping (используйте только целочисленное значение) и вычислите его модуль 2 (т. е. от каждой операции ping вы получаете один бит :либо 0, либо 1).
3. повторяйте процедуру в течение нескольких дней, записывая результаты.
4. соберите все биты, которые вы получили от всех ваших пингов (вероятно, вы получите сотни тысяч битов), и выберите из них свои биты.(возможно, вы хотите выбрать свои биты, используя некоторые данные из того же метода, что и упомянутый выше :))
БУДЬ ОСТОРОЖЕН :в вашем коде вы должны проверить наличие тайм-аута .. и т.д.
