Groupe de travail Réseau	E. Rescorla, RTFM, Inc.	
Request for Comments : 3218	janvier 2002	
Catégorie : Information	Traduction Claude Brière de L'Isle	

Empêcher l'attaque du million de messages sur la syntaxe de message cryptographique

Statut de ce mémoire
Le présent mémoire apporte des informations pour la communauté de l'Internet. Il ne spécifie aucune sorte de norme de l'Internet. La distribution du présent mémoire n'est soumise à aucune restriction.

Notice de copyright
Copyright (C) The Internet Society (2002). Tous droits réservés.

Résumé
Le présent mémoire décrit une stratégie de résistance à l'attaque du million de messages.

Table des Matières
1.	Introduction
2.	Grandes lignes de PKCS-1
2.1	L'attaque du million de messages
2.2	Applicabilité
2.2.1	Note sur le bourrage de chiffrement de bloc
2.3	Contre mesures
2.3.1	Vérification soigneuse
2.3.2	Remplissage aléatoire
2.3.3	OAEP
2.4	Considérations pour la sécurité
3.	Remerciements
4.	Références
5.	Adresse de l'auteur
6.	Déclaration de copyright

1.	Introduction

Lorsque des données sont chiffrées en utilisant RSA, elles doivent être bourrées jusqu'à la longueur du module -- normalement de 512 à 2 048 bits. La technique la plus utilisée pour ce faire est décrite dans [RFC2313]. Cependant, en 1998 Bleichenbacher a décrit une attaque de texte chiffré choisi adaptatif contre SSL [MMA]. Cette attaque, appelée l'attaque du million de messages (MMA, Million Message Attack) permet la récupération d'un seul bloc chiffré en PKCS-1, pourvu que l'attaquant puisse convaincre le receveur d'agir comme une espèce d'oracle particulier. (Un oracle est un programme qui répond à des interrogations fondées sur des informations non disponibles à l'interrogateur (en l'occurrence, la clé privée).) La MMA est aussi possible contre la [RFC2360]. Les agents de carnet d'adresse de messagerie électronique sont les cibles les plus vraisemblables de mise en œuvre de syntaxe de message cryptographique (CMS, Cryptographic Message Syntax) pour la MMA, car les agents de carnet d'adresse de messagerie électronique sont des automates serveurs qui répondent automatiquement à un grand nombre de messages. Le présent document décrit une stratégie de résistance à de telles attaques.

2.	Grandes lignes de PKCS-1

Le premier stade du chiffrement RSA est de transposer le message à chiffrer (en CMS une clé de chiffrement de contenu symétrique (CEK, content-encryption key)) en un entier de la même longueur que (mais numériquement inférieure) le module RSA de la clé publique du receveur (normalement quelque part entre 512 et 2 048 bits). PKCS-1 décrit les procédures les plus courantes pour cette transformation.

On commence par un "bloc de chiffrement" de la même longueur que le module. Les octets les plus à droite du bloc sont affectés au message à chiffrer. Les deux premiers octets sont un octet à zéro et un octet de "type de bloc". Pour le chiffrement, le type de bloc est 2. Les octets restants sont utilisés comme bourrage. Le bourrage est construit en générant une série d'octets aléatoires non à zéro. Le dernier octet de bourrage est à zéro, ce qui permet de distinguer le bourrage du reste du message.

0	2	Octets aléatoires non à zéro	0	Message	

One fois que le bloc a été formaté, l'envoyeur doit ensuite convertir le bloc en un entier. Cela est fait en traitant le bloc comme un entier de forme gros boutienne. Et donc, le nombre résultant est inférieur au module (parce que le premier octet est à zéro), mais dans un rapport de 2^16 (parce que le second octet est 2).

En CMS, le message est toujours une clé de chiffrement de contenu (CEK) symétrique générée de façon aléatoire. Selon le chiffrement utilisé, il peut être n'importe où entre 8 et 32 octets.

Il doit y avoir au moins 8 octets de bourrage non à zéro. Le bourrage empêche un attaquant de vérifier ses suppositions sur le message chiffré. Imaginons que l'attaquant souhaite déterminer si deux clés chiffrées en RSA sont ou non les mêmes. Parce qu'il y a au moins 255^8 (environ 2^64) valeurs de bourrage différentes, il y a une très forte probabilité que deux chiffrements de la même CEK seront différents. Le bourrage empêche aussi l'attaquant de vérifier ses hypothèses de CEK par des essais de chiffrement avec la clé RSA du receveur car il doit essayer chaque bourrage potentiel pour chaque hypothèse. Noter qu'une attaque à moindre coût serait de faire une recherche exhaustive sur l'espace de CEK d'essai de déchiffrement du contenu et d'examiner le libellé pour voir s'il a un sens.

2.1	L'attaque du million de messages

L'objet de l'attaque du million de messages (MMA) est de récupérer un seul bloc de libellé (bloc formaté) étant donné le texte chiffré (bloc chiffré). L'attaquant doit d'abord capturer le texte chiffré en transit puis utiliser le receveur comme un oracle pour récupérer le libellé en envoyant des versions transformées du texte chiffré et en observant la réponse du receveur.

Appelons le texte chiffré C. L'attaquant va générer une série d'entiers S et calculer C'=C*(S^e) mod n. Au déchiffrement, C' produit un libellé correspondant M'. La plupart des valeurs de M' vont passer à la poubelle mais certaines valeurs de M' (environ une sur 2^16) auront les deux premiers octets corrects à 00 02 et vont donc paraître correctement formatées en PKCS-1. L'attaque se poursuit en cherchant une séquence de valeurs S telles que le M' résultant soit formaté correctement en PKCS-1. Ces informations peuvent être utilisées pour découvrir M. Pour son fonctionnement, cette attaque exige normalement environ 2^20 messages et réponses. On trouvera les détails dans [MMA].

2.2	Applicabilité

Comme la MMA exige une telle quantité de messages, elle doit être montée contre une victime qui accepte de traiter un grand nombre de messages. En pratique, aucun humain ne veut lire autant de messages et donc la MMA ne peut être montée que contre une victime automatisée.

La MMA exige aussi que l'attaquant soit capable de distinguer les cas où M' est formaté en PKCS-1 des cas où il ne l'est pas. Dans le cas de la CMS, l'attaquant va envoyer des messages en CMS avec C' remplaçant la CEK enveloppée. Et donc, il y a cinq possibilités :
1.	M' est incorrectement formaté.
2.	M' est correctement formaté mais la CEK est à première vue incorrecte (mauvaise longueur, etc.)
3.	M' est correctement formaté et la CEK paraît correcte. Une signature ou MAC est présente de sorte que les vérifications d'intégrité vont échouer.
4.	M' est correctement formaté et aucune vérification d'intégrité n'est appliquée. Dans ce cas, il y a quelques possibilités (approximativement 1/32) que le bloc de bourrage de CBC soit correctement vérifié. (La probabilité réelle dépend fortement de la mise en œuvre de réception. Voir la "Note sur le bourrage de chiffrement de bloc" ci-dessous). Le message va paraître correct au niveau CMS mais va échouer au niveau application.
5.	M' est correctement formaté et la CEK résultante est correcte. Ceci est extrêmement improbable mais pas impossible.

La MMA exige que l'attaquant soit capable de distinguer le cas 1 des cas 2 à 4. (Il peut toujours distinguer le cas 5, bien sûr). Cela peut arriver si la victime retourne des erreurs différentes pour chaque cas. L'attaquant peut aussi être capable de distinguer ces cas sur la base des délais – le déchiffrement du message et la vérification de la signature prennent un certain temps. Si la victime répond de façon uniforme aux quatre erreurs, aucune attaque n'est alors possible.

2.2.1	Note sur le bourrage de chiffrement de bloc

La [RFC2360] spécifie une sorte particulière de bourrage de chiffrement de bloc dans laquelle le bloc de chiffrement est bourré avec des octets qui contiennent la longueur du bourrage. Par exemple, un bloc de 5 octets serait bourré avec trois octets de valeur 03, comme dans :

XX XX XX XX XX 03 03 03

La [RFC2360] ne spécifie pas comment ce bourrage sera retiré mais observe simplement qu'il est non ambigu. Une mise en œuvre peut simplement obtenir la valeur de l'octet final et tronquer de façon appropriée ou peut vérifier que tous les octets de bourrage sont corrects. Si le receveur tronque simplement, la probabilité qu'un bloc aléatoire apparaisse bourré correctement est en gros de 1/32. Si le receveur vérifie tous les octets de bourrage, la probabilité est alors de 1/256 + (1/256^2) + ... (environ 1/255).

2.3	Contre mesures
2.3.1	Vérification soigneuse
Même sans contre-mesures, une vérification suffisamment soigneuse peu aller assez loin pour diminuer le succès de la MMA. Si la mise en œuvre receveuse vérifie aussi la longueur de la CEK et les bits de parité (si ils sont disponibles) ET répond de façon identique à toutes ces erreurs, les chances qu'un M' donné soit correctement formaté sont substantiellement diminuées. Cela augment le nombre de messages d'essais nécessaires pour retrouver M. Cependant, cette sorte de vérification augmente seulement le facteur de travail et n'élimine pas entièrement l'attaque parce que certains messages seront encore correctement formaté jusqu'à avoir la longueur de la clé. Cependant, la combinaison des trois sortes de vérifications (bourrage, longueur, bits de parité) augmente le nombre de messages à un point tel que l'attaque est impraticable.

2.3.2	Remplissage aléatoire
La contre mesure la plus simple est de traiter les messages mal formatés comme si ils étaient formatés correctement en PKCS-1. Lorsque la victime détecte un message incorrectement formaté, au lieu de retourner une erreur, elle substitue un message généré de façon aléatoire. En CMS, comme le message est toujours une clé de chiffrement de contenu à enroulement (CEK) la victime devrait simplement substituer une CEK à génération aléatoire de longueur appropriée et continuer. Finalement cela résultera en une erreur de vérification de déchiffrement ou de signature mais c'est exactement ce qui serait arrivé si M' se trouvait être correctement formaté mais contenait une CEK incorrecte. Noter que cette approche empêche aussi l'attaquant de distinguer divers cas de défaillance via la mesure des temps car toutes les défaillances retournent en gros le même comportement par rapport au temps. (Le temps nécessaire pour générer le bourrage aléatoire est négligeable dans presque tous les cas. Si une mise en œuvre a un PRNG très lent, il peut générer un bourrage aléatoire pour chaque message et simplement l'éliminer si la CEK se déchiffre correctement).

Dans une mise en œuvre en couches, il est assez possible que la vérification PKCS-1 survienne à un point dans le code où la longueur de la CEK attendue n'est pas connue. Dans ce cas, la mise en œuvre doit s'assurer que les mauvais bourrages de PKCS-1 et les bourrages de PKCS-1 qui sont corrects avec une longueur de CEK incorrecte se comportent de la même façon. On peut le faire facilement en rendant aléatoires les CEK qui ne sont pas à la bonne longueur ou autrement incorrectement formatées lorsqu'elles sont traitées à la couche qui connaît la bonne longueur.

Note : C'est une faute d'utiliser une CEK fixe, parce que l'attaquant pourrait alors produire un message CMS chiffré avec cette CEK. Ce message se déchiffrerait correctement (c'est-à-dire. apparaîtrait comme une application de CMS complètement valide au receveur), et donc permettrait à l'attaquant de déterminer que le formatage PKCS-1 était incorrect. En fait, la nouvelle CEK devrait être cryptographiquement aléatoire, empêchant ainsi l'attaquant de deviner la prochaine CEK "aléatoire" à utiliser.

2.3.3	OAEP
Le bourrage optimal de chiffrement asymétrique (OAEP, Optimal Asymmetric Encryption Padding) [OAEP] [RFC2437] est une autre technique pour faire le bourrage d'un message dans un bloc de chiffrement RSA. Les mises en œuvre qui utilisent OAEP ne sont pas vulnérables à la MMA. Cependant, OAEP est incompatible avec PKCS-1. Les mises en œuvre de S/MIME et de CMS doivent donc continuer d'utiliser PKCS-1 pour le proche avenir si elles souhaitent communiquer avec les mises en œuvre actuelles largement déployées. OAEP est spécifié pour une utilisation avec des clés AES dans CMS ce qui fournit une chemin amélioré vers OAEP.

2.4	Considérations pour la sécurité

Le présent document décrit comment éviter une certaine classe d'attaques en effectuant le déchiffrement PKCS-1 avec RSA.

3.	Remerciements

Merci à Burt Kaliski et à Russ Housley pour leurs commentaires constructifs détaillés.

4.	Références

[RFC2360]	R. Housley, "Syntaxe de message cryptographique", juin 1999. (Obsolète, voir 3369, 3370) (P.S.).

[MMA]	D. Bleichenbacher, "Chosen Ciphertext Attacks against Protocols based on RSA Encryption Standard PKCS #1", Advances in Cryptology -- CRYPTO 98.

[MMAUPDATE]	D. Bleichenbacher, B. Kaliski, and J. Staddon, "Recent Results on PKCS #1: RSA Encryption Standard", RSA Laboratories' Bulletin #7, 26 juin 1998.

[OAEP]	M. Bellare, P. Rogaway, "Optimal Asymmetric Encryption Padding", Advances in Cryptology -- Eurocrypt 94.

[RFC2313]	B. Kaliski, "PKCS n° 1 : Chiffrement RSA version 1.5", mars 1998.

[RFC2437]	B. Kaliski et J. Staddon, "PKCS n° 1 : Spécifications de la cryptographie RSA version 2.0", octobre 1998. (Obsolète, voir RFC 3447) (Information).

5.	Adresse de l'auteur

Eric Rescorla
RTFM, Inc.
2064 Edgewood Drive
Palo Alto, CA 94303
téléphone : (650) 320-8549
mél : ekr@rtfm.com

6.	Déclaration de copyright

Copyright (C) The Internet Society (2002). Tous droits réservés.

Le présent document et ses traductions peuvent être copiés et fournis aux tiers, et les travaux dérivés qui les commentent ou les expliquent ou aident à leur mise en œuvre peuvent être préparés, copiés, publiés et distribués, en tout ou partie, sans restriction d’aucune sorte, pourvu que la déclaration de copyright ci-dessus et le présent et paragraphe soient inclus dans toutes telles copies et travaux dérivés. Cependant, le présent document lui-même ne peut être modifié d’aucune façon, en particulier en retirant la notice de copyright ou les références à la Internet Society ou aux autres organisations Internet, excepté autant qu’il est nécessaire pour le besoin du développement des normes Internet, auquel cas les procédures de copyright définies dans les procédures des normes Internet doivent être suivies, ou pour les besoins de la traduction dans d’autres langues que l’anglais.

Les permissions limitées accordées ci-dessus sont perpétuelles et ne seront pas révoquées par la Internet Society ou successeurs ou ayant droits.

Le présent document et les informations y contenues sont fournies sur une base "EN L’ÉTAT" et LE CONTRIBUTEUR, L’ORGANISATION QU’IL OU ELLE REPRÉSENTE OU QUI LE/LA FINANCE (S’IL EN EST), LA INTERNET SOCIETY ET LA INTERNET ENGINEERING TASK FORCE DÉCLINENT TOUTES GARANTIES, EXPRIMÉES OU IMPLICITES, Y COMPRIS MAIS NON LIMITÉES À TOUTE GARANTIE QUE L’UTILISATION DES INFORMATIONS CI-ENCLOSES NE VIOLENT AUCUN DROIT OU AUCUNE GARANTIE IMPLICITE DE COMMERCIALISATION OU D’APTITUDE À UN OBJET PARTICULIER.

Remerciement
Le financement de la fonction d’édition des RFC est actuellement fourni par l’Internet Society.