Introdução - O que é a Enigma?

Com a chegada da Segunda Guerra Mundial, os países envolvidos viram a necessidade de implementar métodos mais seguros de criptografia para que as comunicações entre rádios e outras comunicações militares não pudessem ser facilmente interceptadas e decifradas, e a Enigma foi a máquina eletromecânica de criptografia adotada pela Alemanha na Segunda Guerra Mundial.

Ao longo da Guerra, muitos pesquisadores aliados estiveram envolvidos na solução da Enigma, ou melhor, nas técnicas de decriptação das mensagens intereceptadas. Suas pesquisas se baseavam em ‘KPA’ - “Known-plaintext attack”, provalmente porque as mensagens interceptadas se limitavam a somente 200 caracteres, o que dificultaria um ataque “ciphertext only”.

Esse resumo é bem breve, então para mais detalhes de como as soluções foram desenvolvidas tanto pelos Polacos Marian Rejewski, Henryk Zygalski e Jerzy Rózycki quanto pelos Britânicos de Bletchey Park com Alan Turing e Gordon Welchman, e para uma explicação mais detalhada das equações presentes no sistema de criptografia, visite o artigo original.

Os Mecanismos da Enigma

1. Uma Breve Descrição

Ao longo dos anos, a máquina Enigma assumiu algumas formas, contudo as alterações não mudaram muito seu escopo externo, mantendo assim a aparência de uma caixa registradora com uma máquina datilográfica.

cover

Ela era formada por 5 componentes:

  • Teclado
  • Plugboard
  • Rotores
  • Refletor
  • Lâmpadas

Assim, o operador pressionava uma tecla, fazendo com que a corrente elétrica passasse para o plugboard, em seguida pelos 3 rotores, da direita para a esquerda, e refletor, nessa sequência. E como o nome já diz, o refletor, com sua própria permutação, fazia com que a corrente realizasse o caminho inverso até chegar na lampboard, iluminando o caractere obtido.

animation

1.1. Teclado e Lâmpadas

O teclado e as lâmpadas representam, respectivamente, o input e o output de um caractere na máquina Enigma. Na versão original, a Enigma possui 26 lâmpadas representando as letras do alfabeto, o mesmo vale para o teclado.

Quando o processo se encerra, a lâmpada acende com a letra encriptada.

1.2. Plugboard

A Plugboard é o único mecanismo que só existe na versão militar da Enigma,

Esse elemento permitia a alteração manual de pares de letras entre si - a parte monoalfabetica da cifra - embaralhando o Alfabeto, e portanto, a mensagem. Essa funcionalidade se dava por cabos com ‘jacks’ nas pontas que conectavam as duas letras em questão.

Esse mecanismo permitia uma permutação adicional antes da entrada nos rotores, adicionando uma camada extra de complexidade à criptografia.

Assim, caso o par “AZ” fosse escolhido, o sinal “A” passaria do teclado para a plugboard, que então se tornaria “Z” e o mesmo vale no caminho inverso.

1.3. Rotores

Os rotores eram o coração da Enigma. Eles eram discos circulares que contavam com 26 contatos elétricos dos dois lados, e cada contato era conectado “aleatoriamente” a outro do lado oposto.

Quando uma tecla do Teclado era pressionada, uma corrente elétrica passava do primeiro rotor, que girava para uma posição diferente. Assim, a corrente elétrica fluia por um conjunto diferente de contatos, embaralhando a mensagem.

rotoranimation

A Enigma possuia 8 possibilidades de rotores e cada um deles mapeava uma letra do alfabeto para um outra. Esse mapeamento é chamado de Permutação ou Wiring.

Abaixo estão representadas essas permutações:

  • Rotor I : EKMFLGDQVZNTOWYHXUSPAIBRCJ Notch: Q
  • Rotor II : AJDKSIRUXBLHWTMCQGZNPYFVOE Notch: E
  • Rotor III : BDFHJLCPRTXVZNYEIWGAKMUSQO Notch: V
  • Rotor IV : ESOVPZJAYQUIRHXLNFTGKDCMWB Notch: J
  • Rotor V : VZBRGITYUPSDNHLXAWMJQOFECK Notch: Z
  • Rotor VI : JPGVOUMFYQBENHZRDKASXLICTW Notches: Z+M
  • Rotor VII : NZJHGRCXMYSWBOUFAIVLPEKQDT Notches: Z+M
  • Rotor VIII : FKQHTLXOCBJSPDZRAMEWNIUYGV Notches: Z+M

1.3.1. Notches:

A melhor maneira, talvez, de entender como funciona o Notch, seja com uma alusão ao Relógio.

O Ponteiro dos Segundos precisa dar uma volta completa (60s) no relógio para que o Ponteiro dos Minutos mova uma posição e esse por sua vez precisa dar uma volta completa (60 min) para que o Ponteiro das Horas mova uma posição.

Assim, para que o ponteiro das horas mova uma posição, o Ponteiro dos Segundos precisa realizar 60 voltas completas, que é equivalente a 3600 segundos.

Clock

Voltando para os rotores, em uma configuração de rotores I-II-III, em que a corrente vem da plugboard para o rotor III.

Para que o rotor II mova uma posição, eu preciso que o rotor III chegue no notch (letra V), que no caso do relógio eram 60 voltas completas com ponteiro iniciando no 12.

Assim, quando o rotor III estiver na posição “V”, a próxima letra digitada fará com que o rotor II mova uma posição.

Cada rotor possui um notch diferente e por volta de 1941, três rotores foram introduzidos com dois notches, ou seja, faria com que o próximo rotor girasse dobro de vezes.

1.3.2. Rings:

A configuração dos ‘Rings’ ou Anéis afetava o mapeamento interno dos rotores e por sua vez, o notch.

Esse anel era um círculo que ficava ao redor do rotor contendo o alfabeto impresso. Assim, era possível rotacionar esse alfabeto alterando a permutação interna dos rotores.

Caso a ‘Ring Setting’ do rotor de tipo IV fosse 2, o Notch seria alterado de “J” para “H”.

CryptoMuseaum

1.4. Refletor

Em seguida, temos o Refletor, que também possui 26 contatos de um lado. Entretanto, ao contrário dos Rotores, um contato é conectado a outro do mesmo lado, retornando a corrente para fazer o caminho inverso até as lâmpadas.

A Enigma possuía três tipos de refletores, representados por:

  • A : EJMZALYXVBWFCRQUONTSPIKHGD
  • B : YRUHQSLDPXNGOKMIEBFZCWVJAT
  • C : FVPJIAOYEDRZXWGCTKUQSBNMHL

Para ilustrar:

Em uma máquina Enigma equipada com um refletor do tipo B, quando o sinal correspondente a letra “A” chegava do rotor esquerdo para o refletor, o sinal passado de volta seria a letra “Y”.

Por causa desse componente que a máquina era capaz de tanto encriptar mensagens quanto decriptá-las, até porque cada letra segue um caminho simétrico.

2. Testes de Mensagem:

Para testar o funcionamento da Enigma implementada, é necessário escolher as configurações iniciais dos rotores, rings e as conexões da plugboard e cifrar um texto arbitrário.

A mensagem original é obtida de volta quando se encripta a cifra com as mesmas configurações iniciais em que a mensagem foi encriptada.

Dada a mensagem m = “GRISUFRJ”, o teste será encriptar m com as seguintes condições:

Rotores=(I,II,III), Keys=(E,D,P), Rings=(4,3,14) e Plugboard=(GR, IS, UF).

ENIGMA_TEST

3. Gillogly’s Attack

Esse ataque brute-force foi publicado em 1995 na Cryptologia por Ph.D. James J. Gillogly.

Ele consiste em encontrar as componentes da enigma utilizadas e na ordem que melhor se encaixam individualmente através de testes estatísticos.

Como durante a Segunda Guerra um ataque brute-force ciphertext only não era viável, tanto pelos tamanhos das mensagens que deveriam ser curtas (apesar dessa restrição ter sido desrespeitada diversas vezes) quanto pelo poder computacional da época, as soluções vistas anterioemente se baseavam em known plaintext attacks. Com o poder computacional atual e com mensagens de tamanho arbitrariamente grande, é possível implementar um ataque ciphertext only.

3.1. Quantidade de Configurações:

Para dar uma noção de como se daria a quantidade de diferentes configurações podem ser utilizadas:

  • Uma máquina Enigma contém 3 rotores funcionando simultaneamente, logo devem ser escolhidos 3 de 8 rotores disponíveis, o que é equivalente a um arranjo simples.

    Prob1

  • Para cada escolha de rotores, devem ser testadas 26 posições iniciais, que é:

    Prob2

  • Além disso, para cada uma dessas possibilidades acima, as configurações de anéis deveriam ser checadas. Contudo, como já foi explicitado nos problemas da enigma, podemos ignorar pelo menos o anel do rotor esquerdo e mantê-lo como zero, o que resulta em:

    Prob3

  • Por fim, devemos encontrar as conexões na Plugboard, que no máximo tem 10 pares conectados. Sabemos então, que:

    1. 6 letras não estão conectadas
    2. A ordem dos pares agrupados não importa : (Par1, Par2, …, Par10) = (Par10, Par1, …, Par2)
    3. A ordem em que as letras são conectadas também não importa (”AB” = “BA”)

    Assim, obtemos:

    Prob4

O total de possibilidades torna a checagem de cada uma das configurações impossível. Felizmente, esse número astronômico pode ser reduzido com ferramentas estatísticas, filtrando os melhores resultados em cada etapa.

3.2. Índice de Coincidência:

O índice de coindicência, ou teste Kappa, é definido pela probabilidade de escolher duas letras iguais de uma mesma mensagem encriptada, seja ela uma cifra mono ou polialfabética.

A sua fórmula é facilmente obtida:

IOC1

onde n_i representa a frequência da letra i na cifra e N representa o tamanho da mensagem.

Assim, a fórmula pode ser reduzida a:

IOC2

Foi através dessa ferramenta que os polacos foram capazes de descobrir que se tratava de uma cifra polialfabética.

3.3. Trigram:

O trigram é um caso de N-gram, que é usado para processamento de linguagem natural em análise estátistica de textos. O trigram procura responder a seguinte pergunta: qual a probabilidade de ocorrer uma sequência espeífica de três elementos consecutivos no texto?

Então, em termos de probabilidade, dado dois termos anteriores ω1, ω2, qual a probabilidade do próximo ser ω3?

TRIGRAM

O modelo escolhido para a análise estatística da mensagem encriptada foi retirado do site PracticalCryptography.

3.5. Ordem dos Rotores:

De ínicio, a Enigma deve manter os anéis em (0,0,0) e a plugboard sem conexões.

Para cada uma das 336 opções de rotores disponíveis, começa a busca por suas posições iniciais.

A configuração que melhor atende à mensagem será obtida ao encriptar novamente a mensagem e calcular o Índice de Coincidência dessa nova cifra.

Por minha escolha, mantive os 3 melhores resultados e seus possíveis plaintexts.

Observe que, por começar com anéis em (0,0,0) o código tentará ajustar as posições iniciais compensando os anéis.

3.6. Ordem dos Anéis:

Com os 3 melhores rotores e respectivas posições iniciais, procuramos pelos anéis que mais aproximam a mensagem encriptada de uma língua natural.

A busca pelo anel do rotor esquerdo é desnecessária, visto que ele quase nunca roda, restando a busca de 676 diferentes posições de anéis, portanto:

RING1

Novamente, utiliza-se o Índice de Coincidência e classifico novamente em relação sua pontuação. Contudo, diferentemente da busca dos rotores, é possível descobrir sua pontuação em IoC individualmente.

Configure os anéis para (0,0,i), onde i é o anel correspondente ao índice do laço ‘for’ e inicie a busca pelo melhor anel para o rotor direito e mantenha o valor de i que melhor pontuou no índice de coincidência, aqui armazenaremos ele como bestScore(i).

Para o segundo anel, utilize outro laço ‘for’ passando agora pelo rotor do meio com configuração de anel (0, j, bestScore(i)) e de novo encripte a mensagem com a configuração correspondente e mantenha o valor j com melhor pontuação.

3.7. Conexões da Plugboard:

O passo final do algoritmo recebe a melhor configuração de Enigma até então e procura por conexões que aumentam sua pontuação no Trigram.

A função que eu implementei recebe como parâmetro a quantidade de conexões desejada, mas caso desejar pode manter o valor máximo 10 como padrão.

Em um laço de n_conexões iterações, procuro o conector com melhor pontuação no Trigram e mantenho essa conexão na Enigma, ou seja, em cada iteração um par de letras é escolhido e ‘plugado’ na Enigma virtual, sempre em busca de um conector que melhore sua pontuação.

4. Resultados:

A mensagem encriptada é:

CIFRA

4.1. Rotores:

1LUGAR

2LUGAR

3LUGAR

4.2. Anéis:

BESTRINGS

4.3. Plugboard:

BESTCONNECT

A mensagem decriptada é o primeiro parágrafo do artigo de Gillogly:

" Polish and British solutions to encrypted German Enigma traffic relied on sophisticated known plaintext attacks. The rotor wiring was known through brilliant cryptanalysis by the Polish mathematician Marian Rejewski and later through capture of naval Enigma rotors"

5. Referências: