немного о криптоанализе "для чайников"
Хотелось бы обсудить со знающими и просто интересующимися, как, собственно происходит криптоанализ, т.е. анализ криптоалгоритмов на стойкость и поиск слабых мест.
Если можно, информацию "для чайников".
Как я вообще это вижу:
Допустим, имеем криптоалгоритм. Из чего он состоит? Да состоит он из набора действий по шифрованию, дешифрованию, управлению ключами. Эти "действия" можно назвать суперпозицией математических теорем. В простейшем случае, каждую суперпозицию (теорему) можно оценить с т.з. вероятности уменьшения сложности взлома.
Возьмем гипотетический алгоритм симметричного шифрования. Он состоит из множества суперпозиций, каждая из которых обладает вероятностью ко взлому с помощью полного перебора, либо, в случае ассиметричных элементов алгоритма, существует вероятность ошибки в теореме.
Идем далее, суперпозиция, представленная в виде графа, может не только уменьшать вероятность успешной атаки, но и увеличивать ее. Если имеем дело с битами и масками, то следует учитывать взаимное влияние не только последовательных усложняющих воздействий, но и возможных параллельных упрощающих.
Кроме вероятностей, существует также набор т.н. "атакующих эвристик". Таким образом, при поиске уязвимостей в крипто-алгоритме следует произвести поиск угроз среди данных эвристик, и оценить наихудшую вероятность успешной атаки. Следует также проанализировать алгоритм с т.з. наибольшего числа срезов эвристик на алгоритм.
Подытоживая все вышесказанное, можно придти к выводу о возможности не только ручного криптоанализа, но и построение автоматизированных средств поиска уязвимостей в протоколах.
Хотелось бы получить немного информации об атакующих эвристиках, а также получить вердикт на мой ход мыслей.
комментариев: 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" – без заголовков и служебных полей, нагенерить чистых шифртекстов всеми мысленными способами и провести все тесты.
комментариев: 155 документов: 20 редакций: 5
Как я себе представляю, статистические закономерности всегда можно найти, при условии что энтропия псевдослучайных функций является составной, и завязана на предопределенные векторы инициализации (или как оно там по научному называется). Тут тонкий момент, очевидно понятный и вам, что поиск статистики в составных раундах зависит от мощности поля инициализации. (Древнее правило "разделяй и властвуй"). Вопрос в том, как происходит запутывание раундов, чтобы псевдослучайные функции складывались не параллельно а последовательно. Это как я себе сейчас представляю блочные шифры. Но вернемся к межблочным связям. Во-первых, есть такой параллельный момент, как постоянность векторов инициализации раунд-функций, независимо от режима сцепления блоков. Во-вторых, при любом режиме сцепления блоков, а не раунд-функций имеем постепенное выраждение инициализационного поля, а следовательно и энтропии. Тут можно подумать над задачкой поиска вырождающегося фактора.
комментариев: 9796 документов: 488 редакций: 5664
комментариев: 9796 документов: 488 редакций: 5664
А может уже P=NP ? :-)
А насколько mcrypt считается эталонным/протестированным? Полагаю, у него репутация всяко не выше хотя бы той же gpg, нет?
комментариев: 9796 документов: 488 редакций: 5664
Достоверно известно только, что это "трудная задача", принадлежность которой к классу NP-полных недоказана. Ну как-то мирятся с этим тридцать лет уже.
И опять же в рамках доказуемой безопасности он используется только в протоколе передачи случайного симметричного сеансового ключа, поэтому то, что им зашифруют один блок вообще роли не играет.
комментариев: 9796 документов: 488 редакций: 5664
К сожалению не в абсолютном, а в условно-практическом, конвенциональном.
Чтобы не разводить бесконечной риторики на основе сомнений в основах крипто на сайте есть статья Коблитца. При всех такого рода вопросах отсылаю к ней.
У Коблитца есть и ещё более глубокие статьи на эту тему, но их пришлось бы набирать в LaTeX'e, так как там обзоры и заключения привязаны к конкретной математике. Такое читать только если в оригинале.