id: Гость   вход   регистрация
текущее время 15:28 29/03/2024
создать
просмотр
ссылки

немного о криптоанализе "для чайников"


Хотелось бы обсудить со знающими и просто интересующимися, как, собственно происходит криптоанализ, т.е. анализ криптоалгоритмов на стойкость и поиск слабых мест.


Если можно, информацию "для чайников".


Как я вообще это вижу:


Допустим, имеем криптоалгоритм. Из чего он состоит? Да состоит он из набора действий по шифрованию, дешифрованию, управлению ключами. Эти "действия" можно назвать суперпозицией математических теорем. В простейшем случае, каждую суперпозицию (теорему) можно оценить с т.з. вероятности уменьшения сложности взлома.


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


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


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


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


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


 
На страницу: 1, 2 След.
Комментарии
— Гость (17/11/2008 21:45)   <#>
Подождём, пока unknown прочитает топик :)
— unknown (17/11/2008 22:13, исправлен 17/11/2008 22:17)   профиль/связь   <#>
комментариев: 9796   документов: 488   редакций: 5664
Очень похожая идея (правда по объединению нескольких видов криптоанализа в один) только в виде построения коммутативных даиаграмм была рассмотрена в работе Дэвида Вагнера, но широкого распространения не получила.

fileпрезентация

fileработа

На практике автоматизированные методы успешно были применены только в рамках алгебраического криптоанализа.

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

На практике выходит, что самый громкий взлом доказывается или чисто аналитически буквально на бумаге или в последнее время развитием алгебраизации и оптимизацией вычислительных методов.
— SATtva (19/11/2008 18:58)   профиль/связь   <#>
комментариев: 11558   документов: 1036   редакций: 4118
Тема называется "немного о криптоанализе для чайников", да?
— Мухтар (19/11/2008 19:53, исправлен 19/11/2008 19:53)   профиль/связь   <#>
комментариев: 155   документов: 20   редакций: 5
Да, а что Вас беспокоит? Я в последний момент написания текста решил переименовать тему.
— Гость (21/11/2008 16:10)   <#>
Мухтар, а если не секрет, какое у вас образование?
— Мухтар (21/11/2008 18:33)   профиль/связь   <#>
комментариев: 155   документов: 20   редакций: 5
Системотехника
— rtf (25/11/2008 04:16)   <#>
Есть область криптоанализа называемая логическим криптоанализом. Алгоритм представляется как КНФ и задача поиска ключа сводится к поиску выполнимого набора КНФ, т.е. ключ представляет собой часть набора. Идея принадлежит Куку. Эвристики в этом случае некие процедуры бэктрекинга.
— Мухтар (25/11/2008 14:36)   профиль/связь   <#>
комментариев: 155   документов: 20   редакций: 5
rtf:
Примерно понятно. Забудьте о декларируемом ключе как о цели.

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

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

Как писал Циммерманн: ни один современный кифер не заботится об энтропии исходных данных. Это фундаментальная криптография.
— unknown (26/11/2008 12:35, исправлен 26/11/2008 13:14)   профиль/связь   <#>
комментариев: 9796   документов: 488   редакций: 5664
Если количество тестов, позволяющих найти любой различитель (distinguisher attacks), а даже не ключ, между шифром и идеальной моделью меньше, чем необходимо на подбор ключа, то он считается взломанным, даже если до практического криптоанализа очень далеко.

Моделью идеального блочного шифра считается PRP – таблица псевдослучайных перестановок. Если размер ключа 2128, а размер блока 264, то можно представить гипотетический гигантский массив неповторяющихся соответсвий {0,1}64 -> {0,1}64, как будто его выбрали случайно и записали. Вот от такого массива и не должен быть отличим шифр. При новом ключе получим абсолютно новое псевдослучайное заполнение таблицы и так для каждого из 2128 ключей будет своя таблица, не имеющая никакой связи с предыдущей (иначе были бы возможны атаки со связанными ключами).

Ограниченый размер блока минимум 64, 128 и размер ключа минимум 128 бит здесь роли не играют, если псевдослучайность заполнения таблицы эмулируется достаточно полно. Вот за полноту такой эмуляции и идёт битва дизайнеров шифров. Автоматизировать этот процесс сложно. Часто прогоняют на автомате какие блоки на конкретные виды криптоанализа, чтобы выбрать лучшую конструкцию, но не весь шифр целиком.

Не знаю, что имел ввиду Циммерман. Принято считать, что шифр должен быть одинаково стоек, шифруют ли им тексты, файлы из одних нулей, подобранные противником тексты, тексты несколько раз прогоняемые в разных направлениях (бумеранг атаки – зашифровали – поменяли параметры – опять расшифровали – дали противнику всё подсмотреть) и т.д., т.е. чтобы и какими изощрёнными способами не подавали на вход и на выход никакого различителя быть не должно иначе шифр считается нестойким.
— Гость (26/11/2008 17:06)   <#>
Мухтару -

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

Вот сюда -

http://ru.intel.com/business/c.....=abouthpc&portalid=4

я послал вот это -

aristillus.narod.ru/faivol.pdf

PS Естественно, что я послал не все, чтобы так сказать не возбуждать умы.
— Мухтар (26/11/2008 18:28)   профиль/связь   <#>
комментариев: 155   документов: 20   редакций: 5
Uknown:
Вы говорите об одном блоке, я вас правильно понял? Вслучае же шифрования массива блоков, имеем дело с механизмом ротации межблочных ключей, искажения исходного текста, и воздействий на основе данных предыдущих итераций. В этом случае, думаю, все обстоит гораздо сложней, т.е. хуже для авторов крипто. С одной стороны, если данные очередного блока различаются хотя бы на бит (например, вмешался генератор случайных чисел), то получим новое значение шифро-блока, практически не коррелируемое с предыдущим. Тем не менее, теоретически, зная длину блока, и при достаточном числе блоков, можем анализировать межблочную корреляцию. Я бы назвал ее корреляцией второго уровня.

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

Это все теория, и я немного подустал пинать мозги в непонятном направлении и защищать начало этой темы.
— Мухтар (26/11/2008 18:32)   профиль/связь   <#>
комментариев: 155   документов: 20   редакций: 5
Гость:
Очень интересный пдф, может быть я что-то из него для себя подчерпну.
— SATtva (26/11/2008 21:37)   профиль/связь   <#>
комментариев: 11558   документов: 1036   редакций: 4118
Режимы шифрования, отличные от ECB, и предназначены для смешения блоков.
— unknown (27/11/2008 10:54)   профиль/связь   <#>
комментариев: 9796   документов: 488   редакций: 5664

Вслучае же шифрования массива блоков, имеем дело с механизмом ротации межблочных ключей


Вот как раз такие экзотические режимы шифрования (rekeying modes) и были отвергнуты по причине того, что на каждый новый блок невыгодно разворачивать новый ключ и массив раундовых подключей (скорость медленная), и по причине того, что многие шифры исследованы на атаки со связанными ключами недостаточно полно. В обычным режимах зависимого шифрования многих блоков (CBC, OFB) никакой ротации межблочных ключей нет.


искажения исходного текста, и воздействий на основе данных предыдущих итераций.


Всё это укладывается в стандартную модель provable security. Сначала конструируется блочный шифр, близкий к идеальной модели, затем доказывается, что любое использование этого шифра (атомарного криптопримитива) не даёт построить при использовании его в данном режиме шифрования или протоколе различитель, способный различить его выход от случайного оракула или чего-нибудь подобного.

Для такой простейшей задачи, как анализ режимов шифрования всё уже изучено. Да, методологию provable security справедливо критикуют за её упрощенчество, редукционистский характер, как раз она возможно не учитывает "тонких корреляций" да ещё и второго уровня.
Но как правило, "доказуемая безопасность" на практике настолько сильная модель, что копать глубже не всегда стараются.

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

Конечно можно намеренно создать слабый режим или протокол шифрования из стойкого шифра, но он не выдержит проверки по модели "доказуемой безопасности". Можно найти т.н. "тривиальный различитель" – например выйти за заранее известные ограничения по количеству блоков, допускаемых к шифрованию одним ключом из "парадокса дней рождения".


Тем не менее, теоретически, зная длину блока, и при достаточном числе блоков, можем анализировать межблочную корреляцию. Я бы назвал ее корреляцией второго уровня.

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


В стойких криптосистемах работы потребуется ещё больше, чем на традиционные методы криптоанализа.
Единственно что, при изобретении новых видов криптоанализа теоретически может сложиться ситуация, когда вы окажетесь правы. Например, при правильном применении считалось, что режим CTR не уступает в стойкости режиму CBC при использовании идеального шифра в модели доказуемой безопасности. А когда Шамир изобрёл недавно кубическую атаку, то уязвимые шифры показали себя хуже в режиме CTR.

Обычно ответ тут один: нужно сосредоточиться на создании исходно стойкого шифра, а не пытаться компенсировать его неидеальность подбором режима шифрования. Если он стоек и близок к идеальной модели в обычных видах криптоанализа, то и в "корреляциях второго уровня" аналитику ничего не светит.
— Мухтар (27/11/2008 14:07)   профиль/связь   <#>
комментариев: 155   документов: 20   редакций: 5
способный различить его выход от случайного оракула или чего-нибудь подобного.

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

Сложно что-то противопоставить. Я лишь хотел заметить что практические программки из интернета, очевидно основанные на рекомендуемых исходных листингах очень легко подвержены анализу с помощью сжатия. Это практика. Может быть, имеет место какие-то непонятные мне человеческие артефакты, что в общем-то логично.

А насчет моего первого абзаца и модели доказуемой безопасности хочу лишь добавить, что вслучае 1% несоответствия одного блока этой модели, имеем лавинообразное ухудшение стойкости вслучае достаточно длинных потоков. Вы упомянули Шамира и кубическую атаку. Вот это хорошо вписывается в реальные расхождения с моделью идеально доказуемой безопасноти. И при большом числе блоков расхождения с идеально доказуемой безопаснотью еще больше, и соответсвтенно больше вариантов анализа, как с помощью метода Шамира, так и с помощью любых других способов, с верными логическими заключениями.

Напоследок хочу добавить, что в мире крипто есть множество старых как мир логических утверждений, гармонично вписывающихся в модель доказуемой безопасноти. Так вот, как мне кажется, эти логические условия не соблюдаются на практике, и желаемое выдается за действительное. Я имею в виду свой опыт по анализу сжатием.
На страницу: 1, 2 След.
Ваша оценка документа [показать результаты]
-3-2-1 0+1+2+3