Gbitten

Meet-in-the-middle é um ataque a sistemas criptográficos que permite reduzir a robustez de sistema que utiliza um algorítmo duas vezes, como por exemplo o Double DES.

Double DES

Meet-in-the-middle tem um princípio simples, porem depende de muito recurso de memória. Imagine o seguinte mecanismo de criptografia:

cryptotext = encripta(y,encripta(x,plaintext))

e consequentemente:

plaintext = decripta(x,decripta(y,cryptotext))

Sendo que as chaves "x" e "y" tem 64 bits cada.

Para realizar o meet-in-the-middle, o agressor precisa conhecer um par "cryptotext" e "plaintext" válido para as chaves x e y (known-plaintext attack). Então ele deve:

1) Gerar valores M para todas as combinações de chaves possíveis (x₁, x₂, x₃, ...):

M1 = encripta(x1,plaintext)
M2 = encripta(x2,plaintext)
M3 = encripta(x3,plaintext)
...

São 2⁶⁴ chaves possíveis, portanto serão 2⁶⁴ valores de M. Todos os valores M e suas chaves correspondentes devem ser armazenados em uma tabela hash (daí a necessidade de muita memória). O esforço realizado neste passo é de 2⁶⁴ operações.

2) Gerar valores N para todas as combinações de chaves possíveis (y₁, y₂, y₃, ...).

N1 = decripta(y1,cryptotext)
N2 = decripta(y2,cryptotext)
N3 = decripta(y3,cryptotext)
...

São 2⁶⁴ chaves possíveis, portanto serão 2⁶⁴ valores de N. A cada valor N calculado, deve-se buscar o um valor igual de M na tabela hash gerada no passo 1. Quando os valores de N e M forem iguais se encontrarão os valores correspondentes das chaves x e y. O esforço realizado neste passo foi de 2⁶⁴ operações.

O esforço total para quebrar as chaves foi de 2⁶⁴ + 2⁶⁴ = 2⁶⁵. Ou seja, foi muito menor que quebrar um algorítmo de 128 bits, na qual o esforço é da ordem de 2¹²⁸.

Marcadores: Ataque

postado por Gustavo Araujo Bittencourt  # 4:12 PM