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

Я, в целом, согласен с Noble Ghost'ом. Ruptor — весьма авторитетный персонаж в области криптографии и математики, и не раз доказывал свой высочайший уровень.

Но в последнее время просматривается грустная тенденция — много громких заявлений и ноль реальных выкладок. На все вопросы — отсыл к дефектоскопу. Сказать "Я умею ломать TEA с любым кол-вом раундов, но мне некогда рассказать вам как именно" — это самый верный способ дискредитировать себя, особенно на ВАСМе . Поэтому реакция MSoft, ftre, CreatorCray, иdrmist вполне предсказуема.

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

 

Цифровая криптология - это не физика и не химия и даже не математика. Тут тысячелетних наработок нет. Она существует с 1975 года с появления DES. До этого всё было засекречено и NIST вынуждены были два раза подавать запрос на DES стандарт. На их первый запрос не было подано ни одного алгоритма!! К чему я это? А к тому, что криптографии никто не знает вообще.

Так что, MSoft, sorry, но гуру в криптографии нет в принципе, есть только толпа новичков, которые делятса на три группы:

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

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

3. Крипто-мафия. Те, кто в криптологии тоже ничего не знают, но при этом считают себя крупными специалистами - это в основном академики, подавляющее их большинство. Ездят по конференциям, смотрят кто чем занимается, ломают друг другу шифры либо прямым обманом (не важно что атака требует 2^253 памяти и 2^247 процессоров или 2^247 времени - им наплевать на правду, главное что очередной 256-битовый шифр можно оклеймить как *сломанный*, хотя 2^128 параллельных крохотных бруте-форсеров сломали бы его за 2^128 времени - этим занимается в основном группа евреев в лице Ора Данкельмана, Эли Бихама и их друзей, под всеобщие аплодисменты с открытыми ртами), либо старыми, хорошо изученными открытыми группой №2 методами типа линейного и дифференциального криптанализа, стараясь либо украсть новые результаты группы №2, либо задавить их авторитетом... Но каждые несколько лет кто-то из группы №2 всё-таки умудряется протиснуться с новой атакой, которая всем доказывает что все эти мафиози на самом деле и себя и других всё это время обманывали. Хотя их это ни капельки не смущает. Они адаптируются к новой атаке и продолжают пускать народу пыль в глаза.

К группе №2 относится например один из моих друзей, всем известный Никола Куртуа - "прародитель" алгебраических атак. Ему даже как известному академику очень трудно публиковать свои работы из-за гигантского сопротивления мафии, хотя его результаты очень конкретные. А большинство тех кто к ней относится - это "quiet achievers", которые просто тихонько делают своё дело, в основном в спец-службах. Им новые результаты гораздо важнее, чем всеобщее признание.

Моё же любимое направление в криптологии - это найти методы создания реальных шифров, про которые можно бы было и на практике и по теории доказать что они не ломаются, никакими атаками в принципе. Это очень не просто, но это реально. Надо только сперва вылезти за пределы линейного и дифференциального криптанализа. Луби & Ракофф ещё в 1988 году опубликовали первую фундаментальную теоретическую работу на эту тему (им два года потребовалось - они ещё в 1986 году подавали, но их бумагу мафия не пустила), а теперь Жак Патаран это проталкивает дальше, хотя и с не меньшим трудом. Я попросил его опубликовать доказательство для более практического варианта, где p кругов, которые меняют какую-то часть из w битов от всего блока на каждом круге, ещё отличается от случайного в полиномиальное время, а p+1 кругов - уже нет. Если будет такое доказательство, то сложив его с такими тестами как мои, можно доказывать безопасность или небезопасность почти любого шифра и ломать его этими же инструментами, только слегка расширенными. Но эту идею как и любую новую идею в криптологии очень трудно протолкнуть.

Я давно отошёл от темы взлома шифров ради их взлома. Кому нужны тысячи сломанных шифров? Людям нужны неломаемые, хотя бы один. В этом мнении я к сожалению почти одинок. В криптологии сейчас почти весь фокус на взлом - на создании чего-то имени себе не сделаешь, только опозориться рискуешь если сломают. Вот я и решил взяться за это трудное и рискованное дело и если кто-то хочет доказать мне что я не прав, сломайте EnRUPT и я буду продолжать учиться.

Если тут кто-то понимает что такое ANF, то вы спокойно можете воспроизвести все мои результаты если вам не лень. И не надо бросатьса помидорами. Это очень просто. Прочитайте эту и эту бумаги и всё должно стать совершенно ясно. Время - деньги, а мне публикация денег не сделает, и так только море времени отнимает без толку. Так что если вы не понимаете что там тестируется и как, тогда просто плюньте на мой web site и не ходите даже туда. Я никого не заставляю ценить мою работу. Сомневайтесь на здоровье.

А если кто-то хочет меня проверить на вшивость, то ради бога! Именно этот метод я и предлагаю на defectoscopy.com как самый честный - пошлите мне ваш заведомо слабый или слишком твёрдый шифр без указания сколько ему нужно кругов для криптостойкости, какой-то шифр который вы сами можете как-то по-хитрому сломать. Я вам отвечу какое минимальное количество кругов ему необходимо и к каким атакам он будет уязвим, хотя в принципе мне и так это приходится делать периодически, но не публично. Блочный, поточный, хаш - всё равно. И мне не понадобятся для этого многие месяцы. Я могу найти все дырки за пару часов или максимум за пару дней если исходник будет слишком сложный. Есть желающие проверить мои методы всем на убеждение? Или я только flamers и троллей разбудил случайно? Я не хотел.

PS: По просьбам общественности переведено на кириллицу.

 

Hochu napomnit osobo aggressivnim trollam, chto topic etogo thread - "kak protestirovat crypto-algoritm", a ne "kak slomat TEA". Na Wikipedia napisano kak lomat TEA.

 

Ruptor
Просьба: Я все понимаю, но читать в транслите несколько напряжно, поэтому просьба попробовать использовать транслитераторы. К примеру этот: http://www.translit.ru Текст получается несколько корявый, но все равно читать проще.

 

-

 

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

 

Фигасебе. Тогда не буду юзать TEA =), но у XTEA стойкость упадет если я вместо 32 использую 16 раундов? Просто скорость шифра тоже важна. И еще подожду EnRupt =) Ах да, поскольку сам господин Ruptor заинтересовался моей скромной затеей, то позволю себе спросить кое что Вообще подобный "шифр", что я хотел поначалу поюзать (первые посты) - имеет смысл, если в качестве датчика ГПСЧ поюзать этот же Xorshift или другой хороший генератор с большим периодом последовательности? Чисто ради интереса. Я нуб =)

Вот еще что бы хотелось раз и навсегда прояснить, а то везде по разному пишут.

TEA - был самый первый из этой серии (как я уже понял его фтопку)
XTEA (он же TEAN?) - вроде получше =) (выражаясь языком нубов)
Block TEA - что за шифр?
XXTEA (модификация Block TEA?) - аналогично с Block TEA

Какой из серии *TEA* наиболее актуален? Есть доки от создателя (Дэвид Вагнер кажется) с схемами алгосов, но я нихрена в них не понимаю =) Точнее на асм переведу, но что из этого "ЧАЯ" лучше хз =)

 

Используйте Rinjdael и будьте спокойны. Если интересно могу дать две свои реализации, одна оптимизирована на скорость, вторая на размер.
Если EnRupt будет принят и проанализирован сообществом, то лет через 5 можно будет начать его использовать. Раньше я бы опасался, ввиду того что сильно много сломано шифров авторы которых (причем имеющие авторитет) заявляли об их крутости и неломаемости.

P.S. это мое личное консервативное мнение, и попрошу не начинать на меня наезжать.

 

XTEA - это исправленный TEA. В нем дырок нет никаких.

Block TEA - это была их первая детская попытка расширить его до блоков любого размера. Пользоваться им нельзя. Они не подумали что расшифровка при соединении текущего слова только с "предыдущим" не имеет никакой криптостойкости. Мои тесты это моментально выявляют. Saarinen это дело сломал сразу же.

Они его исправили - прибавили "следующее" слово и получился XXTEA. В нем тоже дыр нет кроме одного маленького недостатка - для блоков большого размера (которые только 6 полными циклами шифруются) можно найти частичные коллизии за 2^32 операций у кого есть 2^32 процессоров и 2^32 разделенной между ними памяти. Пока трудно сказать что это дает нападающему. Скорее всего ничего. Хотя есть очень маленький шанс, что такая частичная коллизия поможет как-то ускорить слом, возможно какую-то хитрую алгебраическую атаку. Каждый полный цикл вокруг блока добавляет только 2^16 к стойкости от этой атаки, не зависимо от качества самой функции. Это моя собственная атака, хотя это трудно назвать атакой. Она только находит два частично совпадающих зашифрованных блока.

Вообще, я хочу кое-что прояснить. Академики довели народ до паранойи, требуя защиты от любых атак - пассивных, активных и вообще адаптирующихся, в любых условиях... Это в принципе не обязательно если условия среды не позволяют эту атаку провести.

Я же могу рекомендовать это семейство с таким минимальным количеством кругов для защиты от определенных атак:

1. На входе данные, которых нападающий не знает и контролировать не может, IV тоже, знает только что они не случайные. Надо только защитить выход чтобы он выглядел случайно и ключ из него нельзя было восстановить:

TEA - 20 кругов
XTEA - 18 кругов
XXTEA - 4*xw+12 кругов [xw - это количество 32-битовых слов в блоке]

2. Для защиты от активных атак (например линейный и дифференциальный криптанализ) где атакующий может предоставить заранее подготовленный выбранный им набор данных, а потом будет долго и пристально его изучать, но контроля над ключом через IV не имеет и не может подбирать вход в зависимости от выхода:

TEA - 30 кругов
XTEA - 27 кругов
XXTEA - 6*xw+18 кругов [столько же, сколько и TEA для 64-бит блоков]

3. Для защиты от адаптирующихся атак, но где атакующий опять же не может никак повлиять на ключ и не знает о нем ничего:

TEA - 40 кругов
XTEA - 36 кругов
XXTEA - 8*xw+24 кругов

4. Для использования как хаш или где атакующий может влиять на ключ через IV или через протокол обмена ключами, то-есть в самых жестких условиях:

TEA - ломается сколько его ни крути
XTEA - 76 кругов
XXTEA - 8*xw+68 кругов [да, XXTEA слегка слабее чем XTEA когда битами ключа можно манипулировать], а для полной защиты от частичных коллизий в безразмерно больших блоках (xw>16) - не меньше 16*xw кругов.

Это цифры для теоретической криптостойкости. На практике немного меньшее количество кругов выживет. Выбирайте сами. TEA конечно из них самый простой, XXTEA - самый сложный. Я картинки всех троих добавил в доку по EnRUPT чтобы люди могли сравнить и разобраться. Еще рекомендую сдвиги в них поменять с 4-5 на 6-8. Тогда они немного крепче и надо немного меньше кругов - 1) на 2, 2) на 3, 3) на 4 и 4) на 4 круга меньше для каждой из этих 4 групп. Тогда я бы наверное спокойно спал с 18 кругами TEA для минимальной защиты, хотя у меня теперь есть EnRUPT, который гораздо проще и гораздо быстрее и дырок TEA в нем нет. Ему то для этого уровня защиты 16 кругов точно хватит.

А насчет AES... Я не один кто считает что Rijndael надо 20 кругов для криптостойкости. Некоторые из верхушки криптаналитиков со мной в точности с этим согласны. Но опубликованных рабочих атак пока нет, поэтому я предпочитаю об этом молчать и просто рекомендую Twofish.

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

PS: Приведенное количество кругов - это значит отдельных кругов, не полных циклов. Так в TEA и XTEA обычно 64 круга.

 

ntldr чего на тебя наезжать? Ты совершенно прав. Хотя в индустрии и в академическом мире принят срок в 4 года - если за 4 года хорошо известный шифр не смогли сломать, то ему начинают доверять. Я и сам буду трястись первый год - мало ли... Все-таки паранойя, привык уже. Я же столько разных вариантов перебрал за последний год чуть ли не круглосуточно... и каждый раз в них новую дыру находил, либо для определенного размера, либо для какого-то из режимов работы. Вплоть до полного разочарования. А этот вот уже три месяца как ни смотрю, все в порядке. Если не сломают, то все, ухожу на пенсию программы писать полезные с тобой за одно.

 

Во - золотые слова! Подавляющее большинство тех, кто _применяет_ криптографию сами не могут оценить стойкость, и используют "что рекомендовано". И далеко не всегда способны правильно оценить реальные условия атаки. Да еще и предпочитают оптимизацию по скорости, так как она часто напрямую конвертируется в деньги. И в такой ситуации выбрать поменьше раундов - ну очень соблазнительно!

 

Насчет Twofish полностью согласен, потенциально он сильнее AES, но а AES есть очень сильное достоинство - распостраненность. А это значит что при появлении реальных атак на него у нас больше шансов об этом узнать.

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

 

Ruptor, а ГОСТ шифры, например 28147-89, вы из принципа не анализируете?

 

Насчет Twofish и я согласен - мое дилетантское IMHO что его можно пока что считать самым стойким шифром... И не выиграл он AES, как я читал, только потому, более труден в понимании (видимо им влом стало алгос полностью анализировать вот и выбрали Rijndael)

 

Есть такое слово "отмазки". Rijndael АНБ выбрали только потому, что сами его могут сломать, а больше никто не может. Twofish такой же по скорости как 10 кругов Rijndael, а по стойкости - как 20, и даже лучше него в чипах. Оба шифра одинаково сложные. Я поэтому и сделал EnRUPT, чтобы показать, что вовсе не надо усложнять шифр чтобы его исправить или укрепить или расширить его функциональные возможности. Всегда можно найти способ упростив при этом дизайн.

Если бы я был русским и жил в России, я бы наверное их в первую очередь проанализировал. А так как их нигде в природе вокруг меня нет, то я их и не трогал пока меня не попросили. У меня тут кроме основной работы уже большой список шифров на тестирование. Хотя могу протестировать его прямо сейчас пока выходные, в обмен на помощь - помогите мне найти французский патент 194х года, в котором описывается поточный шифр с группой 5-6 битовых счетчиков по модулю 5-6 битовых простых чисел, которые потом преобразуются через большой нелинейный diffusion layer похожий на 2-4 круга блочного шифра. Его легко отличить по набору маленьких простых чисел. Я его когда-то видел, но потерял документ, теперь не могу найти нигде.

 

Чёрт... грузовики книг по криптографии прочитал. А так ничего про неё и не знаю. Даже ни капельки))))

 

Странный какой-то критерий. Я думал по стойкости выбирают. Они не боятся что кто-нибудь ещё вдруг сможет? и все образно говоря окажутся в попе...

 

del

 

Вот такая эта тема криптология - кто кого лучше разведёт, а все последние достижения держатся в строжайшем секрете. Тот же MD5 ФСБ ещё в 1995 году могли подделывать дня за три на одном пентиуме-100, добавляя блок или заменяя блок, а SHA-1 от него не сильно отличается, но туда же - стандарт... Не удивлюсь если русские левши и AES ломать могут лучше американцев.

 

x3 = x0x1x2+x0x1+x2+x3+1;
x2 = x0x1+x2+1;
x1 = x0+x1;
x0 = x0+1;

Пойдёт? Или под C bitslice соптимизировать?

t = x0&x1;
x3 ^= ~(t|x2);
x2 ^= ~t;
x1 ^= x0;
x0 = ~x0;

Ra_ – Зачем это вообще нужно то? Издеваешься?