информационная безопасность
без паники и всерьез
 подробно о проектеRambler's Top100
Где водятся OGRыАтака на InternetВсе любят мед
BugTraq.Ru
Русский BugTraq
 Анализ криптографических сетевых... 
 Модель надежности двухузлового... 
 Специальные марковские модели надежности... 
 Три миллиона электронных замков... 
 Doom на газонокосилках 
 Умер Никлаус Вирт 
главная обзор RSN блог библиотека закон бред форум dnet о проекте
bugtraq.ru / форум / theory
Имя Пароль
ФОРУМ
если вы видите этот текст, отключите в настройках форума использование JavaScript
регистрация





Легенда:
  новое сообщение
  закрытая нитка
  новое сообщение
  в закрытой нитке
  старое сообщение
  • Напоминаю, что масса вопросов по функционированию форума снимается после прочтения его описания.
  • Новичкам также крайне полезно ознакомиться с данным документом.
Зачем так извращаться? 15.01.05 03:44  Число просмотров: 3066
Автор: whiletrue <Роман> Статус: Elderman
Отредактировано 15.01.05 04:09  Количество правок: 4
<"чистая" ссылка>
> Есть желание улучшить не-коррелируемость ГПСЧ. Идея такая:
> береться 11 32-битных чисел от ГПСЧ, одно отбрасывается, а
> от 10 берется поразрядная бент-функция, результат
> становится выходом "улучшенного" генератора. Причем перед
> вызовом bent аргументы подвергаются циклическому битовому
> сдвигу на 0, 1, 3, 5, 7, 11, 13, 17, 19, 23.
>
> Понятно, что вроде-бы должно быть в ~10 раз лучше, но
> хочется теоретического успокоения. Увы нет "погруженности"
> в теорию до желаемого уровня и возможности сделать это в
> доступное время.
>
> Кто может сказать что-либо толкового?

Что такое корреляция? Насколько я понимаю - это зависимость текущего сгенеренного значения от m предыдущих. То есть злоумышленник набирает какую-то статистику и строит некую цепь Маркова, глубины, которую позволяет его компьютер. Значит если увеличить период повторония генерируемой последовательности, то мы таким образом "уменьшим" коррелируемость. То есть усложним задачу злоумышленнику. Я прав?

Обычно рассматривается рекурентная последовательность, т.е. некий автономный автомат с какими-то начальными значениями. Все значения сдвигаются влево, а очередное значение генерится так Ai = g(Ai-1, ... Ai-m-1), где m - ранг рекурентной последовательности. Все делается над неким конечным полем, например GF(2^8) (т.е. символы от 0-255) или GF(2) (бинарная п-ть). Функция g может быть линенейной или нелинейной. В случае линейной рекурентной последовательности Ai = a1*Ai-1+ ...+ am*Ai-m-1 - это называется характеристическим уравнением ЛРП. Над выбранным полем можно рассматривать поле характеристических функций. ЛРП соответсвует характирестический многочлен f(x) = x^m + SUM(ai * x^i). Так вот чтобы построить ЛРП максимальной длины нужно просто взять неприводимый многочлен выбранного ранга (степени) m, период будет равен T=q^m - 1, где q - порядок конечного поля (2 - для бинарной п-ти). И еще есть теоремка, что если мы перемножим два многочлена с периодами T1 и T2, то период результирующего многочлена будет T=T1*T2. Все! Имея это на руках можно генерить последовательности любого самого злостного периода.

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

В твоем случае - надо понять что есть ф-ция g и ее уже анализировать, а для этого надо распотрошить твой ГПСЧ и bent... геморно, имхо. Грубо говоря ты делаешь так, чтобы сгенеренное число зависело от десяти предыдущих, а вдруг твой ГПСЧ генерит ЛРП со значениями, зависящими от i-100, i-31 и i-1, тогда ты можешь сделать хуже, т.к. результирующая п-ть будет иметь меньший период...
<theory>
бент: влияние лунного света на рост телеграфных столбов :) 14.01.05 14:04  
Автор: leo <Леонид Юрьев> Статус: Elderman
<"чистая" ссылка>
Есть желание улучшить не-коррелируемость ГПСЧ. Идея такая: береться 11 32-битных чисел от ГПСЧ, одно отбрасывается, а от 10 берется поразрядная бент-функция, результат становится выходом "улучшенного" генератора. Причем перед вызовом bent аргументы подвергаются циклическому битовому сдвигу на 0, 1, 3, 5, 7, 11, 13, 17, 19, 23.

Понятно, что вроде-бы должно быть в ~10 раз лучше, но хочется теоретического успокоения. Увы нет "погруженности" в теорию до желаемого уровня и возможности сделать это в доступное время.

Кто может сказать что-либо толкового?
Если нужен улучшеный ГПСЧ по сравнению с 32, может просто... 17.01.05 11:54  
Автор: DPP <Dmitry P. Pimenov> Статус: The Elderman
Отредактировано 17.01.05 12:01  Количество правок: 1
<"чистая" ссылка>
> Есть желание улучшить не-коррелируемость ГПСЧ. Идея такая:
> береться 11 32-битных чисел от ГПСЧ, одно отбрасывается, а
> от 10 берется поразрядная бент-функция, результат
> становится выходом "улучшенного" генератора. Причем перед
> вызовом bent аргументы подвергаются циклическому битовому
> сдвигу на 0, 1, 3, 5, 7, 11, 13, 17, 19, 23.

Если нужен улучшеный ГПСЧ по сравнению с 32, может просто воспользоваться 64 разрядным, построеным по аналогичному алгоритму. Он должен быть лучше не на десятичный порядок, а на десяток десятичных порядков. Скорость генерации нзначительно упадет, по сравнению с предложенным.

> Понятно, что вроде-бы должно быть в ~10 раз лучше, но
> хочется теоретического успокоения. Увы нет "погруженности"
> в теорию до желаемого уровня и возможности сделать это в
> доступное время.
>
> Кто может сказать что-либо толкового?

Рискну предложить что-то толковое.
Зачем нужны ГПСЧ? В основном для генерации ключа.
Для чего нужны "улучшеные" ГПСЧ? Чтоб сложнее было поломать атакой на генерацию ключа.
Какой самый лучший ГПСЧ? ГСЧ.
Почему народ пользуется именно ГПСЧ? Удобнее и быстрее - не надо дополнительного оборудования или "набирания случайного текста на клавиатуре".
Так почему бы не организовать ГСЧ на базе существующих устройств без использования клавиатуры? В компе почти нет подходящих устройств. Хотя почему нет, кто-то предлагал сделать что-то подобное на основе звуковой платы, точнее на основе ее "шума". Можно воспользоваться датчиками температуры, вращением кулеров, напряжения, временем перемещения головок дисковода.
Представьте embedded-устройство, в которое пока не хочеться... 17.01.05 16:51  
Автор: leo <Леонид Юрьев> Статус: Elderman
<"чистая" ссылка>
> Если нужен улучшеный ГПСЧ по сравнению с 32, может просто
> воспользоваться 64 разрядным, построеным по аналогичному
> алгоритму. Он должен быть лучше не на десятичный порядок, а
> на десяток десятичных порядков. Скорость генерации
> нзначительно упадет, по сравнению с предложенным.
>
> Рискну предложить что-то толковое.
> Зачем нужны ГПСЧ? В основном для генерации ключа.
> Для чего нужны "улучшеные" ГПСЧ? Чтоб сложнее было поломать
> атакой на генерацию ключа.
> Какой самый лучший ГПСЧ? ГСЧ.
> Почему народ пользуется именно ГПСЧ? Удобнее и быстрее - не
> надо дополнительного оборудования или "набирания случайного
> текста на клавиатуре".
> Так почему бы не организовать ГСЧ на базе существующих
> устройств без использования клавиатуры? В компе почти нет
> подходящих устройств. Хотя почему нет, кто-то предлагал
> сделать что-то подобное на основе звуковой платы, точнее на
> основе ее "шума". Можно воспользоваться датчиками
> температуры, вращением кулеров, напряжения, временем
> перемещения головок дисковода.
Представьте embedded-устройство, в которое пока не хочеться встраивать шумящий диод. Точнее говоря, дело не в самом диоде, а в том что если "доверять" всетолькоему, то нужно принять целый рад мер для его защиты и надежной работы.

Удваиваивание "ширины" генератора съест очень много ресурсов (больше чем в два раза), но при этом на смом деле априорно ничего не гарантирует.
Все правильно. Тогда, если учесть дополнительные условия,... 17.01.05 17:25  
Автор: DPP <Dmitry P. Pimenov> Статус: The Elderman
<"чистая" ссылка>
> Представьте embedded-устройство, в которое пока не хочеться
> встраивать шумящий диод. Точнее говоря, дело не в самом
> диоде, а в том что если "доверять" всетолькоему, то
> нужно принять целый рад мер для его защиты и надежной
> работы.

Все правильно. Тогда, если учесть дополнительные условия, некоррелируемую последовательность ПСЧ можно попытаться получить последовательным шифрованием (DESом, например). Т.е. берем "немножко" начальных случайных 56-64 разрядных чисел, одно - исходный текст, другое ключ шифруем, шифруем. Можно для получения нового ПСЧ сложить текущее и предыдущее зашифрованное значение и то, что получится шифрануть. Что касается быстродействия, то я слышал что даже есть соответствующие чипы, маленькие, быстрые для встраиваемых устройств. Доказать некоррелируемость дложно быть не сложно.

> Удваиваивание "ширины" генератора съест очень много
> ресурсов (больше чем в два раза), но при этом на смом деле
> априорно ничего не гарантирует.

Ну, да, все зависит от алгоритма. Для тупого разрядность вообще не будет играть роли.
Зачем так извращаться? 15.01.05 03:44  
Автор: whiletrue <Роман> Статус: Elderman
Отредактировано 15.01.05 04:09  Количество правок: 4
<"чистая" ссылка>
> Есть желание улучшить не-коррелируемость ГПСЧ. Идея такая:
> береться 11 32-битных чисел от ГПСЧ, одно отбрасывается, а
> от 10 берется поразрядная бент-функция, результат
> становится выходом "улучшенного" генератора. Причем перед
> вызовом bent аргументы подвергаются циклическому битовому
> сдвигу на 0, 1, 3, 5, 7, 11, 13, 17, 19, 23.
>
> Понятно, что вроде-бы должно быть в ~10 раз лучше, но
> хочется теоретического успокоения. Увы нет "погруженности"
> в теорию до желаемого уровня и возможности сделать это в
> доступное время.
>
> Кто может сказать что-либо толкового?

Что такое корреляция? Насколько я понимаю - это зависимость текущего сгенеренного значения от m предыдущих. То есть злоумышленник набирает какую-то статистику и строит некую цепь Маркова, глубины, которую позволяет его компьютер. Значит если увеличить период повторония генерируемой последовательности, то мы таким образом "уменьшим" коррелируемость. То есть усложним задачу злоумышленнику. Я прав?

Обычно рассматривается рекурентная последовательность, т.е. некий автономный автомат с какими-то начальными значениями. Все значения сдвигаются влево, а очередное значение генерится так Ai = g(Ai-1, ... Ai-m-1), где m - ранг рекурентной последовательности. Все делается над неким конечным полем, например GF(2^8) (т.е. символы от 0-255) или GF(2) (бинарная п-ть). Функция g может быть линенейной или нелинейной. В случае линейной рекурентной последовательности Ai = a1*Ai-1+ ...+ am*Ai-m-1 - это называется характеристическим уравнением ЛРП. Над выбранным полем можно рассматривать поле характеристических функций. ЛРП соответсвует характирестический многочлен f(x) = x^m + SUM(ai * x^i). Так вот чтобы построить ЛРП максимальной длины нужно просто взять неприводимый многочлен выбранного ранга (степени) m, период будет равен T=q^m - 1, где q - порядок конечного поля (2 - для бинарной п-ти). И еще есть теоремка, что если мы перемножим два многочлена с периодами T1 и T2, то период результирующего многочлена будет T=T1*T2. Все! Имея это на руках можно генерить последовательности любого самого злостного периода.

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

В твоем случае - надо понять что есть ф-ция g и ее уже анализировать, а для этого надо распотрошить твой ГПСЧ и bent... геморно, имхо. Грубо говоря ты делаешь так, чтобы сгенеренное число зависело от десяти предыдущих, а вдруг твой ГПСЧ генерит ЛРП со значениями, зависящими от i-100, i-31 и i-1, тогда ты можешь сделать хуже, т.к. результирующая п-ть будет иметь меньший период...
Я имел в виду два "смысла", первый именно этот, второй -... 17.01.05 16:37  
Автор: leo <Леонид Юрьев> Статус: Elderman
<"чистая" ссылка>
> Что такое корреляция? Насколько я понимаю - это зависимость
> текущего сгенеренного значения от m предыдущих. То есть
Я имел в виду два "смысла", первый именно этот, второй - корреляция сгенерированных чисел с некими внешними процессами (т.е. качество генератора). Бент-функция пока "успокаивает" меня в обоих случаях.

> злоумышленник набирает какую-то статистику и строит некую
> цепь Маркова, глубины, которую позволяет его компьютер.
Зная алгоритм генерации можно построить гораздо более оптимальный алгоритм для "раскрутки".

> Значит если увеличить период повторония генерируемой
> последовательности, то мы таким образом "уменьшим"
> коррелируемость. То есть усложним задачу злоумышленнику. Я
> прав?
В принципе да, увеличивая период мы в большинстве случаев не упростим задачу.
Но сам-по-себе большой период ничего не гарантирует.

> Обычно рассматривается рекурентная последовательность, т.е.
> некий автономный автомат с какими-то начальными значениями.
> Все значения сдвигаются влево, а очередное значение
> генерится так Ai = g(Ai-1, ... Ai-m-1), где m - ранг
> рекурентной последовательности. Все делается над неким
> конечным полем, например GF(2^8) (т.е. символы от 0-255)
> или GF(2) (бинарная п-ть). Функция g может быть линенейной
> или нелинейной. В случае линейной рекурентной
> последовательности Ai = a1*Ai-1+ ...+ am*Ai-m-1 - это
> называется характеристическим уравнением ЛРП. Над выбранным
> полем можно рассматривать поле характеристических функций.
> ЛРП соответсвует характирестический многочлен f(x) = x^m +
> SUM(ai * x^i). Так вот чтобы построить ЛРП максимальной
> длины нужно просто взять неприводимый многочлен выбранного
> ранга (степени) m, период будет равен T=q^m - 1, где q -
> порядок конечного поля (2 - для бинарной п-ти). И еще есть
> теоремка, что если мы перемножим два многочлена с периодами
> T1 и T2, то период результирующего многочлена будет
> T=T1*T2. Все! Имея это на руках можно генерить
> последовательности любого самого злостного периода.
Период очень часто ничего не даёт, можно взять пару сдвиговых регистров с разным периодом и нелинейно объединить их выходы. Но без продуманности такая схема взламывается лишь немного сложнее простого сдвигового регистра.

> В случае нелинейных РП - там анализируется регулярность
> автомата, строятся какие-то злостные графы, в них
> склеиваются циклы... щас навру, а лезть смотреть неохота.
> Ну смотреть надо в этом направлении.
Это ясно, что в этом направлении...

> В твоем случае - надо понять что есть ф-ция g и ее уже
> анализировать, а для этого надо распотрошить твой ГПСЧ и
> bent... геморно, имхо. Грубо говоря ты делаешь так, чтобы
> сгенеренное число зависело от десяти предыдущих, а вдруг
> твой ГПСЧ генерит ЛРП со значениями, зависящими от i-100,
> i-31 и i-1, тогда ты можешь сделать хуже, т.к.
> результирующая п-ть будет иметь меньший период...
Только в том случае если генератор "собран" на нелинейных функциях 100% коррелирующих с используемой бент-функцией.

Ясно, что по-хорошему нужно анализировать именно генератор (http://leo.yuriev.ru/random), но пока никто ничего толкового не предложил.
Чем же она тебя успокаивает? :) 05.02.05 19:28  
Автор: Serge3leo Статус: Незарегистрированный пользователь
<"чистая" ссылка>
> > Что такое корреляция? Насколько я понимаю - это
> зависимость
> > текущего сгенеренного значения от m предыдущих. То
> есть
> Я имел в виду два "смысла", первый именно этот, второй -
> корреляция сгенерированных чисел с некими внешними
> процессами (т.е. качество генератора). Бент-функция пока
> "успокаивает" меня в обоих случаях.

Чем же она тебя успокаивает? :)

На мой, не просвещённый взгляд. Этот "алгоритм" имеет хоть какой-то смысл, если точно известно, что период ГПСЧ не кратен 11. Всё остальное "вода", т.к. в описаном довеске нет внутреннего состояния. Например, возмите две модельки ГПСЧ типа, скажем x = ( x + 1 ) % 11 и x = ( x + 1 ) % 13 и посмотрите на "улучшение".
По-поводу самого ГПСЧ 06.02.05 13:55  
Автор: leo <Леонид Юрьев> Статус: Elderman
Отредактировано 06.02.05 14:08  Количество правок: 1
<"чистая" ссылка>
Я не нашел способа как его толком проанализировать.

Алгоритм простой - 32-а LSFR по X64+X4+X3+X, выходы этих регистров формируют 32 разряда выхода генератора. Если состояние генератора представить в виде таблицы 64x32, то 32 LSFR образуют 32 строки по 64 бита.
Самое главное - feedback для сдвиговых регистров, он нелинейный. "Обычный" feedback (он в GF(2), но просто вычисляется параллельно для всех 32-х LSFR) складывается по модулю 232 с нелинейной функцией от трех "вертикалей" внутри 32-х LSFR, добавление константы не дает LSFR уйти "в нули".
Проще просмотреть С-код, чем объяснить :)

Дак вот, я не знаю (не нашел) как описать "поворот на 90" (и соответственно весь генератор), при формировании feedback для LSFR, кроме как булевой алгеброй. Но "булево представление" не дает мне возможность проанализировать генератор. У меня нет соответствующего образования и опыта в таких делах, и увы нет времени чтобы "доучиваться". Вполне возможно, что есть "общеизвестный" подход, который позволяет все это легко решить...
IMHO сложнее алгебраическая атака с... 06.02.05 10:59  
Автор: leo <Леонид Юрьев> Статус: Elderman
Отредактировано 06.02.05 11:01  Количество правок: 1
<"чистая" ссылка>
IMHO сложнее алгебраическая атака с целью предсказания внутреннего состояния ГПСЧ.
1




Rambler's Top100
Рейтинг@Mail.ru


  Copyright © 2001-2024 Dmitry Leonov   Page build time: 0 s   Design: Vadim Derkach