как протетестировать крипто-алгоритм?

В общем меня недавно заинтересовали генераторы ПСЧ. Особенно мне стало интересно их применение для генерации гаммы потокового шифра. В общем говоря конкретно про LCG (линейный конгруэнтный датчик ПСП), а именно данная его реализация, дающая период повторения 2^32

Код (Text):

1.  
2.     mov edx,1664525
3.     mul edx
4.     add eax,1013904223

Как начальный вектор для работы датчика можно взять 32 битный ключ для шифрования. Сама гамма накладывается на исходный тест сложением по модулю 2. Для того, чтобы увеличить длину ключа можно использовать несколько проходов, использующих разные части ключа. В общем мне просто интересно и я абсолютный нуб в данной области. Для меня данный алгоритм имел бы одно преимущество по сравнению с этим же RC4\ARCFOUR тем, что не нужно никаких дополнительных таблиц. Т.е. именно мне нужен для своих целей по максимум простой и компактный алго при этом обладающий достаточной стойкостью и RC4 не подходит именно из-за того, что компактность и простота RC4 теряется, поскольку надо иметь еще дополнительно буфер из 256 байт для разворачивания ключа. Конечно глупо сравнивать такой "алгоритм" с RC4. Но мне просто стало интересно как вообще узнать криптостойкий ли алгоритм шифрования? Исходники и бинарник тут, правда на Delphi. Очень простой и компактный код. Пробовал брать текстовый файл размером неск. гбайт содержащий ASCII символ - 'a' (0x61) - выходной шифр-текст абсолютно не сжимается. Но это не показатель. Как вообще узнать насколько быстро сломают шифр?)

 

А что тут ломать-то? Зная 4 байта плейнтекста вычисляешь состояние ГСЧ (eax) и можешь крутить его вперед и назад как хочешь, получая любой элемент гаммы...

 

А как узнать eax? Ну, например 0x61 xor Y = 0x13. То мы вычислим только Y = 0x72. Но само состояние датчика - 4 байта, а мы узнаем только старший байт. (при гаммировании xor'ится со старшим байтом, поскольку у LCG он наиболее "случайный") К тому же если исходный текст прогнали 4 раза с разным ключем, то как дальше вычислять состояние каждого(4) датчика?

 

Младшие байты наверняка можно вычислить математически, но это даже не принципиально: определили старший, а оставшиеся можно перебором. Всего 16 млн. вариантов.

Это как? Типа c = p^k1^k2^k3^k4?
Написал бы тогда уж тут (псевдо)код своего генератора гаммы, чтоли (в сообщение, не в аттачмент).

 

Так то да Т.е. 128-битный ключ делится на 4 блока и шифрование потока происходит в 4 прохода. Я лично не профи в этом поэтому и хочу посоветоваться. А если кратко описать алгос, то:

1. Есть "молотилка" (LCG-датчик) типа x(t+1) = (a*x(t) + c) mod m, где a = 1664525, c = 1013904223, m = 2^32
2. "Шифрование" 32-битным ключем (один проход) делается так: c(i) = p(i) xor x(t)[3], где x(t) - текущее состояние датчика. В качестве начального вектора для x(0) берется 32-битное значение, которое формируется как:
k(n+1) = (a*k(n) + c) mod m. x(0)[n] = k(n+1)[3], где k(0) - 32-битный ключ шифрования.
3. Для того, чтобы увеличить длину ключа, используется несколько проходов. Т.е. например берется 128-битный ключ и разбивается на 4 части и т.д. Чтобы исключить возможность совпадения k1,k2,k3,k4 изначально k1 = f(k1), k2 = f(f(k2)) т.д., где f - та же функция инициализации 32-битного вектора x(0)

хз понятно ли написал вообще нуб нубом

 

Т.е. есть четыре одинаковых регистра сдвига, которые различаются только начальными заполнениями. Очередной байт гаммы — это сумма по модулю 2 старших байтов этих регистров. Так?

ИМХО этот алгоритм ломается тривиально (как именно — надо думать). Во-первых, несмотря на то что регистров 4, период гаммы все равно будет 2^32. Во-вторых, как-то все это оень линейно выглядит...

Эти танцы с бубном не исключают совпадение. Где гарантия что для k1 != k2 будет верно f(k1) != f(f(k2))?

 

Блин а тут то я ступил =) Получается так =)))

 

Используй в качестве ГПСЧ любую нелинейную функцию основаную на сети Файстеля. Ну а стойкий алгоритм или нет - будет ясно после нескольких лет активного его использования всем миром Правда для начала стоит привести математическое обоснование стокости против всех известных на данный момент универсальных атак.

 

Ну это мне не надо

А вот это я и сам хочу узнать как делается В этом собственно и вопрос заключается

 

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

 

Ну, обычно до того как начинать "активное использование" адгоритм лет несколько мучает упомянутое криптографическое сообщество. Так что шансы что с алгоритмом что-то сильно не так значительно уменьшаются.

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

 

Да я для себя делаю и мне пофиг и доказывать никому не нужно ничего =) Пропустил через DIEHARD выходную последовательность, но как интерпретировать результаты?

 

flankerx

критерии надёжности и скорости со временем не меняются .

 

Если бы они не менялись, люди до сих пор использовали бы шифр Цезаря...

Конкурс на AES был объявлен потому, что DES обеспечивал недосточную криптографическую стойкость и был медленным при программной реализации.

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

 

Во многих тестах p-valie порядка 0.9, в некоторых 0.03. Короче тест провален, случайные данные должны давать значения близкие к 0.5

 

ntldr
Ясно, фтопку жесть. тогда может посоветуете алгос, чтоб был потоковый, криптостойкий, очень простой в реализации (типа RC4), но (!) без использования всяких S-BOX и всякой хрени (TEAN как то обходится без всего этого, но опять блочный )

 

Юзайте любой блочный алго в режиме CFB. Подойдет тот же XTEA.

 

Или OFB или CTR

 

flankerx

да, ладно про Цезаря рассказывать - это по сути начало самой криптографии тогда-то и критериев не было. другой вопрос в том, что могут появляться новые мат. методы взлома, но это так редко бывает.

 

[deleted]

Всё. Всем спасибо! Остановился на классическом 16-раундовом TEA в режиме OFB. Довольно шустро шифрует и не очень много кода, хотя криптостойкость наверное так себе. Не AES256 какой-нибудь или Twofish в режиме CBC, но мне хватит =)