Comment le paradoxe des anniversaires aide-t-il à falsifier un contrat signé ?

Parce qu'un faussaire n'a pas besoin de retrouver une empreinte précise : il lui suffit d'un contrat honnête et d'un contrat frauduleux qui partagent la même. Une signature numérique porte en général sur le hachage du message, une courte empreinte numérique, plutôt que sur le message lui-même. Trouver deux entrées quelconques ayant le même hachage, une collision, demande environ 2 puissance l/2 essais pour un hachage de l bits, alors qu'atteindre un hachage précis en demande environ 2 puissance l−1. Ce raccourci s'appelle une attaque des anniversaires.

Le nom vient du paradoxe des anniversaires. Dans une classe de 30 élèves, la probabilité qu'au moins deux soient nés le même jour est d'environ 70 %, ce qui paraît bien trop élevé, parce qu'on compare chaque élève avec tous les autres. Si l'on demande plutôt si quelqu'un est né un jour précis, la probabilité tombe à environ 7,9 %. « N'importe quelle correspondance » est une cible bien plus facile que « cette correspondance-là ».

Voici le scénario classique. Mallory veut faire signer à Bob un contrat frauduleux. Elle rédige un contrat honnête et un contrat frauduleux, puis repère dans le contrat honnête des endroits modifiables sans en changer le sens : des virgules en plus, des lignes vides, une ou deux espaces après une phrase, des synonymes. En combinant ces retouches, elle obtient un nombre énorme de variantes honnêtes, et elle fait varier le contrat frauduleux aussi. Elle les hache toutes jusqu'à ce qu'une version honnête et une version frauduleuse partagent le même hachage. Bob signe la version honnête ; Mallory déplace sa signature sur la version frauduleuse, et la signature « prouve » désormais que Bob l'a signée.

Il y a une limite : même si les signatures numériques présentent des failles liées à l'attaque des anniversaires, celle-ci ne permet pas de casser un système de chiffrement plus vite qu'une simple attaque par force brute.