Comment fonctionne le partage de secret de Shamir

• Le partage de secret de Shamir consiste à diviser un secret en plusieurs fragments ; il ne peut être reconstitué que lorsqu’un nombre de fragments au moins égal au seuil est réuni, et en dessous de ce seuil, aucune information n’est révélée
• Il est utile dans des cas comme une clé maître d’entreprise, la récupération d’un compte familial ou une sauvegarde d’équipe, lorsqu’il est difficile de confier l’intégralité du secret à une seule personne tout en devant pouvoir le restaurer même si certains fragments sont perdus
• Le modèle de base consiste à cacher le secret comme la valeur du point 0 d’un polynôme, puis à distribuer chaque fragment sous la forme d’un point sur la courbe
• Pour un seuil k, on utilise un polynôme de degré k - 1 : deux fragments correspondent à une droite, trois à une parabole, quatre à une courbe cubique
• Le Legacy Kit d’Ente utilise cette méthode comme une couche parmi d’autres pour éviter qu’une carte ne devienne une clé de récupération permanente, tout en permettant de révoquer les cartes émises

---

La méthode qui consiste à diviser un secret avec des points et des polynômes

• Cette méthode a été publiée par Adi Shamir en 1979, et son point essentiel n’est pas seulement qu’elle soit « difficile à casser », mais que si le nombre requis de fragments n’est pas atteint, aucune information n’est révélée
• Deux points distincts déterminent exactement une seule droite, mais avec un seul point, il existe une infinité de droites qui passent par ce point, et chacune coupe l’axe vertical à un endroit différent
• Si le secret est le nombre 7, on peut cacher cette valeur à l’endroit où la droite coupe l’axe vertical
• La pente ne constitue pas le secret lui-même ; elle sert de part aléatoire pour dissimuler le secret
• Si l’on donne à chaque personne un point sur la droite, le point d’une seule personne laisse une infinité de droites possibles, toutes compatibles avec des secrets différents
• En réunissant deux points, la droite est fixée, et il suffit de lire la valeur qu’elle prend en 0 pour reconstituer le secret
• Cette structure correspond à un partage de secret 2-of-n : on peut créer autant de points qu’on le souhaite, mais n’importe quels deux points permettent de retrouver la droite
• Quand le seuil augmente, on utilise des courbes de degré supérieur
  • Une parabole n’est déterminée qu’avec trois points ; si l’on cache le secret à l’endroit où la parabole coupe l’axe vertical, n’importe quels trois fragments permettent la récupération, alors que deux fragments ne suffisent pas
  • De manière générale, pour un seuil k, on utilise un polynôme de degré k - 1
  • 2 fragments correspondent à une droite, 3 fragments à une parabole, 4 fragments à une courbe cubique
  • En pratique, les implémentations n’utilisent pas du papier millimétré mais l’arithmétique des corps finis ; toutefois, la structure reste la même : le secret est la valeur en 0, des coefficients aléatoires le dissimulent, et chaque fragment est un point du polynôme
  • Il est important de comprendre que s’il manque des fragments, il ne s’agit pas simplement d’un calcul difficile du secret : tous les secrets possibles restent encore compatibles

Ente Legacy Kit et ressources de référence

• Ente utilise cette idée dans Legacy Kit
• L’objectif n’est pas seulement de diviser un secret, mais de permettre la récupération sans que les fragments distribués ne deviennent des clés de récupération permanentes
• Legacy Kit utilise la méthode de Shamir comme une couche au sein d’un flux plus large
• Les cartes ne contiennent pas la clé de récupération elle-même ; elles reconstruisent localement un secret distinct, puis participent à une récupération médiée par le serveur
• Grâce à cette structure, les cartes émises peuvent être révoquées, et une carte perdue ne devient pas une responsabilité permanente
• Ressources de référence
  • « How to Share a Secret » d’Adi Shamir
  • « Sharing Secrets Among Friends » de Bruce Schneier
  • Le récit PayPal de Max Levchin
  • Code source d’Ente

[GN⁺]

Commentaires Hacker News

• J’ai écrit mon mémoire de master sur ce sujet. J’ai créé une application qui répartissait les données entre plusieurs fournisseurs de stockage classiques comme Dropbox, Google Drive et OneDrive, en utilisant le partage de secret pour compléter le chiffrement
  L’avantage, c’était que les fournisseurs ne pouvaient plus lire les données, qu’il y avait une redondance supplémentaire puisqu’il suffisait que 2 emplacements restent disponibles, et que, contrairement à d’autres applis de stockage sécurisé où tout est perdu si l’on oublie le mot de passe maître, on pouvait réutiliser les procédures habituelles de récupération de compte

  • L’idée a l’air très bonne ; je me demande si cela a ensuite débouché sur un produit ou une application open source

• Je me demande s’il existe un moyen de combiner plusieurs paires clé/valeur en un seul texte chiffré, sans simplement les concaténer ni faire exploser la taille du résultat, de sorte que tous ceux qui y mettent des informations stockent le même bloc chiffré mais que, avec leur propre clé, chacun déchiffre une valeur différente
  Cela permettrait aux gens de se servir mutuellement de sauvegarde tout en conservant une négation plausible quant à ce qui est réellement stocké

• Dans mon mémoire de master, j’ai appliqué le partage de secret de Shamir à un réseau maillé. L’idée était que même si un nœud du mesh était compromis par un attaquant et que le secret de ce nœud était récupéré, il resterait impossible de casser le chiffrement global

• Notre équipe utilise cette technique pour distribuer la phrase secrète d’un coffre-fort de secours de manière « démocratiquement sûre ». Ce coffre de secours contient la manière d’accéder au coffre principal
  https://packages.debian.org/trixie/ssss est une implémentation correcte et assez intuitive

• Shamir m’a vraiment sauvé la mise une fois. J’ai dû restaurer en urgence une sauvegarde presque oubliée, et j’ai pu reconstituer le mot de passe aléatoire qui avait été utilisé
  Heureusement que j’avais distribué des fragments à ma famille « au cas où »

• Le passage disant que « l’intérêt n’est pas qu’avec trop peu de fragments il soit difficile de calculer le secret, mais qu’avec trop peu de fragments on n’ait absolument aucune information sur le secret. S’il manque un seul fragment, tous les secrets possibles restent également plausibles » me fait penser au processus de factorisation d’entiers via un corps quadratique ou ses variantes
  On cherche un système de congruences modulo n pour finir par calculer les facteurs premiers, mais c’est impossible avant d’en avoir accumulé suffisamment. Chaque congruence contient pourtant certainement une part d’information ; je me suis toujours demandé dans quel espace on était en train de réduire les degrés de liberté
  Ici aussi, chaque fragment restreint l’espace des polynômes, mais pas assez pour révéler le point où la clé coupe l’axe

• C’est une technique vraiment élégante, et c’est au point qu’on pourrait l’enseigner au collège/lycée comme exemple intéressant de ce qu’un informaticien peut faire avec des polynômes

  • Je suis prof de maths au secondaire, et c’est exactement ce que je fais avec mes élèves
    J’introduis Shamir lors d’un cours où l’on retrouve l’équation d’une fonction affine : les élèves choisissent un PIN secret comme pente, créent deux points et les transmettent à deux autres élèves. Ces deux-là doivent alors se mettre en binôme pour retrouver le PIN, et les élèves sont toujours très impliqués

• Bruce Schneier en parlait dans le classique Applied Cryptography, et il y avait aussi une implémentation en Go dans HashiCorp Vault. D’un point de vue pratique, je me suis toujours demandé combien de bits devaient contenir les fragments
  La réponse que j’avais vue sur un newsgroup était « 1 bit de plus que la longueur réelle de la clé ». Aujourd’hui, je me demande quel impact la menace de l’informatique quantique pourrait avoir sur 1) le choix de la taille des fragments et 2) les avantages et inconvénients du partage de secret en général

  • Le schéma de base de Shamir est sûr du point de vue de la théorie de l’information et n’est absolument pas affecté par les ordinateurs quantiques
    On peut créer des fragments Shamir « seuil sur 10 » pour un secret d’1 octet et donner 9 fragments d’1 octet ; aucun ordinateur de l’univers ne pourra retrouver le secret. En pratique, les implémentations doivent ajouter quelques octets pour la vérification d’intégrité, par exemple avec un code d’authentification de message ou une somme de contrôle
  • En général, comme les ordinateurs n’aiment pas trop les approximations, on fait du partage de secret sur un corps fini. La taille d’un fragment correspond à un point (x, y) ; x peut être petit, typiquement de l’ordre de log n lorsqu’il y a n participants, et y est un point arbitraire dans le corps
    Le partage de secret de Shamir est sûr du point de vue de la théorie de l’information : dans un secret k-out-of-n, tant qu’on n’a pas k points, même une attaque par force brute laisse tous les secrets également plausibles. On peut donc choisir la taille en bits du corps comme on veut, mais elle doit évidemment être supérieure à celle du secret. On ne peut pas cacher 100 bits dans un corps fini à 5 éléments
    En général, il faut surtout éviter qu’un attaquant puisse faire une recherche exhaustive sur le secret lui-même, car le schéma est sûr du point de vue de la théorie de l’information, mais le secret ne l’est généralement pas. C’est le cas, par exemple, d’une seed de portefeuille ; on ajoute donc de l’aléa au secret et on choisit un corps de taille suffisante pour empêcher ce type d’attaque
    Selon le modèle de menace, un corps de 80 ou 128 bits est largement suffisant, et la taille des fragments sera donc légèrement supérieure à 80 ou 128 bits. Quant aux ordinateurs quantiques, comme le schéma est sûr du point de vue de la théorie de l’information, aucune attaque n’est possible
  • Sauf changement récent, HashiCorp dispose toujours d’une implémentation pour le processus seal/unseal de Vault
  • Le schéma de Shamir repose sur le théorème fondamental de l’algèbre. Il dit qu’il faut n+1 points pour définir de manière unique un polynôme de degré n
    Donc, pour construire une configuration n-of-k, on crée un polynôme p(x) de degré n-1 puis on en prélève k points arbitraires. Le iᵉ fragment n’est rien d’autre que (xi, yi), donc son nombre de bits est déterminé par le corps dans lequel le polynôme est défini
    Le corps doit être assez grand pour contenir tout le secret, et comme il faut stocker les deux valeurs (x, y), la taille d’un fragment est au minimum le double de celle du secret. Il faut aussi un contrôle d’intégrité pour vérifier qu’un fragment n’a pas été corrompu
    À ma connaissance, l’informatique quantique ne change rien ici. S’il manque ne serait-ce qu’un seul point, le dernier point peut faire varier le secret vers n’importe quelle valeur, et il n’existe aucun moyen de distinguer cela
  • Le secret complet n’a pas nécessairement besoin d’être un seul élément du corps sous-jacent. Il peut aussi s’agir d’un n-uplet d’éléments d’un corps plus petit
    Si l’on ne s’attend pas à un nombre absurde de fragments, GF(2^8) est un choix assez naturel, et il évite d’avoir à manipuler de grands entiers

• L’implémentation d’Ente est ici : (https://2of3.ente.com/)

  • C’est celle que je préfère parmi tout ce que j’ai vu jusqu’ici, et elle est très conviviale. J’aimerais juste qu’elle soit un peu plus configurable
    Idéalement, on pourrait créer des configurations comme 3 of 4: A B C D ou 2 of 3: E F G, ainsi que 1 of 1: H
    Ce serait bien aussi de pouvoir nommer les cartes pour qu’il soit clair, lors de la récupération, de quoi on a exactement besoin. Cela dit, la simplicité du design actuel a aussi ses avantages
  • Il existe aussi une implémentation empaquetée dans la plupart des distributions Linux : http://point-at-infinity.org/ssss
  • Il existe plusieurs versions basées sur le navigateur, utilisables en ligne ou téléchargeables pour un usage hors ligne
    https://bs.parity.io/ -- http://passguardian.com/ -- https://iancoleman.io/shamir/

• Il y a quelques années, j’ai créé un petit outil qui exécute le partage de secret de Shamir dans le navigateur. Si l’on télécharge la page, on peut aussi l’utiliser entièrement hors ligne
  https://simon-frey.com/s4/

  • J’avais téléchargé cette page il y a quelques années et l’avais copiée sur quelques clés USB, avec une base de données KeePass et des fragments de mot de passe
    J’en ai distribué à quelques membres de ma famille en leur disant que, si je mourais, ils devraient les remettre à ma femme