Поскольку сборщик мусора недетерминирован, почему он не используется для безопасной генерации случайных чисел?

13

Я понимаю, что / dev / random - хороший источник энтропии, и это то, что обычно используется. Как раз когда я читаю GC, по крайней мере в Java, кажется приемлемым, что демон сборки мусора выполняется недетерминированно , Если это правда, почему бы нам не использовать время сбора мусора в качестве источника энтропии вместо переменной / dev / random?

edthethird
источник
7
взгляните на некоторые документы для функций rand () в стандартной C-библиотеке. Они специально призывают, что, хотя они дают вам то, что кажется случайным числом, они не могут быть использованы для безопасности. Ваш типичный сборщик мусора, вероятно, попадет в ту же категорию. Если вы собираетесь использовать один для безопасности, вы должны убедиться, что вы используете криптографически безопасный сборщик мусора.
ДХМ
15
что-то недетерминированное все еще может быть очень предсказуемым
трещотка урод
7
В этом случае «недетерминированный» является плохим описанием. Сборщик мусора является полностью детерминированной системой, и если вы полностью осведомлены о ее состоянии и состоянии программы, которая ее использует, вы можете детерминистически предсказать результаты.
Gort the Robot
4
@DXM Знаете ли вы о хорошей реализации криптографически безопасного сборщика мусора? ;)
AJMansfield
7
«Любой, кто рассматривает арифметические методы получения случайных цифр, конечно, находится в состоянии греха». - Джон фон Нейманн
Марк Адлер

Ответы:

58

«Неуказанный» и «случайный» - это два совершенно разных понятия.

Точная работа сборщика мусора не указана и зависит от сборщика мусора (обычно реализуется с помощью виртуальной машины определенного типа, но не обязательно).

Следовательно, у вас нет определенного (то есть детерминированного) времени, когда будет собираться мусор.

Однако любая данная реализация будет следовать некоторым правилам, и существует высокая вероятность того, что два последующих запуска одной и той же программы будут иметь очень похожие шаблоны сборки мусора.

Поэтому фактическая энтропия, обеспечиваемая сборщиком мусора, будет очень низкой (и выяснить, какие части вы действительно можете использовать в качестве энтропии, будет непросто).

Для сравнения: A HashMapв Java не гарантирует какой-либо порядок поиска для своих членов (в основном потому, что гарантируя, что это добавит накладные расходы, которые не стоит платить в большинстве случаев). Однако для данной реализации и данного набора вставок / удалений вы можете определенно рассчитать результирующий порядок. Тот факт, что нет гарантии для любого данного заказа, не означает, что заказ является случайным.

Йоахим Зауэр
источник
20
Я думаю, что было бы справедливо сказать, что если компьютер когда-либо делает что-то действительно недетерминированное, этот компьютер сломается.
Schilcote
Недетерминированный может также означать, что он зависит от некоторого состояния, внешнего по отношению к программе, которая сама по себе может быть детерминированной, но будет совершенно не связана с самой программой и поэтому может отличаться при каждом запуске программы.
asmeurer
@asmeurer Я не думаю, что слышал эти термины в любом таком контексте. На самом деле, я даже не уверен, что вы имеете в виду: каждая программа, которая принимает внешний ввод (то есть большинство полезных программ), "полагается на какое-то внешнее состояние", но это не делает его недетерминированным.
us2012
2
@Schilcote: Некоторые современные процессоры имеют недетерминированный (истинный) ГСЧ, реализованный аппаратно. Они действительно недетерминированы вплоть до квантовой физики.
MSalters
2
@Schilcote Даже без специальных инструкций RNG (Intel RDRAND и RDSEED) компьютер не является полностью детерминированным. Некоторые сроки не определены полностью и могут зависеть от внешних факторов, таких как температура.
CodesInChaos
8

Во-первых, мы должны быть осторожны, чтобы не попасть в ловушку рассуждений, манипулируя простыми словами. Например, мы могли бы спросить, поскольку NFA является «недетерминированным конечным автоматом», почему бы нам не использовать его для получения случайных чисел? В этом случае это будет, потому что это не то, что означает «недетерминированный» в NFA; на самом деле, когда мы моделируем NFA на заданном входе, поведение симуляции является полностью детерминированным.

«Детерминированный» - это загруженная фраза. Для программиста или программиста недетерминированное поведение означает просто «определение точного поведения, о котором сложно думать», и зависит от слишком многих факторов, включая ввод программы.

Однако это не означает, что это не является детерминированным для кого-то, мотивированного для атаки на криптосистему. Иногда факторы окружающей среды и исходные данные могут быть ограничены, и повторяющиеся модели возникают из «недетерминированного» поведения.

Kaz
источник