Banburismus

редактировать

Banburismus - это криптоаналитический процесс, разработанный Аланом Тьюрингом в Блетчли Парк в Британии во время Второй мировой войны. Он использовался Хижиной 8 Блетчли Парка для взлома немецких Кригсмарине (военно-морских) сообщений, зашифрованных на машинах Энигмы. Процесс использовал последовательную условную вероятность для вывода информации о вероятных настройках машины Enigma. Это привело к тому, что Тьюринг изобрел запрет в качестве меры весомости свидетельств в пользу гипотезы. Эта концепция позже была применена в Тьюрингери и во всех других методах, используемых для взлома шифра Лоренца.

Содержание

1 Обзор
2 История
3 Принципы
- 3.1 Пример
- 3.2 Scritchmus
4 Среднее колесо
5 См. Также
6 Ссылки
7 Библиография
8 Дополнительная литература
9 Внешние ссылки

Обзор

Целью Banburismus было сокращение времени, необходимого для электромеханических станков Bombe, путем определения наиболее вероятных правого и среднего колеса Enigma. Хижина 8 выполняла процедуру непрерывно в течение двух лет, остановившись только в 1943 году, когда стало доступно достаточно времени для бомбардировки. Banburismus был развитием «часового метода », изобретенного польским криптоаналитиком Ежи Ружицким.

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

История

В первые несколько месяцев после прибытия в Блетчли-парк в сентябре 1939 года Алан Тьюринг правильно сделал вывод, что настройки сообщений для сигналов Kriegsmarine Enigma были зашифрованы на общем Grundstellung (начальное положение роторов), а затем супер-зашифрованы с помощью биграммы и триграммы поиска Таблица. Эти таблицы триграмм были в книге под названием Kenngruppenbuch (книга K). Однако без таблиц биграмм Hut 8 не могла атаковать трафик. Прорыв был достигнут после инцидента в Нарвике, когда замаскированный вооруженный траулер Polares, направлявшийся в Нарвик в Норвегии, был захвачен HMS Griffin в Северном море 26 апреля 1940 года. Немцы не успели уничтожить все свои криптографические документы, и захваченный материал показал точную форму системы индикации, снабжающей соединениями коммутационной панели и Grundstellung за 23 и 24 апреля, а также журнал операторов, который дал длинный отрезок парного открытого текста и зашифрованного сообщения для 25 и 26 апреля.

Сами таблицы биграмм не были частью захвата, но Hut 8 смогли использовать списки настроек для ретроспективного чтения всего трафика Кригсмарине, который был перехвачен с 22 по 27 апреля. Это позволило им выполнить частичную реконструкцию таблиц биграмм и начать первую попытку использовать Banburismus для атаки на трафик Кригсмарине, начиная с 30 апреля. Подходящими днями были те дни, когда было получено не менее 200 сообщений и для которых частичные биграммы расшифровали индикаторы. Первым днем взлома было 8 мая 1940 года, впоследствии отмечавшееся как «День Фосса» в честь Хью Фосса, криптоаналитика, совершившего этот подвиг.

Выполнение этой задачи длилось до ноября того же года, к тому времени разведданные были очень устаревшими, но они показали, что банбуризмус может работать. Это также позволило реконструировать гораздо больше таблиц биграмм, что, в свою очередь, позволило сломать 14 апреля и 26 июня. Однако 1 июля Кригсмарине изменил таблицу биграмм. К концу 1940 года большая часть теории системы подсчета баллов Banburismus была разработана.

Первое испытание на Лофотенских островах с траулера Krebs 3 марта 1941 г. дало полные ключи на февраль - но не таблицы биграмм или книгу K. Последовательные расшифровки позволили усовершенствовать систему статистической оценки, чтобы банбуризмус мог стать стандартной процедурой против Kriegsmarine Enigma до середины 1943 года.

Принципы

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

Левый конец «Листа Банбури» времен Второй мировой войны, найденного в 2014 году на крыше Хижины 6 в Блетчли-Парк.

Принцип, лежащий в основе Banburismus, относительно прост ( и кажется довольно похожим на Индекс совпадения ). Если два предложения на английском или немецком написаны одно над другим и подсчитывается, как часто буква в одном сообщении совпадает с соответствующей буквой в другом сообщении; совпадений будет больше, чем если бы предложения были случайными цепочками букв. Ожидается, что для случайной последовательности частота повторения отдельных букв будет 1 из 26 (около 3,8%), а для сообщений ВМФ Германии - 1 из 17 (5,9%). Если два сообщения были подробными, то совпадения происходят так же, как и в открытых текстах. Однако, если сообщения не были подробными, то два шифртекста будут сравниваться, как если бы они были случайными, давая частоту повторения примерно 1 из 26. Это позволяет злоумышленнику принять два сообщения, индикаторы которых отличаются только третьим символом, и сдвиньте их друг к другу, ища шаблон повторения, который показывает, где они совпадают по глубине.

Сравнение двух сообщений для поиска повторов было упрощено благодаря тому, что сообщения были помещены на тонкие карточки высотой около 250 мм (10 дюймов) и шириной несколько метров (у них были разные карточки для сообщений разной длины). отверстие в верхней части столбца на карточке представляло букву «А» в этой позиции, отверстие внизу представляло букву «Z». Две карточки для сообщений были положены друг на друга на световом ящике, и там, где Прошел свет, повторы были. Это значительно упростило обнаружение и подсчет повторов. Карты были напечатаны в Банбери в Оксфордшире. Они стали известны как «банбери» в Блетчли-парке, отсюда и название процедура, использующая их: Banburismus.

Применение процедуры scritchmus (см. ниже) дает ключ к пониманию возможного правого ротора.

Пример

Сообщение с индикатором "VFG": XCYBGDSLVWBDJLKWIPEHVYGQZWDTHRQXIKEESQSSPZXARIXEABQIRUCKHGWUEBPF

Сообщение с индикатором "VFX": <63IPLEMSCGV SPVRXMCFQAXVXDVUQILBJUABNLKMKDJMENUNQ

Хижина 8 вставляла их в банбюри и подсчитывала повторы для всех допустимых смещений от −25 букв до +25 букв. Есть два перспективных позиций:

XCYBGDSLVWBDJLKWIPEHVYGQZWDTHRQXIKEESQSSPZXARIXEABQIRUCKHGWUEBPF YNSCFCCPVIPEMSGIZWFLHESCIYSPVRXMCFQAXVXDVUQILBJUABNLKMKDJMENUNQ - - - - - - -

Это смещение из восьми букв показывают девять повторов, в том числе двух биграмм, в перекрытии 56 букв (16 %).

Другая многообещающая позиция выглядит следующим образом:

XCYBGDSLVWBDJLKWIPEHVYGQZWDTHRQXIKEESQSSPZXARIXEABQIRUCKHGWUEBPF YNSCFCCPVIPEMSGIZWAXFLHESCIYSPVRXQQ11 с одним триггером на
Метод Тьюринга для накопления оценки в несколько децибанов позволяет вычислить, какая из этих ситуаций с наибольшей вероятностью представляет сообщения в глубине. Как и следовало ожидать, первый является победителем с коэффициентом 5: 1, второй - только 2: 1.
Тьюринг подсчитал количество одиночных повторов при перекрытии такого количества букв, и количество биграмм и триграмм. Тетраграммы часто представляли немецкое слово в открытом тексте, и их баллы рассчитывались в соответствии с типом сообщения (из анализа трафика) и даже их положением в сообщении. Они были сведены в таблицу, а соответствующие значения суммированы банбуристами при оценке пар сообщений, чтобы увидеть, какие из них могут быть подробными.
Bletchley Park использовал соглашение, согласно которому открытый текст индикатора «VFX» на восемь символов впереди «VFG» или (с точки зрения третьей, отличающейся буквы), что «X = G + 8».
Скритчмус
Скритчмус был частью процедуры Banburismus, которая могла привести к идентификации правого (быстрого) колеса. Банбурист может иметь свидетельства из различных пар сообщений (с разницей только в третьей букве индикатора), показывающие, что «X = Q-2», «H = X-4» и «B = G + 3». Он будет искать в таблицах децибанов все расстояния с коэффициентом лучше, чем 1: 1 (то есть со счетом ≥ +34). Затем была предпринята попытка построить «алфавит конечного колеса» путем формирования «цепочки» букв конечного колеса из этих повторов. Затем они могли бы построить «цепочку» следующим образом:
G - BH --- XQ
Если это затем сравнить с прогрессивным смещением с известной последовательностью букв ротора Enigma, довольно много возможностей не принимается во внимание из-за нарушения либо свойства "взаимного", либо свойства "не самошифровать" машины Enigma:
G - BH --- XQ ABCDEFGHIJKLMNOPQRSTUVWXYZ......... возможно G - BH --- XQ ABCDEFGHIJKLMNOPQRSTUVWXYZ......... невозможно (G зашифровывает до B, но B зашифровывает до E) G - BH --- XQ ABCDEFGHIJKLMNOPQRSTUVWXYZ......... невозможно (H, по-видимому, зашифровывает до H) G - BH --- XQ ABCDEFGHIJKLMNOPQRSTUVWXYZ......... невозможно (G зашифровывает до D, но B зашифровывает до G) G-- BH --- XQ ABCDEFGHIJKLMNOPQRSTUVWXYZ......... невозможно (B зашифровывает до H, но H зашифровывает до J) G - BH --- XQ ABCDEFGHIJKLMNOPQRSTUVWXYZ......... невозможно ( Q очевидно зашифровывает до Q) G - BH --- XQ ABCDEFGHIJKLMNOPQRSTUVWXYZ......... невозможно (G очевидно зашифровывает до G) G - BH --- XQ ABCDEFGHIJKLMNOPQRSTUVWXYZ......... невозможно (G зашифровывает до H, но H зашифровывает до M) G - BH --- XQ ABCDEFGHIJKLMNOPQRSTUVWXYZ......... возможно G- -BH --- XQ ABCDEFGHIJKLMNOPQRSTUVWXYZ......... возможно G - BH --- XQ ABCDEFGHIJKLMNOPQRSTUVWXYZ......... возможно G - BH --- XQ ABCDEFGHIJKLMNOPQRSTUVWXYZ......... невозможно (H зашифровывает до Q, но Q зашифровывает до W) G - BH --- XQ ABCDEFGHIJKLMNOPQRSTUVWXYZ......... невозможно (X зашифровывает до V, но Q зашифровывает до X) G - BH --- XQ ABCDEFGHIJKLMNOPQRSTUVWXYZ......... невозможно (B зашифровывает до Q, но Q зашифровывает до Y) G - BH --- XQ ABCDEFGHIJKLMNOPQRSTUVWXYZ......... невозможно (X зашифровывает до X) Q G - BH --- X->ABCDEFGHIJKLMNOPQRSTUVWXYZ......... возможно -Q G - BH --- X->ABCDEFGHIJKLMNOPQRSTUVWXYZ......... невозможно (Q зашифровывает до B, но B зашифровывает до T) XQ G - BH --->ABCDEFGHIJKLMNOPQRSTUVWXYZ......... возможно -XQ G - BH ->ABCDEFGHIJKLMNOPQRSTUVWXYZ......... невозможно (X зашифровывает до B, еще B зашифровывает до V) --XQ G - BH->ABCDEFGHIJKLMNOPQRSTUVWXYZ......... возможно --- XQ G - BH->ABCDEFGHIJKLMNOPQRSTUVWXYZ......... невозможно ( X зашифровывает до D, но B зашифровывает до X) H --- XQ G - B->ABCDEFGHIJKLMNOPQRSTUVWXYZ......... невозможно (Q зашифровывает до G, но G зашифровывает до V) -H-- -XQ G - B->ABCDEFGHIJKLMNOPQRSTUVWXYZ......... невозможно (H зашифровывает до B, но Q зашифровывает до H) BH --- XQ G ->ABCDEFGHIJKLMNOPQRSTUVWXYZ.........возможно (обратите внимание, что G зашифровывает X, X зашифровывает свойство G) -BH --- XQ G->ABCDEFGHIJKLMNOPQRSTUVWXYZ......... невозможно (B зашифровывает до B) --BH --- XQ G->ABCDEFGHIJKLMNOPQRSTUVWXYZ......... возможно
Так называемый «алфавит с конечным колесом» уже ограничен девятью возможностями, просто создавая буквенную цепочку из пяти букв. полученный всего из четырех пар сообщений. Хижина 8 теперь попытается приспособить другие буквенные цепочки - те, у которых нет букв, общих с первой цепочкой, - в эти девять возможных алфавитов конечных колес.
В конце концов они будут надеяться, что у них останется только один кандидат, который может выглядеть так:
NUP F ---- A - D --- O --XQ G - BH ->ABCDEFGHIJKLMNOPQRSTUVWXYZ
Не только это, но и такой алфавит конечного колеса заставляет сделать вывод, что конечное колесо на самом деле является «Ротором I». Это потому, что «Ротор II» вызвал бы оборот среднего колеса при переходе от «E» к «F», но это находится в середине промежутка буквенной цепочки «F ---- A - D. --- О ". Точно так же исключаются все другие возможные обороты среднего колеса. Ротор I делает свой оборот между Q и R, и это единственная часть алфавита, не охваченная цепью.
То, что разные колеса Enigma имеют разные точки оборота, по-видимому, было мерой разработчиков машины для повышения ее безопасности. Однако именно эта сложность позволила Блетчли-Парку установить идентичность концевого колеса.
Среднее колесо
После того, как конечное колесо идентифицировано, те же принципы могут быть распространены на работу со средним ротором, хотя с дополнительной сложностью, заключающейся в том, что поиск перекрытий в разделении пар сообщений просто первая индикаторная буква, и поэтому перекрытия могут происходить на расстоянии до 650 символов друг от друга.
Работа по выполнению этого выходит за рамки ручного труда, поэтому BP перетащила сообщения на карты с 80 столбцами и использовала Машины Hollerith для поиска повторов тетраграммы или лучше. Это подсказало им, какие банбюри установить на световых коробах (и с какими перекрытиями), чтобы оценить весь повторяющийся узор.
Вооружившись набором вероятных перекрытий средних колес, Хижина 8 могла составлять цепочки букв для среднего колеса почти так же, как было показано выше для конечного колеса. Это, в свою очередь (после Scritchmus), даст хотя бы частичный алфавит среднего колеса, и, надеюсь, по крайней мере, некоторые из возможных вариантов выбора ротора для среднего колеса могут быть исключены из данных о оборотах (как это было сделано при идентификации конечного колеса).
Взятые вместе, вероятные правые и средние колеса дадут набор пробежек бомбы за день, который будет значительно меньше 336 возможных.
См. Также
Последовательный анализ
Ссылки
Библиография
Александр, К. Хью О'Д. (ок. 1945), Криптографическая история работы над немецкой военно-морской загадкой, Национальный архив, Кью, ссылка HW 25/1
Гуд, Джек (1993), «Загадка и рыба», в Хинсли, FH ; Стрипп, Алан (ред.), Codebreakers: The Inside Story of Bletchley Park, Oxford: Oxford University Press, ISBN 978-0-19-280132-6
Хосгуд, Стивен (2008). «Все, что вы хотели знать о банбуризме, но боялись спросить». Архивировано из оригинала 9 марта 2016 г. Получено 9 марта 2016 г.
MacKay, David JC Теория информации, логический вывод и алгоритмы обучения Кембридж: Cambridge University Press, 2003. ISBN 0-521-64298-1. Этот онлайновый учебник включает главу, в которой обсуждаются аспекты теории информации Banburismus.
Махон, А.П. (1945). «История восьмой избы 1939-1945 гг.». Проверено 21 октября 2009 г.
Дополнительная литература
Себаг-Монтефиоре, Хью. Enigma - битва за код. Cassell Military Мягкие обложки, Лондон, 2004. ISBN 978-1-4072-2129-8
Внешние ссылки
Криптографический словарь Блетчли-Парка 1944 года
«Все вы Всегда хотели знать о банбуризме, но боялись спросить " - вся процедура детально исследована на рабочем примере.