Pull to refresh

Comments 113

Фактически они ускорили медленный, но хороший ГСЧ при помощи быстрого старого, доброго ГПСЧ, тем самым получив BM.

ИМХО, я бы не стал использовать эту штуку где-нибудь у себя. Я хочу, чтобы мои программы работали везде, где только можно. 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
А разве в процессоре нет температурного датчика?
А если использовать датчик напряжения?
Под нагрузкой напруга стабильно-максимальная почти.
Ну дык мы будем брать несколько знаков после запятой, вряд ли она на столько постоянная.
UFO just landed and posted this here
по-моему тогда дешевле сделать более точный датчик, чем изобретать новую технологию
Они изобрели новую технологию с целью удешевить простейший аналоговый осциллятор. А вы предлагаете встраивать куда более дорогой прецизионный аналоговый прибор — АЦП!
В кустарных условиях берут младшие биты с микрофона.
UFO just landed and posted this here
UFO just landed and posted this here
Не проблема. Будем знать что микрофон выключен или его нет. И как следствие — обратимся к иным источникам энтропии.

Всяко лучше, чем брать «случайные» биты с выключенного микрофона.
UFO just landed and posted this here
в промышленных условиях зашумленной серверной берут все биты с микрофона :)
В статье ведь шла речь (в том числе) про генераторы, способные создавать действительно случайные последовательности, им нужно только начальное значение (random seed). Как раз такое значение и может дать температурный датчик.
Слишком маленький разброс температур.
После чего все криптоаналитики будут выкладывать кирпичи от получаемых цифр?
Интересно, а как на такие генераторы влияют на температурные сдвиги? В принципе элементы вполне могут иметь несимметричную характеристику в зависимости от температуры. да и со временем они могут расходиться. Это, часом, не повлияет на «случайность»?
Инженеры же не дураки) Народ давно смекнул, что если транзистора размещать на подложке рядышком, то и температурный дрейф у них будет одинаковый. А вообще эта фича с «кто-кого перетянет» давно уже используется в КМОП аналоговой технике(усилители), так что странно, что в интеле только сейчас это сделали.
Ну, я не электронщик — этого не знал)
Но я имел в виду немножко другое: используются два одинаковых элемента. Насколько они одинаковы? Если у них при температуре t1 одинаковая характеристика, то обязательно ли при t2 она будет тоже одинаковая?
Да, при Т2 характеристика тоже будет одинаковая. Вообще она одинаковая будет почти у всех транзисторов на кристалле :)
В статье написано что они придумали для этого, ну прочитайте же.
Чтобы соблюсти сбалансированность инвертеров, мы встроили механизм обратной связи
Оно лучше, чем /dev/random в линуксе? (Напомню, что в linux есть два штатных источника случайных чисел — один из них генерированный — /dev/urandom, второй — /dev/random, представляет из себя младшие биты времени асинхронных прерываний, такие как ввод с клавиатуры, прерывания от сетевой карты и жёсткого диска и т.д.; прерывания таймера по понятным причинам в этот список не включаются).

Я не слышал, чтобы хоть кто-то говорил плохие вещи про /dev/random, единственная претензия — скорость.
А я вообще про линукс не слышал, не то что про /dev/urandom ;)
Господа, куда на этот раз провели интернет?
не тот факт, которым можно было бы хвастаться на хабре…
Теперь я знаю отличный сценарий для толстого вброса на лор.
Ну там всё просто. «Достаем двойные листочки, поля четыре клеточки» — и ЛОР-эксперты моментально преображаются.

Как бы там ни было, я бы не стал ждать чудес от нового генератора, тем более, что мутная логика обработки сырых данных вполне может обладать согласованными с АНБ характеристиками.
Эта команда может использоваться /dev/random как ещё один источник случайных значений.
Я к тому, что эта штука меня смущает. Любая генерация ущербна по определению, потому что следующее число зависит от предыдущего (сколь бы там хитрый не был алгоритм).

Если лет через 7 (когда эта инструкция станет стандартом де-факто) мы услышим, что какой-нибудь мудрый Вася нашёл метод ломания sha-чексум через использование неслучайности последовательности (из 256 бит сделать 64 — ну не подарок ли?), что делать будем?
> метод ломания sha-чексум через использование неслучайности последовательности (из 256 бит сделать 64 — ну не подарок ли?)

Я вас не понял.
Если у нас в основе случайного числа лежит последовательность с seed, то вместо длинного числа мы можем ломать только seed, перебирая результаты применения последовательности.

Если у нас random выдаёт 64 бита (и берёт 64 бита как seed), а мы делаем 256 бит из 4х последовательных чтений, то достаточно перебрать 2^64 seed'ов, чтобы получить все возможные комбинации 256-битной последовательности. Это очень серьёзная уязвимость. Даже если seed берётся рандомом, нам достаточно перебрать все варианты seed'а. Конкретные битности тут не важны — важен принцип, что часть значений зависит от предыдущих.
Именно поэтому в /dev/random подмешивается понемногу отовсюду.
В любом случае, если у нас есть наличие генерации, это ослабляет алгоритм. Собственно, именно упоминание генерации меня и смущает в этой фиче.

Специализированные ГСЧ используются уже давно (обычно это 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, а его предсказание для достаточно специфичного случая.
> единственная претензия — скорость.

Она же самая существенная. Вы не поверите, десяток виртуалок с апачами на 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 назад имел). Если заполнить плоскость случайными значениями, то была видна полсасатость полученной плоскости.
Простой пример картинки, состоящей из цветного шума — распечатанная цветная фотография.
Кстати, для модельных вычислений лучше использовать свой ГПСЧ и сохранять seed, тк повторяемость результатов удобное свойство.
Любому серверу, который устанавливает много защищённых соединений. У меня есть пакет, конфигурирующий сервера. Там в ходе установки генерируются пароли/ключи, так вот, это довольно занудная процедура на две минуты. Если бы оно пролетало быстро, было бы мило. Но только если это настоящий рандом, а не последовательности.
В полиграфии, для стохастического растрирования, например.
Гм, кому может понадобиться поток случайных данных в 3 гб/с (или сколько там)?

Покерные румы смотрят на вас с непониманием…
Все клево, только есть два но:
1) Я бы не называл эту схему цифровой, т.к. в базе лежат явления аналоговой электроники
2) Поиметь геморроя при производстве такой схемы можно, на мой взгляд, не меньше, чем с той, что они называют аналоговой.
И даже
3) Темное место здесь — «алгоритм обратной связи», с помощью которого выравнивается число 1 и 0. Тут можно крупно промахнуться…
1 — по большему счету вся цифра построена на аналоговой базе.

И гонки в цифровых схемах (на которых как раз основано решение) входят в любой начальный курс схемотехники.

2 — какой геморрой? схема целиком цифровая, типовые элементы.
Ну кроме «переделки» инверторов, хотя это может быть типовой открытый коллектор…

3) ну, в ЦК не дураки сидят, полетите ночью мне кажется, что инженеры Интела думают головой перед тем как запускать решение в серию…
Гонки в цифровых схемах рассматриваются как досаждающий фактор и в синхронных устройствах мало кого волнуют — лишь бы выполнялись временные требования. По большому счету, это все казуистика — одна и та же схема может рассматриваться и как цифровая (на макроуровне), так и как аналоговая (на микроуровне). И вот пока она пребывает лишь в состояниях 0 и 1 — она цифровая. Как только начинаем копать вглубь и ловить промежуточные напряжения — она становиться аналоговой. ИМХО, конечно.
Ну а по последнему пункту — будем надеяться.
А мне нравится идея с приемом шумов из внешнего мира через АЦП микроконтроллера. Предварительно можно усилить сигнал. На выходе непредсказуемая комбинация.
Во-первых неодинаковая полоса пропускания приведет к тому, что часть шумов будет иметь больший уровень
Во-вторых весьма вероятно, что будут какие то регулярные шумы
Мне всегда было интересно, насколько в среднем случайны числа, получаемые при помощи движений мышкой (этого часто требуют программы, связанные с генерацией ключей), т.е. я понимаю, что все зависит от пользователя, но все таки?
Эти значения используются не целиком, а младшие биты. Для мыши учитываются:

1) Младшие биты (допустим, 2) координат (итого 4 бита)
2) Младшие биты (аналогично, 2) задержки между позиционированием мыши.

Для лучшей непредсказуемости нужно использовать младший бит.
Напомнили анекдот времён Фидо.
Два программиста:
«У тебя есть генератор случайных чисел?»
Второй не поворачиваясь,
"-137".
Поясните, пожалуйста, насколько безопасно это «усреднение», откидывание крайних значений?
Получается, что, если взять числа от 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
У меня где-то была древняя карточка, с радиоактивным веществом, которая генерила всегда псевдослучайные числа, такой метод используется стопицот лет во всех серьезных системах, что там интел изобрела нового я не понимаю.
встроили карточку в процессор.
А нельзя ли поставить маленькую антенну и ловить электромагнитные помехи вроде тех, что на экране телевизора при ненастроенном канале?
Станислав Лем. «Голос неба». Можно даже за хау-то взять.
Подходим к знанию конкурента, врубаем передатчик, через день ломаем пароли.
Если поймана радиостанция, то переключаться на другой «пустой канал».
Алгоритм поиска пустого канала это инвертированный алгоритм поиска радиостанций из любой магнитолы с автосканированием.
Это же шутка, с долей правды =)
Примерно как: От Маяка так просто не отключиться
Любой начинающий радиотехник знает, что самое сложное — избавиться от приёма «Маяка».
Так уже.
Почитайте что-такое random radio. USB долгл с радиоприемником, использующим радиоволны для генерирования случайных чисел… Ну или random sound, делающий тоже самое используюя звуковую карту и помехи на ее аналоговых цепях.
Эх, ещё одна моя гениальная идея отличного стартапа оказалась перечёркнута с подписью «уже реализовано»…
Довольно простенький, я думаю, можно сделать круче.
К счастью, несложно получить действительно непредсказумые значения, используя хаотическую вселенную, которая со всех сторон окружает строго детерминированный мир компьютерных битов.

На этой фразе мне показалось что я читаю «Автостопом по галактике» Дугласа Адамса :)
Вот оно что, никак не мог впомнить, что мне напомнила эта же фраза.
Меня одного смущает картинка для привлечения внимания, где как-бы из строго случайных битов сложилась вполне себе детерминированная надпись?
>спроектировали дополнительную схему, которая проводит тестирование потоков 256-битных чисел, которые поступают в «нормализатор», чтобы они не были слишком смещёнными в какую-то сторону. Если такое обнаруживается, мы помечаем его как бракованный и не соответствующий стандартам.

Во всем известной книжке «Криптономикон» в Блечтли-парке бабушки доставали буквы из лотерейного барабана (и возвращали назад), и записывали букву в шифроблокнот.

Когда им «казалось», что буква не случайна, они возвращали букву в барабан без записи в шифроблокнот.

Это сформировало дырку в случайности, которой враги сумели воспользоваться.
Не имея возможности заглянуть внутрь процессора и посмотреть, не заложена ли туда спец функция для облегчения жизни всякого рода спецслужбам, предпочитаю использовать мегапараноидальный FortunaGenerator от того же Шнайера. Пока что единственный генератор, глядя на который моё артериальное давление понижается, а не наоборот.
UFO just landed and posted this here
Было бы интересно посмотреть результаты тестов ГСЧ для такого генератора.
Помнится была успешная атака на их генераторы через генераторы ЭМ-шума. причём атака совсем упрощалась, если шифрующий чип охлаждали.

А в схеме intel возможно появление метастабильности? Если да, то почему производитель не боится, что генератор зависнет в одном состоянии?


@nerudo @Kopart @valeriyk

Sign up to leave a comment.

Articles