Взлом шифра Enigma генетическими алгоритмами

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

Взлом шифра Enigma генетическими алгоритмами

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

N.B. Ну а кому лень читать даже этот лонгрид может вначале ознакомиться со статьей про современное положение дел с пресловутым ИИ. Или пролистнуть вниз, где будет ссылка на статью о применении ИИ в картографии - там много красивых картинок, можно и вовсе не читать.

Enigma - зашифрованная история

Enigma представляет веху в истории криптографии. Машина сочетает в себе роторную систему, изобретенную двумя голландскими военно-морскими офицерами в 1915 году, с коммутационной панелью. В результате получился настолько сложный шифр, что его считали неразрушимым. Мобильность и удобство использования Enigma позволили широко использовать ее немецкими военными во время Второй мировой войны. Значение в войне и криптоанализе сделало Enigma, пожалуй, самой известной криптографической машиной в истории. Ее слава также отражена в современных учебниках, например, в книге «Понимание криптографии», где Enigma используется для иллюстрации классической шифровальной машины. 

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

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

Чудо враждебной техники

Enigma - это портативная шифровальная машина, которая в основном использовалась для связи на поле боя и для защиты тактических соединений. Физически Enigma была встроена в деревянный или металлический ящик, состоящий из четырех основных компонентов.

Четыре основных компонента Enigma: четыре ротора, ламповая панель, клавиатура и коммутационная панель.

Роторы и коммутационная панель, показанные на рисунке, определяют состояние Enigma. Это состояние состоит из четырех частей: 

  • выбор и порядок ротора, 
  • настройки кольца, 
  • отображаемые значения, 
  • настройки коммутационной панели. 

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

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

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

На рисунке показано сканирование страницы в такой кодовой книге.

Здесь «Datum» дает фактическую дату использования этого ключа. Walzenlage дает выбор и порядок трех из пяти роторов (8 роторов для морской Enigma). Перед тем, как выбранные роторы были помещены в машину, для каждого ротора была установлена ​​регулировка колец, указанная как «Ringstellung». 

Следующая запись в кодовой книге - это настройка коммутационной панели, «Steckerbindungen», которая устанавливается путем добавления подключаемых соединений между двумя разными символами латинского алфавита. Обычно использовалось 10 штекеров, оставляя 6 символов без каких-либо соединений на коммутационной панели. Коммутационная панель с 0 подключенными штекерами означает, что каждая буква по умолчанию подключена сама к себе. Последняя перечисленная настройка - это «Grundstellung», которая примерно соответствует базовой настройке и дает ежедневное начальное отображаемое значение. Немцы всегда транслировали определенные изменения ежедневных настроек Enigma в начале сообщения. Возможно, наиболее известной является методика работы с двойным индикатором, используемая немцами до сентября 1938 года.

Первые 6 букв сообщения будут содержать настройку сообщения путем двойного шифрования нового отображаемого значения. Например, если параметр сообщения должен быть «RCM», тогда «RCMRCM» будет зашифрован из базовой настройки. Затем оператор изменит отображаемое значение на «RCM» и зашифрует остальную часть сообщения. Эта процедура была сделана, чтобы гарантировать, что разные сообщения были зашифрованы с разных начальных точек и, таким образом, защитили от хорошо известных атак на полиалфавитный шифр замещения. Обратите внимание, что в кодовой книге ключи перечислены в «противоположном» порядке: самая поздняя дата вверху, а более ранняя - внизу. В результате было легко удалить и безопасно уничтожить ключи от прошлых дат.

Электрическая муфта

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

Рисунок показывает упрощенную версию внутреннего устройства Enigma с коммутационной панелью, роторами, клавиатурой и ламповой панелью.

До того, как на клавиатуре будет нажата кнопка «A» (поз. 2), электрическая цепь отключится, и лампа не загорится. Затем при нажатии «A» цепь замыкается, и ток может проходить от батареи к коммутационной панели (3), входному кольцу (4), крайнему правому ротору (5), среднему ротору (5), крайнему левому (5), отражатель (6), снова крайний левый ротор (5), снова средний ротор (5), снова крайний правый ротор (5), снова соединительный щиток (7 и 8), пока, наконец, не достигнет лампового щитка (9).

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

Пример подключения Enigma:

  1. Имеем аккумулятор; он обеспечивает электричеством лампы.
  2. Показывает нажатую букву. В этом примере нажата клавиша «A», что позволяет току от батареи в 1 войти в цепь, как показано красными линиями.
  3. Поскольку буква A не привязана к какой-либо другой букве, сигнал / ток поступает на роторы.
  4. Ток поступает через позицию A во входном кольце.
  5. Ток скремблируется в роторах.
  6. Затем сигнал отражается в отражателе, отправляя ток обратно через роторы.
  7. Ток поступает в S, но поскольку цепь, идущая в S, прерывается стекером, ток продолжается до буквы D.
  8. От D ток идет до лампового щита.
  9. Подойдя к ламповому щиту, загорается буква D, зашифровывая от A до D.

Настройка ротора

В армейской Enigma - это выбор трех роторов из пяти I, II, III, IV и V, и обычно они записываются по порядку. Например: IV II I означает, что были выбраны роторы I, II и IV, а IV, II и I - крайний левый, средний и крайний правый роторы соответственно. Каждый из отдельных роторов содержит 26 перепрограммируемых из 26 потенциальных входов, по одному на каждую букву английского языка.

Настройка ротора Enigma

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

ротор Enigma

В дополнение к трем роторам, есть два дополнительных элемента, упомянутых в отношении машины Enigma, которые имеют некоторое влияние на шифрование:

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

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

Панель

Панель ввода расположена в передней части Enigma. Она определяет попарную замену между 20 буквами с использованием 10 заглушек. Заглушенное соединение между двумя буквами часто называют штекером. Каждый штекер определяет взаимную замену между двумя буквами. Замены штекера вставных панелей применяются дважды, как до, так и после входа в роторы. 

У нас есть три случая: ноль замен коммутационной панели, одна замена коммутационной панели и две замены коммутационной панели. Замена коммутационной панели часто указывается в виде пар букв, разделенных пробелом. Буквы, не входящие в пару, часто называют самонастраивающимися. Появление коммутационной панели (примерно в 1928-1930 гг.) было большим улучшением по сравнению с ранними коммерческими Enigmas и защитило от хорошо известных криптоаналитических атак.

Сложность

Описанная выше версия Enigma довольно сложна. Простой расчет показывает, что различные варианты ротора, сообщений и панели дают 

Сложность

или 4.835703278458517e+24 вариантов настройки.

На практике сообщения были очень короткие, 250 букв или короче, это означает, что крайний левый ротор почти никогда не срабатывает. И реальная сложность будет порядка 2 в 72 степени = 4.722366482869645e+21. Однако даже при таком уменьшении сложность значительна. Даже при наличии современных вычислительных мощностей исчерпывающий поиск по всему пространству состояний будет сложной задачей.

Генетические алгоритмы

Генетические алгоритмы (GA) черпают вдохновение в эволюции. Они начинаются с создания нескольких возможных решений проблемы. Каждое возможное решение упаковано в объект, называемый индивидуальным. Параметры, которые различаются у разных людей, называются генами. Набор этих генов называется геномом или генотипом человека. Случайная выборка обычно используется при создании первых особей, чтобы гарантировать некоторое первоначальное генетическое разнообразие. Физическая подготовка людей может быть определена как фитнес-функция. Особи с высокой приспособленностью по сравнению с другими особями выживают и размножаются, подобно эволюции в реальном мире. Эволюция естественным образом делится на поколения, каждое из которых требует:

  • Оценка людей.
  • Поиск наиболее приспособленных особей (для воспроизводства).
  • Замена наименее приспособленных особей потомками наиболее приспособленных.

Этот процесс повторяется до тех пор, пока модели не перестанут значительно улучшаться. Лучшая особь в популяции называется альфа-особью.

Кроссовер и мутация

Размножение между двумя и более особями называется кроссовером. Кроссовер позволяет новому человеку унаследовать некоторые элементы от каждого родителя. Этот кроссовер может происходить разными способами, но в природе новая особь, как правило, наследует примерно 50% своих генов от двух родителей. Во время кроссовера в геноме потомства могут возникать некоторые мутации, и это также используется в генетических алгоритмах. Эта мутация вносит некоторые необходимые изменения в популяцию. Обычно имеется меньшее количество особей, чем то, которое присутствует в более экстремальных примерах из реальной жизни, таких как популяции антилоп гну. Популяция, используемая в генетическом алгоритме, больше похожа на популяцию людей, населяющих небольшой остров, примерно от 10 до 500 человек. Проблема с небольшими популяциями заключается в том, что они склонны к потере генетического разнообразия, но есть компромисс. Меньшие популяции требуют меньшего количества вычислений на поколение, так как каждому человеку в моделировании нужно назначить приспособленность. Кроме того, меньшая популяция позволяет хорошим вариациям генов распространяться по популяции быстрее, чем это было бы с большой популяцией. Даже в реальном мире небольшая островная популяция может эволюционировать быстрее, чем более крупная популяция на материке. Это указывает на то, что меньшая популяция может развиться быстрее, чем большая, хотя и за счет генетического разнообразия. 

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

Индекс совпадения

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

К счастью, для измерения «близости» к незашифрованному тексту можно использовать несколько различных методов. Многие из них используют предвзятую природу естественных языков. Например, частота букв может указывать на то, насколько они близки к истинному немецкому или истинному английскому языку. Однако эта мера не идеальна при работе с неразрешенной коммутационной панелью, так как 10 заглушек не затрагивают около 5% текста. Кроме того, эти частоты очень уязвимы для шума, поскольку относительные частоты букв могут сильно различаться, особенно при работе с очень короткими текстами. Нам нужна мера, которая работает даже при большом количестве неправильных символов. 

Индекс совпадения (IC), предложенный Уильямом Фредериком Фридманом (1922), является кандидатом на такую ​​меру. Математически это определяется как:

Индекс совпадения (IC)

где IC - индекс совпадения, Fi - частота встречаемости буквы i в тексте, а N - количество букв в тексте.

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

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

Enigma в стране чудес

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

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

Выводы

Enigma построена для искажения частот букв в текстовых сообщениях. Это искажение в сочетании с дискретностью правильных настроек дешифрования, особенно настроек ротора, затрудняет атаку. 

Чтобы проиллюстрировать это, мы ввели новую меру, Индекс совпадения прогресса (PIC), которая является более удобочитаемой версией меры: Индекса совпадения (IC). Анализ с помощью PIC показал, что панель расширения Enigma была уязвима для атаки машинного обучения. Чтобы извлечь выгоду из этой уязвимости, ученые ввели атаку на основе генетического алгоритма для решения проблемы плагина Enigma с использованием атаки только шифрованного текста. Эта атака с генетическим алгоритмом оказалась очень эффективной. Он нашел настройки плагина быстрее, чем предыдущие атаки. 

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

P.S.

Ну вот кратко всетаки не вышло, но я старался как мог.

Как и обещал в конце даю ссылку на статью где не так много текста, но много классных картинок: Где карта Билли? Или заменит ли ИИ картографов?

Если статья хоть кому-то понравилась или пригодилась, буду рад комментариям, в том числе и критике)


Комментарии