Ataque Meet-in-the-middle - Meet-in-the-middle attack

O ataque meet-in-the-middle ( MITM ), um conhecido ataque de texto simples, é um ataque criptográfico de troca espaço-tempo genérico contra esquemas de criptografia que dependem da execução de várias operações de criptografia em sequência. O ataque MITM é a principal razão pela qual Double DES não é usado e porque uma chave Triple DES (168 bits) pode ser forçada por um invasor com 2 ^{56 de} espaço e 2 ¹¹² operações.

Descrição

Ao tentar melhorar a segurança de uma cifra de bloco, uma ideia tentadora é criptografar os dados várias vezes usando várias chaves. Pode-se pensar que isso dobra ou mesmo n- duplica a segurança do esquema de criptografia múltipla, dependendo do número de vezes que os dados são criptografados, porque uma pesquisa exaustiva em todas as combinações possíveis de chaves (força bruta simples) levaria 2 ^{n · K} tentativas se os dados forem criptografados com chaves de k bits n vezes.

O MITM é um ataque genérico que enfraquece os benefícios de segurança do uso de várias criptografias, armazenando valores intermediários das criptografias ou descriptografias e usando-os para melhorar o tempo necessário para a força bruta das chaves de descriptografia. Isso torna um ataque Meet-in-the-Middle (MITM) um ataque criptográfico de troca espaço-tempo genérico .

O ataque MITM tenta encontrar as chaves usando tanto o intervalo (texto cifrado) quanto o domínio (texto simples) da composição de várias funções (ou cifras de bloco) de modo que o mapeamento para a frente através das primeiras funções seja o mesmo que o mapeamento para trás (inverso imagem) através das últimas funções, literalmente reunião no meio da função composta. Por exemplo, embora Double DES criptografe os dados com duas chaves diferentes de 56 bits, Double DES pode ser quebrado com 2 ⁵⁷ operações de criptografia e descriptografia.

O MITM multidimensional (MD-MITM) usa uma combinação de vários ataques MITM simultâneos como descrito acima, onde a reunião acontece em várias posições na função composta.

História

Diffie e Hellman propuseram pela primeira vez o ataque meet-in-the-middle em uma expansão hipotética de uma cifra de bloco em 1977. Seu ataque usou uma compensação de espaço-tempo para quebrar o esquema de criptografia dupla em apenas duas vezes o tempo necessário para quebrar o único - esquema de criptografia.

Em 2011, Bo Zhu e Guang Gong investigaram o ataque multidimensional meet-in-the-middle e apresentaram novos ataques às cifras de bloco GOST , KTANTAN e Hummingbird-2 .

Meet-in-the-middle (1D-MITM)

Suponha que alguém queira atacar um esquema de criptografia com as seguintes características para um determinado texto simples P e texto cifrado C :

${\ displaystyle {\ begin {alinhados} C & = {\ mathit {ENC}} _ ​​{k_ {2}} ({\ mathit {ENC}} _ ​​{k_ {1}} (P)) \\ P & = {\ mathit {DEC}} _ ​​{k_ {1}} ({\ mathit {DEC}} _ ​​{k_ {2}} (C)) \\\ end {alinhado}}}$

onde ENC é a função de criptografia, DEC a função de descriptografia definida como ENC ⁻¹ (mapeamento inverso) e k ₁ e k ₂ são duas chaves.

A abordagem ingênua para forçar este esquema de criptografia é descriptografar o texto cifrado com todos os k ₂ possíveis e descriptografar cada uma das saídas intermediárias com todos os k ₁ possíveis , para um total de 2 ^{k ₁} × 2 ^{k ₂} (ou 2 ^{k ₁ + k ₂} ) operações.

O ataque meet-in-the-middle usa uma abordagem mais eficiente. Ao descriptografar C com k ₂ , obtém-se a seguinte equivalência:

${\ displaystyle {\ begin {alinhados} C & = {\ mathit {ENC}} _ ​​{k_ {2}} ({\ mathit {ENC}} _ ​​{k_ {1}} (P)) \\ {\ mathit { DEC}} _ ​​{k_ {2}} (C) & = {\ mathit {DEC}} _ ​​{k_ {2}} ({\ mathit {ENC}} _ ​​{k_ {2}} [{\ mathit {ENC }} _ {k_ {1}} (P)]) \\ {\ mathit {DEC}} _ ​​{k_ {2}} (C) & = {\ mathit {ENC}} _ ​​{k_ {1}} ( P) \\\ fim {alinhado}}}$

O atacante pode calcular ENC _{k 1} ( P ) para todos os valores de k ₁ e DEC _{k 2} ( C ) para todos os valores possíveis de k ₂ , para um total de 2 ^{k ₁} + 2 ^{k ₂} (ou 2 ^{k ₁ +1} , se k ₁ e k ₂ tiverem o mesmo tamanho) operações. Se o resultado de qualquer uma das operações ENC _{k 1} ( P ) corresponder ao resultado das operações DEC _{k 2} ( C ), o par de k ₁ e k ₂ é possivelmente a chave correta. Essa chave potencialmente correta é chamada de chave candidata . O invasor pode determinar qual chave candidata está correta testando-a com um segundo conjunto de teste de texto simples e texto cifrado.

O ataque MITM é uma das razões pelas quais o Data Encryption Standard (DES) foi substituído pelo Triple DES e não pelo Double DES. Um invasor pode usar um ataque MITM para força bruta Double DES com 2 ⁵⁷ operações e 2 ^{56 de} espaço, tornando-o apenas uma pequena melhoria em relação ao DES. Triple DES usa uma chave de "comprimento triplo" (168 bits) e também é vulnerável a um ataque de encontro no meio em 2 ⁵⁶ espaço e 2 ¹¹² operações, mas é considerado seguro devido ao tamanho de seu espaço de chave.

Uma ilustração do ataque 1D-MITM

Algoritmo MITM

Calcule o seguinte:

• ${\ displaystyle {\ mathit {SubCipher}} _ {1} = {\ mathit {ENC}} _ ​​{f_ {1}} (k_ {f_ {1}}, P), \; \ forall k_ {f_ {1 }}\tinta}$:

  e salve cada um junto com o correspondente em um conjunto A${\ displaystyle {\ mathit {SubCipher}} _ {1}}$${\ displaystyle k_ {f_ {1}}}$

• ${\ displaystyle {\ mathit {SubCipher}} _ {1} = {\ mathit {DEC}} _ ​​{b_ {1}} (k_ {b_ {1}}, C), \; \ forall k_ {b_ {1 }}\tinta}$:

  e compare cada novo com o conjunto A${\ displaystyle {\ mathit {SubCipher}} _ {1}}$

Quando for encontrada uma correspondência, manter como candidato par de chaves-na uma tabela T . Teste os pares em T em um novo par de para confirmar a validade. Se o par de chaves não funcionar neste novo par, faça MITM novamente em um novo par de . ${\ displaystyle k_ {f_ {1}}, k_ {b_ {1}}}$${\ displaystyle (P, C)}$${\ displaystyle (P, C)}$

Complexidade MITM

Se o tamanho da chave for k , este ataque usa apenas 2 ^{k + 1} criptografias (e decriptografias) e O (2 ^k ) de memória para armazenar os resultados dos cálculos de encaminhamento em uma tabela de pesquisa , em contraste com o ataque ingênuo, que precisa de 2 ^{2 · K} criptografias, mas espaço O (1).

MITM multidimensional (MD-MITM)

Embora 1D-MITM possa ser eficiente, um ataque mais sofisticado foi desenvolvido: ataque de encontro no meio multidimensional , também abreviado como MD-MITM . É preferível quando os dados foram criptografados usando mais de 2 criptografias com chaves diferentes. Em vez de se encontrar no meio (um lugar na sequência), o ataque MD-MITM tenta alcançar vários estados intermediários específicos usando os cálculos para frente e para trás em várias posições na cifra.

Suponha que o ataque tenha que ser montado em uma cifra de bloco, onde a criptografia e descriptografia são definidas como antes:

${\ displaystyle C = {\ mathit {ENC}} _ ​​{k_ {n}} ({\ mathit {ENC}} _ ​​{k_ {n-1}} (... ({\ mathit {ENC}} _ ​​{ k_ {1}} (P)) ...))}$

${\ displaystyle P = {\ mathit {DEC}} _ ​​{k_ {1}} ({\ mathit {DEC}} _ ​​{k_ {2}} (... ({\ mathit {DEC}} _ ​​{k_ { n}} (C)) ...))}$

isto é um texto simples P é criptografado várias vezes usando uma repetição da mesma cifra de bloco

Uma ilustração do ataque MD-MITM

O MD-MITM foi usado para criptanálise de, entre muitas, a cifra de bloco GOST , onde foi demonstrado que um 3D-MITM reduziu significativamente a complexidade de tempo para um ataque a ele.

Algoritmo MD-MITM

Calcule o seguinte:

${\ displaystyle {\ mathit {SubCipher}} _ {1} = {\ mathit {ENC}} _ ​​{f_ {1}} (k_ {f_ {1}}, P) \ qquad \ forall k_ {f_ {1} }\tinta}$

e salve cada um junto com o correspondente em um conjunto .${\ displaystyle {\ mathit {SubCipher}} _ {1}}$${\ displaystyle k_ {f_ {1}}}$${\ displaystyle H_ {1}}$

${\ displaystyle {\ mathit {SubCipher}} _ {n + 1} = {\ mathit {DEC}} _ ​​{b_ {n + 1}} (k_ {b_ {n + 1}}, C) \ qquad \ forall k_ {b_ {n + 1}} \ em K}$

e salve cada um junto com o correspondente em um conjunto .${\ displaystyle {\ mathit {SubCipher}} _ {n + 1}}$${\ displaystyle k_ {b_ {n + 1}}}$${\ displaystyle H_ {n + 1}}$

Para cada suposição possível no estado intermediário, calcule o seguinte: ${\ displaystyle s_ {1}}$

${\ displaystyle {\ mathit {SubCipher}} _ {1} = {\ mathit {DEC}} _ ​​{b_ {1}} (k_ {b_ {1}}, s_ {1}) \ qquad \ forall k_ {b_ {1}} \ em K}$

e para cada combinação entre este e o conjunto , salve e em um novo conjunto .${\ displaystyle {\ mathit {SubCipher}} _ {1}}$${\ displaystyle H_ {1}}$${\ displaystyle k_ {b_ {1}}}$${\ displaystyle k_ {f_ {1}}}$${\ displaystyle T_ {1}}$

${\ displaystyle {\ mathit {SubCipher}} _ {2} = {\ mathit {ENC}} _ ​​{f_ {2}} (k_ {f_ {2}}, s_ {1}) \ qquad \ forall k_ {f_ {2}} \ em K}$

e salve cada um junto com o correspondente em um conjunto .${\ displaystyle {\ mathit {SubCipher}} _ {2}}$${\ displaystyle k_ {f_ {2}}}$${\ displaystyle H_ {2}}$

Para cada suposição possível em um estado intermediário, calcule o seguinte: ${\ displaystyle s_ {2}}$

• ${\ displaystyle {\ mathit {SubCipher}} _ {2} = {\ mathit {DEC}} _ ​​{b_ {2}} (k_ {b_ {2}}, s_ {2}) \ qquad \ forall k_ {b_ {2}} \ em K}$

  e para cada combinação entre este e o conjunto , verifique também se${\ displaystyle {\ mathit {SubCipher}} _ {2}}$${\ displaystyle H_ {2}}$

  ele combina com e, em seguida, salva a combinação de subchaves em um novo conjunto .${\ displaystyle T_ {1}}$${\ displaystyle T_ {2}}$

• Para cada suposição possível em um estado intermediário, calcule o seguinte:${\ displaystyle s_ {n}}$

1. ${\ displaystyle {\ mathit {SubCipher}} _ {n} = {\ mathit {DEC}} _ ​​{b_ {n}} (k_ {b_ {n}}, s_ {n}) \ qquad \ forall k_ {b_ {n}} \ em K}$e para cada correspondência entre este e o conjunto , verifique também se ela combina com , salve e em um novo conjunto .${\ displaystyle {\ mathit {SubCipher}} _ {n}}$${\ displaystyle H_ {n}}$${\ displaystyle T_ {n-1}}$${\ displaystyle k_ {b_ {n}}}$${\ displaystyle k_ {f_ {n}}}$${\ displaystyle T_ {n}}$
2. ${\ displaystyle {\ mathit {SubCipher}} _ {n + 1} = {\ mathit {ENC}} _ ​​{f_ {n} +1} (k_ {f_ {n} +1}, s_ {n}) \ qquad \ forall k_ {f_ {n + 1}} \ in K}$e para cada combinação entre este e o conjunto , verifique também${\ displaystyle {\ mathit {SubCipher}} _ {n + 1}}$${\ displaystyle H_ {n + 1}}$

se corresponde com . Se for este o caso, então: " ${\ displaystyle T_ {n}}$

Use a combinação encontrada de subchaves em outro par de texto simples / texto cifrado para verificar a exatidão da chave. ${\ displaystyle (k_ {f_ {1}}, k_ {b_ {1}}, k_ {f_ {2}}, k_ {b_ {2}}, ..., k_ {f_ {n + 1}}, k_ {b_ {n + 1}})}$

Observe o elemento aninhado no algoritmo. A estimativa de cada valor possível em s _j é feita para cada estimativa no s _{j -1} anterior . Isso constitui um elemento de complexidade exponencial para a complexidade geral de tempo desse ataque MD-MITM.

Complexidade MD-MITM

A complexidade de tempo deste ataque sem força bruta é ⋅ ⋅${\ displaystyle 2 ^ {| k_ {f_ {1}} |} + 2 ^ {| k_ {b_ {n + 1}} |} + 2 ^ {| s_ {1} |}}$${\ displaystyle (2 ^ {| k_ {b_ {1}} |} + 2 ^ {| k_ {f_ {2}} |} + 2 ^ {| s_ {2} |}}$${\ displaystyle (2 ^ {| k_ {b_ {2}} |} + 2 ^ {| k_ {f_ {3}} |} + \ cdots))}$

Em relação à complexidade da memória, é fácil ver que são muito menores do que a primeira tabela construída de valores candidatos: à medida que i aumenta, os valores candidatos contidos em devem satisfazer mais condições, portanto, menos candidatos serão transmitidos ao destino final . ${\ displaystyle T_ {2}, T_ {3}, ..., T_ {n}}$${\ displaystyle T_ {1}}$${\ displaystyle T_ {i}}$${\ displaystyle T_ {n}}$

Um limite superior da complexidade da memória do MD-MITM é então

${\ displaystyle 2 ^ {| k_ {f_ {1}} |} + 2 ^ {| k_ {b_ {n + 1}} |} + 2 ^ {| k | - | s_ {n} |} \ cdots}$

onde k denota o comprimento de toda a chave (combinada).

A complexidade dos dados depende da probabilidade de que uma chave errada possa passar (obter um falso positivo), ou seja , onde l é o estado intermediário na primeira fase do MITM. O tamanho do estado intermediário e o tamanho do bloco são geralmente os mesmos! Considerando também quantas chaves faltam para teste após a primeira fase MITM, é . ${\ displaystyle 1/2 ^ {| l |}}$${\ displaystyle 2 ^ {| k |} / 2 ^ {| l |}}$

Portanto, após a primeira fase do MITM, existem , onde está o tamanho do bloco. ${\ displaystyle 2 ^ {| k | -b} \ cdot 2 ^ {- b} = 2 ^ {| k | -2b}}$${\ displaystyle | b |}$

Para cada vez que o valor candidato final das chaves é testado em um novo par de texto simples / texto cifrado, o número de chaves que passarão será multiplicado pela probabilidade de que uma chave possa passar, que é . ${\ displaystyle 1/2 ^ {| b |}}$

A parte do teste de força bruta (testar a chave candidata em novos pares -pares, tem complexidade de tempo , claramente para aumentar os múltiplos de b no expoente, o número tende a zero. ${\ displaystyle (P, C)}$${\ displaystyle 2 ^ {| k | -b} + 2 ^ {| k | -2b} + 2 ^ {| k | -3b} + 2 ^ {| k | -4b} \ cdots}$

A conclusão sobre a complexidade dos dados é por um raciocínio semelhante restrito por aqueles em torno de pares. ${\ displaystyle \ lceil | k | / n \ rceil}$ ${\ displaystyle (P, C)}$

Abaixo está um exemplo específico de como um 2D-MITM é montado:

Um exemplo geral de 2D-MITM

Esta é uma descrição geral de como 2D-MITM é montado em uma criptografia de cifra de bloco.

No MITM bidimensional (2D-MITM), o método é atingir 2 estados intermediários dentro da criptografia múltipla do texto simples. Veja a figura abaixo:

Uma ilustração do ataque 2D-MITM

Algoritmo 2D-MITM

Calcule o seguinte:

${\ displaystyle {\ mathit {SubCipher}} _ {1} = {\ mathit {ENC}} _ ​​{f_ {1}} (k_ {f_ {1}}, P) \ qquad \ forall k_ {f_ {1} }\tinta}$

e salve cada um junto com o correspondente em um conjunto A${\ displaystyle {\ mathit {SubCipher}} _ {1}}$${\ displaystyle k_ {f_ {1}}}$

${\ displaystyle {\ mathit {SubCipher}} _ {2} = {\ mathit {DEC}} _ ​​{b_ {2}} (k_ {b_ {2}}, C) \ qquad \ forall k_ {b_ {2} }\tinta}$

e salve cada um junto com o correspondente em um conjunto B.${\ displaystyle {\ mathit {SubCipher}} _ {2}}$${\ displaystyle k_ {b_ {2}}}$

Para cada possível suposição em um estado intermediário de entre e calcular o seguinte: ${\ displaystyle {\ mathit {SubCipher}} _ {1}}$${\ displaystyle {\ mathit {SubCipher}} _ {2}}$

• ${\ displaystyle {\ mathit {SubCipher}} _ {1} = {\ mathit {DEC}} _ ​​{b_ {1}} (k_ {b_ {1}}, s) \ qquad \ forall k_ {b_ {1} }\tinta}$

  e para cada combinação entre este e o conjunto A, salve e em um novo conjunto T.${\ displaystyle {\ mathit {SubCipher}} _ {1}}$${\ displaystyle k_ {b_ {1}}}$${\ displaystyle k_ {f_ {1}}}$

• ${\ displaystyle {\ mathit {SubCipher}} _ {2} = {\ mathit {ENC}} _ ​​{f_ {2}} (k_ {f_ {2}}, s) \ qquad \ forall k_ {f_ {2} }\tinta}$

  e para cada correspondência entre este e o conjunto B, verifique também se ela corresponde a T para${\ displaystyle {\ mathit {SubCipher}} _ {2}}$

  se for este o caso, então:

Use a combinação encontrada de subchaves em outro par de texto simples / texto cifrado para verificar a exatidão da chave. ${\ displaystyle (k_ {f_ {1}}, k_ {b_ {1}}, k_ {f_ {2}}, k_ {b_ {2}})}$

Complexidade 2D-MITM

A complexidade de tempo deste ataque sem força bruta, é

${\ displaystyle 2 ^ {| k_ {f_ {1}} |} + 2 ^ {| k_ {b_ {2}} |} + 2 ^ {| s |} \ cdot \ left (2 ^ {| k_ {b_ {1}} |} + 2 ^ {| k_ {f_ {2}} |} \ right)}$

onde | ⋅ | denota o comprimento.

O consumo da memória principal é restringido pela construção dos conjuntos A e B onde T é muito menor que os outros.

Para a complexidade dos dados, consulte a subseção sobre complexidade para MD-MITM .

Veja também

• Ataque de aniversário
• Segurança sem fio
• Criptografia
• Ataque meet-in-the-middle de 3 subconjuntos
• Ataque encontro no meio de correspondência parcial

Referências