ataque Biclique - Biclique attack

Um ataque biclique é uma variante da encontram-em-o-Média método (MITM) de análise criptográfica . Ele utiliza um biclique estrutura para aumentar o número de rodadas possivelmente atacadas pelo ataque MITM. Desde criptoanálise biclique é baseada em ataques MITM, é aplicável a ambas as cifras de bloco e (iterativos) de hash-funções . Ataques Biclique são conhecidos por terem ambos cheios quebrados AES e cheia IDEA , embora apenas com uma ligeira vantagem sobre a força bruta. Também tem sido aplicado para o KASUMI cifra e resistência preimage da meada-512 e SHA-2 funções hash.

O ataque biclique ainda é (a partir de 2015/03/13) o melhor ataque única chave conhecida publicamente em AES . A complexidade computacional do ataque é , e para AES128, AES192 e AES256, respectivamente. É o único conhecido publicamente ataque única chave-na AES que ataca o número total de rounds. Ataques anteriores atacaram variantes rodada reduzidas (tipicamente variantes reduzido para 7 ou 8 rodadas). ${\ Displaystyle 2 ^ {126,1}}$${\ Displaystyle 2 ^ {189,7}}$${\ Displaystyle 2 ^ {254,4}}$

À medida que a complexidade computacional de ataque é , é um ataque teórica, o que significa que a segurança da AES não tenha sido quebrado, e a utilização da AES permanece relativamente seguro. O ataque biclique é, no entanto, um ataque interessante, o que sugere uma nova abordagem para a realização de análise criptográfica em blocos de cifragem. O ataque também tornou mais informações a respeito da AES, uma vez que tenha posto em causa a-margem de segurança no número de rodadas aí utilizados. ${\ Displaystyle 2 ^ {126,1}}$

História

O ataque MITM original foi sugerido em primeiro lugar por Diffie e Hellman em 1977, quando discutiram as propriedades cryptanalytic de DES. Eles argumentaram que o tamanho da chave era muito pequeno, e que a reaplicação DES várias vezes com chaves diferentes pode ser uma solução para o tamanho da chave; no entanto, eles desaconselhadas usando double-DES e sugeriu triple-DES, no mínimo, devido a ataques MITM (ataques MITM pode ser facilmente aplicada a double-DES para reduzir a segurança de apenas , uma vez que se pode Bruteforce independentemente o primeiro eo segunda DES-criptografia se eles têm o sem formatação e texto cifrado). ${\ Displaystyle 2 ^ {56} * 2}$${\ Displaystyle 2 * 2 ^ {56}}$

Desde Diffie e Hellman sugeriu ataques MITM, muitas variações têm surgido que são úteis em situações, onde o ataque básico MITM é inaplicável. A variante de ataque biclique foi sugerido em primeiro lugar por Dmitry Khovratovich , Rechberger e Savelieva para utilização com uma função hash de análise criptográfica. No entanto, foi Bogdanov, Khovratovich e Rechberger que mostrou como aplicar o conceito de bicliques para a configuração de chave secreta incluindo criptoanálise bloco cifra, quando publicaram seu ataque a AES. Antes disso, ataques MITM no AES e muitas outras cifras de bloco tinha recebido pouca atenção, principalmente devido à necessidade de bits de chave independentes entre os dois 'subciphers MITM', a fim de facilitar o ataque MITM - algo que é difícil de conseguir com muitos horários chave modernos, tais como o da AES.

o biclique

Para uma explicação geral do que uma estrutura biclique é, veja o wiki páginas para bicliques .

Num ataque MITM, os keybits e , pertencentes à primeira e segunda subcipher, precisa de ser independente; ou seja, eles precisam ser independentes um do outro, então os valores intermediários combinados para o sem formatação e texto cifrado não pode ser calculado independentemente no ataque MITM (existem variantes de ataques MITM, onde os blocos podem ter Shared Key-bits. Veja o ataque MITM 3-subconjunto ). Esta propriedade é muitas vezes difícil de explorar ao longo de um maior número de rodadas, devido à difusão da cifra de atacado. Simplificando: Os mais rodadas que você ataque, o subciphers maiores você terá. Os subciphers maiores que você tem, menos chave-bits independentes entre os subciphers você terá que Bruteforce independente. Naturalmente, o número real de chaves-bits independentes em cada subcipher depende das propriedades de difusão da chave-horário. ${\ Displaystyle K_ {1}}$${\ Displaystyle K_ {2}}$

A forma como o biclique ajuda a combater o acima, é que ela permite, por exemplo, ataque de 7 ciclos de AES usando ataques MITM, e, em seguida, por utilização de uma estrutura biclique de comprimento 3 (isto é, cobre de 3 rondas de cifra), você pode mapear o estado intermediário no início da rodada 7 até o final da última rodada, por exemplo, 10 (se for AES128), atacando assim o número total de assaltos da cifra, mesmo que isso não era possível atacar essa quantidade de arredonda com um ataque básico MITM.

O significado do biclique é, portanto, para construir uma estrutura de forma eficaz, que pode mapear um valor intermediário no final do ataque MITM para o texto cifrado no final. Que texto cifrado o estado intermediário é mapeado para, no final, é claro depende da chave usada para a criptografia. A chave utilizada para mapear o estado para o texto cifrado no biclique, baseia-se nos keybits bruteforced no primeiro e segundo subcipher do ataque MITM.

A essência de ataques biclique é assim, além do ataque MITM, para ser capaz de construir uma estrutura biclique de forma eficaz, que, dependendo das keybits e pode mapear um determinado estado intermédio para o texto cifrado correspondente. ${\ Displaystyle K_ {1}}$${\ Displaystyle K_ {2}}$

Como construir o biclique

bruteforce

Obter estados intermediários e mensagens cifradas, então calcular as chaves que são mapeados entre eles. Isso requer -chave recuperações, uma vez que cada estado intermediário tem de estar ligado a todas as mensagens cifradas. ${\ Displaystyle 2 ^ {d}}$${\ Displaystyle 2 ^ {d}}$${\ Displaystyle 2 ^ {2d}}$

diferenciais-chave relacionadas independentes

(Este método foi sugerido por Bogdanov, Khovratovich e Rechberger em seu artigo: Biclique Cryptanalysis da AES completa)

Preliminar:
Lembre-se que a função do biclique é mapear os valores intermediários, para os valores de texto cifrado, com base na chave de tal forma que:${\ Displaystyle S}$${\ Displaystyle C}$${\ Displaystyle K [i, j]}$
${\ Displaystyle \ forall i, j: S_ {j} {\ xrightarrow [{f}] {K [i, j]}} C_ {i}}$

Procedimento:
Passo um: um estado intermediário ( ), um texto cifrado ( ) e uma chave ( ) é escolhido de tal modo que: , onde é a função que mapeia um estado intermédio para um texto cifrado utilizando uma determinada chave. Este é designado como o cálculo de base. ${\ Displaystyle S_ {0}}$${\ Displaystyle C_ {0}}$${\ Displaystyle K [0,0]}$${\ Displaystyle S_ {0} {\ xrightarrow [{f}] {K [0,0]}} C_ {o}}$${\ Displaystyle f}$

Passo dois: Dois conjuntos de chaves relacionadas de tamanho é escolhido. As teclas são escolhidos de tal forma que: ${\ Displaystyle 2 ^ {d}}$

• O primeiro conjunto de teclas são teclas, que cumpre as seguintes diferencial de requisitos sobre no que diz respeito ao cálculo de base:${\ Displaystyle f}$${\ Displaystyle 0 {\ xrightarrow [{f}] {\ Delta _ {i} ^ {K}}} \ Delta _ {i}}$
• O segundo conjunto de teclas são teclas, que cumpre as seguintes diferencial de requisitos sobre no que diz respeito ao cálculo de base:${\ Displaystyle f}$${\ Displaystyle \ nabla _ {J} {\ xrightarrow [{f}] {\ nabla _ {J} ^ {K}}}} 0$
• As teclas são escolhidos de tal forma que as trilhas do - e -differentials são independentes - ou seja, eles não compartilham todos os componentes não-lineares ativos.${\ Displaystyle \ Delta _ {i}}$${\ Displaystyle \ nabla _ {j}}$

Em outras palavras:
Uma diferença de entrada de 0 deve mapear a uma diferença de saída de sob uma diferença fundamental de . Todas as diferenças são em relação ao cálculo base. Uma diferença de entrada deve mapear a uma diferença de 0 a saída sob uma diferença fundamental de . Todas as diferenças são em relação ao cálculo base. ${\ Displaystyle \ Delta _ {i}}$${\ Displaystyle \ Delta _ {i} ^ {K}}$
${\ Displaystyle \ nabla _ {j}}$${\ Displaystyle \ nabla _ {J} ^ {K}}$

Passo três: Uma vez que as trilhas não partilhe quaisquer componentes não-lineares (tais como S-boxes), as trilhas podem ser combinados para obter: , que está em conformidade com as definições de ambos os diferenciais da etapa 2. É trivial para ver que o tuplo do cálculo de base, também está em conformidade, por definição, para ambos os diferenciais, como os diferenciais são em relação à base de cálculo. Substituindo em nenhuma das duas definições, irá produzir uma vez e . Isto significa que o tuplo do cálculo de base, também podem ser XOR'ed para as trilhas combinadas:
${\ Displaystyle 0 {\ xrightarrow [{f}] {\ Delta _ {i} ^ {K}}} \ Delta _ {i} \ oplus \ nabla _ {j} {\ xrightarrow [{f}] {\ nabla _ {J} ^ {K}}} 0 = \ nabla _ {J} {\ xrightarrow [{f}] {\ Delta _ {i} ^ {K} \ oplus \ nabla _ {J} ^ {K}} } \ Delta _ {i}}$

${\ Displaystyle (S_ {0}, C_ {0}, K [0,0])}$${\ S_ displaystyle {0}, C_ {0}}$ ${\ Displaystyle K [0,0]}$${\ Displaystyle 0 {\ xrightarrow [{f}] {0}} 0}$${\ Displaystyle \ Delta _ {0} = 0, \ nabla _ {0} = 0}$${\ Displaystyle \ Delta _ {0} ^ {K} = 0}$
${\ Displaystyle S_ {0} \ oplus \ nabla _ {j} {\ xrightarrow [{f}] {K [0,0] \ oplus \ Delta _ {i} ^ {K} \ oplus \ nabla _ {j} ^ {K}}} C_ {0} \ oplus \ Delta _ {i}}$

Passo Quatro: É trivial para ver que: Se este é substituído nas trilhas diferenciais combinados acima, o resultado será: Qual é a mesma que a definição, não foi anteriormente tinha acima para um biclique:
${\ Displaystyle S_ {j} = S_ {0} \ oplus \ nabla _ {j}}$
${\ Displaystyle K [i, j] = K [0,0] \ oplus \ Delta _ {i} ^ {K} \ oplus \ nabla _ {J} ^ {K}}$
${\ Displaystyle C_ {i} = C_ {0} \ oplus \ Delta _ {i}}$

${\ Displaystyle S_ {j} {\ xrightarrow [{f}] {K [i, j]}} C_ {i}}$

${\ Displaystyle \ forall i, j: S_ {j} {\ xrightarrow [{f}] {K [i, j]}} C_ {i}}$

Assim, é possível criar um biclique de tamanho ( uma vez que todas as chaves do primeiro conjunto de teclas, podem ser combinados com as chaves do segundo conjunto de chaves). Isso significa que um biclique de tamanho podem ser criados usando apenas cálculos de diferenciais e mais . Se para , em seguida, todas as chaves também será diferente na biclique. ${\ Displaystyle 2 ^ {2d}}$${\ Displaystyle 2 ^ {2d}}$${\ Displaystyle 2 ^ {d}}$${\ Displaystyle 2 ^ {d}}$${\ Displaystyle 2 ^ {2d}}$${\ Displaystyle 2 * 2 ^ {d}}$${\ Displaystyle \ Delta _ {i}}$${\ Displaystyle \ nabla _ {j}}$${\ Displaystyle f}$${\ Displaystyle \ Delta _ {i} \ neq \ nabla _ {j}}$${\ Displaystyle i + j> 0}$${\ Displaystyle K [i, j]}$

Desta forma, é como o biclique é construído na liderança ataque biclique na AES. Deve-se notar que existem algumas limitações práticas na construção bicliques com esta técnica. Quanto mais tempo o biclique é, os mais rodadas as trilhas diferenciais tem de cobrir. As propriedades de difusão da cifra, portanto, desempenha um papel crucial na eficácia da construção da biclique.

Outras maneiras de construir o biclique

Bogdanov, Khovratovich e Rechberger também descrevem uma outra maneira de construir a biclique, chamado de 'Trilhas intercalação relacionada-Key Diferencial' no artigo: "Biclique Cryptanalysis da AES Full".

procedimento Biclique Cryptanalysis

Passo um: o atacante grupos todas as teclas possíveis em chave-subconjuntos de tamanho para alguns , onde a chave de um grupo é indexado como numa matriz de tamanho . O atacante divide a cifra-se em duas sub-cifras, e (tais que ), como num ataque normal MITM. O conjunto de chaves para cada um dos sub-cifras é de cardinalidade , e é chamado e . A chave combinada dos sub-cifras é expressa com a matriz acima referida . ${\ Displaystyle 2 ^ {2d}}$${\ Displaystyle d}$${\ Displaystyle K [i, j]}$${\ DisplayStyle 2 ^ {d} \ vezes 2 ^ {d}}$${\ Displaystyle f}$${\ Displaystyle g}$${\ Displaystyle E = f \ circ g}$${\ Displaystyle 2 ^ {d}}$${\ Displaystyle K [i, 0]}$${\ Displaystyle K [0, j]}$${\ Displaystyle K [i, j]}$

Passo dois: O atacante constrói uma biclique para cada grupo de chaves. O biclique é de dimensão-d, uma vez que mapeia estados internos, para mensagens cifradas, utilizando chaves. A seção "Como construir o biclique" sugere como construir o biclique usando "diferenciais relacionadas-chave Independentes". O biclique é neste caso construída usando os diferenciais do conjunto de chaves, e , pertencendo aos sub-cifras. ${\ Displaystyle 2 ^ {2d}}$${\ Displaystyle 2 ^ {d}}$${\ Displaystyle S_ {j}}$${\ Displaystyle 2 ^ {d}}$${\ Displaystyle C_ {i}}$${\ Displaystyle 2 ^ {2d}}$${\ Displaystyle K [i, 0]}$${\ Displaystyle K [0, j]}$

Terceiro Passo: A atacante leva as possíveis mensagens cifradas, e pede um descriptografia-Oracle para fornecer os correspondentes plaintexts, . ${\ Displaystyle 2 ^ {d}}$${\ Displaystyle C_ {i}}$${\ Displaystyle P_ {i}}$

Passo Quatro: A atacante escolhe um estado interno, e o texto simples correspondente, e realiza o ataque MITM habitual por cima e por ataque do estado interno e o texto simples. ${\ Displaystyle S_ {j}}$${\ Displaystyle P_ {i}}$${\ Displaystyle f}$${\ Displaystyle g}$

Passo Cinco: Sempre que uma chave-candidato é encontrado que coincide com , ou chave é testado em um outro par sem formatação / texto cifrado. se a chave valida por outro par, é altamente provável que é a chave correta. ${\ Displaystyle S_ {j}}$${\ Displaystyle P_ {i}}$

exemplo ataque

O exemplo a seguir é baseado no ataque biclique na AES do papel "Biclique Cryptanalysis da AES Full".
As descrições no exemplo utiliza a mesma terminologia que os autores do ataque utilizado (isto é, para os nomes de variáveis, etc).
Por questões de simplicidade é o ataque na variante AES128 que é coberto abaixo.
O ataque consiste de um 7-redonda ataque MITM com o biclique cobrindo os últimos 3 ciclos.

particionamento Key

O espaço-chave está dividida em grupos de teclas, em que cada grupo consistem em chaves. Para cada um dos grupos, uma base de tecla única para a base do cálculo é seleccionado. A tecla de base tem dois bytes específicos definido como zero, mostrados na tabela abaixo (que representa a chave da mesma maneira AES faz em uma matriz de 4x4 para AES128):${\ Displaystyle 2 ^ {112}}$${\ Displaystyle 2 ^ {16}}$
${\ Displaystyle 2 ^ {112}}$${\ Displaystyle K [0,0]}$

${\ Displaystyle {\ begin {bmatrix} - & - & - & 0 \\ 0 & - & - & - \\ - & - & - & - \\ - & - & - & - \ end {bmatrix}}}$

Os restantes 14 bytes (112 bits) da chave é então enumerados. Isso produz -chaves base única; um para cada grupo de chaves. Os ordinários chaves em cada grupo é então escolhido em relação à sua base-chave. Eles são escolhidos de tal forma que eles são quase idênticos à-chave base. Eles só variam em 2 bytes (ou a 's ou a ' s) dos abaixo mostrados 4 bytes:${\ Displaystyle 2 ^ {112}}$
${\ Displaystyle 2 ^ {16}}$${\ Displaystyle i}$${\ J} displaystyle$

${\ Displaystyle {\ begin {bmatrix} - & - & i & i \\ j & - & j & - \\ - & - & - & - \\ - & - & - & - \ end {bmatrix}}}$

Isto dá e , o que combinado dá chaves diferentes, . estas chaves constituem as chaves no grupo para uma tecla respectiva base. ${\ Displaystyle 2 ^ {8} K [i, 0]}$${\ Displaystyle 2 ^ {8} K [0, j]}$${\ Displaystyle 2 ^ {16}}$${\ Displaystyle K [i, j]}$${\ Displaystyle 2 ^ {16}}$

construção Biclique

${\ Displaystyle 2 ^ {112}}$bicliques é construído usando a técnica de "Independente diferenciais relacionada-chave", como descrito na secção "Como para construir o biclique".
O requisito para a utilização dessa técnica, era que as prospectivas para trás e diferenciais-fugas que precisam de ser combinado, não partilham qualquer elemento não-lineares activas. Como é sabido que este é o caso?
Devido à maneira como as chaves no passo 1 é escolhido em relação à chave de base, as trilhas diferenciais utilizando as teclas não partilham qualquer S-boxes activos (que é o único componente não-linear em AES), com as trilhas diferenciais usando o chave . Por conseguinte, é possível XOR as trilhas diferenciais e criar o biclique. ${\ Displaystyle \ Delta _ {i}}$${\ Displaystyle K [i, 0]}$${\ Displaystyle \ nabla _ {j}}$${\ Displaystyle K [0, j]}$

ataque MITM

Quando os bicliques são criados, o ataque MITM quase pode começar. Antes de fazer o ataque MITM, os valores intermédios do em texto , os valores intermédios do texto cifrado: , e os estados intermediários correspondentes e sub-chaves ou , são pré-computado e armazenado, no entanto. ${\ Displaystyle 2 ^ {d}}$
${\ Displaystyle P_ {i} {\ xrightarrow [{}] {K [i, 0]}} {\ xrightarrow [{v_ {i}}] {}}}$
${\ Displaystyle 2 ^ {d}}$
${\ Displaystyle {\ xleftarrow [{v_ {j}}] {} {} \ xleftarrow [{}] {K [0, j]}} S_ {j}}$
${\ Displaystyle K [i, 0]}$${\ Displaystyle K [0, j]}$

Agora o ataque MITM pode ser realizada. A fim de testar uma chave , é somente necessário para recalcular as partes da cifra, que é conhecido irá variar entre e . Para o cálculo para trás a partir de , isto é 4-S caixas que precisa de ser recalculadas. Para a frente computação de a , é apenas a 3 (uma explicação em profundidade para a quantidade de recálculos necessários podem ser encontrados em "Biclique Cryptanalysis do total AES" papel, onde este exemplo é retirado). ${\ Displaystyle K [i, j]}$${\ Displaystyle P_ {i} {\ xrightarrow [{}] {K [i, 0]}} {\ xrightarrow [{v_ {i}}] {}}}$${\ Displaystyle P_ {i} {\ xrightarrow [{}] {K [i, j]}} {\ xrightarrow [{v_ {i}}] {}}}$${\ Displaystyle S_ {j}}$${\ Displaystyle {\ xleftarrow [{v_ {j}}] {}}}$${\ Displaystyle P_ {i}}$${\ Displaystyle {\ xrightarrow [{v_ {i}}] {}}}$

Quando os valores intermediários correspondem, uma chave-candidata entre e é encontrado. A chave-candidato é então testado em um outro par sem formatação / texto cifrado. ${\ Displaystyle K [i, j]}$${\ Displaystyle P_ {i}}$${\ Displaystyle S_ {j}}$

Resultados

Este ataque reduz a complexidade computacional da AES128 a , que é 3-5 vezes mais rápido do que uma abordagem bruteforce. A complexidade de dados do ataque é ea complexidade de memória é . ${\ Displaystyle 2 ^ {126,18}}$${\ Displaystyle 2 ^ {88}}$${\ Displaystyle 2 ^ {8}}$

Referências