Comments 113
Фактически они ускорили медленный, но хороший ГСЧ при помощи быстрого старого, доброго ГПСЧ, тем самым получив BM.
ИМХО, я бы не стал использовать эту штуку где-нибудь у себя. Я хочу, чтобы мои программы работали везде, где только можно. RdRand не будет работать нигде, кроме как на новейших, пока еще не вышедших в продажу, Intell'овских процессорах.
ИМХО, я бы не стал использовать эту штуку где-нибудь у себя. Я хочу, чтобы мои программы работали везде, где только можно. RdRand не будет работать нигде, кроме как на новейших, пока еще не вышедших в продажу, Intell'овских процессорах.
Не спешите с выводами, возможно, вам понадобится серверная, криптографическая программка для одного и только одного из ваших проектов. Там, очевидно, логично и допустимо использование зависимой от платформы функции.
Ну как раз проблема «чтобы работало везде» легко снимается универсальным интерфейсом с подменным ГПСЧ (со стороны ОС). Тот же /dev/random, ну и аналоги в АПИ других ОС. А там, если идея действительно будет использовать, глядишь — и другие производители процессоров подтянутся, так что пару лет и аппаратные ГСЧ будут везде.
Ну так по идее это за нас должна делать ОС. Ждём поддержку этой фичи в /dev/random (и аналогичном виндовом API, который наверняка есть, но название которого мне не известно).
а что мешает сделать как-то так?
function myrnd() {
if($cpu == 'mega cool intel cpu')
return intel_random_value();
else
return rand();
}
Чем раньше начнёшь, тем раньше настанет мир во всём мире. HTML5 тоже казался несбыточной мечтой.
Пройдёт 8 лет… И вы уже не будете думать о поддержке вашего по такими старыми процессорами…
Спасибо за познавательную статью.
Никогда не понимал таких комментариев.
Есть что сказать, чтобы другие почитали — пиши.
Хочется сказать спасибо — поставь плюс.
Такие комментарии, имхо, пишутся только ради того, чтобы другие читатели поддержали и поплюсовали вас.
Есть что сказать, чтобы другие почитали — пиши.
Хочется сказать спасибо — поставь плюс.
Такие комментарии, имхо, пишутся только ради того, чтобы другие читатели поддержали и поплюсовали вас.
Никогда не понимал таких комментариев.
Хочется сделать замечание — напиши в хабрапочту.
Нечего сказать, но просто не нравится — поставь минус.
Такие комментарии, имхо, пишутся только ради того, чтобы другие читатели втянулись в холивар и слили кого-нибудь в минус.
Если же по теме, то такие комментарии — альтернативный способ поблагодарить автора, когда плюсы, например, закончились.
Хочется сделать замечание — напиши в хабрапочту.
Нечего сказать, но просто не нравится — поставь минус.
Такие комментарии, имхо, пишутся только ради того, чтобы другие читатели втянулись в холивар и слили кого-нибудь в минус.
Если же по теме, то такие комментарии — альтернативный способ поблагодарить автора, когда плюсы, например, закончились.
Да пусть даже и холивар, если это уменьшит количество бесполезных комментариев.
В данном случае, мы уже вступили =)
В данном случае, мы уже вступили =)
Интересно сколько + в этих 24 из тех 16. И испытывали ли плюсущие из пересечения муки совести?
Альтернативно поблагодарить — это занести в избранное. А написать «Спасибо» в комментариях — это спам.
Бывает иногда хочется похвалить человека теплым словцом, а не только безличным плюсом за топик :)
Никогда не думал, что случайные числа — это так сложно!
UFO just landed and posted this here
А разве в процессоре нет температурного датчика?
слишком медленно это
А если использовать датчик напряжения?
Под нагрузкой напруга стабильно-максимальная почти.
В статье ведь шла речь (в том числе) про генераторы, способные создавать действительно случайные последовательности, им нужно только начальное значение (random seed). Как раз такое значение и может дать температурный датчик.
После чего все криптоаналитики будут выкладывать кирпичи от получаемых цифр?
Интересно, а как на такие генераторы влияют на температурные сдвиги? В принципе элементы вполне могут иметь несимметричную характеристику в зависимости от температуры. да и со временем они могут расходиться. Это, часом, не повлияет на «случайность»?
Инженеры же не дураки) Народ давно смекнул, что если транзистора размещать на подложке рядышком, то и температурный дрейф у них будет одинаковый. А вообще эта фича с «кто-кого перетянет» давно уже используется в КМОП аналоговой технике(усилители), так что странно, что в интеле только сейчас это сделали.
Оно лучше, чем /dev/random в линуксе? (Напомню, что в linux есть два штатных источника случайных чисел — один из них генерированный — /dev/urandom, второй — /dev/random, представляет из себя младшие биты времени асинхронных прерываний, такие как ввод с клавиатуры, прерывания от сетевой карты и жёсткого диска и т.д.; прерывания таймера по понятным причинам в этот список не включаются).
Я не слышал, чтобы хоть кто-то говорил плохие вещи про /dev/random, единственная претензия — скорость.
Я не слышал, чтобы хоть кто-то говорил плохие вещи про /dev/random, единственная претензия — скорость.
А я вообще про линукс не слышал, не то что про /dev/urandom ;)
Эта команда может использоваться /dev/random как ещё один источник случайных значений.
Я к тому, что эта штука меня смущает. Любая генерация ущербна по определению, потому что следующее число зависит от предыдущего (сколь бы там хитрый не был алгоритм).
Если лет через 7 (когда эта инструкция станет стандартом де-факто) мы услышим, что какой-нибудь мудрый Вася нашёл метод ломания sha-чексум через использование неслучайности последовательности (из 256 бит сделать 64 — ну не подарок ли?), что делать будем?
Если лет через 7 (когда эта инструкция станет стандартом де-факто) мы услышим, что какой-нибудь мудрый Вася нашёл метод ломания sha-чексум через использование неслучайности последовательности (из 256 бит сделать 64 — ну не подарок ли?), что делать будем?
> метод ломания sha-чексум через использование неслучайности последовательности (из 256 бит сделать 64 — ну не подарок ли?)
Я вас не понял.
Я вас не понял.
Если у нас в основе случайного числа лежит последовательность с seed, то вместо длинного числа мы можем ломать только seed, перебирая результаты применения последовательности.
Если у нас random выдаёт 64 бита (и берёт 64 бита как seed), а мы делаем 256 бит из 4х последовательных чтений, то достаточно перебрать 2^64 seed'ов, чтобы получить все возможные комбинации 256-битной последовательности. Это очень серьёзная уязвимость. Даже если seed берётся рандомом, нам достаточно перебрать все варианты seed'а. Конкретные битности тут не важны — важен принцип, что часть значений зависит от предыдущих.
Если у нас random выдаёт 64 бита (и берёт 64 бита как seed), а мы делаем 256 бит из 4х последовательных чтений, то достаточно перебрать 2^64 seed'ов, чтобы получить все возможные комбинации 256-битной последовательности. Это очень серьёзная уязвимость. Даже если seed берётся рандомом, нам достаточно перебрать все варианты seed'а. Конкретные битности тут не важны — важен принцип, что часть значений зависит от предыдущих.
Именно поэтому в /dev/random подмешивается понемногу отовсюду.
В любом случае, если у нас есть наличие генерации, это ослабляет алгоритм. Собственно, именно упоминание генерации меня и смущает в этой фиче.
Специализированные ГСЧ используются уже давно (обычно это USB/PCI устройства, типа «вьюги»), засунуть их в процессор идея правильная, однако, не с режимом генерации…
Специализированные ГСЧ используются уже давно (обычно это USB/PCI устройства, типа «вьюги»), засунуть их в процессор идея правильная, однако, не с режимом генерации…
А, теперь я вас понимаю. Пользовательская программа сгенерила число, затем ядро сгенерило число и подмешало в /dev/random, пользовательская программа рассчитала, какое число получило ядро.
/dev/random — это не совсем генератор. Ядро копит энтропию (случайные битики) от внешних источников: клацания по клавиатуре, задержек сетевых пакетов и так далее. И от этого уже seed-ится генератор, который /dev/urandom, который пере-seed-ивается из /dev/random через определённые интервалы времени или количества выданных случайных байтов. Как-то так. Есть ощущение, что это вполне надёжно.
… и пользователю выдается блок данных в разы меньше размера внутреннего состояния (pool).
От всего pool берется sha; затем полученный хеш примешивается к pool:
«We mix the hash back into the pool to prevent backtracking attacks (where the attacker knows the state of the pool plus the current outputs, and attempts to find previous ouputs), unless the hash function can be inverted. By mixing at least a SHA1 worth of hash data back, we make brute-forcing the feedback as hard as brute-forcing the hash.»
Затем к исходному хешу добавляется еще один блок данных из пула; затем хеш ополовинивается:
hash[0] ^= hash[3]; hash[1] ^= hash[4];
hash[2] ^= rol32(hash[2], 16);
Дополнительно, ядро не позволяет получать слишком много случайных данных из /dev/random подряд без подмешивания в pool свежей энтропии.
Т.о. знание «что часть значений зависит от предыдущих», дает мало преимуществ для ситуации, т.к. размер пула = 32*128 бит = 4 кбит — 512 байт больше объема данных, выдаваемых за один раз и больше объема данных, который может быть получен через /dev/random без добавления энтропии извне.
/dev/urandom в этом плане опаснее, т.к. не имеет ограничений по исчерпанию энтропии. Но как раз urandom и не нужно использовать для важных применений.
Была описана атака www.cs.huji.ac.il/~reinman/presentations/LRNG.pdf — оценка сложности 2^96 — 2^64 для устройства, имеющего малое количество источников энтропии = openwrt. Тем не менее, это не перебор seed, а его предсказание для достаточно специфичного случая.
От всего pool берется sha; затем полученный хеш примешивается к pool:
«We mix the hash back into the pool to prevent backtracking attacks (where the attacker knows the state of the pool plus the current outputs, and attempts to find previous ouputs), unless the hash function can be inverted. By mixing at least a SHA1 worth of hash data back, we make brute-forcing the feedback as hard as brute-forcing the hash.»
Затем к исходному хешу добавляется еще один блок данных из пула; затем хеш ополовинивается:
hash[0] ^= hash[3]; hash[1] ^= hash[4];
hash[2] ^= rol32(hash[2], 16);
Дополнительно, ядро не позволяет получать слишком много случайных данных из /dev/random подряд без подмешивания в pool свежей энтропии.
Т.о. знание «что часть значений зависит от предыдущих», дает мало преимуществ для ситуации, т.к. размер пула = 32*128 бит = 4 кбит — 512 байт больше объема данных, выдаваемых за один раз и больше объема данных, который может быть получен через /dev/random без добавления энтропии извне.
/dev/urandom в этом плане опаснее, т.к. не имеет ограничений по исчерпанию энтропии. Но как раз urandom и не нужно использовать для важных применений.
Была описана атака www.cs.huji.ac.il/~reinman/presentations/LRNG.pdf — оценка сложности 2^96 — 2^64 для устройства, имеющего малое количество источников энтропии = openwrt. Тем не менее, это не перебор seed, а его предсказание для достаточно специфичного случая.
> единственная претензия — скорость.
Она же самая существенная. Вы не поверите, десяток виртуалок с апачами на ssl выгребают весь пул рандома хост машины за секунды.
Она же самая существенная. Вы не поверите, десяток виртуалок с апачами на ssl выгребают весь пул рандома хост машины за секунды.
Повторю, я ничего не имею против переноса ssl-акселераторов из специализированных железок в процессор. Меня смущает только описание алгоритма, когда неудачи аппаратной генерации корректируют программно. Либо число рандомное, либо нет. Дальше это уже (в режиме доведения до абсурда):
int get_random()
{
/*
return the random number
it was generated by throwing a dice
*/
return 4;
}
UFO just landed and posted this here
Гм, кому может понадобиться поток случайных данных в 3 гб/с (или сколько там)?
модельные вычисления, заполнение массивов, например генерация картинок.
Там довольно сильно тормозить будет.
Там довольно сильно тормозить будет.
Генерация картинок? Кому это нужна картинка состоящая из цветного шума? :-)
И хотелось бы увидеть практический пример модельных вычислений или нужность больших массивов со случайными числами.
Я с этим не сталкивался ни разу. :-)
И хотелось бы увидеть практический пример модельных вычислений или нужность больших массивов со случайными числами.
Я с этим не сталкивался ни разу. :-)
Почему «цветной шум»? Простейшим математическим преобразованием линейное распределение превращается и в Гаусса и в Пуассона и во множество других. Где применяется? В ситуациях когда надо настроить алгоритм на обработку изображений, примеров которых мало или вообще нет. Например съёмка камерой со спутника. Для каждой орбиты/камеры, спектрального диапазона изображение будет весьма специфично. Построение изображения, которое потом будет обрабатываться требует значительного времени. Или в ситуации когда надо проверить алгоритм на работу в условиях сильных шумов, понять его границы, когда он разваливается. Берутся изображения из архива, для которых известно решение и на них накладываются шумы. Если хочется получить хорошую статистику — то это много тысяч тестов.
Между прочем, псевдослучайный генератор в винде имеет неплохую периодичность (по крайней мере лет 6-7 назад имел). Если заполнить плоскость случайными значениями, то была видна полсасатость полученной плоскости.
Между прочем, псевдослучайный генератор в винде имеет неплохую периодичность (по крайней мере лет 6-7 назад имел). Если заполнить плоскость случайными значениями, то была видна полсасатость полученной плоскости.
Простой пример картинки, состоящей из цветного шума — распечатанная цветная фотография.
Кстати, для модельных вычислений лучше использовать свой ГПСЧ и сохранять seed, тк повторяемость результатов удобное свойство.
Любому серверу, который устанавливает много защищённых соединений. У меня есть пакет, конфигурирующий сервера. Там в ходе установки генерируются пароли/ключи, так вот, это довольно занудная процедура на две минуты. Если бы оно пролетало быстро, было бы мило. Но только если это настоящий рандом, а не последовательности.
В полиграфии, для стохастического растрирования, например.
Гм, кому может понадобиться поток случайных данных в 3 гб/с (или сколько там)?
Покерные румы смотрят на вас с непониманием…
Все клево, только есть два но:
1) Я бы не называл эту схему цифровой, т.к. в базе лежат явления аналоговой электроники
2) Поиметь геморроя при производстве такой схемы можно, на мой взгляд, не меньше, чем с той, что они называют аналоговой.
И даже
3) Темное место здесь — «алгоритм обратной связи», с помощью которого выравнивается число 1 и 0. Тут можно крупно промахнуться…
1) Я бы не называл эту схему цифровой, т.к. в базе лежат явления аналоговой электроники
2) Поиметь геморроя при производстве такой схемы можно, на мой взгляд, не меньше, чем с той, что они называют аналоговой.
И даже
3) Темное место здесь — «алгоритм обратной связи», с помощью которого выравнивается число 1 и 0. Тут можно крупно промахнуться…
1 — по большему счету вся цифра построена на аналоговой базе.
И гонки в цифровых схемах (на которых как раз основано решение) входят в любой начальный курс схемотехники.
2 — какой геморрой? схема целиком цифровая, типовые элементы.
Ну кроме «переделки» инверторов, хотя это может быть типовой открытый коллектор…
3) ну,в ЦК не дураки сидят, полетите ночью мне кажется, что инженеры Интела думают головой перед тем как запускать решение в серию…
И гонки в цифровых схемах (на которых как раз основано решение) входят в любой начальный курс схемотехники.
2 — какой геморрой? схема целиком цифровая, типовые элементы.
Ну кроме «переделки» инверторов, хотя это может быть типовой открытый коллектор…
3) ну,
Гонки в цифровых схемах рассматриваются как досаждающий фактор и в синхронных устройствах мало кого волнуют — лишь бы выполнялись временные требования. По большому счету, это все казуистика — одна и та же схема может рассматриваться и как цифровая (на макроуровне), так и как аналоговая (на микроуровне). И вот пока она пребывает лишь в состояниях 0 и 1 — она цифровая. Как только начинаем копать вглубь и ловить промежуточные напряжения — она становиться аналоговой. ИМХО, конечно.
Ну а по последнему пункту — будем надеяться.
Ну а по последнему пункту — будем надеяться.
А мне нравится идея с приемом шумов из внешнего мира через АЦП микроконтроллера. Предварительно можно усилить сигнал. На выходе непредсказуемая комбинация.
Мне всегда было интересно, насколько в среднем случайны числа, получаемые при помощи движений мышкой (этого часто требуют программы, связанные с генерацией ключей), т.е. я понимаю, что все зависит от пользователя, но все таки?
Напомнили анекдот времён Фидо.
Два программиста:
«У тебя есть генератор случайных чисел?»
Второй не поворачиваясь,
"-137".
Два программиста:
«У тебя есть генератор случайных чисел?»
Второй не поворачиваясь,
"-137".
Поясните, пожалуйста, насколько безопасно это «усреднение», откидывание крайних значений?
Получается, что, если взять числа от 0 до 255, то 0 и 255 будут выпадать значительно реже вероятности их выпадения?
Получается, что, если взять числа от 0 до 255, то 0 и 255 будут выпадать значительно реже вероятности их выпадения?
«он их не перемножает, а производит более сложные криптографические операции.»
Дональд Э. Кнут. Глава 3. Случайные числа // Искусство программирования
Ну или в википедии: ru.wikipedia.org/wiki/%D0%93%D0%B5%D0%BD%D0%B5%D1%80%D0%B0%D1%82%D0%BE%D1%80_%D0%BF%D1%81%D0%B5%D0%B2%D0%B4%D0%BE%D1%81%D0%BB%D1%83%D1%87%D0%B0%D0%B9%D0%BD%D1%8B%D1%85_%D1%87%D0%B8%D1%81%D0%B5%D0%BB
Дональд Э. Кнут. Глава 3. Случайные числа // Искусство программирования
Ну или в википедии: ru.wikipedia.org/wiki/%D0%93%D0%B5%D0%BD%D0%B5%D1%80%D0%B0%D1%82%D0%BE%D1%80_%D0%BF%D1%81%D0%B5%D0%B2%D0%B4%D0%BE%D1%81%D0%BB%D1%83%D1%87%D0%B0%D0%B9%D0%BD%D1%8B%D1%85_%D1%87%D0%B8%D1%81%D0%B5%D0%BB
У меня где-то была древняя карточка, с радиоактивным веществом, которая генерила всегда псевдослучайные числа, такой метод используется стопицот лет во всех серьезных системах, что там интел изобрела нового я не понимаю.
А нельзя ли поставить маленькую антенну и ловить электромагнитные помехи вроде тех, что на экране телевизора при ненастроенном канале?
Станислав Лем. «Голос неба». Можно даже за хау-то взять.
Подходим к знанию конкурента, врубаем передатчик, через день ломаем пароли.
А потом поймать Маяк и привет
Так уже.
Почитайте что-такое random radio. USB долгл с радиоприемником, использующим радиоволны для генерирования случайных чисел… Ну или random sound, делающий тоже самое используюя звуковую карту и помехи на ее аналоговых цепях.
Почитайте что-такое random radio. USB долгл с радиоприемником, использующим радиоволны для генерирования случайных чисел… Ну или random sound, делающий тоже самое используюя звуковую карту и помехи на ее аналоговых цепях.
можно — так работает random.org
К счастью, несложно получить действительно непредсказумые значения, используя хаотическую вселенную, которая со всех сторон окружает строго детерминированный мир компьютерных битов.
На этой фразе мне показалось что я читаю «Автостопом по галактике» Дугласа Адамса :)
На этой фразе мне показалось что я читаю «Автостопом по галактике» Дугласа Адамса :)
А пароли всё равно qwerty и q1w2e3r4!
Меня одного смущает картинка для привлечения внимания, где как-бы из строго случайных битов сложилась вполне себе детерминированная надпись?
>спроектировали дополнительную схему, которая проводит тестирование потоков 256-битных чисел, которые поступают в «нормализатор», чтобы они не были слишком смещёнными в какую-то сторону. Если такое обнаруживается, мы помечаем его как бракованный и не соответствующий стандартам.
Во всем известной книжке «Криптономикон» в Блечтли-парке бабушки доставали буквы из лотерейного барабана (и возвращали назад), и записывали букву в шифроблокнот.
Когда им «казалось», что буква не случайна, они возвращали букву в барабан без записи в шифроблокнот.
Это сформировало дырку в случайности, которой враги сумели воспользоваться.
Во всем известной книжке «Криптономикон» в Блечтли-парке бабушки доставали буквы из лотерейного барабана (и возвращали назад), и записывали букву в шифроблокнот.
Когда им «казалось», что буква не случайна, они возвращали букву в барабан без записи в шифроблокнот.
Это сформировало дырку в случайности, которой враги сумели воспользоваться.
Не имея возможности заглянуть внутрь процессора и посмотреть, не заложена ли туда спец функция для облегчения жизни всякого рода спецслужбам, предпочитаю использовать мегапараноидальный FortunaGenerator от того же Шнайера. Пока что единственный генератор, глядя на который моё артериальное давление понижается, а не наоборот.
Было бы интересно посмотреть результаты тестов ГСЧ для такого генератора.
Помнится была успешная атака на их генераторы через генераторы ЭМ-шума. причём атака совсем упрощалась, если шифрующий чип охлаждали.
Sign up to leave a comment.
Как работает новый генератор случайных чисел Intel