The OpenNET Project / Index page

[ новости /+++ | форум | теги | ]

Для ядра Linux 3.13 представлены патчи с улучшением генерации случайных чисел

19.11.2013 09:44

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

Например, как один из источников энтропии теперь может использоваться регистр времени, который слишком груб для точного отслеживания времени, однако годится в качестве одного из источников энтропии. Кроме этого реализован режим "канарейки", при котором в лог ядра (printk) выводится сообщение, если программа попытается использовать /dev/urandom до того как он будет полностью инициализирован, что может потенциально привести к проблемам c надёжностью криптографических операций.

На платформе х86 данная проблема как правило не возникает (у самого разработчика на ноутбуке инициализация этого устройства завершается на 1.5 секунды раньше чем монтируется rootfs и какая-либо программа получает шанс использовать устройство), однако предполагается, что это может быть проблемой на платформах ARM или MIPS.

В будущем предполагается реализовать поведение при котором при недостаточном накоплении энтропии выполнение программы приостанавливается до момента когда устройство /dev/urandom будет инициализировано и готово вернуть программе качественные случайные данные, что должно положительно сказаться на безопасности.

  1. Главная ссылка к новости (http://git.kernel.org/cgit/lin...)
  2. OpenNews: Проблемы с надёжностью генератора псевдослучайных чисел из состава ядра Linux
  3. OpenNews: Выявлена проблема с генерацией предсказуемых случайных чисел на процессорах MIPS
  4. OpenNews: Во FreeBSD устранена уязвимость в генераторе случайных чисел
  5. OpenNews: Оценка возможности создания аппаратных бэкдоров, работающих на транзисторном уровне
  6. OpenNews: NIST и RSA отзывают ранее стандартизованный Dual EC DRBG из-за возможного бэкдора
Автор новости: Аноним
Лицензия: CC BY 3.0
Короткая ссылка: https://opennet.ru/38461-random
Ключевые слова: random, kernel, linux
При перепечатке указание ссылки на opennet.ru обязательно


Обсуждение (46) Ajax | 1 уровень | Линейный | +/- | Раскрыть всё | RSS
  • 1.3, Аноним (-), 12:05, 19/11/2013 [ответить] [﹢﹢﹢] [ · · · ]  
  • +/
    Я тут подумал, а что если...

    Смотрите есть всем известная штука как атомные часы. Цезий в них колеблется с частотой 9.2 ГГц.
    Вопрос насколько это удобный источник энтропии?

    И совсем уж непонятный вопрос насколько для его вычисления будет достаточно кластера в процессорами в 4 ГГц?
    Имею ввиду один т.е один процессор с одним шагом другой с другим?

     
     
  • 2.6, Аноним (-), 12:12, 19/11/2013 [^] [^^] [^^^] [ответить]  
  • +/
    Немного перепоясню мыслю.

    Допустим у вас есть карманные атомные часы (вес 35 г)
    Они выдают вам псевдослучайную величину типа наносекунд.
    Достаточно ли 1000 процессоров для имитации поведения поведения таких часов?
    Кто хорошо знает теорию погрешностей измерений?

     
     
  • 3.10, анонимм (?), 12:37, 19/11/2013 [^] [^^] [^^^] [ответить]  
  • –18 +/
    С какого бы перепоя им выдавать случайные значения? На то они и атомные часы, что они работают стабильно. Ты наверное неграмотная шваль навроде фанбоев поцтеринга и перепутал атомные часы распадом атомных ядер, которые вроде как распадаются случайно?
     
     
  • 4.36, Аноним (-), 22:53, 19/11/2013 [^] [^^] [^^^] [ответить]  
  • +/
    > На то они и атомные часы, что они работают стабильно.

    Часы как источник энтропии обычно используют в том контексте что заранее неизвестно в какое время вас (генератор случайных чисел) позвали из "вон той программы". Этот факт можно поюзать как дополнительный источник энтропии.

     
  • 3.13, anonymous (??), 13:13, 19/11/2013 [^] [^^] [^^^] [ответить]  
  • –1 +/
    Аноним выше, конечно тролль, но он прав. Псевдослучайная величина может быть расчитанна на основе показаний атомных часов. Хотя алгоритмы получения псевдослучайных величин могут основываться не только на времени.
    Заданный же вопрос остался вне пределов моего понимания.
     
     
  • 4.19, Аноним (-), 15:15, 19/11/2013 [^] [^^] [^^^] [ответить]  
  • –2 +/
    Поясню.
    У вас есть атом цезия с частотой 10 ГГц, ну это для упрощения да?
    т.е.
    он допустим выдает псевдослучайные значения времени.

    типа 0,00000000001 и каждую секунду значение  меняется до неузначаемости..

    Процессор с частотой в 1 ГГц совершает 1 такт за 0,000000001 секунды в 10 раз медленнее. Т.е он в принципе ничего не может предугадать поведение атома цезия, вернее вероятность этого явно меньше 10% сколько раз колебнулся атом цезия пока этот проц совершил 1 такт 5 или все 9?

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

    И еще, а если использовать атомные часы с пониженной точностью, ошибающиеся на 1 наносекунду , каждую секунду?( ошибка на 1 секунду в 30 лет) Такие часы будут обладать большей случайностью. Не так ли?


    Да и шутнику про атомную батарейку, современный атомные часы выпученные в 2011 году потребляют 0,3 Вт...

     
     
  • 5.20, Аноним (-), 15:20, 19/11/2013 [^] [^^] [^^^] [ответить]  
  • +/

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

     
     
  • 6.23, anonymous (??), 15:58, 19/11/2013 [^] [^^] [^^^] [ответить]  
  • +1 +/
    Вы все же что то не то говорите.
    Суть атомных часов (насколько я понимаю) в том что они выдают строго заданную частоту с крайне маленькой погрешностью. Таким образом отрезок времени может быть измерен спомощью количества колебаний атома и переведен в необходимые единицы времени.
    Атомные часы не выдают псевдослучайное число - генератор псевдослучайных чисел расчитывает их по некоторому алгоритму. Причем алгоритм, по большому счету, может вообще не использовать время при генерации псевдослучайного числа.

    Поэтому ответ на Ваш вопрос(с некоторыми допущениями в условии) звучит так - все зависит от алгоритма генератора псевдослучайных чисел.

     
     
  • 7.24, Аноним (-), 17:05, 19/11/2013 [^] [^^] [^^^] [ответить]  
  • –1 +/
    Это я понял, но базисом псевдослучайного числа в данном случаем может быть время, показания датчиков напряжения температуры тока и пр на материнке и т.д.
    Т.е. понятно что генератор складывает перемножает возводит в степень округляет вычитает и пр. Потом вычитает четные цифры и з нечетных и т.д.

    Кто-то допустим пишет генератор на базе звуковых шумов.
    Это все понятно.

    Я же говор об изменчивости базисов для этого псевдослучайного числа.
    Т.е чем чаще меняется базис тем более "случайным" является псевдослучайное число. И чем шире диапазон изменений базиса, тем лучше. Базис количества колебаний атома цезия в атомных часах изменяется постоянно.

    Даже если допустить что вам полностью известен алгоритм генерации, полностью повторить условия базиса у вас не получится. Ведь так?

     
     
  • 8.25, anonymous (??), 18:28, 19/11/2013 [^] [^^] [^^^] [ответить]  
  • +/
    Если значение получаемое из генератора расчитывается исключительно по времени - ... текст свёрнут, показать
     
  • 8.26, Аноним (-), 18:45, 19/11/2013 [^] [^^] [^^^] [ответить]  
  • –1 +/
    Последний раз объясняю хотя глупо чего то объяснять дураку да ещё и ширнутому к... текст свёрнут, показать
     
     
  • 9.42, Аноним (-), 23:41, 19/11/2013 [^] [^^] [^^^] [ответить]  
  • +/
    Уважаемый, вы непоняли Сейчас используется в ГПСЧ счетчик тактов процессора Что... текст свёрнут, показать
     
  • 2.11, Аноним (-), 13:00, 19/11/2013 [^] [^^] [^^^] [ответить]  
  • +/
    и атомную батарейку для ноутбука
     

  • 1.5, Аноним (-), 12:10, 19/11/2013 [ответить] [﹢﹢﹢] [ · · · ]  
  • +/
    Интересно войдёт ли в ядро 3.13 патч для моего бука, который вводит более прогрессивную, чем в винде, систему управления яркостью с помощью клавиш Fn)
    20 делений яркости против 10 в оффтопике, причём последняя вырубает яркость нахрен (актуально ночью).
    https://bugzilla.kernel.org/show_bug.cgi?id=62941 На всё про всё ушел ровно месяц.
     
     
  • 2.9, st (??), 12:23, 19/11/2013 [^] [^^] [^^^] [ответить]  
  • +1 +/
    вот бы и для остальных ноутов такое прикрутить, у меня вот 4 деления против 8ми в винде, хотя на ядре 2.6.xx было одинаково 8
     
     
  • 3.18, Аноним (-), 15:14, 19/11/2013 [^] [^^] [^^^] [ответить]  
  • –1 +/
    > вот бы и для остальных ноутов такое прикрутить, у меня вот 4
    > деления против 8ми в винде, хотя на ядре 2.6.xx было одинаково
    > 8

    Ещё было бы неплохо подправить изменения громкости, чтобы по 2%, а не по 6%, изменялось за один ход.

     
     
  • 4.22, rshadow (ok), 15:51, 19/11/2013 [^] [^^] [^^^] [ответить]  
  • +3 +/
    Неплохо было бы находить тех дядь которые ломают постоянно все эти клавиши и другие настройки, и руки им обрывать.
     
  • 2.14, Сергей (??), 13:35, 19/11/2013 [^] [^^] [^^^] [ответить]  
  • +/
    Смотря какое число выдаст генератор ;-)
     
  • 2.37, Аноним (-), 22:54, 19/11/2013 [^] [^^] [^^^] [ответить]  
  • +/
    > причём последняя вырубает яркость нахрен

    ...и юзер чешет репу: wtf, экран нотика сдох?

     

  • 1.7, myhand (ok), 12:13, 19/11/2013 [ответить] [﹢﹢﹢] [ · · · ]  
  • +/
    > выполнение программы приостанавливается до момента когда устройство /dev/urandom будет инициализировано и готово вернуть программе качественные случайные данные, что должно положительно сказаться на безопасности.

    Новая дырка для DOS?

     
     
  • 2.12, anonymous (??), 13:04, 19/11/2013 [^] [^^] [^^^] [ответить]  
  • +/
    Поправьте меня, если я ошибаюсь, но вроде бы /dev/urandom инициализируется при загрузке системы. Так что только если очень специальный DOS.
     
  • 2.30, Аноним (-), 19:22, 19/11/2013 [^] [^^] [^^^] [ответить]  
  • +/
    Оно же отдает псевдослучайные значения не зависимо от содержимого буфера энтропии. Сколько надо столько и отдаст. Скорость правда несколько мегабайт в секунду получается. Очень мало.
     
     
  • 3.38, Аноним (-), 22:56, 19/11/2013 [^] [^^] [^^^] [ответить]  
  • +/
    Основные грабли - в том что программа может попросить данные рано, когда там вообще пусто. При этом полученные программой  данные могут быть не такими уж и случайными.

    Если программа в этот момент генерила какой-нить RSA ключ - получится не комильфо.

     

  • 1.8, Аноним (-), 12:18, 19/11/2013 [ответить] [﹢﹢﹢] [ · · · ]  
  • +13 +/
    Случайные числа стали еще случайнее и это не случайно, на всякий случай.
     
     
  • 2.15, тоже Аноним (ok), 13:40, 19/11/2013 [^] [^^] [^^^] [ответить]  
  • +1 +/
    Случается, случаются и неслучайные случаи.
     
     
  • 3.27, Аноним (-), 18:48, 19/11/2013 [^] [^^] [^^^] [ответить]  
  • +/
    > Случается, случаются и неслучайные случаи.

    Дык то случайно!

     

  • 1.16, Аноним (-), 14:01, 19/11/2013 [ответить] [﹢﹢﹢] [ · · · ]  
  • +/
    А может быть с этим патчем числа стали менее случайными? Вспомните кивок Линуса.
     
     
  • 2.17, Xaionaro (ok), 14:46, 19/11/2013 [^] [^^] [^^^] [ответить]  
  • +/
    Ну, это всё-таки Теодор Тсо ;).. Плюс всё равно другие разработчики будут изучать этот код перед коммитом)
     
     
  • 3.28, Аноним (-), 18:49, 19/11/2013 [^] [^^] [^^^] [ответить]  
  • –1 +/
    > Плюс всё равно другие разработчики будут изучать этот код перед коммитом)

    Если они такие же как баран сверху с атомными часами ... то удачи.


     
     
  • 4.46, Xaionaro (ok), 17:51, 20/11/2013 [^] [^^] [^^^] [ответить]  
  • –1 +/
    >> Плюс всё равно другие разработчики будут изучать этот код перед коммитом)
    > Если они такие же как баран сверху с атомными часами ... то
    > удачи.

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

     
  • 2.21, Аноним (-), 15:32, 19/11/2013 [^] [^^] [^^^] [ответить]  
  • –7 +/
    Вы все еще верите в отсутствие закладок в ядре. Все это сказочки для фанатиков, любому разумному человеку ясно что линукс одна больша дырень.
     
     
  • 3.29, Аноним (-), 18:51, 19/11/2013 [^] [^^] [^^^] [ответить]  
  • +2 +/
    > любому разумному человеку ясно что линукс одна больша дырень.

    Ты попутал свою жопу с линуксом, ****илло :)

     
  • 3.41, Аноним (-), 23:22, 19/11/2013 [^] [^^] [^^^] [ответить]  
  • +1 +/
    > Вы все еще верите в отсутствие закладок в ядре. Все это сказочки
    > для фанатиков, любому разумному человеку ясно что линукс одна больша дырень.

    Какое жирное трололо сегодня к нам пришло.

     

  • 1.31, pavlinux (ok), 21:49, 19/11/2013 [ответить] [﹢﹢﹢] [ · · · ]  
  • –1 +/
    + /* was: x^32 + x^26 + x^20 + x^14 + x^7 + x + 1 */
    + /* x^32 + x^26 + x^19 + x^14 + x^7 + x + 1 */

    А чёй-то он в третьем члене градус понизил? АНБшнеги попросили?

    ---
    В документе указано (http://eprint.iacr.org/2012/251.pdf)




    if i = 0 then
        rot ← rot + 14 (mod 32)
    else
        rot ← rot + 7 (mod 32)


    Тцо нарисовал AND 31



    input_rotate = (input_rotate + (i ? 7 : 14)) & 31;



    Если i=0 и input_rotate будет равен 18, то в первом случае input_rotate = 0, у Тцо - input_rotate = 7. :/

     
     
  • 2.32, torteg (?), 22:21, 19/11/2013 [^] [^^] [^^^] [ответить]  
  • +/
    Это градус неадеквата
     
  • 2.33, anonymous (??), 22:36, 19/11/2013 [^] [^^] [^^^] [ответить]  
  • +/
    Не факт. Я, конечно, ихсходников не читал, но предпологаю, что там вычисления по-модулю.  Кстати, если не лень, то можешь попробовать на множители пораскладывать. В каком многочлене будет выше наименьшая  степень множителя, тот сложнее анализировать. Если есть кто более сведующий в теории чисел,  то поправьте, если я ошибся.
     
     
  • 3.34, pavlinux (ok), 22:38, 19/11/2013 [^] [^^] [^^^] [ответить]  
  • +/
    Ну там примерно так объясняется code 3 1 1 Analysis Without Input When the inp... большой текст свёрнут, показать
     
  • 2.35, Аноним (-), 22:38, 19/11/2013 [^] [^^] [^^^] [ответить]  
  • +/
    Не факт. Я, конечно, ихсходников не читал, но предпологаю, что там вычисления по-модулю.  Кстати, если не лень, то можешь попробовать на множители пораскладывать. В каком многочлене будет выше наименьшая  степень множителя, тот сложнее анализировать. Если есть кто более сведующий в теории чисел,  то поправьте, если я ошибся.
     
  • 2.39, Аноним (-), 23:03, 19/11/2013 [^] [^^] [^^^] [ответить]  
  • +/
    > В документе указано (http://eprint.iacr.org/2012/251.pdf)

    Ага, там еще написано: "However, Q(X) can be made irreducible by changing just one
    feedback position" - подчеркивая что существующий PRNG не самый оптимальный по длине неповторяющейся последовательности.

     
  • 2.40, Andrey Mitrofanov (?), 23:09, 19/11/2013 [^] [^^] [^^^] [ответить]  
  • +1 +/
    > + /* was: x^32 + x^26 + x^20 + x^14 + x^7
    > + x + 1 */
    > + /* x^32 + x^26 + x^19 + x^14 + x^7 +
    > x + 1 */
    > А чёй-то он в третьем члене градус понизил? АНБшнеги попросили?

    1/ Там ещё 103->104 строкой выше
    2/ А ещё на 10 строк выше начная наука про "чёй0та" -->
    + * GF(2**32). They suggest a slight change to the generator

    > ---
    > В документе указано (http://eprint.iacr.org/2012/251.pdf)
    > if i = 0 then
    >     rot ← rot + 14 (mod 32)
    > else
    >     rot ← rot + 7 (mod 32)
    > Тцо нарисовал AND 31

    Это одно и тэ ж.

    > input_rotate = (input_rotate + (i ? 7 : 14)) & 31;
    > у Тцо - input_rotate = 7. :/

    Окстись,
    32 & 31 == 32 mod 32 == 0

     
     
  • 3.43, pavlinux (ok), 02:03, 20/11/2013 [^] [^^] [^^^] [ответить]  
  • +/
    >  1/ Там ещё 103->104 строкой выше

    Как я понял фича в том, что раньше генерились числа вплоть до 2^(96*32)-1, теперь до (2^(128*32)-1)/3  

    >> Тцо нарисовал AND 31
    > Это одно и тэ ж.
    >> input_rotate = (input_rotate + (i ? 7 : 14)) & 31;
    >> у Тцо - input_rotate = 7. :/
    > Окстись,
    > 32 & 31 == 32 mod 32 == 0

    А, пля... мой косяк, не туда смотрел :]

     
     
  • 4.44, Andrey Mitrofanov (?), 13:11, 20/11/2013 [^] [^^] [^^^] [ответить]  
  • +/
    >>  1/ Там ещё 103->104 строкой выше
    > Как я понял фича в том, что раньше генерились числа вплоть до
    > 2^(96*32)-1, теперь до (2^(128*32)-1)/3

    Юноша! B-D Ну, взял бы 45К текста drivers/char/random.c, да посмотрел бы.

    Превое число из 6 - размер, следующие ("taps", краны, ответвления) - это гру-гря "мешалки" для пула, массива _байтов_ размером от 64 до 2048 штук.

    Числа там не "генерятся", там _биты (в виде байтов, но не суть) **XOR**-ятся (=это не те полиномы, прапорщик!) и сдвигаются. Идея в том, чтобы вх.данные замешивать в пул математикой _наподобие_ крипто-хеша, чтобы _изменения воспринимались и накапливались, но злоумышленник (или не сильно "[не]ровные" вх.воздействия) не мог[ли] привести к генерации предсказуемого.

    Картинки тут: en.wikipedia.org/wiki/Linear_feedback_shift_register
    Чтение на 4 c +: guugle: /dev/random site:lwn.net, <<Результатов: примерно 1 520>>

     
     
  • 5.45, pavlinux (ok), 14:29, 20/11/2013 [^] [^^] [^^^] [ответить]  
  • +/
    > да посмотрел бы.

    В отличии от тебя, мне лень разжёвывать.
    Для посетителей опеннета пойдёт, чтоб оценить масштаб изменений:

    (2^(128*32)-1)/3 > 2^(96*32)-1

    детальней все описано в PDF_ке.

     
     
  • 6.47, Andrey Mitrofanov (?), 19:32, 20/11/2013 [^] [^^] [^^^] [ответить]  
  • +1 +/
    > В отличии от тебя, мне лень разжёвывать.
    > Для посетителей опеннета пойдёт, чтоб оценить масштаб изменений:
    > (2^(128*32)-1)/3 > 2^(96*32)-1

    Про градусы в членах писал другой павлин? Ну, привет ему.

    > детальней все описано в PDF_ке.

    Теперь и я pdf-ку перелистал. Научная наука, со своими картинками. ПрЕдмет исчерпан, ты победил.

     
     
  • 7.48, pavlinux (ok), 18:49, 22/11/2013 [^] [^^] [^^^] [ответить]  
  • +/
    >> В отличии от тебя, мне лень разжёвывать.
    >> Для посетителей опеннета пойдёт, чтоб оценить масштаб изменений:
    >> (2^(128*32)-1)/3 > 2^(96*32)-1
    > Про градусы в членах писал другой павлин? Ну, привет ему.

    Во втором примере видал 23-степень?

     
     
  • 8.49, Andrey Mitrofanov (?), 21:35, 22/11/2013 [^] [^^] [^^^] [ответить]  
  • +/
    Какой пример, я только по картинкам ... текст свёрнут, показать
     

     Добавить комментарий
    Имя:
    E-Mail:
    Текст:



    Партнёры:
    PostgresPro
    Inferno Solutions
    Hosting by Hoster.ru
    Хостинг:

    Закладки на сайте
    Проследить за страницей
    Created 1996-2024 by Maxim Chirkov
    Добавить, Поддержать, Вебмастеру