id: Гость   вход   регистрация
текущее время 20:27 28/03/2024
Автор темы: Гость, тема открыта 23/12/2014 00:28 Печать
Категории: криптография, алгоритмы
создать
просмотр
ссылки

Crypto How stuff Works


Бывает ли книга по криптографии, где бы детально обсуждались и сравнивались различные примитивы и конструкции низкого уровня; возможно безотносительно к реализациям конкретных шифров на их основе. Интересно посмотреть, почему cделали так, а не иначе, что и насколько сильнее/слабее, быстрее/медленнее и пр.


 
На страницу: 1, 2, 3 След.
Комментарии
— unknown (23/12/2014 09:39)   профиль/связь   <#>
комментариев: 9796   документов: 488   редакций: 5664

Монографий нет. Даже публикации от разработчиков достаточно урезанные. Изредка что-то подобное рассматривается в диссертациях, но и то, выбирается какое-то узкотематическое направление в разработке и в нём рассматривается несколько конструкций.
— Гость (23/12/2014 12:24)   <#>
Никому не интересно или "широкой публике знать не положено"?
— unknown (23/12/2014 12:56, исправлен 23/12/2014 12:57)   профиль/связь   <#>
комментариев: 9796   документов: 488   редакций: 5664

«Узкой» публике неинтересно доносить это для «широкой». На таком фундаментальном уровне — публикации только по узкоспецифическим вопросам. Вероятно, негласно считается, что для понимания этого нужно знать столько теории, столько перечитать частных случаев криптоанализа, что узкоспецифичные публикации будут ясны сами по себе, а монографии и сравнительные обзоры не нужны.

— ZAS (23/12/2014 21:03)   <#>
Складывается впечатление, что решения, применяемые разработчиками, довольно произвольны и в большинстве слабо обоснованы. Относится и к принятым стандартам, и к признанным мастерам жанра. Прослеживается желание преодолеть конкретные уязвимости, а дальше говорится фраза вроде "мы проверили случай x = 1,2,3,4,5 и предполагаем что данное соотношение работает до x = 1e9..."
— unknown (24/12/2014 10:00, исправлен 24/12/2014 16:55)   профиль/связь   <#>
комментариев: 9796   документов: 488   редакций: 5664

Есть такое. Неполнота теории, погоня за передовыми наработками.


Но всё ещё сложнее в плане тенденций и накопления знаний. Например, после Twofish и Rijndael началось повальное увлечение MDS-матрицами в шифрах и хэшах. Вышло масса исследований по критериям проектирования этих матриц. По этим критериям их и сравнивали. Затем придумали другие классы матриц. Затем стали изобретать компактные и итеративные матрицы, опять ещё больше новых классов. Всё больше углубления в детали, но всё меньше исследователей понимают всю тему в целом и не могут толком сравнить MDS-матрицы если те принадлежат к совершенно разным классам. А ведь линейные преобразования можно делать и не на MDS-матрицах, даже сейчас есть вполне современные алгоритмы и без них. Есть специалист, который может убедительно сравнить MDS и ARX-смешивание (Addition, Rotation, XOR)? Неизвестно, и специалистов с таким охватом нет, и область неисследована.


С S-блоками также: в девяностые была мода на S-блоки на бент-функциях (CAST). Замечательно через них всё расписывали и доказывали. Затем от этого дизайна отказались. Тренд больше стал на алгебраические S-блоки. Но где подробное доказательство, что они лучше в пересчёте стойкости на производительность по сравнению с предыдущими конструкциями?
Возможно, где-то в кулуарах и частных переписках между собой посовещались и решили, что новое направление перспективнее. Но ведь были раньше и до сих пор активно разрабатываются и шифры/хэши вообще без S-блоков, где нелинейный слой задаётся по другому. Кто-то привёл общее доказательство, что лучше: слабая нелинейная функция на весь блок или сильные, но маленькие S-блоки, ведь последующий линейный слой размажет и размешает результат нелинейного в обоих случаях? А сколько вообще неисследованных вопросов в межраундовых взаимодействиях, ключевом расписании и пр., к которым толком и не подступались.


P.S.: вспомнил коммент spinore про квантмех:


Есть такие вещи, которые выполняют только специально обученные люди, которые уже угрохали кучу лет в то, чтобы разобраться с темой. Квантмех, как и какая-нибудь биология или медицина — не те области, куда можно легко въехать, скондачка. Несмотря на кажущуюся простоту самых основ, под ними зарыто большое число очень непростых фактов, которые людям в теме хорошо известны и уже обыденны, а только пришедшему в тему их никто не расскажет. Даже если самому изучать всё по книжкам, нет толковых книжек, которые были бы достаточны. Разные аспекты и темы неплохо освящены в некоторых книгах, но нет такой одной книги, где был бы полностью представлен современный своего рода «теоретический минимум».

И про исследователей:

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

А вы "How stuff works" хотели… Когда тематика устоится и устареет, может тогда будет какая-то запоздалая популяризация фундаментальных основ.

— ZAS (24/12/2014 20:50)   <#>
Вышло масса исследований по критериям проектирования этих матриц. По этим критериям их и сравнивали. Затем придумали другие классы матриц. Затем стали изобретать компактные и итеративные матрицы, опять ещё больше новых классов. Всё больше углубления в детали, но всё меньше исследователей понимают всю тему в целом и не могут толком сравнить MDS-матрицы если те принадлежат к совершенно разным классам. А ведь линейные преобразования можно делать и не на MDS-матрицах, даже сейчас есть вполне современные алгоритмы и без них. Есть специалист, который может убедительно сравнить MDS и ARX-смешивание (Addition, Rotation, XOR)?


Недавно пыталися уяснить это для себя. Как мат. прикидками, так и радиолюбительскими методами.
Возьмем за основу S-box от AES. Вопрос: как, используя этот S-box как строительный блок, сделать S-box большего размера с ассимптотически правильной диф. характеристикой?
Простейший и самый неэффективный вариант – слои с циклическим сдвигом на пол-блока. Требуется >4 раундов.а
Немногим эффективнее слои с какими-то P-box между ними.
Более эффективный вариант – FN (или UFN). >3 раундов. Просто, но нераспараллелить, потому медленно.
Еще более эффективный вариант – смешивание полиномом. >2 раундов. Причем, полином совcем не обязан быть MDS, что подтверждается опытом. (критерий оптимизации суммы активных S-box до и после – странное требование).
При ARX смешивании можно нарваться на неожиданные проблемы типа разность здесь компенсируется разностью там, и это может проходить из раунда в раунд. SHA-2 дизайн – пример оптимизации против таких эффектов.

А вы "How stuff works" хотели… Когда тематика устоится и устареет, может тогда будет какая-то запоздалая популяризация фундаментальных основ.


C публикации DES прошло больше 40 лет. В общем кажется понятным как сделать сильный перестраховочный шифр или хеш-функцию, но получается в несколько раз медленнее, чем лучшие варианты.
— unknown (24/12/2014 21:54, исправлен 24/12/2014 22:00)   профиль/связь   <#>
комментариев: 9796   документов: 488   редакций: 5664

См. Anubis и Twofish. Только у таких составных S-блоков сразу вылезают неприятные характеристики.



Бывают конструкции и без MDS (в том же Twofish?), но не просто так все на нём зациклились. Там взяты основы из теории кодирования и есть какой-то переход на branch-number и ещё какие-то критерии.



Я вот какое-то время назад решил поиграть в любительство с randomness-экстракторами. Шнайер и Кравчик писали, что можно использовать обычные хэши. Перечитал кучу работ, думаю, а я чем хуже? Очень радовался своей первой конструкции, так ловко там перестраховался. Затем нашёл несколько протечек — противник может различать одинаковые малые блоки в начале массива сырой энтропии. А затем и вовсе на пальцах сам себе доказал, что в лучшем случае стойкость экстрактора такой конструкции будет равна размеру выхода хэша. Т.е. он всего-лишь вычислительно стойкий, а не информационно-теоретический. Стоило всё это городить, чтобы получить такой жалкий результат!


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


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


Также как с MDS-матрицами, когда посмотрел отсылки к теории кодирования, а там кучи томов и публикаций, опять понял, что это не осилить. Потрындеть на общем уровне можно, но чего-то создавать не для целей профессиональной публикации смысла нет, особенно граничащее с фундаменталкой. Если поймать специалиста в коридоре и заставить его смыслить свои самопальные опусы, то скорее всего он поднимет насмех эти потуги. Ну это моя личная позиция, я её придерживаюсь и отстаиваю, но не навязываю. Можете дальше изобретать конечно, в качестве криптолюбительства, разминки для мозгов, интеллектуальных головоломок…

— Гость (24/12/2014 22:08)   <#>
А в прикладной области криптолюбительство тоже смерти подобно, или имеет право на существование?

Доспутим, если попытаться изобрести свой протокол передачи чего-либо, всю криптографию отдав GPG. Литературу на какую тему вообще стоит читать, если интересны сериализованные структуры данных и сетевые протоколы?
— unknown (24/12/2014 22:45, исправлен 24/12/2014 22:51)   профиль/связь   <#>
комментариев: 9796   документов: 488   редакций: 5664

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


Когда начинаешь думать о «криптоперестраховках», то начинаешь рыть теорию и понимаешь, как мало на самом деле понимаешь. Вылезают целые неисследованные области, пласты для возможных открытий, на которые можно потратить кучу усилий и годы работы без гарантии успеха. Чтобы это всё осилить, нужно становиться чистым теоретиком, которому все эти ваши перестраховки неинтересны. А если не осилить теорию, то не можешь реально делать перестраховки. Потому перестраховочная криптография и непопулярна. Те, кто её могут, она им ненужна и неинтересна — слишком много интересной теории вылезает на таком уровне.



Я дошёл до границ своей (не)компетентости в этой теме. А ведь так легко сначала всё казалось. Даже горячие головы убеждали, что надо только взяться, работ мало потому, что тему мало кто исследует. Оказывается, работ полно и исследований тоже, а за десятилетия результата нет. Потому что тема плохо формализуется на уровне теоретических определений отрицаемости. Толку в практике без хорошей теории.



Вот теория, ориентированная на практическое конструирование протоколов, Introduction to Modern Cryptography, Lecture Notes on Cryptography, есть ещё видео на курсере, похожие лекции от других авторов. Это студентам на один семестр. Я если и осилил, то на троечку. Подглядывая туда, я могу разбирать доказательства (даже находил ошибки у самих уважаемых авторов), но самостоятельно доказать стойкость протокола — нет. А если не можете доказать стойкость любого прикладного протокола по Беллейру-Рогвею, то считайте, что вы в криптографии дуб-дубом (вот как я ;) — ваше место только бумажки в какой-нибудь редколлегии перекладывать, да на форумах трындеть.


Конечно, не боги горшки обжигают, но в любом случае — или этому надо посвящать свою профессиональную карьеру, или никак.

— ZAS (24/12/2014 22:53)   <#>
>как строительный блок, сделать S-box большего размера с ассимптотически правильной диф. характеристикой?

См. Anubis и Twofish. Только у таких составных S-блоков сразу вылезают неприятные характеристики.


О том и речь. Пытался обьединить так, чтобы получить правильную дифф. характеристику.

>Причем, полином совcем не обязан быть MDS, что подтверждается опытом.
Бывают конструкции и без MDS (в том же Twofish?), но не просто так все на нём зациклились. Там взяты основы из теории кодирования и есть какой-то переход на branch-number и ещё какие-то критерии.


Требование MDS вытекает из максимизации суммы branch number до и после. Это как 2+2=4. Но насколько я читал умных книжек и пытался думать и разбираться, мне не очевидно почему сумма branch number является адекватным критерием качества перестановки. Произвольно выбрали какой-то критерий и по нему оптимизировали.

Шнайер и Кравчик писали, что можно использовать обычные хэши.


Скажу вам по секрету, что если читать внимательно, то видно что Шнаер заядлый шифропанк; и Бернштейн тоже :)

Не могу говорить за всех, но на своём опыте могу сказать, что лезть в фундаментальные вещи — это не любительство и не попытка разобраться,


Не боги горшки обжигают. Таки единственный способ разобраться в теме – заниматься темой. Хотя бы на любительском уровне. Непродуманное использование готовых чужих блоков – верный способ наступить на грабли; примеров масса.
— unknown (24/12/2014 23:06, исправлен 24/12/2014 23:20)   профиль/связь   <#>
комментариев: 9796   документов: 488   редакций: 5664

Так бы и линейный слой вообще не был нужен. Да вообще, насостовляли бы из маленьких таблиц один большой S-блок с входом-выходом в 128-бит, вот вам и идеальный шифр! А по сути — блочный шфир с множеством раундов — это ведь попытка эмуляции этого самого и есть.



Про него я в курсе, также как и то, что как теоретик он — нулевой. Практик, организатор, интуиция у него хорошая, но не более. Про подозрения о более существенном вкладе соавторов в его работы я ранее где-то упоминал. К тому же в крипто он фактически давно уже не у дел. Прославился популяризаторской книжкой в девяностые и удачным продвижением пары тройки своих с соавторами идей.



А ведь и правда :)



Я успел придти к такому же выводу в итоге :)



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

— ZAS (25/12/2014 04:30)   <#>
>О том и речь. Пытался обьединить так, чтобы получить правильную дифф. характеристику.

Так бы и линейный слой вообще не был нужен. Да вообще, насостовляли бы из маленьких таблиц один большой S-блок с входом-выходом в 128-бит, вот вам и идеальный шифр! А по сути — блочный шфир с множеством раундов — это ведь попытка эмуляции этого самого и есть.


Как правильно составить большой S-блок из многих маленьких является одной из вечных задач криптографии :)

Было бы удобно иметь универсальный блочный примитив на все случаи, позволяющий работать с блоками произвольного размера. Пусть неэффективный, но простой. С безопасностью не менее 128 бит.

Мне нравится ARX-примитив из трех строчек:

S(x)
{
x = (x << a) +/- x;
x = (x >> b) ^ x;
x = cyclic_shift(x, c);
}

a,b,c – константы (возможно, зависящие от раунда), key – раундовый ключ.

Примитив является биекцией. Хотя обратную функцию напрямую вычислять неудобно, проще завернуть примитив в сеть Файстеля.

L = L + S(R^key[i]);
R = R + S(L^key[i+1]);


Получается конструкция с оптимальным чередованием сдвигов, арифметики и логических операций. Конструкция более несимметричная чем используемые в threefish и пр.; то есть функции для соседних битов существенно отличаются; чтобы осложнить rotational cryptoanalysis.
Можно сделать примитив для слов произвольной ширины, с применением широкой арифметики. Оно обеспечивает диффузию за логарифмическое количество раундов. Выбор констант a,b,c важен; возможны хорошие и плохие варианты. Детерминированной процедуры выбора констант не придумал; нашел варианты для 32- и 64- бит слов перебором.

Теперь, имея примитив из 6-раундов Файстеля (L+R = 128 бит), обеспечивающий хорошую диффузию, применим его к блоку данных произвольной ширины. Простейшее решение – циклический сдвиг данных на одно слово в каждом раунде. Но это линейная диффузия, нужно раундов на порядок больше чем размер блока в словах.

Придумать хорошую схему перемешивания для произвольного размера блока оказалось нетривиальной задачей.
Можно сделать как многоуровневую сеть Файстеля, можно как интерливер слов через пол-блока, можно через какой-то произвольный полином. Тут пока нет идей.

http://www.zas-comm.ru
— unknown (25/12/2014 09:41)   профиль/связь   <#>
комментариев: 9796   документов: 488   редакций: 5664

Есть тривиальная по конструкции схема симметричного шифрования на квазигруппах, в том числе и блочного, там нет ни линейного слоя, ни S-блоков в чистом виде для нелинейного, только сцепление квазигрупп определённым способом, используя свойства некоммутативных операций.

Развивают это некие болгары, идея известна десятки лет. Вроде и не совсем маргинальщина, но не взлетает. Там возникает масса вопросов по теории алгебраических операций. Да и когда начинают реализовывать, получаются опять же громоздкие конструкции, с теми же сетями Файстеля, да ещё и менее стойкие в итоге.
— Гость (25/12/2014 17:28)   <#>

Особенно хорошо, если эта задача точно такая же, как создание вечного двигателя. Не бывает идеальных блочных шифров (доказывается строго) идеальных S-блоков, и чем больше S-блок, тем очевидней это вылазит, наверно.
— unknown (25/12/2014 17:50)   профиль/связь   <#>
комментариев: 9796   документов: 488   редакций: 5664

Наоборот. Если он задан истинно случайной большой таблицей, то он идеален как одноразовый блокнот идеальный блочный шифр. Случано сгенерированная таблица размером 2128 • 2128 = 2256 — это IBC, он же большой S-блок. И вообще, чем больше таблица, тем она лучше. А вот всякие трюки с заданием функций алгебраически и созданием больших таблиц из маленьких — это такая тонкая оптимизация эмуляции вечного двигателя.
На страницу: 1, 2, 3 След.
Ваша оценка документа [показать результаты]
-3-2-1 0+1+2+3