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

В первых десятилетиях 20 века массово велись разработки и внедрение шифровальных машин, и вскоре на сцену вышла легендарная «Энигма» Артура Шербиуса. Это был гигантский технологический рывок. Наиболее широко машина использовалась в гитлеровской Германии во время Второй мировой войны. Другие страны-участники также разрабатывали подобные устройства, и одним из таких стала SIGABA.

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

SIGABA — электромеханическое шифровальное устройство, массово использовавшееся США во время Второй мировой войны, вплоть до 1950-х годов. Также этот прибор известен под маркировками ECM Mark II, Converter M-134-C, CSP-889 и CSP-2900.

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

Считается, что немецкие криптоаналитики не смогли взломать SIGABA. Самый эффективный опубликованный современный взлом устройства — атака с известным открытым текстом, которая требует как минимум 2^60.2 шагов и больших вычислительных мощностей, сравнимых с теми, которые требуются для восстановления 56-битного ключа алгоритма симметричного шифрования DES. В этой статье мы разберем новую атаку по принципу «разделяй и властвуй» с известным открытым текстом, которая может восстановить ключ менее чем за 24 часа на мощном персональном компьютере, используя многочисленные недостатки в конструкции SIGABA. С помощью этой атаки решим несколько задач с полным пространством ключей.

Шифровальная машина SIGABA

Механизм шифрования и дешифрования SIGABA состоит из трех банков по пять роторов в каждом: банк шифров, банк управления и банк индексов, как показано на рисунке 1 для модели CSP-889.

Шифровальные и управляющие роторы имеют по 26 входов и выходов каждый (по количеству букв английского алфавита). Они взаимозаменяемы и выбираются из набора, состоящего из десяти роторов. Кроме того, они могут быть установлены в двух возможных ориентациях — вперед или назад (таким образом увеличивая размер ключевого пространства в 2¹⁰ раз). Любопытно, что буквы, начертанные на шифровальных и управляющих роторах, перемещаются по алфавиту в обратном алфавитном порядке, когда они установлены в прямом направлении, и в алфавитном порядке при установке в обратной ориентации.

Шифровальные роторы реализуют шифрование (слева направо) и дешифрование (справа налево). Роторы банка шифров шагают в соответствии с нерегулярным шаблоном, генерируемым банками роторов управления и индекса. Этот нерегулярный пошаговый механизм был разработан с целью предотвращения статистических и механизированных атак, которые оказались эффективными против систем с обычным или предсказуемым пошаговым механизмом, таких как Enigma, Hagelin C-38 или Lorenz SZ42.

Два управляющих ротора, крайний левый и крайний правый, неподвижны и не вращаются во время шифрования или дешифрования. Быстрый ротор всегда вращается (что интересно, этот ротор расположен между медленным и средним роторами). Всякий раз, когда быстрый ротор переходит от O к N (при прямой ориентации) или от O к P (при реверсивной ориентации), средний ротор делает шаг. Аналогичным образом, всякий раз, когда средний ротор проходит путь от O к N (при прямой ориентации) или от O к P (при реверсивной ориентации), медленный ротор также делает шаг.

На каждом шаге шифрования входы F, G, H и I крайнего правого (неподвижного) управляющего ротора активируются и запитываются электрическим током (в то время как остальные 22 входа остаются неактивными). 26 выходов крайнего левого управляющего ротора входят в логику ввода индекса, описанную на рисунке 2, четыре из которых активны в любой момент.

Банк индексов состоит из пяти стационарных роторов, которые не вращаются во время шифрования или дешифрования. Каждый ротор имеет десять входов и выходов. Эти роторы отличаются от роторов шифрования и управления, и их можно устанавливать только в направлении вперед. Логика ввода индекса распределяет 26 входов на 10 выходов, которые входят в крайний левый ротор индекса. Как видно на рисунке 2, эти 26 входов неравномерно распределены между десятью выходами. Логика вывода индекса, описанная на рисунке 3, отображает десять выходов крайнего правого ротора индекса в пять управляющих сигналов пошагового управления, управляющих роторами шифратора.

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

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

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

Различия между моделями SIGABA CSP-2900 и CSP-889

1. В модели CSP-889 четыре активных входа в группу управляющих роторов (F, G, H и I). В модели CSP-2900 их шесть (D, E, F, G, H и I).

2. Логика входа в группу роторов индекса отличается и представлена на рисунке 4. Подключены все десять входов (в CSP-889 вход 1 всегда неактивен). Также не используются выходы P, Q и R управляющих роторов (в отличие от модели CSP-889, где используются все 26 входов).

3. В результате на каждом шаге могут быть активны до шести из десяти выходов группы роторов индекса. Поскольку они объединяются попарно с помощью логической схемы вывода индекса (без изменений для CSP-2900), задействуются все пять роторов шифра  в отличие от четырех в CSP-889.

4. В то время как в модели CSP-889 пять шифровальных роторов при прямой ориентации шагают так, чтобы отображаемые буквы двигались в обратном алфавитном порядке (и в алфавитном порядке при реверсивной ориентации), в модели CSP-2900 шифровальные роторы 2 и 4 шагают в обратном направлении, так что отображаемые буквы идут в алфавитном порядке при прямой ориентации (и в обратном алфавитном порядке при обратной ориентации). Роторы шифрования 1, 3 и 5 перемещаются в том же направлении, что и роторы шифрования в модели CSP-889. В результате, даже если все пять роторов шифра будут двигаться вместе, они не будут двигаться в одном и том же направлении и, следовательно, никогда не останутся в одном и том же относительном положении.

Анализ ключевого пространства

Предполагая, что существует набор из десяти роторов, из которых выбираются роторы шифрования и управления, для этих роторов возможен выбор. Каждый из этих роторов может быть установлен как в прямом, так и в реверсивном направлении. Таким образом, размер пространства ключей для настроек десяти роторов банков шифрования и управления, включая их начальные позиции, составляет, 10! ×210×2610=2^78.8 (здесь и далее все степени округляются до десятых долей).

Существует 5! возможных вариантов комплектования роторов индекса. Таким образом, размер пространства ключей для настроек роторов банка индексов, включая их начальные позиции, равен, 5!×105=2^23.5, а общий размер пространства ключей SIGABA равен 2^78.8+23.5=2^102.3.

Однако размер пространства ключей для банка индексов ограничен тем фактом, что пять роторов реализуют (стационарную) перестановку десяти входов, а логика вывода индекса отображает десять выходов только в пять выходов. Таким образом, размер практического пространства ключей для индексных роторов, включая логику вывода индекса, составляет всего 10!/25 = 113400=2^16.8, а общий размер практического пространства ключей SIGABA составляет 2^78.8+16.8=2^95.6. 

Предварительный криптоанализ SIGABA

В предыдущих исследованиях описывают разные варианты атаки SIGABA:

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

— Атаки на упрощенные и ослабленные версии SIGABA.

— Атака по известному открытому тексту в два этапа, которая требуют 2^86.7 шагов (эта атака применима только к модели CSP-889). На первом этапе рассматриваются только роторы шифрования и оцениваются все их возможные настройки (выбор ротора, ориентация, стартовые позиции). Для каждой такой настройки (из 2^43.4 возможных настроек ротора шифрования) первый символ зашифрованного текста применяется к пяти роторам шифрования, а расшифрованный символ сравнивается с известным символом открытого текста. Если символы не совпадают, настройка сбрасывается.

Для проверки второго символа тестируются все варианты степпинга роторов шифрования (в модели CSP-889 30 вариантов и как минимум один шаг ротора, а максимум четыре). Если после шага расшифровка второго символа зашифрованного текста дает ожидаемый символ известного открытого текста, процесс повторяется для следующих символов.

Сохраняются только те настройки роторов шифрования, которые выдержали испытание для всех известных символов открытого текста. Ожидается, что для определения настройки роторов шифрования достаточно сообщения состоящего из 100 символов известного открытого текста, при этом количество таких настроек 2^34.5. На втором этапе все подходящие настройки роторов шифрования проверяются на соответствие всем возможным настройкам роторов управления и индекса, и при наличии 2^95.6-43.4=2^52.2 таких настроек общий коэффициент работы атаки составляет 2^34.5+52.2=2^86.7. Авторы метода также предлагают вариант с уменьшенным коэффициентом 2^84.5 и соответственно сниженной до 82% вероятностью успеха.

— Атака «встреча посередине» (MITM), которая восстанавливает ключ из зашифрованного текста и только восьми известных букв открытого текста, применимая к модели CSP-889. Сходным с предыдущим методом образом эта атака проводится в два этапа.

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

На втором этапе все возможные настройки роторов управления и индекса проверяются и применяются к восьми циклам шифрования, чтобы увидеть, создает ли какой-либо из них один из шаблонов шага, хранящихся в хэш-таблице. Если такой шаблон найден в хеш-таблице, для расшифровки зашифрованного текста используются комбинированные настройки роторов шифра, управления и индекса, а результирующая расшифровка оценивается с помощью некоторой статистической величины, например, индекса совпадения. В исследовании этой атаки приведена примерная оценка вычислительной мощности (требуется около 80 ГБ ОЗУ), а общий коэффициент работы составляет 260.2. Эта атака применима при наличии значительных вычислительных мощностей при использовании специализированного оборудования.

Статистический анализ пошаговых последовательностей ротора шифра

Шаговая последовательность роторов шифрования имеет статистические характеристики, которые отличают ее от случайной пошаговой схемы. Он управляется двумя наборами роторов: управляющими роторами и индексными роторами. В модели CSP-889 четыре активных входа (из 26) поступают на роторы управления, и эти активные входы направляются через эти роторы на четыре входа логики индексного входа (см. рис. 1). Поскольку некоторые из управляющих роторов меняют свое положение во время шифрования, четыре активных входа в логику ввода индекса, вероятно, будут меняться после каждого цикла шифрования. Таким образом, во время криптоанализа настройки управляющих роторов неизвестны, и мы предполагаем, что четыре активных входа в логику ввода индекса распределены случайным образом.

Логика ввода индекса преобразует 26 входных сигналов в десять выходных сигналов, как показано на рисунке 2. Роторы индекса применяют стационарное отображение этих десяти входных сигналов в десять выходных сигналов, которые объединяются попарно с помощью операции ИЛИ (OR) логикой вывода индекса, генерируя пять шагов управляющих сигналов (по одному на каждый ротор шифрования).

Как описано выше, размер пространства ключей для настроек роторов банка индексов равен 5!×105=2^23.5, а размер практического пространства ключей для индексных роторов составляет всего 10!/25 = 113400 конфигураций отличающихся криптологически. 

В процессе исследования были смоделированы 113400 уникальных конфигураций. Для каждой конфигурации протестировали все возможные комбинации четырех активных входов, входящих в логику ввода индекса (26!/(4!×20!) = 14950), фиксируя пять выходных сигналов логики вывода индекса. В процессе подсчета количества вхождений каждого шаблона (для пяти выходных сигналов) было обнаружено явное расхождение результатов с ожидаемыми случайными пошаговыми шаблонами.

Чтобы проиллюстрировать эту статистическую погрешность, исследуем следующую конфигурацию ротора индекса:

— порядок индексных роторов 1, 2, 3, 4 и 5 слева направо;

— все индексные роторы находятся в положении «0».

Для этой конфигурации на рис. 5 показаны счетчики каждого шаблона (например, 00110 означает, что роторы 1, 2 и 5 не выполняют шаг после шифрования, а роторы 3 и 4 делают шаг). Можно увидеть, что хотя некоторые шаблоны встречаются редко (например, 00100 и 01000), другие шаблоны встречаются гораздо чаще (например, 00111 и 01011). Мы наблюдаем аналогичное смещение, когда смотрим на количество шагов каждого ротора шифра, как показано на рисунке 6. Три ротора делают шаг в 51% случаев, а два других — в 74%. В среднем роторы шагают примерно в 60% случаев.

Подобные смещения наблюдаются и с другими конфигурациями роторов индекса модели SIGABA CSP-889. В предыдущих исследованиях было обнаружено, что 113400 уникальных конфигураций могут быть разделены на 89 статистически эквивалентных категорий на основе вероятностей шагания роторов шифра после шифрования. Вычисленные вероятности для этих категорий, показаны на рисунке 7.

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

— Это количество делится на 14950, чтобы получить приблизительную вероятность того, что этот ротор сработает во время шифрования.

— Сортируются вероятности для пяти роторов шифрования в порядке возрастания.

Затем сравниваем эти вероятности с ожидаемыми, если бы ротор шифра работал случайным образом. Теоретически для пяти роторов шифрования существуют 25 = 32 шаблонов, но на практике возможны только 32 – 2 = 30 из них, так как хотя бы один из роторов должен шагать, а шагать могут не более четырех роторов. Если бы эти шаблоны были выбраны случайным образом, вероятность случайного шагания ротора шифра была бы равна 15/30 = 50% (для любого ротора шифра существует 15 шаблонов, в которых он будет шагать, и 15 шаблонов, в которых нет).

Как видно из рисунка 7, фактические вероятности в каждой категории отличаются от вероятностей случайного шага (50%), а среднее значение для пяти роторов шифра в данной категории колеблется от 53.8% до 61.2%. Таким образом, среднее количество изменений положения роторов шифрования в каждом цикле, составляет от 2.69 до 3.06, что выше, чем случайное ожидание в 2.5. Кроме того, в большинстве категорий вероятности также значительно различаются между отдельными роторами.

Статистика шагания роторов шифрования искажена, потому что логика ввода индекса неравномерно распределяет 26 выходных сигналов роторов шифрования по десяти входам роторов индекса. Например, вход 9 банка индексов является результатом операции «ИЛИ» шести сигналов, и он с большей вероятностью будет активен, чем вход 2, который генерируется только из одного сигнала, как показано на рисунке 2.

Для модели CSP-2900 наблюдается 80 различных категорий, и отклонение от вероятностей случайного шага еще более выражено, как показано на рисунке 8. Для большинства категорий все пять роторов шифрования с большей вероятностью будут шагать, чем сохранять свое положение. В некоторых случаях один из роторов почти всегда срабатывает (с вероятностью до 99.94%). Эта более сильная статистическая погрешность удивительна, поскольку CSP-2900 — более поздняя усовершенствованная модель аппаратуры шифрования SIGABA. Ожидалось более случайное поведение по сравнению с ранней моделью CSP-889.

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

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

Предлагаемая атака по принципу «разделяй и властвуй» с известным открытым текстом состоит из двух этапов:

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

2. Обработка возможных настроек роторов шифрования и пошаговых последовательностей, созданных (и ранжированных) на предыдущем этапе, для проверки на выполнимость, т. е. последовательность шагов, может быть воспроизведена с некоторыми допустимыми настройками роторов управления и индекса. Если это возможно, выполняется полный тест дешифрования с комбинированными настройками шифрования, управления и индекса.

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

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

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

Приложения:

— полное описание машины и ее истории (EN)

— патент SIGABA (EN)

— симулятор шифровальной машины SIGABA (github) 

— SIGABA Simulator for Windows (zip, exe)

НЛО прилетело и оставило здесь промокод для читателей нашего блога:

— 15% на все тарифы VDS (кроме тарифа Прогрев) — HABRFIRSTVDS.