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

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


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


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


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


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


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


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


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


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


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


 
На страницу: 1, 2 След.
Комментарии
— unknown (27/11/2008 15:27)   профиль/связь   <#>
комментариев: 9796   документов: 488   редакций: 5664
При идеальном режиме шифрования блока (с помощью оракула или таблиц подстановки) имеем полностью некоррелируемый поток, при условии что исходные данные, разбитые на блоки, не повторяются.

Ну возьмём к примеру режим сцепления CBC.

Первый блок – случайный вектор инициализации.
Дальше: Ci = Ek (Pi xor Ci-1)

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

Тогда получим цепочку из Ci = Ek (Ci-1)

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

Оракул используется при пересчёте PRP/PRF (перестановок к псевдослучайным функциям) для упрощения доказательств.

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

В шифре RC4 и некоторых других действительно были открыты различители (даже при отбрасывании первых байтов). При многих гигабайтах потока он проваливает даже статистические тесты.

Но все современные блочные шифры тестировались через программы Diehard и NIST battery test во всех режимах и со всеми типами исходных текстов (включая "все нули") на многие гигибайты (может даже терабайты) данных. И уж там помимо теста на сжатие есть и более изощрённые тесты.

Если есть сомнения, то можно взять эталонную реализацию шифров из mcrypt в режиме "bare" – без заголовков и служебных полей, нагенерить чистых шифртекстов всеми мысленными способами и провести все тесты.
— Мухтар (27/11/2008 16:44)   профиль/связь   <#>
комментариев: 155   документов: 20   редакций: 5
При многих гигабайтах потока он проваливает даже статистические тесты.

Как я себе представляю, статистические закономерности всегда можно найти, при условии что энтропия псевдослучайных функций является составной, и завязана на предопределенные векторы инициализации (или как оно там по научному называется). Тут тонкий момент, очевидно понятный и вам, что поиск статистики в составных раундах зависит от мощности поля инициализации. (Древнее правило "разделяй и властвуй"). Вопрос в том, как происходит запутывание раундов, чтобы псевдослучайные функции складывались не параллельно а последовательно. Это как я себе сейчас представляю блочные шифры. Но вернемся к межблочным связям. Во-первых, есть такой параллельный момент, как постоянность векторов инициализации раунд-функций, независимо от режима сцепления блоков. Во-вторых, при любом режиме сцепления блоков, а не раунд-функций имеем постепенное выраждение инициализационного поля, а следовательно и энтропии. Тут можно подумать над задачкой поиска вырождающегося фактора.
— Гость (27/11/2008 17:21)   <#>
Уж не взялись ли вы полиномиально обратить произвольную полиномиальную фувнкцию? :-О
— unknown (27/11/2008 17:57)   профиль/связь   <#>
комментариев: 9796   документов: 488   редакций: 5664
Энтропия падает при многократном применении PRF (за счёт коллизий) и то ограниченно, но не PRP (блочных шифров) – всегда будет разный ответ из псевдослучайно переставленной таблицы соответствий открытый текст – шифртекст.
— unknown (27/11/2008 17:58)   профиль/связь   <#>
комментариев: 9796   документов: 488   редакций: 5664
Уж не взялись ли вы полиномиально обратить произвольную полиномиальную фувнкцию?

А может уже P=NP ? :-)
— rtfai (27/11/2008 18:06)   <#>
Шифры, шифры... А известно ли Вам, что вероятней всего RSA, дискретный логарифм и и дискретный логарифм на эллиптической кривой вскрываются полиномиально? Под рукой нет ссылки, но если это NPC задачи, то NP=co-NP. А RSA, это блочный шифр ECB.
— Гость (28/11/2008 01:30)   <#>
Если есть сомнения, то можно взять эталонную реализацию шифров из mcrypt в режиме "bare" – без заголовков и служебных полей, нагенерить чистых шифртекстов всеми мысленными способами и провести все тесты.

А насколько mcrypt считается эталонным/протестированным? Полагаю, у него репутация всяко не выше хотя бы той же gpg, нет?
— unknown (28/11/2008 09:10)   профиль/связь   <#>
комментариев: 9796   документов: 488   редакций: 5664
Строго говоря, mcrypt не считается. Эталонными считаются только коды присланные на конкурс NIST и утверждённые к финалу.

А известно ли Вам, что вероятней всего RSA, дискретный логарифм и и дискретный логарифм на эллиптической кривой вскрываются полиномиально?

Достоверно известно только, что это "трудная задача", принадлежность которой к классу NP-полных недоказана. Ну как-то мирятся с этим тридцать лет уже.

А RSA, это блочный шифр ECB.

И опять же в рамках доказуемой безопасности он используется только в протоколе передачи случайного симметричного сеансового ключа, поэтому то, что им зашифруют один блок вообще роли не играет.
— Гость (28/11/2008 10:19)   <#>
Достоверно известно только, что это "трудная задача"
В каком смысле "достоверно" и в каком смысле "трудная"?
— unknown (28/11/2008 11:49)   профиль/связь   <#>
комментариев: 9796   документов: 488   редакций: 5664
В каком смысле "достоверно" и в каком смысле "трудная"?

К сожалению не в абсолютном, а в условно-практическом, конвенциональном.

Чтобы не разводить бесконечной риторики на основе сомнений в основах крипто на сайте есть статья Коблитца. При всех такого рода вопросах отсылаю к ней.

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