URL: https://www.opennet.me/cgi-bin/openforum/vsluhboard.cgi
Форум: vsluhforumID3
Нить номер: 92726
[ Назад ]

Исходное сообщение
"Для ядра Linux 3.13 представлены патчи с улучшением генераци..."

Отправлено opennews , 19-Ноя-13 11:53 
Разработчик Теодор Тсо представил (http://git.kernel.org/cgit/linux/kernel/git/torvalds/linux.g...) патч, улучшающий работу с случайными числами для ядра 3.13. Наиболее заметными изменениями является улучшение производительности и повышение качества энтропии, а также ряд улучшений, касающихся работы генератора случайных чисел на платформах, отличных от х86.


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


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

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

URL: http://git.kernel.org/cgit/linux/kernel/git/torvalds/linux.g...
Новость: http://www.opennet.me/opennews/art.shtml?num=38461


Содержание

Сообщения в этом обсуждении
"Для ядра Linux 3.13 представлены патчи с улучшением генераци..."
Отправлено Аноним , 19-Ноя-13 12:05 
Я тут подумал, а что если...

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

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


"Для ядра Linux 3.13 представлены патчи с улучшением генераци..."
Отправлено Аноним , 19-Ноя-13 12:12 
Немного перепоясню мыслю.

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


"Для ядра Linux 3.13 представлены патчи с улучшением генераци..."
Отправлено анонимм , 19-Ноя-13 12:37 
С какого бы перепоя им выдавать случайные значения? На то они и атомные часы, что они работают стабильно. Ты наверное неграмотная шваль навроде фанбоев поцтеринга и перепутал атомные часы распадом атомных ядер, которые вроде как распадаются случайно?

"Для ядра Linux 3.13 представлены патчи с улучшением генераци..."
Отправлено Аноним , 19-Ноя-13 22:53 
> На то они и атомные часы, что они работают стабильно.

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


"Для ядра Linux 3.13 представлены патчи с улучшением генераци..."
Отправлено anonymous , 19-Ноя-13 13:13 
Аноним выше, конечно тролль, но он прав. Псевдослучайная величина может быть расчитанна на основе показаний атомных часов. Хотя алгоритмы получения псевдослучайных величин могут основываться не только на времени.
Заданный же вопрос остался вне пределов моего понимания.

"Для ядра Linux 3.13 представлены патчи с улучшением генераци..."
Отправлено Аноним , 19-Ноя-13 15:15 
Поясню.
У вас есть атом цезия с частотой 10 ГГц, ну это для упрощения да?
т.е.
он допустим выдает псевдослучайные значения времени.

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

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

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

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


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


"Для ядра Linux 3.13 представлены патчи с улучшением генераци..."
Отправлено Аноним , 19-Ноя-13 15:20 

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


"Для ядра Linux 3.13 представлены патчи с улучшением генераци..."
Отправлено anonymous , 19-Ноя-13 15:58 
Вы все же что то не то говорите.
Суть атомных часов (насколько я понимаю) в том что они выдают строго заданную частоту с крайне маленькой погрешностью. Таким образом отрезок времени может быть измерен спомощью количества колебаний атома и переведен в необходимые единицы времени.
Атомные часы не выдают псевдослучайное число - генератор псевдослучайных чисел расчитывает их по некоторому алгоритму. Причем алгоритм, по большому счету, может вообще не использовать время при генерации псевдослучайного числа.

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


"Для ядра Linux 3.13 представлены патчи с улучшением генераци..."
Отправлено Аноним , 19-Ноя-13 17:05 
Это я понял, но базисом псевдослучайного числа в данном случаем может быть время, показания датчиков напряжения температуры тока и пр на материнке и т.д.
Т.е. понятно что генератор складывает перемножает возводит в степень округляет вычитает и пр. Потом вычитает четные цифры и з нечетных и т.д.

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

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

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


"Для ядра Linux 3.13 представлены патчи с улучшением генераци..."
Отправлено anonymous , 19-Ноя-13 18:28 
Если значение получаемое из генератора расчитывается исключительно по времени - Rand(t), то очевидно, что для получения значения которое будет сгенерированно через n колебаний атома (с частотой v) вы можете использовать Rand(t + n/v)

Но, я полагаю, что все же не улавливаю суть вопроса.


"Для ядра Linux 3.13 представлены патчи с улучшением генераци..."
Отправлено Аноним , 19-Ноя-13 18:45 
>Базис количества колебаний атома цезия в атомных часах изменяется постоянно.

Последний раз объясняю (хотя глупо чего то объяснять дураку да ещё и ширнутому какой то гадостью) - НЕТ! Атомные часы потому и в большом деманде что они _крайне_ стабильные. Меряй время бабушкиным будильником - это будет куда как более случайные величины.


"Для ядра Linux 3.13 представлены патчи с улучшением генераци..."
Отправлено Аноним , 19-Ноя-13 23:41 
Уважаемый, вы непоняли

Сейчас используется в ГПСЧ счетчик тактов процессора. Что если использовать счетчик пикосекунд из атомных часов?

И потом это промежути атомные часы меряют правильно. Время же и количество колебаний постоянно растет.


"Для ядра Linux 3.13 представлены патчи с улучшением генераци..."
Отправлено Аноним , 19-Ноя-13 13:00 
и атомную батарейку для ноутбука

"Для ядра Linux 3.13 представлены патчи с улучшением генераци..."
Отправлено Аноним , 19-Ноя-13 12:10 
Интересно войдёт ли в ядро 3.13 патч для моего бука, который вводит более прогрессивную, чем в винде, систему управления яркостью с помощью клавиш Fn)
20 делений яркости против 10 в оффтопике, причём последняя вырубает яркость нахрен (актуально ночью).
https://bugzilla.kernel.org/show_bug.cgi?id=62941 На всё про всё ушел ровно месяц.

"Для ядра Linux 3.13 представлены патчи с улучшением генераци..."
Отправлено st , 19-Ноя-13 12:23 
вот бы и для остальных ноутов такое прикрутить, у меня вот 4 деления против 8ми в винде, хотя на ядре 2.6.xx было одинаково 8

"Для ядра Linux 3.13 представлены патчи с улучшением генераци..."
Отправлено Аноним , 19-Ноя-13 15:14 
> вот бы и для остальных ноутов такое прикрутить, у меня вот 4
> деления против 8ми в винде, хотя на ядре 2.6.xx было одинаково
> 8

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


"Для ядра Linux 3.13 представлены патчи с улучшением генераци..."
Отправлено rshadow , 19-Ноя-13 15:51 
Неплохо было бы находить тех дядь которые ломают постоянно все эти клавиши и другие настройки, и руки им обрывать.

"Для ядра Linux 3.13 представлены патчи с улучшением генераци..."
Отправлено Сергей , 19-Ноя-13 13:35 
Смотря какое число выдаст генератор ;-)

"Для ядра Linux 3.13 представлены патчи с улучшением генераци..."
Отправлено Аноним , 19-Ноя-13 22:54 
> причём последняя вырубает яркость нахрен

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


"Для ядра Linux 3.13 представлены патчи с улучшением генераци..."
Отправлено myhand , 19-Ноя-13 12:13 
> выполнение программы приостанавливается до момента когда устройство /dev/urandom будет инициализировано и готово вернуть программе качественные случайные данные, что должно положительно сказаться на безопасности.

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


"Для ядра Linux 3.13 представлены патчи с улучшением генераци..."
Отправлено anonymous , 19-Ноя-13 13:04 
Поправьте меня, если я ошибаюсь, но вроде бы /dev/urandom инициализируется при загрузке системы. Так что только если очень специальный DOS.

"Для ядра Linux 3.13 представлены патчи с улучшением генераци..."
Отправлено Аноним , 19-Ноя-13 19:22 
Оно же отдает псевдослучайные значения не зависимо от содержимого буфера энтропии. Сколько надо столько и отдаст. Скорость правда несколько мегабайт в секунду получается. Очень мало.

"Для ядра Linux 3.13 представлены патчи с улучшением генераци..."
Отправлено Аноним , 19-Ноя-13 22:56 
Основные грабли - в том что программа может попросить данные рано, когда там вообще пусто. При этом полученные программой  данные могут быть не такими уж и случайными.

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


"Для ядра Linux 3.13 представлены патчи с улучшением генераци..."
Отправлено Аноним , 19-Ноя-13 12:18 
Случайные числа стали еще случайнее и это не случайно, на всякий случай.

"Для ядра Linux 3.13 представлены патчи с улучшением генераци..."
Отправлено тоже Аноним , 19-Ноя-13 13:40 
Случается, случаются и неслучайные случаи.

"Для ядра Linux 3.13 представлены патчи с улучшением генераци..."
Отправлено Аноним , 19-Ноя-13 18:48 
> Случается, случаются и неслучайные случаи.

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


"Для ядра Linux 3.13 представлены патчи с улучшением генераци..."
Отправлено Аноним , 19-Ноя-13 14:01 
А может быть с этим патчем числа стали менее случайными? Вспомните кивок Линуса.

"Для ядра Linux 3.13 представлены патчи с улучшением генераци..."
Отправлено Xaionaro , 19-Ноя-13 14:46 
Ну, это всё-таки Теодор Тсо ;).. Плюс всё равно другие разработчики будут изучать этот код перед коммитом)

"Для ядра Linux 3.13 представлены патчи с улучшением генераци..."
Отправлено Аноним , 19-Ноя-13 18:49 
> Плюс всё равно другие разработчики будут изучать этот код перед коммитом)

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



"Для ядра Linux 3.13 представлены патчи с улучшением генераци..."
Отправлено Xaionaro , 20-Ноя-13 17:51 
>> Плюс всё равно другие разработчики будут изучать этот код перед коммитом)
> Если они такие же как баран сверху с атомными часами ... то
> удачи.

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


"Для ядра Linux 3.13 представлены патчи с улучшением генераци..."
Отправлено Аноним , 19-Ноя-13 15:32 
Вы все еще верите в отсутствие закладок в ядре. Все это сказочки для фанатиков, любому разумному человеку ясно что линукс одна больша дырень.

"Для ядра Linux 3.13 представлены патчи с улучшением генераци..."
Отправлено Аноним , 19-Ноя-13 18:51 
> любому разумному человеку ясно что линукс одна больша дырень.

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


"Для ядра Linux 3.13 представлены патчи с улучшением генераци..."
Отправлено Аноним , 19-Ноя-13 23:22 
> Вы все еще верите в отсутствие закладок в ядре. Все это сказочки
> для фанатиков, любому разумному человеку ясно что линукс одна больша дырень.

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


"Для ядра Linux 3.13 представлены патчи с улучшением генераци..."
Отправлено pavlinux , 19-Ноя-13 21:49 
+    /* 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. :/

"Для ядра Linux 3.13 представлены патчи с улучшением генераци..."
Отправлено torteg , 19-Ноя-13 22:21 
Это градус неадеквата

"Для ядра Linux 3.13 представлены патчи с улучшением генераци..."
Отправлено anonymous , 19-Ноя-13 22:36 
Не факт. Я, конечно, ихсходников не читал, но предпологаю, что там вычисления по-модулю.  Кстати, если не лень, то можешь попробовать на множители пораскладывать. В каком многочлене будет выше наименьшая  степень множителя, тот сложнее анализировать. Если есть кто более сведующий в теории чисел,  то поправьте, если я ошибся.

"Для ядра Linux 3.13 представлены патчи с улучшением генераци..."
Отправлено pavlinux , 19-Ноя-13 22:38 
> Не факт. Я, конечно, ихсходников не читал, но предпологаю, что там вычисления
> по-модулю.  Кстати, если не лень, то можешь попробовать на множители
> пораскладывать. В каком многочлене будет выше наименьшая  степень множителя, тот
> сложнее анализировать. Если есть кто более сведующий в теории чисел,  
> то поправьте, если я ошибся.

Ну там примерно так объясняется


3.1.1 Analysis Without Input

When the input is set to zero, the mixing function is equivalent to an LFSR over GF(2^32) with
feedback polynomial Q(X) = α^3*(P(X) − 1) + 1, where α is the primitive element of GF(2^32)
corresponding to X defined by the CRC-32-IEEE 802.3 polynomial, and P(X) depends on the
size of the pool:

     input pool: P(X) = X^128 + X^103 + X^76 + X^51 + X^25 + X + 1
     output pool: P(X) = X^32 + X^26 + X^20 + X^14 + X^7 + X + 1.

The multiplication by α^3 is done by a lookup table, called twist-table in the source code.
The actual system slightly differs from what is stated in the comments of the source code.
First, the design of the mixing function is claimed to rely on a Twisted Generalized Feedback
Shift Register (TGFSR) as defined in [MK92]. However, TGFSRs are LFSRs on binary words
with a trinomial feedback polynomial whereas the mixing function uses a heptanomial. The
case of general polynomials on finite fields is treated in standard literature, such as [LN97].
Moreover, the maximal period, that is the primitivity of the feedback polynomial, seems to
have been ill understood, as the comments mention the primitivity for polynomials on GF(2),
whereas the primitivity must be checked on GF(232). This confusion is also repeated in [GPR06,
Definition 2.2].

Finally, the polynomial Q(X) = α^3*(P(X) − 1) + 1 is not primitive over GF(2^32), nor is it
even irreducible. Thus, the resulting LFSR does not achieve maximal period. The period is less
than 2^(92∗32) − 1, rather than the maximal value of 2^(128∗32) − 1, for the input pool,
and less than 2^(26∗32)−1 instead of 2^32∗32 − 1 for the output pool.

We do not believe these reduced periods can lead to practical attacks. However, Q(X) can be
made irreducible by changing just one feedback position:

   input pool: P(X) = X^128 + X^104 + X^76 + X^51 + X^25 + X + 1
   output pool: P(X) = X^32 + X^26 + X^19 + X^14 + X^7 + X + 1.

These modified polynomials have periods of (2^128∗32−1)/3 and (2^32∗32−1)/3, respectively.
A primitive polynomial can be easily achieved by using (α^i)*(P(X)−1)+1 with gcd(i,2^32−1) = 1,
for example for i = 1,2,4,7, . . ., and an adequate polynomial P(X). This would change the size
of the twist-table to 2^i elements. For instance, α^2*(X^32+X^26+X^23+X^14+X^7+X)+1 is primitive.
All these computations can be made using computational algebra systems like magma [BCP97].

Хотя в последнем примере, при 3-м члене 23-степень.


"Для ядра Linux 3.13 представлены патчи с улучшением генераци..."
Отправлено Аноним , 19-Ноя-13 22:38 
Не факт. Я, конечно, ихсходников не читал, но предпологаю, что там вычисления по-модулю.  Кстати, если не лень, то можешь попробовать на множители пораскладывать. В каком многочлене будет выше наименьшая  степень множителя, тот сложнее анализировать. Если есть кто более сведующий в теории чисел,  то поправьте, если я ошибся.

"Для ядра Linux 3.13 представлены патчи с улучшением генераци..."
Отправлено Аноним , 19-Ноя-13 23:03 
> В документе указано (http://eprint.iacr.org/2012/251.pdf)

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


"Для ядра Linux 3.13 представлены патчи с улучшением генераци..."
Отправлено Andrey Mitrofanov , 19-Ноя-13 23:09 
> + /* 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


"Для ядра Linux 3.13 представлены патчи с улучшением генераци..."
Отправлено pavlinux , 20-Ноя-13 02:03 
>  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

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


"Для ядра Linux 3.13 представлены патчи с улучшением генераци..."
Отправлено Andrey Mitrofanov , 20-Ноя-13 13:11 
>>  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>>


"Для ядра Linux 3.13 представлены патчи с улучшением генераци..."
Отправлено pavlinux , 20-Ноя-13 14:29 
> да посмотрел бы.

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

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

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


"Для ядра Linux 3.13 представлены патчи с улучшением генераци..."
Отправлено Andrey Mitrofanov , 20-Ноя-13 19:32 
> В отличии от тебя, мне лень разжёвывать.
> Для посетителей опеннета пойдёт, чтоб оценить масштаб изменений:
> (2^(128*32)-1)/3 > 2^(96*32)-1

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

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

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


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

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


"Для ядра Linux 3.13 представлены патчи с улучшением генераци..."
Отправлено Andrey Mitrofanov , 22-Ноя-13 21:35 
> Во втором примере видал 23-степень?

Какой пример, я только по картинкам.