Résumé

  • Le RFC 1186 annonçait 1 450 000 octets par seconde sur un Sun SPARC, environ 70 000 sur un DEC MicroVAX II et 32 000 sur un 80286 à 20 MHz. La difficulté de fabriquer deux messages donnant la même empreinte restait une conjecture.
  • Le RFC 1320 a remplacé ce texte en 1992 avec une implémentation de référence plus portable. Le RFC 6150 a classé MD4 comme historique en 2011 après des attaques documentées contre sa résistance aux collisions.

Un chiffre de débit se vérifie en lançant le programme. Une propriété de sécurité se vérifie en essayant de le tromper, et l'épreuve peut durer des années. Le RFC 1186 de Ronald Rivest réunissait ces deux calendriers. Il décrivait MD4, une fonction transformant un message de longueur quelconque en une empreinte de 128 bits, envisagée notamment pour signer de gros fichiers avec RSA.

Le texte ne se contentait pas de promettre la rapidité. Il donnait trois machines et trois résultats : 1 450 000 octets par seconde sur Sun SPARC, environ 70 000 sur MicroVAX II et environ 32 000 sur un 80286 à 20 MHz. Il précisait aussi que le calcul ne nécessitait pas de grandes tables de substitution. Le lecteur pouvait inspecter dans l'annexe l'interface C, l'implémentation, un programme d'essai et une session exemple. Cette partie de la proposition avait des octets, du matériel et un mode d'emploi.

L'autre partie portait le mot « conjecture ». Rivest estimait à environ 2^64 opérations la recherche de deux messages ayant la même empreinte, et à 2^128 celle d'un message correspondant à une empreinte fixée. Le résumé disait que l'algorithme était récent et appelait de nouvelles analyses. Ces nombres décrivaient la difficulté supposée d'une attaque, pas une mesure effectuée sur les trois ordinateurs. Confondre les deux aurait donné à un chronomètre le pouvoir d'attester une propriété cryptographique.

MD4 était publié dans le domaine public pour examen et éventuelle adoption comme norme. Le RFC d'octobre 1990 restait informatif. Sa description fixait les mots de 32 bits, les blocs de 512 bits, le bourrage et l'encodage de la longueur initiale. Chaque détail facilitait une implémentation compatible; les chercheurs pouvaient désormais attaquer exactement la même construction que les programmeurs exécutaient.

En avril 1992, le RFC 1320 a remplacé le RFC 1186. Sa modification principale, selon son propre texte, était une implémentation de référence plus portable. Il ajoutait aussi un identifiant d'algorithme pour des applications OSI. MD4 circulait mieux entre environnements. Sa résistance restait soumise à l'examen annoncé dès le départ.

Le bilan de cet examen figure dans le RFC 6150. Le document de mars 2011 rappelle une attaque pratique contre les collisions en 1996, estimée à 2^20 calculs MD4, puis un résultat de 2004 ramenant cette complexité à 2^8. Le chiffre de 1990, 2^64, appartenait désormais à l'histoire de l'hypothèse. L'IETF a fait passer le RFC 1320 au statut Historic et recommandé l'abandon de MD4 au profit d'algorithmes existants comme SHA-256.

Le retrait exigeait encore du travail. Le RFC 6150 inventoriait des références et des usages résiduels, dont une voie de compatibilité Microsoft, et rappelait qu'une primitive cryptographique se retire plus lentement qu'elle ne se publie. En 1990, le logiciel arrivait avec un code à exécuter et une difficulté d'attaque à éprouver. En 2011, le registre public portait les résultats de cette épreuve et la facture de migration.

Sources