Разработчик Теодор Тсо представил (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...
Новость: https://www.opennet.ru/opennews/art.shtml?num=38461
Я тут подумал, а что если...Смотрите есть всем известная штука как атомные часы. Цезий в них колеблется с частотой 9.2 ГГц.
Вопрос насколько это удобный источник энтропии?И совсем уж непонятный вопрос насколько для его вычисления будет достаточно кластера в процессорами в 4 ГГц?
Имею ввиду один т.е один процессор с одним шагом другой с другим?
Немного перепоясню мыслю.Допустим у вас есть карманные атомные часы (вес 35 г)
Они выдают вам псевдослучайную величину типа наносекунд.
Достаточно ли 1000 процессоров для имитации поведения поведения таких часов?
Кто хорошо знает теорию погрешностей измерений?
С какого бы перепоя им выдавать случайные значения? На то они и атомные часы, что они работают стабильно. Ты наверное неграмотная шваль навроде фанбоев поцтеринга и перепутал атомные часы распадом атомных ядер, которые вроде как распадаются случайно?
> На то они и атомные часы, что они работают стабильно.Часы как источник энтропии обычно используют в том контексте что заранее неизвестно в какое время вас (генератор случайных чисел) позвали из "вон той программы". Этот факт можно поюзать как дополнительный источник энтропии.
Аноним выше, конечно тролль, но он прав. Псевдослучайная величина может быть расчитанна на основе показаний атомных часов. Хотя алгоритмы получения псевдослучайных величин могут основываться не только на времени.
Заданный же вопрос остался вне пределов моего понимания.
Поясню.
У вас есть атом цезия с частотой 10 ГГц, ну это для упрощения да?
т.е.
он допустим выдает псевдослучайные значения времени.типа 0,00000000001 и каждую секунду значение меняется до неузначаемости..
Процессор с частотой в 1 ГГц совершает 1 такт за 0,000000001 секунды в 10 раз медленнее. Т.е он в принципе ничего не может предугадать поведение атома цезия, вернее вероятность этого явно меньше 10% сколько раз колебнулся атом цезия пока этот проц совершил 1 такт 5 или все 9?
Вопрос, сколько нужно процессоров чтобы псевдослучайное число на базе времени стало предугаданным?
И еще, а если использовать атомные часы с пониженной точностью, ошибающиеся на 1 наносекунду , каждую секунду?( ошибка на 1 секунду в 30 лет) Такие часы будут обладать большей случайностью. Не так ли?
Да и шутнику про атомную батарейку, современный атомные часы выпученные в 2011 году потребляют 0,3 Вт...
Поправлюсь, какой бы алгоритм предугадывания вы не писали, быстрее частоты проца значение не найти...Нужен кластер... вопрос, сколько и какой теоретически частоты нужен кластер для такой реализации, и вообще возможен ли он, если в кластере задержки в 10000 раз больше...
Вы все же что то не то говорите.
Суть атомных часов (насколько я понимаю) в том что они выдают строго заданную частоту с крайне маленькой погрешностью. Таким образом отрезок времени может быть измерен спомощью количества колебаний атома и переведен в необходимые единицы времени.
Атомные часы не выдают псевдослучайное число - генератор псевдослучайных чисел расчитывает их по некоторому алгоритму. Причем алгоритм, по большому счету, может вообще не использовать время при генерации псевдослучайного числа.Поэтому ответ на Ваш вопрос(с некоторыми допущениями в условии) звучит так - все зависит от алгоритма генератора псевдослучайных чисел.
Это я понял, но базисом псевдослучайного числа в данном случаем может быть время, показания датчиков напряжения температуры тока и пр на материнке и т.д.
Т.е. понятно что генератор складывает перемножает возводит в степень округляет вычитает и пр. Потом вычитает четные цифры и з нечетных и т.д.Кто-то допустим пишет генератор на базе звуковых шумов.
Это все понятно.Я же говор об изменчивости базисов для этого псевдослучайного числа.
Т.е чем чаще меняется базис тем более "случайным" является псевдослучайное число. И чем шире диапазон изменений базиса, тем лучше. Базис количества колебаний атома цезия в атомных часах изменяется постоянно.Даже если допустить что вам полностью известен алгоритм генерации, полностью повторить условия базиса у вас не получится. Ведь так?
Если значение получаемое из генератора расчитывается исключительно по времени - Rand(t), то очевидно, что для получения значения которое будет сгенерированно через n колебаний атома (с частотой v) вы можете использовать Rand(t + n/v)Но, я полагаю, что все же не улавливаю суть вопроса.
>Базис количества колебаний атома цезия в атомных часах изменяется постоянно.Последний раз объясняю (хотя глупо чего то объяснять дураку да ещё и ширнутому какой то гадостью) - НЕТ! Атомные часы потому и в большом деманде что они _крайне_ стабильные. Меряй время бабушкиным будильником - это будет куда как более случайные величины.
Уважаемый, вы непонялиСейчас используется в ГПСЧ счетчик тактов процессора. Что если использовать счетчик пикосекунд из атомных часов?
И потом это промежути атомные часы меряют правильно. Время же и количество колебаний постоянно растет.
и атомную батарейку для ноутбука
Интересно войдёт ли в ядро 3.13 патч для моего бука, который вводит более прогрессивную, чем в винде, систему управления яркостью с помощью клавиш Fn)
20 делений яркости против 10 в оффтопике, причём последняя вырубает яркость нахрен (актуально ночью).
https://bugzilla.kernel.org/show_bug.cgi?id=62941 На всё про всё ушел ровно месяц.
вот бы и для остальных ноутов такое прикрутить, у меня вот 4 деления против 8ми в винде, хотя на ядре 2.6.xx было одинаково 8
> вот бы и для остальных ноутов такое прикрутить, у меня вот 4
> деления против 8ми в винде, хотя на ядре 2.6.xx было одинаково
> 8Ещё было бы неплохо подправить изменения громкости, чтобы по 2%, а не по 6%, изменялось за один ход.
Неплохо было бы находить тех дядь которые ломают постоянно все эти клавиши и другие настройки, и руки им обрывать.
Смотря какое число выдаст генератор ;-)
> причём последняя вырубает яркость нахрен...и юзер чешет репу: wtf, экран нотика сдох?
> выполнение программы приостанавливается до момента когда устройство /dev/urandom будет инициализировано и готово вернуть программе качественные случайные данные, что должно положительно сказаться на безопасности.Новая дырка для DOS?
Поправьте меня, если я ошибаюсь, но вроде бы /dev/urandom инициализируется при загрузке системы. Так что только если очень специальный DOS.
Оно же отдает псевдослучайные значения не зависимо от содержимого буфера энтропии. Сколько надо столько и отдаст. Скорость правда несколько мегабайт в секунду получается. Очень мало.
Основные грабли - в том что программа может попросить данные рано, когда там вообще пусто. При этом полученные программой данные могут быть не такими уж и случайными.Если программа в этот момент генерила какой-нить RSA ключ - получится не комильфо.
Случайные числа стали еще случайнее и это не случайно, на всякий случай.
Случается, случаются и неслучайные случаи.
> Случается, случаются и неслучайные случаи.Дык то случайно!
А может быть с этим патчем числа стали менее случайными? Вспомните кивок Линуса.
Ну, это всё-таки Теодор Тсо ;).. Плюс всё равно другие разработчики будут изучать этот код перед коммитом)
> Плюс всё равно другие разработчики будут изучать этот код перед коммитом)Если они такие же как баран сверху с атомными часами ... то удачи.
>> Плюс всё равно другие разработчики будут изучать этот код перед коммитом)
> Если они такие же как баран сверху с атомными часами ... то
> удачи.Разработчик ядра linux - это очень уважаемая и престижная деятельность. Вы, вероятно, плохо себе представляете требования к коду ядра.
Вы все еще верите в отсутствие закладок в ядре. Все это сказочки для фанатиков, любому разумному человеку ясно что линукс одна больша дырень.
> любому разумному человеку ясно что линукс одна больша дырень.Ты попутал свою жопу с линуксом, ****илло :)
> Вы все еще верите в отсутствие закладок в ядре. Все это сказочки
> для фанатиков, любому разумному человеку ясно что линукс одна больша дырень.Какое жирное трололо сегодня к нам пришло.
+ /* 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. :/
Это градус неадеквата
Не факт. Я, конечно, ихсходников не читал, но предпологаю, что там вычисления по-модулю. Кстати, если не лень, то можешь попробовать на множители пораскладывать. В каком многочлене будет выше наименьшая степень множителя, тот сложнее анализировать. Если есть кто более сведующий в теории чисел, то поправьте, если я ошибся.
> Не факт. Я, конечно, ихсходников не читал, но предпологаю, что там вычисления
> по-модулю. Кстати, если не лень, то можешь попробовать на множители
> пораскладывать. В каком многочлене будет выше наименьшая степень множителя, тот
> сложнее анализировать. Если есть кто более сведующий в теории чисел,
> то поправьте, если я ошибся.Ну там примерно так объясняется
3.1.1 Analysis Without InputWhen 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-степень.
Не факт. Я, конечно, ихсходников не читал, но предпологаю, что там вычисления по-модулю. Кстати, если не лень, то можешь попробовать на множители пораскладывать. В каком многочлене будет выше наименьшая степень множителя, тот сложнее анализировать. Если есть кто более сведующий в теории чисел, то поправьте, если я ошибся.
> В документе указано (http://eprint.iacr.org/2012/251.pdf)Ага, там еще написано: "However, Q(X) can be made irreducible by changing just one
feedback position" - подчеркивая что существующий PRNG не самый оптимальный по длине неповторяющейся последовательности.
> + /* 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
> 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А, пля... мой косяк, не туда смотрел :]
>> 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>>
> да посмотрел бы.В отличии от тебя, мне лень разжёвывать.
Для посетителей опеннета пойдёт, чтоб оценить масштаб изменений:(2^(128*32)-1)/3 > 2^(96*32)-1
детальней все описано в PDF_ке.
> В отличии от тебя, мне лень разжёвывать.
> Для посетителей опеннета пойдёт, чтоб оценить масштаб изменений:
> (2^(128*32)-1)/3 > 2^(96*32)-1Про градусы в членах писал другой павлин? Ну, привет ему.
> детальней все описано в PDF_ке.
Теперь и я pdf-ку перелистал. Научная наука, со своими картинками. ПрЕдмет исчерпан, ты победил.
>> В отличии от тебя, мне лень разжёвывать.
>> Для посетителей опеннета пойдёт, чтоб оценить масштаб изменений:
>> (2^(128*32)-1)/3 > 2^(96*32)-1
> Про градусы в членах писал другой павлин? Ну, привет ему.Во втором примере видал 23-степень?
> Во втором примере видал 23-степень?Какой пример, я только по картинкам.