Les attaques cryptographique sophistiquées sont-elles toujours meilleures que la force brute ?

Si la cryptographie est la science du secret, la cryptanalyse est l’art de casser des mécanismes cryptographiques. Un algorithme suffisamment efficace qui brise une propriété de sécurité offerte par un mécanisme cryptographique est une “attaque”. L’efficacité, donc la dangerosité des attaques cryptographiques est généralement évaluée dans le modèle calculatoire usuel des cours d’algorithmique : la Random Access Machine, (ou une de ses variantes) que personne ne se risque à définir précisément.

Dans cet exposé, je voudrais essayer de souligner qu’envisager des modèles de calculs plus réalistes, notamment le modèle AT en vogue dans l’étude des circuits VLSI dès la fin des années 1970 soulève un certain nombre de questions.

Quand on y réfléchit quelques minutes, on peut se rendre compte que, si jamais on essayait de les programmer, on trouverait que de nombreuses attaques cryptographiques sophistiquées sont inférieures dans la pratique à des idées très naïves (recherche exhaustive, etc.).

De plus, optimiser la complexité de certaines attaques dans le modèle AT est un objectif complètement différent de celui d’optimiser le nombre d’opérations. Cela aboutit à des résultats différents. Alors, quelle est la “bonne” manière de faire de la cryptanalyse ?