Garanties de dureté pour AES

De nombreux cryptosystèmes à clé publique ont une sorte de sécurité prouvable. Par exemple, le cryptosystème Rabin est aussi difficile que l'affacturage.

Je me demande si ce type de sécurité prouvable existe pour les cryptosystèmes à clé secrète, tels que AES. Sinon, quelle est la preuve qu'il est difficile de casser de tels cryptosystèmes? (autre que la résistance aux attaques par essais et erreurs)

Remarque: je connais les opérations AES (AddRoundKey, SubBytes, ShiftRows et MixColumns). Il semble que la dureté d'AES découle de l'opération MixColumns, qui à son tour doit hériter de sa difficulté d'un problème difficile sur Galois Fields (et donc de l'algèbre). En fait, je peux reformuler ma question comme suit: "Quel problème algébrique dur garantit la sécurité d'AES?"

MIXCOLUMNS empêche les attaques qui ne se concentrent que sur quelques S-box, car le mélange des colonnes nécessite que tous les S-box participent au cryptage. (Les concepteurs de Rijndael ont appelé cela une «stratégie à large piste».) La raison pour laquelle l'analyse d'une S-box est difficile est due à l'utilisation de l'opération d'inversion de champ fini. L'inversion "lisse" les tableaux de distribution des entrées de la boîte S, de sorte que les entrées semblent (presque) uniformes, c'est-à-dire qu'on ne peut les distinguer d'une distribution aléatoire sans la clé. C'est la combinaison des deux fonctionnalités qui permet à Rijndael de se protéger contre les attaques connues.

En passant, le livre The Design of Rijndael est une très bonne lecture, et discute de la théorie et de la philosophie de la cryptographie.

Comme l'a dit David, nous n'avons pas de telles réductions pour AES. Cependant, cela ne signifie pas que le cryptosystème Rabin ou RSA est plus sécurisé que AES. En fait, je ferais confiance à la sécurité (au moins unidirectionnelle, probablement aussi pseudo-aléatoire) des chiffrements de blocs tels que AES / DES, etc. est difficile, précisément parce qu'il n'y a pas de structure algébrique et qu'il est donc plus difficile d'imaginer qu'il y aura une sorte d'algorithme révolutionnaire.

On peut construire des chiffres de bloc directement à partir de fonctions unidirectionnelles, ce qui est une hypothèse minimale pour une grande partie de la crpyotgraphie, mais la construction résultante sera terriblement inefficace et donc non utilisée.

Puisqu'on peut convertir n'importe quel schéma de chiffrement à clé publique en schéma à clé secrète de manière générique, vous pouvez obtenir des schémas à clé secrète avec des garanties de sécurité prouvables similaires.

Mais cette réponse est pédante: pour le blockcipher déployé typique, nous n'avons pas d'analyse de sécurité prouvable dans le sens de la réduction au problème de calcul. Il y a eu des propositions de blockciphers avec des réductions de sécurité, mais le bagage de calcul nécessaire pour faciliter une réduction les rend non compétitifs avec des schémas plus efficaces comme les algorithmes AES.

Fait intéressant, la communauté de la sécurité prouvée a généralement convenu qu'il est judicieux de prendre la sécurité du chiffrement par blocs (permutation pseudo-aléatoire) comme hypothèse, puis de la réduire lors de l'analyse des protocoles de niveau supérieur qui utilisent le chiffrement par blocs comme composant. Autrement dit, contrairement à certains autres défis de la conception de protocoles sécurisés, il semble suffisant de faire confiance à l'intuition des cryptanalystes pour la sécurité en ce qui concerne les chiffreurs de blocs.