Partage secret - Secret sharing

Le partage de secret (également appelé partage de secret ) fait référence à des méthodes de distribution d'un secret parmi un groupe de participants, chacun d'eux se voyant attribuer une part du secret. Le secret ne peut être reconstitué que lorsqu'un nombre suffisant, de types éventuellement différents, d'actions sont réunis ; les actions individuelles ne sont d'aucune utilité en elles-mêmes.

Dans un type de système de partage secret, il y a un croupier et n joueurs . Le croupier donne une part du secret aux joueurs, mais ce n'est que lorsque des conditions spécifiques sont remplies que les joueurs pourront reconstituer le secret à partir de leurs parts. Le croupier y parvient en donnant à chaque joueur une part de manière à ce que tout groupe de t (pour le seuil ) ou plus de joueurs puisse ensemble reconstruire le secret, mais aucun groupe de moins de t joueurs ne le peut. Un tel système est appelé schéma à ( t , n ) -seuil (parfois il est écrit comme schéma à ( n , t ) -seuil).

Le partage secret a été inventé indépendamment par Adi Shamir et George Blakley en 1979.

Importance

Les schémas de partage secret sont idéaux pour stocker des informations très sensibles et très importantes. Les exemples incluent : les clés de cryptage , les codes de lancement de missiles et les comptes bancaires numérotés . Chacune de ces informations doit rester hautement confidentielle, car leur exposition pourrait être désastreuse, cependant, il est également essentiel qu'elles ne soient pas perdues. Les méthodes traditionnelles de cryptage sont mal adaptées pour atteindre simultanément des niveaux élevés de confidentialité et de fiabilité. En effet, lors du stockage de la clé de cryptage, il faut choisir entre conserver une seule copie de la clé dans un emplacement pour un maximum de secret, ou conserver plusieurs copies de la clé dans différents emplacements pour une plus grande fiabilité. L'augmentation de la fiabilité de la clé en stockant plusieurs copies diminue la confidentialité en créant des vecteurs d'attaque supplémentaires ; il y a plus de chances qu'une copie tombe entre de mauvaises mains. Les schémas de partage de secrets résolvent ce problème et permettent d'atteindre des niveaux arbitrairement élevés de confidentialité et de fiabilité.

Les schémas de partage secret sont importants dans les environnements de cloud computing . Ainsi, une clé peut être distribuée sur de nombreux serveurs par un mécanisme de partage de secret à seuil. La clé est ensuite reconstruite en cas de besoin. Le partage secret a également été suggéré pour les réseaux de capteurs où les liens sont susceptibles d'être exploités en envoyant les données en partage, ce qui complique la tâche de l'espion. La sécurité dans de tels environnements peut être renforcée en changeant continuellement la façon dont les actions sont construites.

Partage secret « sécurisé » ou « non sécurisé »

Un schéma de partage de secret sécurisé distribue les partages de sorte que toute personne avec moins de t partages n'ait pas plus d'informations sur le secret qu'une personne avec 0 partage.

Considérons par exemple le schéma de partage secret dans lequel la phrase secrète « mot de passe » est divisée en les partages « pa–––––– », « ––ss–––– », « ––––wo–– », et "––––––rd". Une personne avec 0 partage sait seulement que le mot de passe se compose de huit lettres, et devrait donc deviner le mot de passe à partir de 26 ⁸ = 208 milliards de combinaisons possibles. Une personne avec une part, cependant, n'aurait à deviner que les six lettres, à partir de 26 ⁶ = 308 millions de combinaisons, et ainsi de suite à mesure que plus de personnes s'entendent. Par conséquent, ce système n'est pas un schéma de partage de secret « sécurisé », car un joueur avec moins de t partages de secrets est en mesure de réduire le problème d'obtention du secret interne sans avoir d'abord besoin d'obtenir tous les partages nécessaires.

En revanche, considérons le schéma de partage de secret où X est le secret à partager, P _i sont des clés de chiffrement asymétriques publiques et Q _i leurs clés privées correspondantes. Chaque joueur J reçoit { P ₁ ( P ₂ (...( P _N ( X )))), Q _j }. Dans ce schéma, tout joueur avec la clé privée 1 peut supprimer la couche externe de cryptage, un joueur avec les clés 1 et 2 peut supprimer la première et la deuxième couche, et ainsi de suite. Un joueur avec moins de N clés ne peut jamais atteindre complètement le secret X sans avoir d'abord besoin de déchiffrer un blob chiffré par clé publique pour lequel il n'a pas la clé privée correspondante - un problème qui est actuellement considéré comme infaisable par les calculs. De plus, nous pouvons voir que tout utilisateur possédant toutes les N clés privées est capable de déchiffrer toutes les couches externes pour obtenir X , le secret, et par conséquent ce système est un système de distribution de secret sécurisé.

Limites

Plusieurs schémas de partage de secrets sont censés être sécurisés sur le plan de l'information et peuvent être prouvés l'être, tandis que d'autres renoncent à cette sécurité inconditionnelle pour une efficacité améliorée tout en maintenant une sécurité suffisante pour être considérés comme aussi sécurisés que les autres primitives cryptographiques courantes. Par exemple, ils pourraient permettre aux secrets d'être protégés par des partages de 128 bits d'entropie chacun, puisque chaque partage serait considéré comme suffisant pour contrecarrer tout adversaire imaginable d'aujourd'hui, nécessitant une attaque par force brute de taille moyenne 2 ¹²⁷ .

Commun à tous les schémas de partage de secrets sécurisés inconditionnellement, il existe des limitations :

• Chaque part du secret doit être au moins aussi grande que le secret lui-même. Ce résultat est basé sur la théorie de l'information , mais peut être compris intuitivement. Étant donné t − 1 parts, aucune information ne peut être déterminée sur le secret. Ainsi, le partage final doit contenir autant d'informations que le secret lui-même. Il existe parfois une solution de contournement à cette limitation en compressant d' abord le secret avant de le partager, mais cela n'est souvent pas possible car de nombreux secrets (clés par exemple) ressemblent à des données aléatoires de haute qualité et sont donc difficiles à compresser.
• Tous les schémas de partage de secrets utilisent des bits aléatoires . Pour distribuer un secret d'un bit parmi les t personnes seuil , t − 1 bits aléatoires sont nécessaires. Pour distribuer un secret de longueur arbitraire b bits, une entropie de ( t − 1) × b bits est nécessaire.

Partage de secrets triviaux

t = 1

t = 1 le partage de secret est trivial. Le secret peut simplement être distribué à tous les n participants.

t = n

Il existe plusieurs ( t , n ) schémas de partage de secret pour t = n , lorsque tous les partages sont nécessaires pour récupérer le secret :

1. Encodez le secret sous la forme d'un nombre binaire de longueur arbitraire s . Donnez à chaque joueur i (sauf un) un nombre aléatoire p _i de même longueur que s . Donnez au dernier joueur le résultat de ( s XOR p ₁ XOR p ₂ XOR ... XOR p _{n −1} ) où XOR est exclusif au niveau du bit ou . Le secret est le XOR bit à bit de tous les numéros des joueurs ( p ).
2. De plus, (1) peut être exécuté à l'aide de n'importe quel opérateur linéaire dans n'importe quel champ . Par exemple, voici une alternative fonctionnellement équivalente à (1). Choisissons des entiers 32 bits avec une sémantique de débordement bien définie (c'est-à-dire que la bonne réponse est préservée, modulo 2 ³² ). Premièrement, s peut être divisé en un vecteur de M entiers de 32 bits appelé v _secret . Alors ( n − 1) joueurs reçoivent chacun un vecteur de M entiers aléatoires, le joueur i recevant v _i . Le joueur restant reçoit v _n = ( v _secret − v ₁ − v ₂ − ... − v _{n −1} ). Le vecteur secret peut ensuite être récupéré en additionnant tous les vecteurs du joueur.

1 < t < n , et, plus généralement, tout sous-ensemble souhaité de {1,2,...,n}

La difficulté réside dans la création de schémas qui sont toujours sécurisés, mais ne nécessitent pas tous les n partages. Par exemple, imaginez que le conseil d'administration d'une entreprise souhaite protéger sa formule secrète. Le président de la société devrait pouvoir accéder à la formule en cas de besoin, mais en cas d'urgence, 3 des 12 membres du conseil d'administration pourraient débloquer la formule secrète ensemble. Cela peut être accompli par un schéma de partage secret avec t = 3 et n = 15, où 3 actions sont attribuées au président et 1 à chaque membre du conseil d'administration.

Lorsque l'efficacité de l'espace n'est pas un problème, des schémas triviaux t = n peuvent être utilisés pour révéler un secret à tout sous-ensemble souhaité de joueurs simplement en appliquant le schéma pour chaque sous-ensemble. Par exemple, pour révéler un secret s à deux des trois joueurs Alice, Bob et Carol, créez trois ( ) partages secrets différents pour s , en donnant les trois ensembles de deux partages à Alice et Bob, Alice et Carol, et Bob et Carole. ${\displaystyle {\binom {3}{2}}}$${\style d'affichage t=n=2}$

Partage efficace des secrets

L'approche triviale devient rapidement impraticable à mesure que le nombre de sous-ensembles augmente, par exemple lors de la révélation d'un secret à 50 des 100 joueurs, ce qui nécessiterait la création de schémas et chaque joueur doit maintenir des ensembles d'actions distincts pour chaque schéma. Dans le pire des cas, l'augmentation est exponentielle. Cela a conduit à la recherche de schémas permettant de partager efficacement les secrets avec un certain nombre de joueurs. ${\displaystyle {\binom {100}{50}}\environ 1.009\times 10^{29}}$${\displaystyle {\binom {99}{49}}\approx 5.04\times 10^{28}}$

Le schéma de Shamir

Dans ce schéma, n'importe quel t sur n actions peut être utilisé pour récupérer le secret. Le système repose sur l'idée que vous pouvez ajuster un polynôme unique de degré t − 1 à n'importe quel ensemble de t points qui se trouvent sur le polynôme. Il faut deux points pour définir une ligne droite, trois points pour définir complètement une quadratique, quatre points pour définir une courbe cubique, et ainsi de suite. C'est-à-dire qu'il faut t points pour définir un polynôme de degré t − 1 . La méthode consiste à créer un polynôme de degré t − 1 avec le secret comme premier coefficient et les coefficients restants choisis au hasard. Trouvez ensuite n points sur la courbe et donnez-en un à chacun des joueurs. Lorsqu'au moins t des n joueurs révèlent leurs points, il y a suffisamment d'informations pour leur adapter un ( t − 1) polynôme de degré, le premier coefficient étant le secret.

Le schéma de Blakley

Deux droites non parallèles dans le même plan se coupent en un seul point. Trois plans non parallèles dans l'espace se coupent en un seul point. Plus généralement, tout hyperplan de dimension n non parallèle ( n − 1) se coupe en un point spécifique. Le secret peut être codé comme n'importe quelle coordonnée unique du point d'intersection. Si le secret est codé en utilisant toutes les coordonnées, même si elles sont aléatoires, alors un initié (quelqu'un en possession d'un ou plusieurs des hyperplans ( n − 1) -dimensionnels ) obtient des informations sur le secret puisqu'il sait qu'il doit se trouver sur son avion. Si un initié peut acquérir plus de connaissances sur le secret qu'un étranger, alors le système n'a plus de sécurité théorique de l'information . Si une seule des n coordonnées est utilisée, alors l'initié ne sait pas plus qu'un étranger (c'est-à-dire que le secret doit se trouver sur l' axe des x pour un système à 2 dimensions). Chaque joueur reçoit suffisamment d'informations pour définir un hyperplan ; le secret est récupéré en calculant le point d'intersection des avions, puis en prenant une coordonnée spécifiée de cette intersection.

Le schéma de Blakley en trois dimensions : chaque part est un plan et le secret est le point d'intersection de trois parts. Deux partages sont insuffisants pour déterminer le secret, bien qu'ils fournissent suffisamment d'informations pour le réduire à la ligne d' intersection des deux plans.

Le schéma de Blakley est moins économe en espace que celui de Shamir ; alors que les parts de Shamir sont chacune aussi grandes que le secret d'origine, les parts de Blakley sont t fois plus grandes, où t est le nombre seuil de joueurs. Le schéma de Blakley peut être renforcé en ajoutant des restrictions sur les avions utilisables en tant qu'actions. Le schéma résultant est équivalent au système polynomial de Shamir.

Utilisation du théorème des restes chinois

Le théorème des restes chinois peut également être utilisé dans le partage de secrets, car il nous fournit une méthode pour déterminer de manière unique un nombre S modulo k de nombreux entiers deux à deux premiers entre eux , étant donné que . Il existe deux schémas de partage secret qui utilisent le théorème des restes chinois , les schémas de Mignotte et d'Asmuth-Bloom. Ce sont des schémas de partage de secret à seuil, dans lesquels les parts sont générées par réduction modulo les entiers , et le secret est récupéré en résolvant essentiellement le système de congruences en utilisant le théorème des restes chinois . ${\displaystyle m_{1},m_{2},...,m_{k}}$${\displaystyle S<\prod _{i=1}^{k}m_{i}}$${\style d'affichage m_{i}}$

Partage de secret proactif

Si les joueurs stockent leurs partages sur des serveurs informatiques non sécurisés, un attaquant pourrait s'introduire et voler les partages. S'il n'est pas pratique de changer le secret, les actions sans compromis (à la Shamir) peuvent être renouvelées. Le croupier génère un nouveau polynôme aléatoire avec un terme constant zéro et calcule pour chaque joueur restant une nouvelle paire ordonnée, où les coordonnées x de l'ancienne et de la nouvelle paire sont les mêmes. Chaque joueur ajoute ensuite les anciennes et les nouvelles coordonnées y et conserve le résultat comme nouvelle coordonnée y du secret.

Tous les partages non mis à jour que l'attaquant a accumulés deviennent inutiles. Un attaquant ne peut récupérer le secret que s'il trouve suffisamment d'autres partages non mis à jour pour atteindre le seuil. Cette situation ne devrait pas arriver car les joueurs ont supprimé leurs anciennes actions. De plus, un attaquant ne peut récupérer aucune information sur le secret d'origine à partir des fichiers de mise à jour car ils ne contiennent que des informations aléatoires.

Le croupier peut modifier le nombre de seuils lors de la distribution des mises à jour, mais doit toujours rester vigilant quant aux joueurs conservant des actions expirées.

Partage de secrets vérifiables

Un joueur peut mentir sur sa propre part pour accéder à d'autres parts. Un système de partage de secrets vérifiables (VSS) permet aux joueurs d'être certains qu'aucun autre joueur ne ment sur le contenu de leurs actions, jusqu'à une probabilité d'erreur raisonnable. De tels schémas ne peuvent pas être calculés de manière conventionnelle ; les joueurs doivent collectivement additionner et multiplier des nombres sans que personne ne sache exactement ce qui est ajouté et multiplié. Tal Rabin et Michael Ben-Or ont conçu un système informatique multipartite (MPC) qui permet aux joueurs de détecter la malhonnêteté de la part du croupier ou d'une partie jusqu'à un tiers du nombre seuil de joueurs, même si ces joueurs sont coordonnés par un attaquant « adaptatif » qui peut changer de stratégie en temps réel en fonction des informations révélées.

Partage de secret sécurisé informatiquement

L'inconvénient des schémas de partage de secret à sécurité inconditionnelle est que le stockage et la transmission des partages nécessitent une quantité de ressources de stockage et de bande passante équivalente à la taille du secret multipliée par le nombre de partages. Si la taille du secret était importante, disons 1 Go, et que le nombre d'actions était de 10, alors 10 Go de données doivent être stockées par les actionnaires. Des techniques alternatives ont été proposées pour augmenter considérablement l'efficacité des schémas de partage de secrets, en abandonnant l'exigence de sécurité inconditionnelle.

L'une de ces techniques, connue sous le nom de partage secret fait court , combine l'algorithme de dispersion d'informations (IDA) de Rabin avec le partage secret de Shamir. Les données sont d'abord cryptées avec une clé générée aléatoirement, à l'aide d'un algorithme de cryptage symétrique. Ensuite, ces données sont divisées en N morceaux à l'aide de l'IDA de Rabin. Cet IDA est configuré avec un seuil, d'une manière similaire aux schémas de partage de secrets, mais contrairement aux schémas de partage de secrets, la taille des données résultantes augmente d'un facteur de (nombre de fragments / seuil). Par exemple, si le seuil était de 10 et que le nombre de fragments produits par IDA était de 15, la taille totale de tous les fragments serait (15/10) ou 1,5 fois la taille de l'entrée d'origine. Dans ce cas, ce schéma est 10 fois plus efficace que si le schéma de Shamir avait été appliqué directement sur les données. La dernière étape du partage de secret simplifié consiste à utiliser le partage de secret Shamir pour produire des parts de la clé symétrique générée de manière aléatoire (qui est généralement de l'ordre de 16 à 32 octets), puis de donner une part et un fragment à chaque actionnaire.

Une approche connexe, connue sous le nom d'AONT-RS, applique une transformation tout ou rien aux données en tant qu'étape de pré-traitement vers un IDA. La transformation Tout ou rien garantit que tout nombre de partages inférieur au seuil est insuffisant pour déchiffrer les données.

Partage de secrets multi-secrets et peu encombrants (par lots)

Un schéma de partage de secrets k- of- n, à sécurité théorique de l'information, génère n parts, chacune d'une taille au moins égale à celle du secret lui-même, ce qui fait que le stockage total requis est au moins n fois plus grand que le secret. Dans le partage multi-secrets conçu par Matthew K. Franklin et Moti Yung , plusieurs points des secrets de l'hôte polynomial; la méthode s'est avérée utile dans de nombreuses applications, du codage aux calculs multipartites. Dans le partage de secret efficace dans l'espace, conçu par Abhishek Parakh et Subhash Kak , chaque partage correspond à peu près à la fraction (k-1) de la taille du secret.

Ce schéma utilise l'interpolation polynomiale répétée et a des applications potentielles dans la diffusion sécurisée d'informations sur le Web et dans les réseaux de capteurs . Cette méthode est basée sur un partitionnement de données faisant intervenir les racines d'un polynôme dans un corps fini. Certaines vulnérabilités des schémas de partage de secrets économes en espace associés ont été signalées plus tard. Ils montrent qu'un schéma basé sur une méthode d'interpolation ne peut pas être utilisé pour implémenter un schéma ( k , n ) lorsque les k secrets à distribuer sont intrinsèquement générés à partir d'un polynôme de degré inférieur à k − 1 , et le schéma ne fonctionne pas si tous des secrets à partager sont les mêmes, etc.

Autres utilisations et applications

Un schéma de partage de secret peut sécuriser un secret sur plusieurs serveurs et rester récupérable malgré plusieurs pannes de serveur. Le courtier peut agir en tant que plusieurs participants distincts, répartissant les actions entre les participants. Chaque partage peut être stocké sur un serveur différent, mais le dealer peut récupérer le secret même si plusieurs serveurs tombent en panne tant qu'ils peuvent récupérer au moins t partages ; cependant, les pirates qui s'introduisent dans un serveur ne connaîtront toujours pas le secret tant que moins de t partages sont stockés sur chaque serveur.

C'est l'un des principaux concepts derrière le projet informatique Vanish à l' Université de Washington , où une clé aléatoire est utilisée pour crypter les données, et la clé est distribuée en tant que secret sur plusieurs nœuds d'un réseau P2P . Pour déchiffrer le message, au moins t nœuds du réseau doivent être accessibles ; le principe de ce projet étant que le nombre de noeuds de partage secrets sur le réseau diminuera naturellement au fil du temps, ce qui provoque donc le secret pour finalement disparaître . Cependant, le réseau est vulnérable à une attaque Sybil , rendant ainsi Vanish non sécurisé.

Tout actionnaire qui dispose de suffisamment d'informations pour décrypter le contenu à tout moment est en mesure de prendre et de stocker une copie de X. Par conséquent, bien que des outils et des techniques tels que Vanish puissent rendre les données irrécupérables dans leur propre système après un certain temps, il n'est pas possible pour forcer la suppression des données une fois qu'un utilisateur malveillant les a vues. C'est l'une des principales énigmes de la gestion des droits numériques .

Un revendeur pourrait envoyer t actions, qui sont toutes nécessaires pour récupérer le secret d'origine, à un seul destinataire. Un attaquant devrait intercepter tous les t actions pour récupérer le secret, une tâche qui est plus difficile que l' interception d' un seul fichier, en particulier si les actions sont envoyées en utilisant différents médias (par exemple , certains sur l' Internet , certains envoyés par la poste sur CD ).

Pour les secrets volumineux, il peut être plus efficace de chiffrer le secret, puis de distribuer la clé à l'aide du partage de secret.

Le partage de secret est une primitive importante dans plusieurs protocoles pour le calcul multipartite sécurisé . Le partage de secret peut également être utilisé pour l'authentification des utilisateurs dans un système.

Voir également

Les références

Liens externes

• Ubuntu Manpage: gfshare - explication du partage secret de Shamir dans GF (2 ⁸ )
• Description des schémas de Shamir et Blakley
• Brevet pour l'utilisation du partage de secrets pour récupérer les phrases de passe PGP (et autres ?) Brevet américain 6,662,299
• Une bibliographie sur les schémas de partage de secrets
• Systèmes de signature de code utilisant le secret partagé sur la Wayback Machine (archivé le 14 février 2008)
• Beimel, Amos (2011). « Schémas de partage de secrets : une enquête » (PDF) .