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

Тема в разделе "WASM.CRYPTO", создана пользователем BaGiE, 1 дек 2007.

  1. BaGiE

    BaGiE New Member

    Публикаций:
    0
    Регистрация:
    27 мар 2005
    Сообщения:
    84
    Адрес:
    Mordor
    В общем меня недавно заинтересовали генераторы ПСЧ. Особенно мне стало интересно их применение для генерации гаммы потокового шифра. В общем говоря конкретно про 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) - выходной шифр-текст абсолютно не сжимается. Но это не показатель. Как вообще узнать насколько быстро сломают шифр?)
     
  2. flankerx

    flankerx New Member

    Публикаций:
    0
    Регистрация:
    2 июл 2004
    Сообщения:
    423
    Адрес:
    Moscow, Russia
    А что тут ломать-то? Зная 4 байта плейнтекста вычисляешь состояние ГСЧ (eax) и можешь крутить его вперед и назад как хочешь, получая любой элемент гаммы...
     
  3. BaGiE

    BaGiE New Member

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

    flankerx New Member

    Публикаций:
    0
    Регистрация:
    2 июл 2004
    Сообщения:
    423
    Адрес:
    Moscow, Russia
    Младшие байты наверняка можно вычислить математически, но это даже не принципиально: определили старший, а оставшиеся можно перебором. Всего 16 млн. вариантов.

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

    BaGiE New Member

    Публикаций:
    0
    Регистрация:
    27 мар 2005
    Сообщения:
    84
    Адрес:
    Mordor
    Так то да :) Т.е. 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)

    хз понятно ли написал :) вообще нуб нубом :)
     
  6. flankerx

    flankerx New Member

    Публикаций:
    0
    Регистрация:
    2 июл 2004
    Сообщения:
    423
    Адрес:
    Moscow, Russia
    Т.е. есть четыре одинаковых регистра сдвига, которые различаются только начальными заполнениями. Очередной байт гаммы — это сумма по модулю 2 старших байтов этих регистров. Так?

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

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

    BaGiE New Member

    Публикаций:
    0
    Регистрация:
    27 мар 2005
    Сообщения:
    84
    Адрес:
    Mordor
    Блин а тут то я ступил =) Получается так =)))
     
  8. ntldr

    ntldr New Member

    Публикаций:
    0
    Регистрация:
    20 ноя 2007
    Сообщения:
    125
    Используй в качестве ГПСЧ любую нелинейную функцию основаную на сети Файстеля. Ну а стойкий алгоритм или нет - будет ясно после нескольких лет активного его использования всем миром :) Правда для начала стоит привести математическое обоснование стокости против всех известных на данный момент универсальных атак.
     
  9. BaGiE

    BaGiE New Member

    Публикаций:
    0
    Регистрация:
    27 мар 2005
    Сообщения:
    84
    Адрес:
    Mordor
    Ну это мне не надо ;)

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

    ntldr New Member

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

    flankerx New Member

    Публикаций:
    0
    Регистрация:
    2 июл 2004
    Сообщения:
    423
    Адрес:
    Moscow, Russia
    Ну, обычно до того как начинать "активное использование" адгоритм лет несколько мучает упомянутое криптографическое сообщество. Так что шансы что с алгоритмом что-то сильно не так значительно уменьшаются.

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

    BaGiE New Member

    Публикаций:
    0
    Регистрация:
    27 мар 2005
    Сообщения:
    84
    Адрес:
    Mordor
    Да я для себя делаю и мне пофиг и доказывать никому не нужно ничего =) Пропустил через DIEHARD выходную последовательность, но как интерпретировать результаты?
     
  13. UbIvItS

    UbIvItS Well-Known Member

    Публикаций:
    0
    Регистрация:
    5 янв 2007
    Сообщения:
    6.077
    flankerx
    критерии надёжности и скорости со временем не меняются :derisive:.
     
  14. flankerx

    flankerx New Member

    Публикаций:
    0
    Регистрация:
    2 июл 2004
    Сообщения:
    423
    Адрес:
    Moscow, Russia
    Если бы они не менялись, люди до сих пор использовали бы шифр Цезаря...

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

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

    ntldr New Member

    Публикаций:
    0
    Регистрация:
    20 ноя 2007
    Сообщения:
    125
    Во многих тестах p-valie порядка 0.9, в некоторых 0.03. Короче тест провален, случайные данные должны давать значения близкие к 0.5
     
  16. BaGiE

    BaGiE New Member

    Публикаций:
    0
    Регистрация:
    27 мар 2005
    Сообщения:
    84
    Адрес:
    Mordor
    ntldr
    Ясно, фтопку :) жесть. тогда может посоветуете алгос, чтоб был потоковый, криптостойкий, очень простой в реализации (типа RC4), но (!) без использования всяких S-BOX и всякой хрени (TEAN как то обходится без всего этого, но опять блочный :dntknw: )
     
  17. ntldr

    ntldr New Member

    Публикаций:
    0
    Регистрация:
    20 ноя 2007
    Сообщения:
    125
    Юзайте любой блочный алго в режиме CFB. Подойдет тот же XTEA.
     
  18. flankerx

    flankerx New Member

    Публикаций:
    0
    Регистрация:
    2 июл 2004
    Сообщения:
    423
    Адрес:
    Moscow, Russia
    Или OFB или CTR

    :derisive:
     
  19. UbIvItS

    UbIvItS Well-Known Member

    Публикаций:
    0
    Регистрация:
    5 янв 2007
    Сообщения:
    6.077
    flankerx
    да, ладно про Цезаря рассказывать - это по сути начало самой криптографии тогда-то и критериев не было. другой вопрос в том, что могут появляться новые мат. методы взлома, но это так редко бывает:).
     
  20. BaGiE

    BaGiE New Member

    Публикаций:
    0
    Регистрация:
    27 мар 2005
    Сообщения:
    84
    Адрес:
    Mordor
    [deleted]

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