Chapitre 7 FAQ de sci.crypt Chapitre 9 Retour à la case départ

Divers points techniques...

Ceci est le huitiè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

8.1. Comment récupérer des mots de passe de WordPerfect perdus?

On a démontré que le chiffrement dans WordPerfect est particulièrement facile à casser.
La méthode utilise un OU exclusif avec deux flux de clés répétitifs:
un mot de passe entré au clavier et un compteur sur un octet initialisé à 1+la longueur du mot de passe. On trouvera une description complète dans Bennett [BEN87] et Bergen et Caelli [BER91].

Chris Galas écrit:
Il y a quelques temps quelqu'un cherchait une solution pour décrypter des documents WordPerfect et je pense avoir trouvé une solution. Il y a une société nommée: Accessdata (87 East 600 South, Orem, UT 84058), 1-800-658-5199 qui a un logiciel qui décrypte les fichiers WordPerfect, Lotus 1-2-3, Quatro-Pro, MS Excel et Paradox. Le coût du logiciel est 185 $. Un prix excessif, mais si vous pensez que votre mot de passe fait 10 caractères ou moins, passez-leur un coup de fil et demandez la démo gratuite. La démo décrypte les fichiers qui ont un mot de passe de 10 caractères au plus.
Bruce Schneier dit que le numéro de téléphone d'AccessData est 801-224-6970.

8.2. Comment casser un Vigenère?

Un chiffre à clé répétée, où le cryptogramme est quelque chose qui ressemble à "texte clair" XOR "CléCléCléClé" etc. est appelé un chiffre de Vigenère. Si la clé n'est pas trop longue et si le texte clair est en anglais, suivez ces instructions :
1. Découvrez la longueur de la clé en comptant les coïncidences (Voir Gaines [GAI44], Sinkov [SIN66].) Essayez tous les décalages du cryptogramme par rapport à lui-même et comptez les octets qui sont égaux. Si les deux morceaux de cryptogrammes ont utilisé la même clé, environ 6 % des octets seront égaux. Sinon, moins de 0,4 % seront égaux (en supposant que la clé soit composée d'octets de 8 bits aléatoire et que le texte clair est en ASCII)
[NdT: en français, ces pourcentages seront différents mais le principe est le même]
Le plus petit déplacement qui marche donne la taille de la clé.

2. Décalez le texte de cette longueur et faites un OU exclusif avec lui-même. Ceci supprime la clé et laisse le texte "XORé" avec lui même. Comme l'anglais a seulement 1 bit d'information réelle par octet, deux chaînes de textes XORés ensemble ont seulement 2 bits par octet, ce qui donne une redondance suffisante pour choisir un déchiffrement unique (et en fait, une chaîne de texte XORé avec lui même a une entropie de 1 bit par octet seulement)
[NdT: le lecteur me pardonnera cette traduction barbare de "XORed" par "XORé". je voulais éviter une périphrase trop lourde]

Si la clé est courte, on peut même traiter ça plus facilement comme une substitution polyalphabétique standard. Tous les vieux textes de cryptanalyse expliquent comment casser cela. Entre les mains d'un expert, ces méthodes marchent avec un texte seulement dix fois plus long que la clé. Voir, par exemple, Gaines [GAI44], Sinkov [SIN66].

8.3. Comment envoyer du courrier chiffré sous UNIX? [PGP, RIPEM, PEM, ...]

Voici une méthode populaire, avec la commande des:

cat file | compress | des private_key | uuencode | mail

Cependant, il y a un standard Internet en cours appelé PEM (Privacy Enhanced Mail) [Courrier à Confidentialité Améliorée]. Il est décrit dans les RFC 1421 à 1424. Pour rejoindre la liste de discussion, contactez pem-dev-request@tis.com. Au moment où l'on écrit ces lignes, une version bêta de PEM est en test.

Il y a aussi deux programmes disponibles dans le domaine public pour chiffrer du courrier: PGP et RIPEM. Les deux sont disponibles par FTP. Chacun a son propre groupe de discussion: alt.security.pgp et alt.security.ripem. Chacun a aussi sa propre FAQ.

PGP est surtout utilisé en dehors des Etats-Unis car il utilise l'algorithme RSA sans licence et le brevet RSA est seulement (ou principalement) en force aux Etats-Unis.

RIPEM est principalement utilisé aux Etats-Unis car il utilise RSAREF qui est disponible gratuitement aux Etats-Unis mais pas à l'extérieur.

Comme les deux programmes utilisent un algorithme à clé secrète pour chiffrer le corps du message (PGP utilisait IDEA, RIPEM le DES) et RSA pour chiffrer la clé, ils devraient être capables de communiquer. Bien qu'il y ait eu des appels répétés pour que chacun puisse comprendre le format et les choix algorithmiques de l'autre, aucune interopérabilité n'est possible à cette date (d'après ce que nous en savons).

8.4. La commande UNIX crypt est-elle sûre?

Non. Voir [REE84]. il existe un programme nommé cbw (crypt breaker's workbench) qui peut faire des attaques texte chiffré seul contre les fichiers chiffrés par crypt. Une source de CBW est [FTPCB].

8.5. Comment doit-on utiliser la compression avec le chiffrement?

Beaucoup de gens ont proposé de faire une compression parfaite suivie par une méthode de chiffrement simple (par exemple XOR avec une clé répétée). Ca pourrait marcher, à condition que vous puissiez faire une compression parfaite. Malheureusement, ce n'est faisable que si vous connaissez la distribution exacte de toutes les entrées possibles, ce qui est loin d'être le cas.

La compression aide le chiffrement en réduisant la redondance du texte clair. Ca augmente la taille du texte chiffré que vous pouvez envoyer avec une clé d'une taille donnée (voir la distance d'unicité).

Presque tous les systèmes de compression, à moins qu'ils n'aient été conçu avec la cryptographie à l'esprit, produisent une sortie qui démarre avec une redondance très élevée. Par exemple la sortie de la commande Unix compress commence par un nombre magique bien connu de trois octets. Ceci donne un texte clair connu qui peut être utilisé dans certaines attaques. Cependant, la compression est généralement bénéfique car elle supprime les autres textes clairs connus au milieu du texte. En général, plus basse est la redondance du texte clair plus difficile est la cryptanalyse.

De plus, la compression raccourcit le texte en entrée et en sortie, et réduit le temps de calcul nécessaire pour l'algorithme de chiffrement, donc même si la sécurité n'était pas accrue, la compression avant chiffrement serait bénéfique.

La compression après chiffrement est stupide. Si l'algorithme de chiffrement est bon, il produira une sortie statistiquement indiscernable d'une source aléatoire, et aucun algorithme de compression ne peut réussir à compresser des octets aléatoires. D'un autre côté, si la compression réussit à trouver un modèle qui compresse la sortie de l'algorithme de chiffrement, il y a une faille dans cet algorithme.

8.6. Y a t-il un chiffre incassable?

Oui. La clé aléatoire une fois [ou masque jetable] est incassable; voir le chapitre 4. Malheureusement il faut distribuer une clé aussi longue que le texte clair.

Bien sûr, un cryptosystème n'a pas besoin d'être absolument incassable pour être utile. Il lui suffit plutôt d'être assez fort pour résister à des attaques venant des ennemis potentiels pendant la durée de validité des données qu'il protège.

8.7. Qu'est-ce qu'"aléatoire" veut dire en cryptographie?

Les applications cryptographiques demandent plus qu'un simple générateur pseudo aléatoire commun. Une source de bits est cryptographiquement aléatoire s'il est impossible de calculer ce que sera le Nième bit en connaissant l'algorithme ou le matériel qui génère le flux et la séquence des N-1 premiers bits, quel que soit N.

Un générateur logiciel (ou pseudo aléatoire) est une fonction qui transforme une graine vraiment aléatoire en une chaîne de bits plus longue et apparemment aléatoire. Cette graine doit être suffisamment grosse pour ne pas pouvoir être devinée par l'opposant. Idéalement, elle devrait être réellement aléatoire (peut-être générée par un dispositif matériel)

Par exemple, ceux qui ont des Sparcstation 1 peuvent générer des nombres aléatoires en utilisant l'entrée audio sans micro comme source. Par exemple:
cat /dev/audio | compress - > foo
donne un fichier à haute entropie (pas totalement aléatoire, mais avec "beaucoup de hasard"). On peut chiffrer ce fichier en utilisant un deses morceaux comme clé, pour convertir cette graine en chaîne pseudo aléatoire.

Quand on cherche des dispositifs matériels qui produisent cette entropie, il est important de mesurer réellement cette entropie plutôt que supposer que ça doit être aléatoire parce que ça a l'air compliqué. Par exemple, les temps de réponse d'un disque ont l'air imprévisibles pour beaucoup de gens mais un disque qui tourne ressemble beaucoup à une horloge et ses temps de réponse ont une entropie assez basse.

8.8. Qu'est-ce que la distance d'unicité?

Voir [SHA49]. La distance d'unicité est une approximation de la quantité de texte chiffré telle que sa taille en bits est égale à la somme de véritable information (entropie) qu'il y a dans le texte clair correspondant et dans la clé. Des textes clairs sensiblement plus longs que ça ont probablement un seul déchiffrement valide. C'est utilisé pour vérifier la validité d'une attaque texte clair seul. Les textes plus courts que cette valeur ont probablement plusieurs déchiffrements valides équiprobables; la difficulté qu'éprouve l'attaquant à choisir le bon augmente la sécurité.

Comme toutes les mesures statistiques ou de théorie de l'information, la distance d'unicité ne fait pas de prédictions déterministes mais donne plutôt des résultats probabilistes: typiquement, la quantité minimale de texte chiffré pour laquelle il est probable qu'on obtiendra un seul texte clair en essayant toutes les clés possibles pour le déchiffrement. Normalement, les cryptologistes ne travaillent pas directement avec la distance d'unicité. Ils déterminent plutôt la probabilité de tel ou tel événement.

Imaginons que la distance d'unicité d'un chiffre est de D caractères. Si moins de D caractères de texte chiffré ont été interceptés, alors on n'a pas assez d'information pour distinguer la véritable clé dans l'ensemble des clés possibles. Le DES a une distance d'unicité de 17,5 caractères, ce qui est plus petit que trois blocs (chaque bloc correspond à 8 caractères ASCII). Ceci peut sembler trop bas a priori, mais la distance d'unicité ne donne aucune indication sur la puissance de calcul nécessaire pour trouver la clé quand D caractères ont été interceptés.

En fait, la cryptanalyse véritable suit rarement les lignes directrices utilisées dans la discussion sur la distance d'unicité. (Comme toutes les autres mesures comme la taille de la clé, la distance d'unicité est quelque chose qui garantit l'insécurité si elle est trop petite, mais ne garantit pas la sécurité si elle est grande). En pratique, peu de cryptosystèmes sont impénétrables à toute analyse; toutes sortes de caractéristiques peuvent servir de points d'entrée pour casser des messages chiffrés. Toutefois, de telles considérations théoriques sont parfois utiles, par exemple pour déterminer un intervalle de changement de clé dans un cryptosystème particulier. Les cryptanalystes emploient aussi une batterie de tests statistiques et de théorie de l'information pour diriger leur analyse dans les directions les plus prometteuses.

Malheureusement, l'essentiel de la littérature sur l'application des statistiques à la cryptanalyse est encore classifié, même le travail de 1940 d'Alan Turing (voir [KOZ84]). Pour avoir un aperçu de ce que l'on peut faire, voir [KUL68] et [GOO83].

8.9. Qu'est-ce que la gestion de clé et pourquoi est-ce important?

Un des axiomes fondamentaux de la cryptographie est que l'ennemi possède tous les détails du système cryptographique général, et qu'il ne lui manque que les clés. (bien sûr, on peut supposer que la CIA n'a pas pour habitude de donner les détails de ses cryptosystèmes au Mossad, mais le Mossad les trouvera probablement de toute façon). L'utilisation répétée d'une quantité de clé finie introduit une redondance qui peut faciliter la cryptanalyse. Ainsi, en particulier dans les systèmes de communications modernes où l'on échange des quantités énormes de données, les deux participants doivent avoir non seulement un cryptosystème robuste mais aussi suffisamment de clés pour couvrir le traffic.

La gestion des clés concerne la distribution, l'authentification et la manipulation des clés.

Un exemple public de technologie moderne de gestion de clés est le téléphone sécurisé STU III, qui pour son utilisation classifiée fait appel à des "Crypto Ignition Keys" et à un centre de gestion de clés géré par la NSA. Il y a une hiérarchie dans les CIK: certaines clés sont utilisées par le personnel de contrôle autorisé pour valider des clés de trafic et pour effectuer des opérations de maintenance ou d'installation, comme la déclaration de clés perdues.

Ceci devrait donner une idée de l'étendue du problème de gestion de clés. Pour des systèmes à clé publique, il y a plusieurs questions similaires, souvent en rapport avec en qui avons-nous confiance?

8.10. Peut-on utiliser des nombres pseudo aléatoires ou chaotiques comme flux de clé?

Les équations chaotiques et les fractals produisent apparemment "du hasard" à partir de générateurs relativement compacts. Le plus simple exemple peut-être est le générateur à congruence linéaire, un des types de générateurs aléatoires les plus populaires, où il n'y a pas de correspondance évidente entre les "graines" et les sorties. Malheureusement, le graphe d'une telle séquence sera un réseau régulier dans un espace de dimension suffisante. Ce réseau correspond mathématiquement à une structure que les cryptanalystes pourront très aisément exploiter. Des générateurs plus compliqués ont des structures plus compliquées, c'est pour cela qu'ils produisent des images intéressantes [NdT: on est passé aux fractals, je suppose !] -- mais une séquence cryptographiquement forte n'aura pas de structure calculable du tout. Voir [KNU81], exercice 3.5-7; [REE77]; et [BOY89].

8.11. Quelle est la fréquence exacte des lettres en anglais?

Il y a trois réponses à cette question, chacune légèrement plus profonde que la précédente. Vous pouvez trouver la première réponse dans divers livres: c'est-à-dire une liste de fréquences calculées directement à partir d'un échantillon de texte anglais.

La deuxième réponse est que la "langue anglaise" varie d'un auteur à l'autre et a changé au cours du temps, donc il n'y a pas de liste absolue. Bien sûr les listes dans les livres sont "correctement" calculées, mais elles sont toutes différentes: chaque liste dépend de l'échantillon utilisé. Un message donné aura des statistiques différentes du langage pris comme un tout.

La troisième réponse est que oui, aucun message particulier ne va avoir les même caractéristiques que l'anglais en général, mais que pour toutes les utilisations raisonnables ces légères différences ne gêneront pas. En fait les "statistiques bayésiennes" (et d'autres mots à la mode comme "méthodes d'entropie maximum" et "estimation du maximum de vraisemblance") étudient des questions comme Quelle est la probabilité qu'un texte avec ces fréquences soit en anglais? et fournissent des réponses raisonnablement solides.

Donc faites votre propre liste à partir de votre propre échantillon de textes anglais. Ca sera bien suffisant en pratique si vous l'utilisez correctement.

8.12. Qu'est-ce qu'Enigma?

Pour un projet en sécurité de données nous cherchons des renseignements sur le code allemand Enigma et comment il a été cassé par les Britanniques durant la deuxième guerre mondiale.
Voir [WEL82], [DEA85], [KOZ84], [HOD83], [KAH91].

8.13. Comment mélanger des cartes?

C'est un cas particulier de la permutation d'un tableau de valeur, en utilisant une fonction (pseudo) aléatoire. Toutes les permutations possibles doivent être équiprobables. Pour faire ça, il vous faut une fonction aléatoire (modran(x)) qui produit des valeurs entières uniformément réparties dans l'intervalle [0..x-1]. Etant donnée cette fonction, vous pouvez mélanger avec le code [C] suivant: (sachant que ARRLTH la longueur du tableau arr[] et que swap() échange les valeurs aux deux adresses données)

for ( n = ARRLTH-1; n > 0 ; n-- ) swap( &arr[modran( n+1 )], &arr[n] ) ;

modran(x) ne peut pas être obtenue par un simple (ranno() % x) car l'intervalle de sortie de ranno() peut ne pas être divisible par x, bien que dans la plupart des cas l'erreur sera très faible.
[NdT: je ne traduis pas la dernière phrase qui a l'art de rendre compliqué quelque chose de fort simple. Voyez directement Knuth, ça m'évitera de faire des contresens] Voir [KNU81] pour plus de détails.

8.14. Peut-on empecher le piratage d'un logiciel en chiffrant un CDROM?

On exprime souvent le désir de publier un CD-ROM avec plusieurs logiciels, chacun chiffré séparément, et on veut utiliser des clés différentes pour chaque utilisateur pour éviter le piratage (clés éventuellement limitées dans le temps).

D'après ce que nous en savons, ceci est impossible, car il n'existe rien sur un PC ou une station de travail standard qui identifie l'utilisateur au clavier. S'il existait une telle identification, alors le CD-ROM pourrait être chiffré avec une clé basée en partie sur celle vendue à l'utilisateur et en partie sur un numéro unique. Toutefois, dans ce cas le CD-ROM est unique et c'est contraire au principe [NdT: on presse normalement un grand nombre de CD-ROM identiques]

Si le CD-ROM doit être chiffré une fois et produit en masse, alors il y a une clé (ou un ensemble de clés) pour ce chiffrement à une étape du processus. Cette clé est utilisable avec n'importe quelle copie des données du CD-ROM. Le pirate doit seulement isoler cette clé et la vendre avec la copie illégale.

8.15. Peut-on cryptanalyser automatiquement des systèmes simples?

Certainement. Pour les produits commerciaux vous pouvez essayer AccessData; voir la question 8.1. Nous ne connaissons pas de sites FTP avec de tels logiciels, mais il y a beaucoup de papiers sur le sujet. Voir [PEL79], [LUC88], [CAR86], [CAR87], [KOC87], [KOC88], [KIN92], [KIN93], [SPI93].

8.16. Quel codage est utilisé par VCR+?

Une question qui revient souvent sur sci.crypt. Les codes programment un magnétoscope à entrée numérique. Voir [SHI92] pour une description.
Chapitre 7 FAQ de sci.crypt Chapitre 9 Retour à la case départ
Michel Arboi
Last modified: Sun Mar 25 16:21:21 CEST 2007