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

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

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

Понимание машины

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

Под этим простым интерфейсом скрывается продуманная электромеханическая схема с тремя основными компонентами — распределительным щитом с десятью симметричными переключателями замены ключей (например, L на K и K на L), тремя роторами, которые можно выбрать из 5–8 возможных роторов, и наконец, отражатель. Каждый ротор имеет «начальную» конфигурацию, которая определяет начальное положение. Как только вы нажмете букву, роторы будут вращаться, и сигнал пройдет через 1) коммутатор, который может изменить букву на другую; 2) три ротора, каждый из которых будет менять букву; 3) отражатель, который предсказуемо изменит букву и, наконец, 4) снова коммутатор, который может еще раз изменить выходную букву на другую.

Подход грубой силы

Исходная настройка, которую в современных терминах можно назвать ключом шифрования, состоит из 3 роторов, которые нужно использовать из 5–8 доступных, начальная позиция каждого ротора между 1–26 и десятью парами букв. заменил на распределительном щите. Выбор 3 из 5 — это всего лишь 60 различных возможностей. Двадцать шесть возможных исходных позиций на них составляют 17 576 возможностей. Пока это около миллиона различных настроек, что по современным меркам вполне управляемо. Коммутатор позволяет нам симметрично заменить десять букв десятью другими буквами, оставив шесть нетронутыми. Это дает нам около 150 триллионов возможных конфигураций (см. это видео для математики). Таким образом, общее количество ключей, которые нужно попробовать, примерно в миллион раз больше!

Продолжая наши теоретические расчеты, наши современные процессоры могут легко выполнять около 3 миллиардов простых операций с одним ядром в секунду. Допустим, требуется около 100 таких операций, чтобы попытаться декодировать простое сообщение с заданной настройкой. Таким образом, одно ядро ​​может попробовать 30 миллионов конфигураций в секунду. Итак, чтобы попробовать все возможности, нам потребуется 150 триллионов, деленных на 30, что составляет 5 триллионов секунд: около 160 000 лет! Не то, чтобы это имело большое значение, но ключ шифрования меняется каждые 24 часа, так что грубая форсировка была невозможна тогда и невозможна сегодня! Кроме того, если вам повезло и вы наткнулись на правильную конфигурацию, вам понадобится механизм, который без вмешательства человека идентифицирует ответ как правильный. Для этого существуют эвристики, но они потребуют больше циклов ЦП и добавят несколько нулей к годам, необходимым для расшифровки этого методом грубой силы.

Как они это делают?

Если вы похожи на меня, вы, вероятно, думаете, что создание машины для медленного вычисления комбинаций мало поможет решить эту проблему. Именно здесь вы осознаете огромную ценность времени, потраченного на то, чтобы по-настоящему разобраться в своей проблеме. Союзные войска захватили несколько машин Enigma во время войны, что дало им полный доступ к их испытаниям. Они поняли, что одним интересным побочным эффектом схемы было то, что она никогда не шифровала заданную букву для себя. Это может показаться не таким уж большим, но оно открывает множество возможностей для атак с известным зашифрованным текстом, что означает возможность угадать ключ шифрования на основе просмотра некоторых примеров известного текста, зашифрованного с использованием этого ключа. В реальном мире это не так сложно представить. Вы ожидаете «доброе утро» в начале многих утренних сообщений или текста «отчет о погоде» в ежедневном утреннем отчете о погоде. Алан Тьюринг и его команда использовали эту известную уязвимость в зашифрованном тексте, чтобы построить машину Bombe для взлома кода.

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

Почему персонаж не мог зашифровать сам себя?

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

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

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

Взлом кода

Для этого раздела нам нужно иметь возможность использовать машину-загадку. Если у вас нет доступа к реальному, лучше всего использовать симулятор. Я написал один на Python, и он доступен на GitHub. Код должен быть в значительной степени не требующим пояснений и содержать комментарии в тех местах, где он немного отличается от описания в этом посте. Существует файл Readme.md для инструкций по локальному запуску через командную строку.

Чтобы взломать код, используя известный зашифрованный текст, мы должны вывести тело следующей функции:

def predict_enigma_config(ciphertext, plaintext)
    -> List[RotorConfig, PlugboardConfig]:

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

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

Открытый текст: HELLOWORLD
Зашифрованный текст: OJWAHLFOZN

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

Также обратите внимание, что с той же начальной настройкой вы можете выполнять симметричные операции между обычным и зашифрованным текстом, что дает нам больше данных для работы. Например, при начальной настройке вы можете получить O из H и H из O. После одного вращения вы можете получить J из E и E из J и т. д.

Имея это в виду, давайте начнем с L, так как она встречается в нашем тексте четыре раза. При третьем вращении L становится W. Предположим, что L подключен к B на коммутационной панели. Когда вы посылаете B через ротор с этой настройкой, скажем, мы получаем X. Итак, теперь мы знаем LB и XW как настройки коммутационной панели, соответствующие нашему первоначальному предположению. Тогда мы знаем, что L становится A при четвертом вращении. Скажем, B через роторы дает Y, поэтому мы получаем YA. Затем мы знаем, что L становится W на 6-м вращении. Скажем, теперь B дает A, поэтому новое правило — AW. Напомним, наши правила: LB, XW, YA и AW. Это плохо, потому что последнее правило AW физически не имеет силы, так как разъемы для A и W уже заняты. Поэтому нам нужно отбросить наше первоначальное предположение о LB.

Это все еще слишком медленно, так как мы делаем предположения, выполняем некоторые вычисления, чтобы опровергнуть их, и делаем новые предположения. Нам потребуется еще много времени, прежде чем мы придем к догадке, которая сработает. Теперь пришло время представить умную оптимизацию. При заданной настройке роторов, когда мы угадали LB, мы получили X через роторы для входа B. Однако теперь мы знаем, что B был неправильным входом для передачи. Это означает, что реальный вход может быть любым от A до Z, кроме B (включая L, если он не подключен к коммутационной панели). Мы также знаем, что роторы могут быть сведены к отображению 1:1 от буквы к букве, где никакие две буквы не могут быть сопоставлены с одной и той же буквой, основываясь на нашем предыдущем обсуждении. Таким образом, X не может быть правильным ответом вне роторов, когда вы нажимаете A. В результате мы также можем отбросить XB, YA и AW как неправильные настройки коммутационной платы, поскольку они возникли из неправильного базового предположения, и это невозможно. начать с другого предположения и прийти к тому же выводу, пока мы все еще с той же настройкой ротора.

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

Есть частичное решение?

Прежде чем мы начнем, давайте поймем, почему я говорю, что частичное решение напечатает достаточно узнаваемый текст для носителя языка. Скажем, мы нашли правильную конфигурацию ротора — что мы и сделаем, потому что попробуем их все. Вывод по-прежнему будет мусором, если мы не установим правильно какие-либо контакты коммутационной панели. Когда мы правильно поставим одну булавку, некоторые буквы будут расположены правильно, но этого может быть недостаточно. Если мы поместим 3–4 правильных вывода, включая несколько часто встречающихся букв (помните, что мы отдаем им приоритет в нашем алгоритме), текст может выглядеть как естественный язык с некоторыми ошибками. Мы можем использовать это свойство вместе с эвристикой обнаружения естественного языка, такой как индекс совпадения (IoC), чтобы попытаться расшифровать код энигмы без какого-либо известного зашифрованного текста.

Заключение

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