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

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

Следует сказать, что под термином «криптоанализ» также подразумевают попытку найти уязвимость в криптографическом алгоритме или протоколе.

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

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

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

Итак, к основным методам криптоанализа относятся:

Классический криптоанализ, который подразделяется на:

• Частотный анализ выявляет частоту появления отдельных символов и их сочетаний. Любителям детективов Артура Конана Дойля, наверняка, знаком этот метод по рассказу «Пляшущие человечки». Было выявлено, что вероятность появления отдельных букв, а также их порядок в словах и фразах языка подчинено статистическим закономерностям. К примеру, сочетание букв «ся» в русском языке более частотно нежели «цы», а «оь» вообще никогда не встречается. Таким образом, проанализировав объемный текст, зашифрованный методом замены, можно по частотам появления тех или других символов восстановить открытый текст. Сегодня метод частотного анализа широко применяется в программах по подбору паролей и позволяют значительно сократить время поиска.
• Метод Касиски заключается в поиске групп символов, повторяющихся в зашифрованном тексте. Группы состоят как минимум из трех символов, а расстояние между ними кратно длине ключевого слова. Длинна слова соответствует наибольшему общему делителю всех расстояний.
• Метод индексных совпадений
• Метод взаимных индексных совпадений

Линейный криптоанализ

Линейный криптоанализ представляет собой другой тип криптоаналитического вскрытия, изобретенный Мицуру Мацуи (Mitsuru Matsui) [1016, 1015, 1017]. Это вскрытие использует линейные приближения для описания работы блочного шифра (в данном случае DES.)

Это означает, что если вы выполните операцию XOR над некоторыми битами открытого текста, затем над некоторыми битами шифротекста, а затем над результатами, вы получите бит, который представляет собой XOR некоторых битов ключа. Это называется линейным приближением, которое может быть верным с некоторой вероятностью p. Если p ? 1/2, то это смещение можно использовать. Используйте собранные открытые тексты и связанные шифротексты для предположения о значениях битов ключа. Чем больше у вас данных, тем вернее предположение. Чем больше смещение, тем быстрее вскрытие увенчается успехом.

Как определить хорошее линейное приближение для DES? Найдите хорошие одноэтапные линейные приближения и объедините их. (Начальная и заключительная перестановки снова игнорируются, так как они не влияют на вскрытие.) Взгляните на S-блоки. У них 6 входных битов и 4 выходных. Входные биты можно объединить с помощью операции XOR 63 способами (2⁶ — 1), а выходные биты — 15 способами. Теперь для каждого S-блока можно оценить вероятность того, что для случайно выбранного входа входная комбинация XOR равна некоторой выходной комбинации XOR. Если существует комбинация с достаточно большим смещением, то линейный криптоанализ может сработать.

Если линейные приближения не смещены, то они будут выполняться для 32 из 64 возможных входов. Я избавлю вас от длительного изучения таблиц, наиболее смещенным S-блоком является пятый S-блок. Действительно, для 12 входов второй входной бит равен XOR всех четырех выходных битов. Это соответствует вероятности 3/16 или смещению 5/16, что является самым большим смещением для всех S-блоков. (Шамир писал об этом в [1423], но не смог найти способа использовать.)

На Рис. 12-8 показано, как воспользоваться этим для вскрытия функции этапа DES.

Криптоанализ

b26 — это входной бит S-блока 5. (Я нумерую биты слева направо от 1 до 64. Мацуи игнорирует это принятое для DES соглашение и нумерует свои биты справа налево и от 0 до 63. Этого хватит, чтобы свести вас с ума.) c₁₇, c₁₈, c₁₉, c₂₀ — это 4 выходных бита S-блока 5. Мы можем проследить b₂₆ в обратном направлении от входа в S-блок. Для получения b₂₆ бит объединяется с помощью XOR с битом подключа K_i,26. А бит X₁₇ проходит через подстановку с расширением, чтобы превратиться в a₂₆. После S-блока 4 выходных бита проходят через P-блок, превращаясь в четыре выходных бита функции этапа: Y₃, Y₈, Y₁₄ и Y₂₅. Это означает, что с вероятностью 1/2 — 5/6:

X₁₇ A Y₃ A Y₈ A Y₁₄ A Y₂₅ = K_i,26

Рис. 12-8. 1-этапное линейное приближение для DES.

Способ, которым можно объединить линейные приближения для различных этапов, похож на тот, который обсуждался для дифференциального криптоанализа. На Рис. 12-9 показано 3-этапное линейное приближение с вероятностью 1/2+0.0061. Качество отдельных приближений различно: последнее очень хорошо, первое достаточно хорошо, а среднее — плохо. Но вместе эти три 1-этапных приближения дают очень хорошее трехэтапное приближение.

Рис. 12-9. 3-этапное линейное приближение DES.

Базовое вскрытие должно использовать наилучшее линейное приближение для 16-этапного DES. Для него требуется 2⁴⁷ известных открытых блоков, а результатом вскрытия является 1 бит ключа. Это не очень полезно. Если вы поменяете местами открытый текст и шифротекст и используете дешифрирование вместе с шифрованием, вы сможете получить 2 бита. Это все еще не очень полезно.

Существует ряд тонкостей. Используйте 14-этапное линейное приближение для этапов с 2 по 15. Попробуем угадать 6 битов подключа для S-блока 5 первого и последнего этапов (всего, таким образом, 12 битов ключа). Для эффективности выполняем линейный криптоанализ параллельно 2¹² раз и выбираем правильный вариант, основываясь на вероятностях. Это раскрывает 12 битов и b₂₆, а поменяв местами открытый текст и шифротекст мы получим еще 13 битов. Для получения оставшихся 30 битов используйте исчерпывающий поиск. Существуют и друге приемы, но описанный является основным.

При вскрытии таким образом полного 16 этапного DES ключ будет раскрыт в среднем с помощью 2⁴³ известных открытых текстов. Программная реализации этого вскрытия, работая на 12 рабочих станциях HP9735, раскрыла ключ DES за 50 дней [1019]. В момент написания этой книги это наиболее эффективный способ вскрытия DES.

Линейный криптоанализ сильно зависит от структуры S-блоков, оказалось, что S-блоки DES не оптимизированы против такого способа вскрытия. Действительно, смещение в S-блоках, выбранных для DES, находится между 9 и 16 процентами, что не обеспечивает надежной защиты против линейного криптоанализа [1018]. Согласно Дону Копперсмиту [373, 374] устойчивость к линейному криптоанализу «не входило в число критериев проектирования DES». Либо разработчикам не было известно о линейном криптоанализе, либо при проектировании они отдали преимущество устойчивости против известного им еще более мощного средства вскрытия.

Линейный криптоанализ новее, чем дифференциальный, и в ближайшее время возможно дальнейшее продвижение в этом направлении. Некоторые идеи выдвинуты в [1270, 811], но не ясно, можно ли их эффективно применить против полного DES. Однако они очень хорошо работают против вариантов с уменьшенным числом этапов.

Что такое криптоанализ

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

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

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

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

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

Методы криптоанализа

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

Атаки на блочные шифры

Метод дифференциального криптоанализа впервые был применен для атаки на блочный шифр FEAL-4 [169]. Впоследствии метод был усовершенствован и успешно применен для криптоанализа DES [170,258-260). Метод дифференциального криптоанализа позволил по­лучить ответ на вопрос о числе циклов криптографического преобразования стандарта DES. Этот ответ важен с точки зрения разработки эффективных методов криптоанализа произ­вольных итерированных блочных шифров конструкции Фейстеля. Вопрос формулировался следующим образом: почему число циклов преобразования равно шестнадцати, не больше и не меньше? Известно, что после пяти циклов каждый бит шифротекста является функци­ей всех битов открытого текста и ключа [196,261]. После восьми циклов наблюдается пик лавинного эффекта — шифротекст представляет собой случайную функцию всех битов от­крытого текста и ключа [262]. Успешные атаки на DES с тремя, четырьмя и шестью циклами подтвердили результаты исследований лавинного эффекта [263]. На первый взгляд, крипто­графическое преобразование с большим числом циклов (> 8) представляется необоснованным с точки зрения эффективности реализации. Однако успешный дифференциальный крипто­анализ DES доказал: трудоемкость (объем перебора) атаки на открытом тексте для DES с любым количеством циклов, меньшим шестнадцати, ниже, чем трудоемкость силовой ата­ки. При этом необходимо отметить, что вероятность успеха при силовой атаке выше, чем при атаке методом дифференциального криптоанализа. Тот факт, что метод дифференци­ального криптоанализа был известен в момент разработки DES, но засекречен по очевидным соображениям, подтвержден публичными заявлениями самих разработчиков [264,265].

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

Исходя из различий в получившихся шифротекстах ключам присваиваются различные вероятности. Истинный ключ определяется в процессе дальнейшего анализа пар шифротекстов — это наиболее вероятный ключ среди множества претендентов. Для пояснения рассмо­трим один цикл криптографического преобразования DES (рис. 11.22).

Рисунок 11.22 – Один цикл DES-преобразования для двух входных блоков X и X¢

Пусть задана пара входов, X и X¢, с несходством DХ.. Вы­ходы, Y и Y¢, — известны, сле­довательно, известно и несход­ство DY. Известны перестанов­ка с расширением Е и Р-блок, следовательно, известны DА и DС. Значения на выходе сум­матора по модулю 2 не извест­ны, однако их несходство DВ известно и равно DА. Доказано, что для любого заданного DА не все значения DС равноверо­ятны. Комбинация DА и DС позволяет предположить значе­ния битов для Е(Х) Å К_i, и Е(Х‘) Å К_i . To, что Е(X) и Е(Х‘) известны, дает нам ин­формацию о К_i .

На каждом цикле в преобразовании участвует 48-битный подключ исходного 56-битного секретного ключа. Таким образом, раскрытие К₁₆ позволяет восстановить 48 бит ключа. Остальные восемь можно восстановить при помощи силовой атаки.

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

Криптоанализ

Таблицу можно построить для каждого из восьми S-блоков DES.

Различные несходства на отдельных циклах можно объединять. Кроме того, при условии, что циклы независимы, вероятности могут перемножаться.

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

Таблица 11.18. Дифференциальный криптоанализ: результаты атаки на DES

В табл. 11.18 приводится обзор наилучших результатов успешного дифференциальною криптоанализа DES с различным количеством циклов [260]. Первый столбец содержит ко­личество циклов. Два следующих столбца содержат нижнюю оценку числа выборочных или заданных (известных) открытых текстов, необходимых для осуществления атаки. Четвер­тый столбец содержит количество действительно проанализированных открытых текстов. В последнем столбце приведена оценка трудоемкости атаки после обнаружения требуемой пары.

Наилучший известный результат успешного дифференциального криптоанализа DES с шестнадцатью циклами требует 247 выборочных открытых текстов. Можно воспользоваться атакой на известном открытом тексте, но для этого потребуется уже 255 известных образцов. Трудоемкость атаки — 237 DES-шифрований. Дифференциальный криптоанализ эффекти­вен против DES и аналогичных алгоритмов с постоянными S-блоками. Трудоемкость атаки зависит от структуры S-блоков. Для всех режимов шифрования ЕСВ, СВС, CFB и OFB атака имеет одинаковую трудоемкость [260]. Криптостойкость DES может быть повышена путем увеличения числа циклов. Трудоемкость дифференциального криптоанализа DES с семнадцатью или восемнадцатью циклами эквивалентна трудоемкости силовой атаки. При девятнадцати и более циклах дифференциальный криптоанализ невозможен в принципе — для его реализации потребуется более 264 выборочных открытых текстов (DES оперирует блоками по 64 бита, следовательно, существует 2 различных открытых текстов). В общем случае доказательство криптостойкости по отношению к атаке методом дифференциальною криптоанализа заключается в оценке числа открытых текстов, необходимых для выполнения атаки. Атака невозможна, если полученная оценка превышает 2^b, где b — разрядность блока в битах.