Chapitre 2 FAQ de sci.crypt Chapitre 4 Retour à la case départ

Cryptologie de base

Ceci est le troisième des dix chapitres de la FAQ de sci.crypt. Nous n'avons pas le temps d'envoyer ce qui manque par courrier électronique, donc ne demandez rien.
Des notes comme "[KAH67]" renvoient à la liste de références au dernier chapitre.

Les chapitres de cette FAQ sont disponibles par FTP anonyme sur ftp://rtfm.mit.edu/pub/usenet/news.answers/cryptography-faq/part[xx]
La FAQ de cryptographie est postée sur les groupes de discussions sci.crypt, talk.politics.crypto, sci.answers, et news.answer tous les 21 jours.

Table des matières

3.1. Qu'est-ce que la cryptologie? La cryptographie? Un texte clair? Un texte chiffré? Le chiffrement? Une clé?

Le début de l'histoire: quand Jules César envoyait des messages, il ne faisait pas confiance aux messagers. Alors il remplaçait chaque A par un D, chaque B par un E et ainsi de suite. Seuls ceux qui connaissaient la règle décalage de 3 pouvaient déchiffrer le message.

Un cryptosystème ou un système de chiffrement est une méthode permettant de camoufler des messages de telle façon que seules certaines personnes puissent les lire. La cryptographie est l'art de créer et d'utiliser de tels systèmes. La cryptanalyse est l'art de casser ces cryptosystèmes -- de voir à travers le camouflage. La cryptologie est l'étude de la cryptographie et de la cryptanalyse.

Le texte original est appelé texte clair ou libellé. Le texte camouflé est appelé texte chiffré ou cryptogramme. Le chiffrement est la méthode qui convertit le texte clair en cryptogramme. Le déchiffrement est l'inverse.
[NdT: déchiffrer signifie lire le texte clair en connaissant la convention secrète. Décrypter signifie le lire sans connaître cette convention]

Un cryptosystème est généralement un ensemble d'algorithmes. Ces algorithmes sont étiquetés; les étiquettes sont appelées clés. Par exemple, César a probablement utilisé la méthode décalage de N avec des valeurs de N différentes. Il est naturel de dire que N est la clé.

Les gens qui reçoivent les messages sont les destinataires. Les autres sont les ennemis, les adversaires, les intercepteurs, les espions...

3.2. Avec quels livres puis-je démarrer en cryptographie?

Pour une introduction technique, les articles généraux donnés au chapitre 10 sont le meilleur endroit où commencer car ils sont en général concis, bien écrits, par des gens compétents. Toutefois, la plupart de ces articles parlent de la cryptologie qui a été pratiquée dans les 50 dernières années et sont plus abstraits et mathématiques qu'historiques.
The Codebreakers de Kahn [KAH67] [NdT: la guerre des codes secrets] est encyclopédique aussi bien sur le plan technique qu'historique jusqu'au milieu des années 60.

Gaines [GAI44] ou Sinkov [SIN66] sont des introductions à la cryptanalyse. Ils sont recommandés à ceux qui veulent inventer leurs algorithmes car c'est une erreur courante d'essayer de faire un système sans savoir comment en casser un.

La sélection d'un algorithme pour le DES a attiré l'attention de nombreux chercheurs sur les problèmes de cryptologie. De nombreux manuels ont été publiés suite à ça. Le livre de Denning [DEN82] est une bonne introduction à un large éventail de techniques de sécurité comprenant les algorithmes de chiffrement, la sécurité des bases de données, le contrôle d'accès et les modèles formels de sécurité. Même commentaires pour les livres de Price & Davies [PRI84] et Pfleeger [PFL89].

Les livres de Konheim [KON81] et Meyer & Matyas [MEY82] sont très techniques. Konheim et Meyer ont été tous deux directement impliqués dans le développement du DES et les deux livres présentent une analyse minutieuse du DES. Le livre de Konheim est très mathématique, avec une analyse détaillée de nombreux systèmes classiques. Meyer et Matyas se concentrent sur les méthodes modernes, tout particulièrement la gestion de clés et l'intégration de fonctions de sécurité dans les ordinateurs et les réseaux. Essayez G. Simmons dans [SIM91] si vous cherchez une documentation plus récente.

Les livres de Rueppel [RUE86] et Koblitz [KOB89] se concentrent sur l'application de la théorie des nombres et de l'algèbre à la cryptographie.

3.3. Comment fait-on de la cryptanalyse?

La cryptanalyse classique met en oeuvre une combinaison intéressante de raisonnement analytique, d'utilisation d'outils mathématiques, de recherche de motifs [NdT: pattern ?!], de patience, de détermination et de chance. Le meilleur manuel disponible sur ce sujet est the Military Cryptanalytics series [FRIE1]. Il est clair que la compétence en cryptanalyse est acquise pour l'essentiel en cassant des systèmes. Une telle expérience est considérée comme si précieuse que certaines cryptanalyses effectuées par les Alliés durant la seconde guerre mondiale sont toujours classifiées.

La cryptanalyse des systèmes modernes à clés publiques peut consister à factoriser un entier ou extraire un logarithme discret. Ce n'est pas le domaine traditionnel du cryptanalyste. Ce sont les spécialistes de théorie des nombres qui ont le plus de succès contre les systèmes à clés publiques.

3.4. Qu'est-ce qu'une recherche par force brute et quelle est sa signification?

Vite fait: si f(x) = y et que vous connaissez y et que vous pouvez calculer f, vous pouvez trouver x en essayant toutes les valeurs possibles. C'est la recherche brutale.

Exemple: un cryptanalyste a trouvé un texte clair et le cryptogramme correspondant, mais il ne connait pas la clé. Il peut essayer de chiffrer le texte clair avec chacune des clés possibles jusqu'à ce que le cryptogramme corresponde -- ou bien il peut déchiffrer le cryptogramme pour retrouver le texte clair si c'est plus rapide ainsi.
Dans un cryptosystème bien conçu, l'espace des clés est si grand que la force brute est inutilisable.

Les avancées technologiques modifient parfois ce qui est perçu comme "possible". Par exemple, le DES qui est utilisé depuis plus de 10 ans maintenant a 2^56 (soit environ 10^17) clés différentes. Un calcul nécessitant autant d'opérations était quasiment infaisable au milieu des années 70. La situation est bien différente maintenant avec la baisse terrible du coût par instruction. Des machines massivement parallèles menacent la sécurité du DES contre la force brute.
Des scénarios sont décrits par Garron et Outerbridge [GAR91].
[NdT: récemment, l'Electronic Frontier Foundation a cassé un DES en moins de trois jours avec une machine spécialisée qui a coûté moins de 250000 $. Cf. http://www.eff.org/descracker.html]

Une version plus sophistiquée peut consister à effectuer une recherche exhaustive sur un petit ensemble de clés possibles.

3.5. Quelles sont les propriétés vérifiées par tous les systèmes de chiffrement forts?

La sécurité d'un système solide réside dans le secret qui entoure la clé plutôt que dans le secret censé entourer l'algorithme.

Comme nous l'avons mentionné plus haut, un système robuste a un espace de clés grand. Il a une distance d'unicité suffisamment grande; voir la question 8.8

Un système robuste produira certainement des cryptogrammes qui paraissent aléatoires à tous les tests statistiques standards (voir par exemple [CAE90]).

Un système robuste résistera à toutes les attaques connues précédemment. Un système qui n'a jamais été analysé est suspect.

Si un système réussit tous ces tests, est-il nécessairement sûr ?
Certainement pas. De nombreux systèmes faibles ont eu l'air bons de prime abord. Toutefois, il est parfois possible de démontrer mathématiquement qu'un système est fort. "Si on peut casser ce système, alors on peut aussi résoudre le problème difficile bien connu de factorisation des nombres". Voir le chapitre 6 .

3.6. Si un système de chiffrement est théoriquement incassable, alors l'est-il en pratique?

Les méthodes cryptanalytiques incluent ce qu'on appelle la cryptanalyse pratique: l'ennemi ne va pas juste contempler le cryptogramme jusqu'à ce qu'il devine le texte clair. Par exemple, il peut deviner des fragments probables du texte clair. Si le fragment est correct il peut en déduire la clé et déchiffrer le reste du message. Ou il peut exploiter des "isologs" -- le même libellé chiffré avec plusieurs systèmes ou plusieurs clés. Ainsi il peut trouver une solution même si la théorie dit qu'il n'a pas la moindre chance.

Quelquefois, les cryptosystèmes fonctionnent mal ou sont mal utilisés. Le masque jetable, par exemple, perd toute sa sécurité s'il est utilisé plus d'une fois! Même l'attaque à texte clair choisi, où l'ennemi envoie des textes clairs dans le système de chiffrement jusqu'à en déduire la clé, a été utilisée. Voir [KAH67].

3.7. Pourquoi tant de gens utilisent-ils encore des systèmes relativement faciles à casser?

Certains n'en connaissent pas de meilleurs. Les amateurs pensent souvent qu'ils peuvent concevoir des systèmes sûrs sans savoir ce qu'un cryptanalyste averti peut faire. Et quelquefois personne n'a la motivation suffisante pour passer du temps à craquer un système.

3.8. Quelles sont les types de cryptanalyses de base?

Une attaque cryptanalytique standard consiste à connaître un texte clair et le cryptogramme correspondant et d'en déduire la clé. Ce texte clair peut être connu parce qu'il est standard (une formule de politesse, un en-tête ou une finale connu...) ou parce qu'il a été deviné. Si on devine qu'un texte est contenu dans un message, sa position est probablement inconnue, mais le message est souvent assez court pour que le cryptanalyste puisse essayer toutes les positions possibles et attaque chaque cas en parallèle. Dans ce cas, le texte connu peut être quelque chose de si commun qu'on est sûr qu'il sera dans le message.

Un système de chiffrement robuste sera incassable non seulement via la cryptanalyse à texte clair connu (en supposant que l'ennemi connaisse tout le texte clair pour un cryptogramme donné) mais également face au texte clair choisi adaptatif -- une attaque qui rend la vie du cryptanalyste beaucoup plus facile. Dans cette attaque, l'ennemi choisit quel va être le texte clair N+1 seulement après avoir analysé le cryptogramme N.

Par exemple, d'après ce que l'on sait, le DES est raisonnablement robuste même face à une attaque à texte clair choisi adaptatif -- l'attaque que Biham et Shamir ont utilisée.
Bien sûr, nous n'avons pas accès aux secrets des services de cryptanalyse du gouvernement. On suppose que le DES est raisonnablement robuste face à l'attaque à texte clair connu et que le triple DES est très robuste face à toutes les attaques.

En résumé, les types de bases d'attaques dans l'ordre de difficulté pour le cryptanalyste (la plus dure d'abord) sont:
  1. Cryptogramme seul: l'attaquant possède seulement le message chiffré et doit déterminer le texte clair, sans aucune connaissance sur son contenu.
    On considère en général que cette attaque est possible, et la résistance d'un système face à elle est la base de la sécurité cryptographique.
  2. Texte clair connu: l'attaquant possède le texte clair et le cryptogramme correspondant d'un message qu'il n'a pas choisi. Le message est dit compromis.
    Dans certains systèmes, une seule paire libellé/cryptogramme compromet tout le système, y compris les communications passées et futures, et la résistance à cette attaque est caractéristique d'un code sûr.
    Dans les attaques suivantes, l'attaquant a la possibilité de "suggérer" à l'envoyeur de chiffrer ou déchiffrer des textes arbitraires. Les codes qui résistent à ces attaques ont la sécurité la plus élevée.
  3. Texte clair choisi: l'attaquant a la possibilité de trouver le cryptogramme correspondant à un libellé de son choix.
  4. Cryptogramme choisi: l'attaquant peut choisir des cryptogrammes et trouver les libellés correspondants. Cette attaque peut être utilisée dans des systèmes à clé publique, elle révèle la clé privée.
  5. Texte clair choisi adaptatif: l'attaquant peut déterminer les cryptogrammes correspondant à une série de textes clairs choisis de façon interactive ou itérative, en se basant sur les résultats précédents. C'est le nom général pour une méthode d'attaque des chiffres produits appelée cryptanalyse différentielle.

Le chapitre suivant de la FAQ donne les détails mathématiques derrière les différents types de cryptanalyses.
Chapitre 2 FAQ de sci.crypt Chapitre 4 Retour à la case départ
Michel Arboi
Last modified: Sun Mar 25 16:20:33 CEST 2007