Garantias de dureza para AES

14

Muitos sistemas de criptografia de chave pública têm algum tipo de segurança comprovável. Por exemplo, o sistema criptográfico Rabin é comprovadamente tão difícil quanto fatorar.

Gostaria de saber se existe esse tipo de segurança comprovável para sistemas de criptografia de chave secreta, como o AES. Se não, qual é a evidência de que é difícil quebrar esses sistemas de criptografia? (exceto resistência a ataques de tentativa e erro)

Observação: eu estou familiarizado com operações AES (AddRoundKey, SubBytes, ShiftRows e MixColumns). Parece que a dureza do AES deriva da operação MixColumns, que por sua vez deve herdar sua dificuldade de algum problema difícil nos Galois Fields (e, portanto, na álgebra). De fato, posso reafirmar minha pergunta como: "Qual problema algébrico difícil garante a segurança da AES?"

MS Dousti
fonte

Respostas:

8

MIXCOLUMNS evita ataques focados em apenas algumas caixas S, porque a mistura das colunas exige que todas as caixas S participem da criptografia. (Os projetistas de Rijndael chamaram isso de "estratégia de trilha ampla".) A análise da razão de uma caixa S é difícil é devido ao uso da operação de inversão de campo finito. A inversão "suaviza" as tabelas de distribuição das entradas da caixa S, de modo que as entradas parecem (quase) uniformes, isto é, indistinguíveis de uma distribuição aleatória sem a chave. É a combinação dos dois recursos que tornam Rijndael comprovadamente seguro contra ataques conhecidos.

Como um aparte, o livro The Design of Rijndael é uma leitura muito boa e discute a teoria e a filosofia da criptografia.

Aaron Sterling
fonte
1
Boa explicação. Obrigado. Na verdade, eu tinha acesso ao livro, mas não sabia qual parte ler (em relação à minha pergunta). Você sugere algum capítulo ou seção especial?
MS Dousti 12/09/10
3
Eu o li há mais de dois anos, fora de uma biblioteca, para não ter o sumário à minha frente e não tenho certeza se poderia dar uma resposta concreta à sua pergunta, exceto que gostei da maneira eles projetaram as caixas S para serem facilmente implementáveis. No entanto, uma coisa que posso sugerir é a explicação de Stinson sobre o AES e outras redes de permuta-substituição em Criptografia: Teoria e Prática. É o capítulo 3 da edição que tenho e parece que você pode fazer o download do livro gratuitamente neste link: ebookee.com/…
Aaron Sterling
1
Obrigado por sugerir o livro de Stinson. Você também pode consultar o Sumário de O Design de Rijndael e ver se isso lembra alguma coisa útil?
MS Dousti 13/09/10
2
Obrigado pelo link! :-) Sim, a seção 3.6 e o ​​capítulo 5 foram muito interessantes para mim, porque discutiram "por que" e não apenas "o que".
Aaron Sterling
10

Como David disse, não temos essas reduções para a AES. No entanto, isso não significa que o sistema de criptografia Rabin ou RSA seja mais seguro que o AES. De fato, eu confiaria na segurança (pelo menos unidirecional, provavelmente também pseudo-aleatória) de cifras de bloco como AES / DES etc. é difícil, precisamente porque não há estrutura algébrica e, portanto, é mais difícil imaginar que haverá algum tipo de algoritmo inovador.

Pode-se construir cifras de bloco diretamente a partir de funções de mão única, o que é uma suposição mínima para grande parte da criptografia, mas a construção resultante será terrivelmente ineficiente e, portanto, não será utilizada.

Boaz Barak
fonte
Obrigado Boaz. Eu acho que a construção de Luby-Rackoff é uma que fornece pseudo-aleatória provável com base em estruturas semelhantes a DES, certo?
MS Dousti 19/09/10
3
sim. Mais precisamente, você inicia com uma função unidirecional, converte-a em um gerador pseudo-aleatório usando Hastad, Impagliazzo, Luby, Levin e depois converte-a em uma função pseudo-aleatória usando Goldreich, Goldwasser, Micali e, de fato, use Luby-Rackoff convertê-lo em uma permutao pseudo-aleatório (isto é, o bloco ci PHER)
Boaz Barak
6

Como é possível converter qualquer esquema de criptografia de chave pública em um esquema de chave secreta de maneira genérica, você pode obter esquemas de chave secreta com garantias de segurança comprováveis ​​semelhantes.

Mas essa resposta é pedante: para o típico código de bloco implantado, não temos uma análise de segurança comprovável no sentido de redução ao problema computacional. Houve propostas para códigos de bloqueio com reduções de segurança, mas a bagagem computacional necessária para facilitar uma redução os torna não competitivos com esquemas mais eficientes, como os algoritmos AES.

Curiosamente, a comunidade de segurança comprovada geralmente concordou que é sensato considerar a segurança de código de bloco (permutação pseudo-aleatória) como uma suposição e reduzi-la ao analisar protocolos de nível superior que empregam o código de bloco como componente. Ou seja, diferente de outros desafios no design de protocolo seguro, parece suficiente confiar na intuição dos analistas de criptografia quanto à segurança quando se trata de códigos de bloqueio.

David Cash
fonte