Частично рассекречено методическое пособие АНБ по взлому неизвестных шифров18.06.2021 13:46

Скульптура Kryptos у штаб-квартиры ЦРУ

Агентство национальной безопасности США наконец-то рассекретило третью часть известного учебника «Военная криптоаналитика» (MILCRYP), написанного для обучения специалистов АНБ и военных криптоаналитиков во время Холодной войны. Последняя часть трёхтомника опубликована с некоторыми купюрами, но всё равно представляет огромную ценность, ведь у нас не так много практических пособий по взлому шифров. Речь идёт о неизвестных, сложных кодах, которые составлены по непонятным правилам. Как к ним подступиться? Как найти зацепки? Книга отвечает на эти вопросы.

Возможно, учебник АНБ поможет расшифровать тексты, которые в течение многих десятилетий и столетий не поддаются криптоанализу. И даже тысячелетий, как в случае с критской письменностью из III тысячелетия до нашей эры (минойская цивилизация).
Автор учебника — военный криптолог Ламброс Каллимахос (Lambros Callimahos), ассистент и давний помощник Уильяма Фридмана, «отца американской криптологии», автора трёх учебников по военной криптографии и разработчика девяти шифровальных машин, три из которых запатентованы, а шесть остаются засекреченными по сей день. Именно группа Фридмана взломала японский код Purple в начале Второй мировой войны.

Трёхтомник вышел в октябре 1977 года.

Трилогия «Военная криптоаналитика» объясняет, как взламывать все типы кодов, включая военные коды и головоломки, которые создаются исключительно в соревновательных целях. Это методическое пособие по классической криптографии, которая оперирует с буквами и цифрами. В отличие от современной (компьютерной) криптографии, которая манипулирует с битами, хотя иногда данные области пересекаются.

Первые две части в открытом доступе с 80-х:

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

Однако в 1992 году Министерство юстиции США заявило, что публикация третьей книги может нанести ущерб национальной безопасности, раскрыв «методы АНБ по взлому шифров». С того же года началась борьба криптографического сообщества за раскрытие информации. Властям был направлен ряд запросов по Закону о свободе информации. В конце концов, в декабре 2020 года книгу всё-таки опубликовали.

По мнению специалистов, ключевой в книге Каллимахоса является глава под названием «Принципы криптодиагностики» (Principles of Cryptodiagnosis), в которой описывается систематический трёхэтапный подход к расшифровке сообщения, закодированного неизвестным методом. С содержанием этой главы можно ознакомиться на страницах 323−414 в опубликованном pdf.

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

Как подробно описывает Каллимахос в этой главе, следует начать со сбора всех необходимых данных. Это данные трёх типов:

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

В «спортивных» головоломках часть открытого текста может быть передана в помощь разгадывающему. В случае с секретными военными сообщениями разгадывающий может подозревать, что в шифротексте зашифрованы определённые слова, основываясь на прошлых знаниях. Например, могут быть такие ключевые термины, как [НАЧАЛО], [КОНЕЦ] или конкретные имена, места, адреса.

Примеры индикаторов

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

Например, изучим такой лог шифровок:

Поскольку $A1$ — очевидный дискриминант, индикатор может находиться в позиции $A2$ . А если для шифрования индикатора используется текстовая группа, то мы можем выявить важную закономерность, если попробуем сложение разных групп возле начала или конца. Иногда требуется вычитание всех пар групп $A1-A5$ и $Z4-Z0$ цифра за цифрой (любопытно, что в этом месте две страницы учебника остались засекречены: вероятно, там упоминались какие-то нестандартные техники). В нашем случае вычитаем все пять цифр числа $A3$ последовательно из цифр числа $A2$ :

6−8=8
7−2=5
4−1=3
7−4=3
0−8=2

Таким образом, $67470−82148=85332$ .

Вот общий результат:

А это уже упорядоченная последовательность. Видно, что сложение первых двух разрядов даёт третий: $8+5=(1)3$

,

и так далее, то есть это последовательность в возрастающем порядке. Более того, если вычесть $2$

из колонки $GR$

(количество текстовых блоков в каждом сообщении), то из двух последних разрядов мы получим непрерывный след в координатном пространстве 10×10:

Первая координата $3−2$ соообщения с $62−2=60$ текстовыми группами даёт нам число $32+60=92$ . Это координата начала следующего сообщения с отметки $9−2$ . В том сообщении $81−2=79$ текстовых групп, что переносит нас в точку $92+79=(1)71$ . И так далее.

В следующем примере зашифрованные индикаторы в группе $A2$ вскрываются, если из них вычесть значения $Z1$ .

1−8=3
4−3=1
5−1=4
7−6=1
1−5=6

Теория подтверждается путём аналогичного вычитания значений $Z0$ из цифр в колонке $А2$ , что даёт аналогичные расшифрованные индикаторы:

Как несложно было заметить, разница между значениями $А2$ и $А3$ такая же, как между $Z1$ и $Z0$ . Это дополнительно указывает на то, что их следует использовать попарно.

Когда мы расшифровали индикаторы, наступает третий этап — попытка понять и объяснить эти характеристики.

Три названных шага — пример байесовского вывода. Это «статистический вывод, в котором свидетельство и/или наблюдение используются, чтобы обновить или вновь вывести вероятность того, что гипотеза может быть верной; название байесовский происходит от частого использования в процессе вывода теоремы Байеса, которая была выведена из работ преподобного Томаса Байеса».

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

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

Представьте, что вы создали головоломку, но спустя много лет никто так и не смог её разгадать. Это весьма печально. В таком случае автор начинает выпускать подсказки. Например, головоломка из книги «Маскарад» от 1979 года была решена только после публикации нескольких подсказок в 1980 году в газете Sunday Times.

Ответ к головоломке «Маскарад» спрятан в 15 иллюстрациях книги. На каждой картине нужно провести линию от левого глаза каждого изображённого существа через самую длинную цифру на левой руке и до одной из букв на границе страницы. Затем от левого глаза через самую длинную цифру на левой ноге; от правого глаза через самую длинную цифру на правой руке; и, наконец, от правого глаза через самую длинную цифру на правой ноге. Из букв, обозначенных этими линиями, можно составить слова, либо рассматривая их как анаграммы, либо применяя последовательность животных и цифр, предложенную на картине

Если никто не разгадал загадку даже после множества подсказок, значит код слишком сложен для взлома. Это означает, что в конечном итоге придётся раскрыть метод, который вы использовали. Одним из примеров является сложнейший шифр Chaocipher. В данном случае сообщения практически невозможно расшифровать, если не знать метод.

Истории известны примеры, как шифры всё-таки поддаются взлому после многолетних усилий. В прошлом году был разгадан знаменитый шифр Z340, который разработал серийный убийца Зодиак в 1969 году. Шифр взломала международная команда любителей-криптоаналитиков после 51 года напряжённой работы. В течение многих лет команда тщательно и систематически вела список наблюдений. В конце концов, это дало результат.

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

Другой пример — скульптура Kryptos у офиса ЦРУ, работа американского скульптора Джима Сэнборна. На ней несколько шифровок, которые тоже долгое время не поддавались взлому. Самая сложная из них — К4.

Шифротекст К4 остаётся неразгаданным около 30 лет. Вот он:

OBKRUOXOGHULBSOLIFBBWFLRVQQPRNGKSSOTWTQSJQSSEKZZWATJKLUDIAWINFBNYPVTTMZFPKWGDKZXTJCDIGKUHUAUEKCAR

Это действительно сложный шифр. Его составитель Эд Шейдт (Ed Scheidt), председатель Криптографического центра ЦРУ, оценивал сложность в 9 из 10 возможных баллов. Так было необходимо, чтобы шифр не разгадали быстро — всё-таки он ежедневно будет раздражать лучших аналитиков из ЦРУ по дороге в офис. По замыслу автора, шифр должен быть разгадан через пять, семь или, может быть, десять лет.

Однако Эд просчитался.

Последняя подсказка от Джима Сэнборна по секции K4, апрель 2020 года

Почему шифр K4 настолько трудный? Во-первых, фрагмент состоит всего из 97 символов, очень короткий, что означает меньшее количество данных и меньшее количество подсказок. Метод шифрования, использованный для его создания, неизвестен, и существует мало контекста того, как он мог быть зашифрован. Независимые криптографы на конференции DEFCON жаловались и на другие трудности: офис ЦРУ трудно найти (у него нет адреса), а на территорию не пускают посторонних лиц. Поэтому скульптуру трудно разглядеть в непосредственной близости.

В одной из классических книг Джорджа Пойи «Как решать задачу» (см. русский перевод (pdf) для учителей математики от 1959 года) предлагается общий принцип решения любой задачи — обратиться к аналогичной задаче, которая уже была решена. Этот принцип применим и в мире исторических головоломок.

Но Шейдт признался, что по мере работы над Kryptos менял методологию — специально, чтобы усложнить задачу.

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

В презентации АНБ от 2007 года упоминается, что «десятки» сотрудников агентства пытались разгадать шифровку K4. Всё безуспешно.

Впрочем, надежда не умирает. С каждым годом взламывается всё больше исторических текстов, которые считались абсолютно невозможными для расшифровки. И наши вычислительные возможности растут. Возможно, когда-нибудь шифровку К4 вскроет обычный взломщик-любитель, а вовсе не агент АНБ.

Неразгаданные шифры

Вот небольшая подборка письменностей, которые до сих пор не поддались расшифровке.
Работы хватит ещё на несколько поколений.

На правах рекламы

Закажите сервер и сразу начинайте работать! Создание VDS любой конфигурации в течение минуты. Эпичненько :)

Подписывайтесь на наш чат в Telegram.