Банбуризм - Banburismus


Шифровальная машина Enigma
Enigma-logo.svg

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

Обзор

Целью 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 года, впоследствии отмечавшееся как «День Фосса» в честь Хью Фосса , криптоаналитика, совершившего этот подвиг.

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

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

Принципы

Banburismus использовал слабое место в процедуре индикатора (настройках зашифрованного сообщения) трафика 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 ": YNSCFCCPVIPEMSGIZWFLHESCIYSPVRXMCFQAXVXDVUQILBJUABNLKMKDJMENUNQ

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

XCYBGDSLVWBDJLKWIPEHVYGQZWDTHRQXIKEESQSSPZXARIXEABQIRUCKHGWUEBPF
        YNSCFCCPVIPEMSGIZWFLHESCIYSPVRXMCFQAXVXDVUQILBJUABNLKMKDJMENUNQ
                      - --  -   -          -  -   --

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

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

XCYBGDSLVWBDJLKWIPEHVYGQZWDTHRQXIKEESQSSPZXARIXEABQIRUCKHGWUEBPF
       YNSCFCCPVIPEMSGIZWFLHESCIYSPVRXMCFQAXVXDVUQILBJUABNLKMKDJMENUNQ
                ---

Это смещение семи показывает только одну триграмму, перекрывающую 57 букв.

Метод Тьюринга накопления оценки в несколько децибанов позволяет вычислить, какая из этих ситуаций с наибольшей вероятностью будет представлять сообщения в глубине. Как и следовало ожидать, первый - победитель с коэффициентом 5: 1 на, второй - только 2: 1.

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

Блетчли Парк использовал соглашение, согласно которому открытый текст индикатора «VFX» находится на восемь символов впереди «VFG», или (в терминах только третьей, отличающейся буквы), что «X = G + 8».

Scritchmus

Scritchmus был частью процедуры Banburismus, которая могла привести к идентификации правого (быстрого) колеса. Банбурист может иметь доказательства из различных пар сообщений (с разницей только в третьей букве индикатора), показывающие, что «X = Q-2», «H = X-4» и «B = G + 3». Он будет искать в таблицах децибанов все расстояния с коэффициентом лучше, чем 1: 1 (т. Е. Со счетом ≥ +34). Затем была предпринята попытка построить «алфавит конечного колеса» путем формирования «цепочек» букв конечного колеса из этих повторов. Затем они могли построить «цепочку» следующим образом: 

G--B-H---X-Q

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

G--B-H---X-Q
ABCDEFGHIJKLMNOPQRSTUVWXYZ  ......... is possible

 G--B-H---X-Q
ABCDEFGHIJKLMNOPQRSTUVWXYZ  ......... is impossible (G enciphers to B, yet B enciphers to E)

  G--B-H---X-Q
ABCDEFGHIJKLMNOPQRSTUVWXYZ  ......... is impossible (H apparently enciphers to H)

   G--B-H---X-Q
ABCDEFGHIJKLMNOPQRSTUVWXYZ  ......... is impossible (G enciphers to D, yet B enciphers to G)

    G--B-H---X-Q
ABCDEFGHIJKLMNOPQRSTUVWXYZ  ......... is impossible (B enciphers to H, yet H enciphers to J)

     G--B-H---X-Q
ABCDEFGHIJKLMNOPQRSTUVWXYZ  ......... is impossible (Q apparently enciphers to Q)

      G--B-H---X-Q
ABCDEFGHIJKLMNOPQRSTUVWXYZ  ......... is impossible (G apparently enciphers to G)

       G--B-H---X-Q
ABCDEFGHIJKLMNOPQRSTUVWXYZ  ......... is impossible (G enciphers to H, yet H enciphers to M)

        G--B-H---X-Q
ABCDEFGHIJKLMNOPQRSTUVWXYZ  ......... is possible

         G--B-H---X-Q
ABCDEFGHIJKLMNOPQRSTUVWXYZ  ......... is possible

          G--B-H---X-Q
ABCDEFGHIJKLMNOPQRSTUVWXYZ  ......... is possible

           G--B-H---X-Q
ABCDEFGHIJKLMNOPQRSTUVWXYZ  ......... is impossible (H enciphers to Q, yet Q enciphers to W)

            G--B-H---X-Q
ABCDEFGHIJKLMNOPQRSTUVWXYZ  ......... is impossible (X enciphers to V, yet Q enciphers to X)

             G--B-H---X-Q
ABCDEFGHIJKLMNOPQRSTUVWXYZ  ......... is impossible (B enciphers to Q, yet Q enciphers to Y)

              G--B-H---X-Q
ABCDEFGHIJKLMNOPQRSTUVWXYZ  ......... is impossible (X enciphers to X)

Q              G--B-H---X->
ABCDEFGHIJKLMNOPQRSTUVWXYZ  ......... is possible

-Q              G--B-H---X->
ABCDEFGHIJKLMNOPQRSTUVWXYZ  ......... is impossible (Q enciphers to B, yet B enciphers to T)

X-Q              G--B-H--->
ABCDEFGHIJKLMNOPQRSTUVWXYZ  ......... is possible

-X-Q              G--B-H-->
ABCDEFGHIJKLMNOPQRSTUVWXYZ  ......... is impossible (X enciphers to B, yet B enciphers to V)

--X-Q              G--B-H->
ABCDEFGHIJKLMNOPQRSTUVWXYZ  ......... is possible

---X-Q              G--B-H->
ABCDEFGHIJKLMNOPQRSTUVWXYZ  ......... is impossible (X enciphers to D, yet B enciphers to X)

H---X-Q              G--B->
ABCDEFGHIJKLMNOPQRSTUVWXYZ  ......... is impossible (Q enciphers to G, yet G enciphers to V)

-H---X-Q              G--B->
ABCDEFGHIJKLMNOPQRSTUVWXYZ  ......... is impossible (H enciphers to B, yet Q enciphers to H)

B-H---X-Q              G-->
ABCDEFGHIJKLMNOPQRSTUVWXYZ  ......... is possible (note the G enciphers to X, X enciphers to G property)

-B-H---X-Q              G->
ABCDEFGHIJKLMNOPQRSTUVWXYZ  ......... is impossible (B enciphers to B)

--B-H---X-Q              G->
ABCDEFGHIJKLMNOPQRSTUVWXYZ  ......... is possible

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

В конце концов они будут надеяться, что у них останется только один кандидат, который может выглядеть так: 

         NUP
F----A--D---O
--X-Q              G--B-H->
ABCDEFGHIJKLMNOPQRSTUVWXYZ

Не только это, но и такой алфавит конечного колеса заставляет сделать вывод, что конечное колесо на самом деле является "Ротором I". ВНИМАНИЕ !!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!! Это потому, что «Ротор II» вызвал бы оборот среднего колеса при переходе от «E» к «F», но он находится в середине промежутка буквенной цепочки «F ---- A - D. --- О ". Точно так же исключаются все другие возможные обороты среднего колеса. Ротор I совершает свой оборот между Q и R, и это единственная часть алфавита, не охваченная цепочкой.

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

Среднее колесо

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

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

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

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

Смотрите также

Рекомендации

Библиография

дальнейшее чтение

Внешние ссылки