Уязвимость в генераторе случайных чисел в ОС FreeBSD

Надо еще проверить, какая последовательность генерится в линуксе

>Генератор случайных чисел должен генерировать бесконечную неповторяющуюся последовательность чисел.

Любой программный ГСЧ генерирует повторяющуся последовательность.

>Любой программный ГСЧ генерирует повторяющуся последовательность.

Это только если он использует только системный таймер. А если брать трафик через сетевую карту, клавиатуру, мышь, звуковую карту и подмешивать ГСЧ?

Я так понял, что он программно-аппаратный (все внешние события складывает в пул энтропии; man random).

> Надо еще проверить, какая последовательность генерится в линуксе

Проверяли неоднократно - одна из лучших. Единственный недостаток - слово ЖОПА редко встречается.

>А если брать трафик через сетевую карту, клавиатуру, мышь, звуковую карту

Я же говорил - _программный_. Читай - алгоритмический.

>и подмешивать ГСЧ?

Можно чудовищно испортить распределение. Результат в общем случае не гарантирован, поэтому применение подобных методов - очень узкоспециализированное (типа генерации ключей и т.п.)

Лучший вариант - использование хардверных ГСЧ на тепловых шумах и т.п., но судя по сабжу - речь, всё же, о программном решении.

либоя дурак, либо.... одно из двух :)

Пару лет назад я читал учебник по Perl Т.Кристиансена и Н. Торкингтон издательства О'райли, авторы пишут что генератор "случайных" чисел не такой уж "случайный", и приводят алгоритмы обхода этой проблемы.....

ээээээээ

в чем новость?!

http://vitus-wagner.livejournal.com/141948.html

>все внешние события складывает в пул энтропии

Стрёмно, не уверен, что так делают. Тем более непонятно, как тогда зацикливание получают.

Скорее всего имеется в виду банальный короткий цикл в определённых условиях. На эти грабли наступают уже лет пятьдесят :)

...

Заглянул по ссылке - там сказаное "return an endless supply of pseudo-random bytes when read". Если реально "endless", то явно подмешиваются внешние события. Но тогда оно уже и не "pseudo"...

>Скорее всего имеется в виду банальный короткий цикл в определённых условиях. На эти грабли наступают уже лет пятьдесят :)

Блин может еще строчку в исходниках линукс сюда запостить? Работает он просто, устройства которые выдают прерывания случайно (зависят от пользователя - клавиатура, мышь) во время прерывания передают время прерывания специальной функции и все. Че там может (в линуксе) работать не так?

У трансметты, ещё в линейке С3 была фича - аппаратно усиливались шумы по питанию. И их мгновенное значение можно было считать в любой момент. Т.е. это и есть "настоящий", а не программный генератор СЧ. Будем надеяться и ждать, когда же до этого додумаются AMD и Intel.

У интела же раньше был хардверный RNG на матплатах, не?

>Будем надеяться и ждать, когда же до этого додумаются AMD и Intel.

HW_RANDOM - Hardware Random Number Generator Core support
HW_RANDOM_OMAP -  Hardware Random Number Generator Core support
HW_RANDOM_GEODE - AMD Geode HW Random Number Generator support
HW_RANDOM_INTEL - Intel HW Random Number Generator support
HW_RANDOM_PASEMI - PA Semi HW Random Number Generator support
HW_RANDOM_AMD - AMD HW Random Number Generator support
HW_RANDOM_IXP4XX - Intel IXP4xx NPU HW Random Number Generator support
HW_RANDOM_VIA - VIA HW Random Number Generator support

ЕМНИП, массовая поддержка хардверной ГСЧ появилась в i810.

Недавно такуюже уязвимость в венде нашли...

> ЕМНИП, массовая поддержка хардверной ГСЧ появилась в i810.

и тамже закончилась.

еще раз доказывает то что МС тырит все что пишут БЗДуны...

хочешь поработать бесплатно на майкрософт - пиши софт под БЗД лицензией

[root@fedora ~]# grep -i random /boot/config-2.6.23.1-49.fc8
CONFIG_HW_RANDOM=y
CONFIG_HW_RANDOM_INTEL=m
CONFIG_HW_RANDOM_AMD=m
CONFIG_HW_RANDOM_GEODE=m
CONFIG_HW_RANDOM_VIA=m
[root@fedora ~]# find /lib/modules/|grep -i random
/lib/modules/2.6.23.1-49.fc8/kernel/drivers/char/hw_random
/lib/modules/2.6.23.1-49.fc8/kernel/drivers/char/hw_random/intel-rng.ko
/lib/modules/2.6.23.1-49.fc8/kernel/drivers/char/hw_random/geode-rng.ko
/lib/modules/2.6.23.1-49.fc8/kernel/drivers/char/hw_random/amd-rng.ko
/lib/modules/2.6.23.1-49.fc8/kernel/drivers/char/hw_random/via-rng.ko
[root@fedora ~]# ls -lah /lib/modules/2.6.23.1-49.fc8/kernel/drivers/char/hw_random/*|sort
-rw-r--r-- 1 root root 14K 2007-11-09 13:51 /lib/modules/2.6.23.1-49.fc8/kernel/drivers/char/hw_random/intel-rng.ko
-rw-r--r-- 1 root root 7.4K 2007-11-09 13:51 /lib/modules/2.6.23.1-49.fc8/kernel/drivers/char/hw_random/geode-rng.ko
-rw-r--r-- 1 root root 7.4K 2007-11-09 13:51 /lib/modules/2.6.23.1-49.fc8/kernel/drivers/char/hw_random/via-rng.ko
-rw-r--r-- 1 root root 8.0K 2007-11-09 13:51 /lib/modules/2.6.23.1-49.fc8/kernel/drivers/char/hw_random/amd-rng.ko
[root@fedora ~]# lsmod |grep -i rng
[root@fedora ~]#

> Можно чудовищно испортить распределение. Результат в общем случае не гарантирован, поэтому применение подобных методов - очень узкоспециализированное (типа генерации ключей и т.п.)

Если источники не коррелируют, ничего испортить нельзя. Наоборот, несколько плохих, но разнородных источников дают лучший результат, чем все они по отдельности. Все всегда именно так и делали -- чем больше разнородного мусора намешаешь в результат, тем он лучше. Посмотри на cdrom со случайными числами Джорджа Марсаглии, автора diehard'а, и почитай описание того, как они были получены. А также почитай про то, что он наблюдал с теми самыми аппаратными генераторами, которые ты тут восхваляешь. Вот тебе даже ссылочка: http://www.stat.fsu.edu/pub/diehard/cdrom/pscript/cdmake.ps И впредь не надо городить пургу с надутыми щеками, противно смотреть в самом деле.

Under certain circumstances, a bug in the internal state tracking on
the random(4) and urandom(4) devices can be exploited to allow replaying
of data distributed during subsequent reads.

я дурак, или не понял, в чём же собственно заключаются эти "некоторые условия"?

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

AiFiLTr0@Invyl:~$ time grep -i жопа /dev/urandom
Binary file /dev/urandom matches
real 0m19.819s
user 0m0.124s
sys 0m19.089s

По вашему 20 сек это много?

труЪ линухоидs ищут "Жопа" в /dev/null

Всю свою сознательную жизнь ...

>AiFiLTr0@Invyl:~$ time grep -i жопа /dev/urandom
>Binary file /dev/urandom matches
>real 0m19.819s
>user 0m0.124s
>sys 0m19.089s

>По вашему 20 сек это много?


замучался ждать - вырубил))
[anders@fedora ~]$ time grep -i жопа /dev/urandom
real 8m31.002s
user 3m39.325s
sys 4m4.822s

Могу поспорить, что локаль - utf8

Проблема в том, что жопа в UTF кодируется 8 байтами! Соответственно, ждать надо _гораздо_ дольше, чем если искать жопу в koi8-r, скажем :)

>time grep -i жопа /dev/urandom

А причем здесь urandom? Речь идёт именно про random.

я так же и подумал.... ))))))
представь - искать нечто вроде 你好 )))

BSD сломалась, а-а-а-а-а!!! [бегает по комнате]

хм недавно в винде нашли что генератор пошивый.

рандомогенераторокапец?

Команда ученых из университета Хайфы под началом Бенни Пинкаса смогла определить алгоритм генерации чисел функцией CryptGenRandom в Windows 2000.

Анализ показал, что генератор далек от случайного, или даже псевдо-случайного. Исследователям удалось предсказать появление чисел после определения начального состояния генератора. "Генератор работает в пользовательском режиме, не в режиме ядра и таким образом получить доступ к его состоянию можно даже без административных привилегий", - объясняют они.

Криптографам удалось обнаружить, что в работу генератора системная энтропия начинает вмешивать только после того, как он выдаст 128 Кб данных в запрашиваемый процесс. Таким образом, узнав один раз состояние генератора, можно предсказать 128К случайных чисел.

где прочитать

http://www.xakep.ru/post/41111/default.asp?print=true

>где прочитать

>http://www.xakep.ru/post/41111/default.asp?print=true

Не нужно делать PR плагиаторам из "Хацкера". Первоисточник на русском - статья "Неслучайные случайности" Бёрда Киви из "бумажной" Компьютерры №44. (Дословно передрали, гады!)

> Не нужно делать PR плагиаторам из "Хацкера". А это что за темка такая от 8 ноября? http://www.linux.org.ru/view-message.jsp?msgid=2255339

> авторы пишут что генератор "случайных" чисел не такой уж "случайный", и приводят алгоритмы обхода этой проблемы.....

хаха. алгоритма получения случайных чисел не существует по определению.
существуют генераторы псв - псевдо-случайных чисел, которые генерируют всегда одну и ту же последовательность.
в сад учить арифметику и ТВ.
интересно что за алгоритмы предлагают уважаемые мастера языка генерирования отчетов

> По вашему 20 сек это много?

$ time grep -i жопа /dev/urandom

^C real 4m57.033s user 2m3.824s sys 1m59.687s

$ uname -rn galaxy 2.6.22-14-generic

Ну и где?

Искал в koi

что вы зафлудили всё генераторами да жопами своими?!

новость про то, что BSD - говно.

а вы - ГСЧ.. RNG...

тьфу бл*ть.

> новость про то, что BSD - говно.

Ну это само-собой, чего тут обсуждать?

Не мешай. Кому есть дело до BSD?

нужно было подождать еще пару недель, а потом сказать, что вот ошибка в БСД )))

> time grep -i жопа /dev/urandom

> По вашему 20 сек это много?

Тоже мне хакер блин. А без "-i" попробовать и дождаться результата - слабо?

>хм недавно в винде нашли что генератор пошивый.

>рандомогенераторокапец?

Нет просто генератор в винде из бсд с3,14здили

bsd:~> time grep -i жопа /dev/urandom Binary file /dev/urandom matches 0.804u 27.682s 0:28.48 100.0% 101+1048k 0+0io 0pf+0w bsd:~> uname -srp FreeBSD 7.0-BETA2 i386

[sp@home: ~] % time grep -i жопа /dev/urandom Binary file /dev/urandom matches egrep -i жопа /dev/urandom 0,31s user 44,47s system 94% cpu 47, 423 total [sp@home: ~] % uname -sr Linux 2.6.22-12-386

> http://www.stat.fsu.edu/pub/diehard/cdrom/pscript/cdmake.ps

Ужас, целый CDROM из 4.8 миллиарда битов! Самое смешное в этой истории то, что этот CDROM перестал быть случайным сразу с момента своего создания, и теперь он скатился до низкого звания ГПсевдоСЧ... :)

> Самое смешное в этой истории то, что этот CDROM перестал быть случайным сразу с момента своего создания

Если читал то, что цитируешь, то заметил бы, что данные предлагаются для монте-карло симуляций, а не для генерации ключей.

> данные предлагаются для монте-карло симуляций, а не для генерации ключей.

А какая собственно разница? Может быть, для Monte-Carlo и Sensitivity Analysis хорошая случайность еще важнее. Все зависит от задачи.

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

> Проблема в том, что жопа в UTF кодируется 8 байтами! Соответственно, ждать надо _гораздо_ дольше, чем если искать жопу в koi8-r, скажем :)

Что свидетельствует, что с koi8-r жопа настает намного раньше.

>Будем надеяться и ждать, когда же до этого додумаются AMD и Intel.

Intel до этого додумалась ЕМНИП ещё в 810 чипсете. В Via C3 вроде как тоже аппаратный ГСЧ был.

>> Что свидетельствует, что с koi8-r жопа настает намного раньше.

Бгааа ... а если в utf16 искать? или utf32?

> Случайность нельзя вогнать в рамки детерминированности, чем является, например, единичный CDROM ;)

Внутри записанной на диске последовательности бит сложно найти какие-либо закономерности, поэтому она и называется случайной. Разумеется, в данном случае эта последовательность ограничена и заранее известна. Поэтому она подходит только для ограниченного числа задач. Если вы определяете последовательность случайных чисел как "то, что заранее неизвестно", он вам ничем не поможет. А вот если, например, есть сомнения в качестве используемого генератора случайных чисел, этот диск может помочь это проверить, в том случае если требуемого объема записанных на нем случайных чисел достаточно.

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

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

Но я пока сталкивался с тем, что для улучшения свойст выборки часто добавляют криптографию. Конечно, это - не панацея, но все же биты перемешивает хорошо.

На самом деле, мне эта тема очень итересна, о она напрямую связана с моими профессиональными занятиями - софт для имитационного моделирования. Пока мы обходимся двумя генераторами: простой (1) и на основе криптографии (2). Все сделано на основе стандартных библиотек и при минимальном вмешательстве с нашей стороны.

> А причем здесь urandom? Речь идёт именно про random.

Не заметил. Снова проверил там тоже ничто не нашлось. :( 2.6.18 2.6.22 ...