Banburismus - Banburismus

Banburismus foi um processo criptanalítico desenvolvido por Alan Turing em Bletchley Park, na Grã-Bretanha, durante a Segunda Guerra Mundial . Foi usado pela Hut 8 de Bletchley Park para ajudar a quebrar mensagens da Kriegsmarine (naval) alemã codificadas em máquinas Enigma . O processo usou probabilidade condicional sequencial para inferir informações sobre as configurações prováveis ​​da máquina Enigma. Isso deu origem à invenção da proibição por Turing como uma medida do peso da evidência a favor de uma hipótese. Este conceito foi posteriormente aplicado em Turingery e todos os outros métodos usados ​​para quebrar a cifra de Lorenz .

Visão geral

O objetivo do Banburismus era reduzir o tempo necessário para as máquinas eletromecânicas Bombe , identificando as rodas direita e média mais prováveis do Enigma . O Hut 8 executou o procedimento continuamente por dois anos, parando apenas em 1943, quando o tempo de bombardeio suficiente tornou-se prontamente disponível. Banburismus foi um desenvolvimento do " método do relógio " inventado pelo criptanalista polonês Jerzy Różycki .

Hugh Alexander foi considerado o melhor dos banburistas. Ele e IJ Good consideraram o processo mais um jogo intelectual do que um trabalho. Não era "fácil o suficiente para ser trivial, mas não difícil o suficiente para causar um colapso nervoso".

História

Nos primeiros meses após chegar a Bletchley Park em setembro de 1939, Alan Turing deduziu corretamente que as configurações de mensagem dos sinais Kriegsmarine Enigma foram codificadas em um Grundstellung comum (posição inicial dos rotores) e, então, supercifradas com um bigrama e uma tabela de pesquisa de trigrama . Essas tabelas de trigramas estavam em um livro chamado Kenngruppenbuch (livro K) . No entanto, sem as tabelas bigram, o Hut 8 não foi capaz de começar a atacar o tráfego. Um grande avanço foi alcançado após o ataque de Narvik em que o arrastão armado disfarçado Polares , que estava a caminho de Narvik na Noruega , foi apreendido pelo HMS  Griffin no Mar do Norte em 26 de abril de 1940. Os alemães não tiveram tempo para destruir todos os seus documentos criptográficos, e o material capturado revelava a forma precisa do sistema de indicação, fornecia as conexões do plugboard e Grundstellung para 23 e 24 de abril e o registro dos operadores, que fornecia um longo trecho de texto simples emparelhado e mensagem criptografada para os dias 25 e 26.

As próprias tabelas bigram não faziam parte da captura, mas o Hut 8 foi capaz de usar as listas de configurações para ler retrospectivamente todo o tráfego da Kriegsmarine que foi interceptado de 22 a 27 de abril. Isso permitiu que eles fizessem uma reconstrução parcial das tabelas de bigrama e iniciassem a primeira tentativa de usar o Banburismus para atacar o tráfego da Kriegsmarine, a partir de 30 de abril. Os dias elegíveis eram aqueles em que pelo menos 200 mensagens foram recebidas e para os quais as tabelas de bigrama parciais decifraram os indicadores . O primeiro dia a ser quebrado foi 8 de maio de 1940, posteriormente celebrado como o "Dia de Foss" em homenagem a Hugh Foss , o criptanalista que realizou o feito.

Essa tarefa durou até novembro daquele ano, quando a inteligência estava muito desatualizada, mas mostrou que o Banburismus poderia funcionar. Também permitiu que muito mais das tabelas de bigrama fossem reconstruídas, o que por sua vez permitiu que os dias 14 de abril e 26 de junho fossem quebrados. No entanto, a Kriegsmarine mudou as tabelas de bigrama em 1º de julho. No final de 1940, grande parte da teoria do sistema de pontuação do Banburismus havia sido elaborada.

A pitada Primeira Lofoten da traineira Krebs em 03 de março de 1941 desde que as chaves completas para fevereiro - mas há mesas bigrama ou livro K . As consequentes descriptografias permitiram que o sistema de pontuação estatística fosse refinado para que o Banburismus pudesse se tornar o procedimento padrão contra o Kriegsmarine Enigma até meados de 1943.

Princípios

O Banburismus utilizou uma fraqueza no procedimento do indicador (as configurações da mensagem criptografada) do tráfego do Kriegsmarine Enigma. Ao contrário dos procedimentos do Exército Alemão e do Enigma da Força Aérea , o Kriegsmarine usava um Grundstellung fornecido por listas-chave e, portanto, era o mesmo para todas as mensagens em um determinado dia (ou dois dias). Isso significava que os indicadores de três letras estavam todos codificados com as mesmas configurações do rotor, de modo que todos estavam em profundidade uns com os outros. Normalmente, os indicadores para duas mensagens nunca eram os mesmos, mas poderia acontecer que, no meio de uma mensagem, as posições do rotor se tornassem as mesmas da posição inicial dos rotores para outra mensagem, as partes das duas mensagens que se sobrepunham desta forma foram em profundidade.

A extremidade esquerda de uma "Folha de Banbury" da Segunda Guerra Mundial encontrada em 2014 no espaço do telhado da Cabana 6 em Bletchley Park .

O princípio por trás do Banburismus é relativamente simples (e parece ser bastante semelhante ao Índice de Coincidência ). Se duas sentenças em inglês ou alemão são escritas uma acima da outra, e é feita uma contagem de quantas vezes uma letra em uma mensagem é igual à letra correspondente na outra mensagem; haverá mais correspondências do que ocorreria se as sentenças fossem sequências de letras aleatórias. Para uma sequência aleatória, espera-se que a taxa de repetição para letras únicas seja de 1 em 26 (cerca de 3,8%), e para as mensagens da Marinha alemã, foi mostrado ser 1 em 17 (5,9%). Se as duas mensagens forem profundas, as correspondências ocorrerão exatamente como ocorreram nos textos simples. No entanto, se as mensagens não forem profundas, os dois textos criptografados serão comparados como se fossem aleatórios, dando uma taxa de repetição de cerca de 1 em 26. Isso permite que um invasor pegue duas mensagens cujos indicadores diferem apenas no terceiro caractere, e deslize-os um contra o outro procurando o padrão de repetição gratuito que mostra onde eles se alinham em profundidade.

A comparação de duas mensagens para procurar repetições foi facilitada ao perfurar as mensagens em cartões finos de cerca de 250 mm de altura (10 ") por vários metros de largura (eles tinham cartões diferentes para comprimentos de mensagem diferentes). Um orifício na parte superior de um coluna no cartão representava um 'A' naquela posição, um orifício na parte inferior representava um 'Z'. Os dois cartões de mensagem foram colocados um em cima do outro em uma caixa de luz e onde a luz brilhou, havia uma repetição. Isso tornou muito mais simples detectar e contar as repetições. Os cartões foram impressos em Banbury, em Oxfordshire. Eles ficaram conhecidos como "banburies" em Bletchley Park e, portanto, o procedimento que os utiliza: Banburismus.

A aplicação do procedimento de scritchmus (veja abaixo) dá uma pista quanto ao possível rotor direito.

Exemplo

Mensagem com indicador " VFG ": XCYBGDSLVWBDJLKWIPEHVYGQZWDTHRQXIKEESQSSPZXARIXEABQIRUCKHGWUEBPF

Mensagem com indicador " VFX ": YNSCFCCPVIPEMSGIZWFLHESCIYSPVRXMCFQAXVXDVUQILBJUABNLKMKDJMENUNQ

O Hut 8 colocaria isso em banburies e contaria as repetições para todos os deslocamentos válidos - 25 letras a +25 letras. Existem duas posições promissoras:

XCYBGDSLVWBDJLKWIPEHVYGQZWDTHRQXIKEESQSSPZXARIXEABQIRUCKHGWUEBPF
        YNSCFCCPVIPEMSGIZWFLHESCIYSPVRXMCFQAXVXDVUQILBJUABNLKMKDJMENUNQ
                      - --  -   -          -  -   --

Este deslocamento de oito letras mostra nove repetições, incluindo dois bigramas, em uma sobreposição de 56 letras (16%).

A outra posição promissora é parecida com esta:

XCYBGDSLVWBDJLKWIPEHVYGQZWDTHRQXIKEESQSSPZXARIXEABQIRUCKHGWUEBPF
       YNSCFCCPVIPEMSGIZWFLHESCIYSPVRXMCFQAXVXDVUQILBJUABNLKMKDJMENUNQ
                ---

Este deslocamento de sete mostra apenas um único trigrama em uma sobreposição de 57 letras.

O método de Turing de acumular uma pontuação de vários decibãs permite o cálculo de qual dessas situações tem mais probabilidade de representar mensagens em profundidade. Como era de se esperar, o primeiro é o vencedor com chances de 5: 1, o último é de apenas 2: 1.

Turing calculou as pontuações para o número de repetições simples em sobreposições de tantas letras e o número de bigramas e trigramas. Os tetragramas geralmente representavam a palavra alemã no texto simples e suas pontuações eram calculadas de acordo com o tipo de mensagem (da análise de tráfego) e até mesmo sua posição na mensagem. Estes foram tabulados e os valores relevantes somados pelos banburistas ao avaliar pares de mensagens para ver quais eram provavelmente mais profundas.

Bletchley Park usou a convenção de que o texto simples do indicador "VFX", estando oito caracteres à frente de "VFG", ou (em termos de apenas a terceira letra diferente), que "X = G + 8".

Scritchmus

Scritchmus era a parte do procedimento do Banburismus que poderia levar à identificação da roda direita (rápida). O Banburist pode ter evidências de vários pares de mensagens (com apenas a terceira letra indicadora diferente) mostrando que "X = Q − 2", "H = X − 4" e "B = G + 3". Ele pesquisaria as folhas de decibãs para todas as distâncias com chances melhores do que 1: 1 (ou seja, com pontuações ≥ +34). Foi então feita uma tentativa de construir o 'alfabeto da roda final' formando 'cadeias' de letras da roda final a partir dessas repetições. Eles poderiam então construir uma "cadeia" da seguinte forma:

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

Se isso for comparado em deslocamentos progressivos com a sequência de letras conhecida de um rotor Enigma, algumas possibilidades são descontadas devido à violação da propriedade "recíproca" ou da propriedade "não autocifrável" da máquina 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

O chamado "alfabeto da roda final" já está limitado a apenas nove possibilidades, simplesmente estabelecendo uma cadeia de letras de cinco letras derivadas de meros quatro pares de mensagens. A Hut 8 agora tentaria encaixar outras cadeias de letras - aquelas sem letras em comum com a primeira cadeia - nesses nove candidatos a alfabetos de roda final.

Eventualmente, eles esperam ficar com apenas um candidato, talvez com esta aparência:

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

Não apenas isso, mas o alfabeto da roda final força a conclusão de que a roda final é na verdade "Rotor I". Isso ocorre porque "Rotor II" teria causado um giro no meio da roda ao passar de "E" para "F", mas isso está no meio da corrente de letras "F ---- A - D --- O ". Da mesma forma, todos os outros turnovers da roda central possíveis são excluídos. O rotor I gira entre "Q" e "R", e essa é a única parte do alfabeto que não é distribuída por uma corrente.

O fato de as diferentes rodas Enigma terem diferentes pontos de rotação foi, presumivelmente, uma medida dos projetistas da máquina para melhorar sua segurança. No entanto, essa mesma complicação permitiu que Bletchley Park deduzisse a identidade da roda final.

Roda do meio

Uma vez que a roda final é identificada, esses mesmos princípios podem ser estendidos para lidar com o rotor do meio, embora com a complexidade adicional de que a pesquisa é por sobreposições em pares de mensagens que compartilham apenas a primeira letra do indicador, e que as sobreposições poderiam, portanto, ocorrer no topo a 650 caracteres de distância.

A carga de trabalho para fazer isso está além do trabalho manual, então a BP perfurou as mensagens em cartões de 80 colunas e usou máquinas Hollerith para procurar por repetições de tetragramas ou melhor. Isso disse a eles quais banburies instalar nas caixas de luz (e com quais sobreposições) para avaliar todo o padrão de repetição.

Armado com um conjunto de prováveis ​​sobreposições da roda central, o Hut 8 poderia compor correntes de letras para a roda central da mesma forma que foi ilustrado acima para a roda final. Isso, por sua vez (depois de Scritchmus), daria pelo menos um alfabeto parcial da roda do meio e, com sorte, pelo menos algumas das opções possíveis de rotor para a roda do meio poderiam ser eliminadas do conhecimento de rotação (como foi feito na identificação da roda final).

Juntas, as prováveis ​​rodas do lado direito e do meio dariam um conjunto de corridas de bomba durante o dia, que seriam significativamente reduzidas das 336 possíveis.

Veja também

Referências

Bibliografia

Leitura adicional

links externos