Pull to refresh

Comments 28

Статья немного не полна как минимум по части Windows: в каких версиях используется описываемый алкгоритм? Какие API-функции его используют? Мне известно минимум две функции WinAPI для генерации случайных чисел и еще 2-3 штуки для генерации криптоключей. И есть у меня подозрения, что описанный алгоритм может быть ими (не)использован поразному...

Да, спасибо за комментарий. Боялся перегрузить и сделать статью огромной и нечитаемой. По Windows в основном полагался на статью для Windows 10. Основной API:

  • SystemPrng

  • ProcessPrng

  • BCryptGenRandom

  • CryptGenRandom

  • RtlGenRandom

Во-первых, эти события должны быть недетерминированные. Во-вторых, их должно быть тяжело пронаблюдать извне.

Я бы сказал, что во-вторых — ключевое. Потому что даже если мы в качестве рандома берем температуру в комнате, но наблюдатель никак не может ни измерить ее, ни повлиять на нее, рандом получается вполне себе рандомный.

RDRAND очень интересная инструкция, в линуксе была дискуссия использовать ли, полагаться ли только на нее (как настаивал Интел) - в Вики есть ссылки про возможный backdoor, и найденную год назад уязвимость (вроде пропатчили микрокод).

Почему-то вспомнилась лабораторная работа в университете: её целью было формирование нормального распределения при помощи генератора случайных чисел.
Периодически у студентов вместо красивого горба из учебника получался «забор»: в определённых условиях ГСЧ вырождался, и начинал выдавать определённые числа по кругу. Интересно, существуют ли алгоритмы, у которых математически доказано отсутствие вырождение ГСЧ на большом промежутке времени?

Интересно, существуют ли алгоритмы, у которых математически доказано отсутствие вырождение ГСЧ на большом промежутке времени?

Немного не в теме, а числа после дроби в Пи можно такими считать?

Мне вот недавно надо было сгенерировать надёжный пин код.
Я задумался как сгенерировать случайный?
Пришлось бросать 4 монеты,
1,2,5,10 рублей.
4 бита дают значения 0-15.
если выпадают 10-15 значение отбрасывается.
Если 0-9 вуаля, у нас есть одна цифра пина.

P.S. нет 12 гранного кубика у меня не нашлось.

А я обычно делаю `echo $RANDOM` и этого достаточно для любых оффлайновых случайностей.

Мне захотелось максимальной секъюрности.
Правда это только с пин кодом работает. 256бит ключ я так поленился генерировать.

А в чём несекьюрность echo $RANDOM? Карго культ?

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

С точки зрения единичного числа-секрета в оффлайне достаточно знать, что любое число из диапазона вероятно.

А если оно не равновероятно, то для пин-кода угроза состоит в том, что...?

Ну давайте представим. Пин код 2 бита(для наглядности).
шанс угадать, при условии что биты случайные-1/2^2=0.25
Теперь представим себе что каждый бит с вероятностью 0.25=0 и с вероятностью 0.75=1
Тогда заявив что пин код 11 вы угадаете его в 0.75^2=0.5625 случаев. Падение безопасности более чем в 2 раза.

Для этого надо знать, чем вы генерировали. Так что я всё равно спрошу, в чём риск для единичного оффлайн-секрета?

Для этого надо знать, чем вы генерировали.

Надо. Но:
1)можно предположить.
2)вы поручитесь что у вас на компе нет зловредов? я нет.

Окей, даже если вы знаете, что человек набрал `echo $RANDOM`, что это даёт? Три попытки. Вы даже не знаете алгоритм отображения [0-65535] в [0-9999].

Да, я весьма уверен, что у меня на компьютере нет malware бытового уровня.

Вы даже не знаете алгоритм отображения [0-65535] в [0-9999].

Это значит, что я УЖЕ знаю, что 0-9999 будет вероятнее, чем 10000-65535

В обзоре катастрофически не хватает упоминания haveged, который наполняет пул энтропией за счёт недетерминированности ряда событий в многопроцессорной системы.

Фактически, спасение для виртуалок, у которых очень мало родной энтропии.

UFO landed and left these words here

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

а вот они то емнип задействованы, покрайней мере в linux (если исходить из того что мне когда-то преподавали в ВУЗе), да и в статье шла речь про драйверы устройств как источник в windows (почему-то плохой).

а ещё вспоминается webmoney где надо было подёргать мышкой в пределах окна для получения энтропии и archlinux при установке которого надо подолбить по клавиатуре для тех же целей (или это уже пофиксили?).

но если в современных ОС ГпСЧ хотя бы имеет документацию то вот спец приборы выдающие рандом обычно представляют собой чёрный ящик (помнится создатели "годвиля" такой купили за дорого и оказались разочарованы) непонятно как и насколько "случайно" работающий. вот про них я бы почитал..

archlinux при установке которого надо подолбить по клавиатуре для тех же целей (или это уже пофиксили?).

не видел такого. думаю уже давно. да и не помню когда при установки Arch Linux нужно так прям много энтропии. разве что pacman-keyring инициализировать, но там ни так много и надо.

В Windows процесс создания простых чисел подчинен достаточно сложной древовидной структуре.

А зачем там именно простые числа?

Это очепятка, там конечно же, случайные, а не простые
Спасибо огромное!

Чёрт, ну я даже подумал же через Ctrl-Enter сообщить. Но решил, что это я дуб дубом и почему-то упустил, что где-то в AES-based ГПСЧ нужны именно простые.

И тогда еще вопрос: я же правильно догадываюсь, что MS взял именно AES-based, чтобы на всех более менее современных процессорах использовать аппаратное ускорение AES?

Из-за последнего существует 2 способа взаимодействия со случайными числами в Linux — /dev/random и /dev/urandom. Первый блокируется, когда оценка по количеству энтропии становится ниже нуля, а второй выдает числа всегда, даже если пул не пополняется случайными битам

In 2020, the Linux kernel version 5.6 /dev/random only blocks when the CPRNG hasn't initialized. Once initialized, /dev/random and /dev/urandom behave the same

Sign up to leave a comment.

Articles