Algorithme à Double Ratchet

En cryptographie, l'algorithme du Double Ratchet (précédemment appelé Axolotl Ratchet) est un algorithme de gestion de clés qui a été développé par Trevor Perrin et Moxie Marlinspike en 2013. Il peut être utilisé dans le cadre d'un protocole cryptographique pour fournir un chiffrement de bout en bout pour la messagerie instantanée. Après un premier échange de clés, il gère le renouvellement continu et la maintenance des clés de session à courte durée de vie. Il combine un Ratchet basé sur l'échange de clés Diffie-Hellman (DH) et un Ratchet basé sur une fonction de dérivation de clés (KDF) comme par exemple une fonction de hachage et est donc appelé un double Ratchet. Le terme de Ratchet ou Cliquet peut-être traduit par l'idée d'une roue dentée (roue à rochet) qui ne peut tourner que dans un seul sens, chaque dent correspondant à un état particulier.

Ratchet wheel ou roue à rochet

Propriétés

L'algorithme à Double Cliquet prend en charge des fonctionnalités qui étaient déjà bien connues dans le monde de la cryptographie : chiffrement des communications de bout en bout, authentification de l'interlocuteur distant et protection contre la modification des messages échangés. Il hérite à la fois des propriétés du protocole d'échange de clés Diffie-Hellman, qui permet à deux interlocuteurs de convenir d'une même clé privée sans l'échanger explicitement, et du principe de Dérivation de Clés qui permet de créer de nouvelles clés à partir des anciennes sans qu'on puisse retrouver les anciennes clés à l'aide des nouvelles. Le protocole de messagerie Off The Record (qui fait usage de l'algorithme de Diffie-Hellman) permet d'assurer la confidentialité persistante (confidentialité des communications passées) des échanges de données et de rétablir automatiquement la confidentialité dans le cas où une des clés de session aurait été compromise. Il permet également d'assurer la confidentialité persistante des communications dans le cas où la clé privée principale aurait été compromise.

Le protocole de dérivation de clés permet de renouveler les clés de session sans interaction entre les deux interlocuteurs.

Fonctionnement

De manière métaphorique, on peut se figurer que chaque interlocuteur possède deux roues dentées (d'où le nom de l'algorithme) : une roue pour les paires de clés Diffie-Hellman, et une roue pour les clés dérivées. Le protocole de Diffie-Hellman permet de renouveler la clé secrète partagée, tandis que la chaine KDF (key derivation function) permet de créer de nouvelles clés de session éphémères. Dans le cas d'applications de messagerie chiffrée comme Signal ou WhatsApp, chaque clé de session correspond à un unique message envoyé ou reçu.

Comme indiqué précédemment, la dérivation de clé fonctionne sous forme de chaîne. On part d'une clé secrète partagée et d'une entrée (un sel ou un poivre) qu'on fournit à la fonction de dérivation. Celle-ci fournit deux nouvelles clés : une clé de chiffrement ou déchiffrement pour le prochain message, et une clé d'initiation pour la fonction de dérivation KDF.

Schéma de la chaîne de création de clés par dérivation KDF

Chaque nouvelle clé créée par la KDF ne permet pas de retrouver les clés précédentes, à l'instar d'une fonction de hachage. C'est ce qui assure la confidentialité persistante des messages antérieurs. Chaque interlocuteur possède donc deux chaînes KDF : une pour envoyer, et une pour recevoir. La chaîne KDF de réception de chaque interlocuteur se synchronise avec la chaîne d'émission de l'autre interlocuteur en calculant les clés correspondant aux messages reçus. Idéalement, chaque message envoyé contient dans ses métadonnées sa propre position dans la chaîne, ce qui permet au destinataire de déchiffrer le message avec la bonne clé, même si l'ordre des messages a été interverti au cours de la communication.

Cependant, si ce système assure la sécurité des messages précédents, il ne permet pas d'assurer la confidentialité des messages futurs. En effet, un attaquant ayant réussi à compromettre une des clés d'initiation de la chaîne KDF pourra aisément en déduire les clés à venir. C'est la raison pour laquelle les interlocuteurs utilisent aussi souvent que possible le protocole Diffie-Hellman pour réinitialiser les chaînes KDF.

Si on suppose que les interlocuteurs se nomment Bob et Alice, on pourrait résumer l'algorithme de la manière suivante :

• Bob et Alice conviennent d'une clé secrète via Diffie-Hellman
• Alice veut envoyer $n$ messages à Bob
  • Alice calcule les $n$ prochaines clés de session via la chaîne KDF
  • Alice chiffre les messages avec chacune des clés
  • Alice envoie les messages à Bob
• Bob reçoit les messages
  • Bob calcule les $n$ clés suivantes de sa chaîne de réception
  • Bob déchiffre les messages
• Si Bob veut répondre aux messages, il effectue les mêmes opérations qu'Alice
• Périodiquement Bob et Alice conviennent d'une nouvelle clé secrète via Diffie-Hellman

Applications

Voici une liste d'applications qui font usage cet algorithme ou une version dérivée de celui-ci :

• ChatSecure
• Conversations
• Cryptocat
• Facebook Messenger
• G Data Secure Chat
• Gajim
• GNOME Fractal
• Google Allo
• Google Messages
• Haven
• Pond
• Element
• Signal
• Silent Phone
• Skype
• Viber
• WhatsApp
• Wire

(Attention, certaines n'en font usage que pour certains types de conversation)

Liens externes

• (en) Caractéristiques techniques
• (en) « Advanced cryptographic ratcheting », un résumé de l'algorithme par Moxie Marlinspike