Garantias de dureza para AES

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?"

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.

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.

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.