Shamir Secret Sharing

Eine Wallet ist eine Anwendung oder ein Gerät zum Empfangen und Senden von Bitcoin. Anna möchte eine Sicherung, bei der einige Aufzeichnungen verloren gehen dürfen. Sie wählt drei von fünf: Es entstehen fünf verschiedene Anteile, und beliebige drei gültige Anteile desselben Satzes stellen das Geheimnis wieder her. Zwei darf sie verlieren, drei nicht. Die nötige Anzahl heißt Schwelle; allgemein bedeutet k aus n, dass k der n erzeugten Anteile gebraucht werden und n−k verloren gehen dürfen. Die Schwelle erkennt aber Annas Zustimmung nicht. Wer drei Anteile erhält oder ihre Besitzer zur Zusammenarbeit bringt, kann dasselbe Geheimnis wiederherstellen. Eine niedrigere Schwelle erleichtert die Wiederherstellung, verkleinert aber auch die dafür ohne Anna nötige Gruppe. [1] [6]

Anna gewinnt wenig, wenn alle fünf Dateien in einem einzigen Cloudkonto liegen. Geht dieses verloren oder wird es kompromittiert, sind alle Anteile zugleich betroffen. Zur Sicherung gehören eine durchdachte Verteilung, Angaben zu Verfahren und Parametern sowie eine Wiederherstellungsprüfung auf einem vertrauenswürdigen Gerät. Sollen auch Erben den Plan nutzen, müssen sie wissen, was sie suchen und wie sie sicher damit umgehen. Eine neue zufällige Aufteilung desselben Geheimnisses S erzeugt einen neuen Satz; alte und neue Anteile werden nicht vermischt. Ein ausreichender alter Satz stellt S jedoch weiterhin her. Eine Neuverteilung widerruft also keine bereits offengelegte brauchbare Sicherung und ändert auch das Geheimnis nicht. [1] [4]

Bei der gewöhnlichen Wiederherstellung liegt das gesamte Geheimnis wieder auf einem Gerät vor. Ist es kompromittiert, kann ein Angreifer es genau dann erlangen. Handelt es sich um einen Private Key, also einen geheimen Zahlenwert zum Erstellen einer digitalen Signatur zur Freigabe einer Ausgabe, kann sein Besitzer anschließend ohne weitere Anteile signieren. Multisig verlangt dagegen mehrere Signaturen entsprechend den Bedingungen der jeweiligen Ausgabe. Daneben gibt es Schwellwertsignaturen: Mit einem zusätzlichen MPC-Protokoll, einer sicheren gemeinsamen Berechnung mehrerer Teilnehmer, können Anteile zu einer Signatur beitragen, ohne den ganzen Schlüssel zusammenzusetzen. NIST unterscheidet diese Fälle. Ein Shamir-Anteil allein richtet noch kein solches Signaturprotokoll ein. [3] [5] [6]

Zwei Programme mit Shamir im Namen müssen die Anteile des jeweils anderen nicht lesen können. Für die Wiederherstellung müssen Rechenoperationen, Wertecodierung, Kennungen und Zugehörigkeit zum selben Satz passen. SLIP-39 ist ein konkreter darauf aufbauender Standard: Er ergänzt eine Wortliste, Metadaten als Begleitinformationen, Gruppen, Verschlüsselung und Fehlerprüfungen. Das Grundprinzip ist daher keine Anleitung, eine vorhandene Seed Phrase von Hand zu teilen. Bevor du einer solchen Sicherung eine Wallet anvertraust, musst du das unterstützte Format kennen und prüfen, ob der vorgesehene Ablauf sie tatsächlich wiederherstellt. [2]

Bei drei von fünf ist klar, was der Verlust von zwei Anteilen bedeutet. Ein beschädigter oder gefälschter Anteil kann die grundlegende Berechnung jedoch zu einem anderen Geheimnis führen, statt einen Mangel zu melden. Das Verfahren allein bestätigt weder die Herkunft noch die Ehrlichkeit des Erstellers. Fehlererkennung, Fehlerkorrektur und verifiable secret sharing, also Verfahren zur Prüfung einer korrekten Aufteilung, sind zusätzliche Schichten mit eigenen Voraussetzungen. SLIP-39 ergänzt beispielsweise eine Prüfsumme und einen Prüfwert namens digest. Das bedeutet weder, dass jede Anwendung von Shamir Secret Sharing dieselben Prüfungen bietet, noch, dass eine richtige Prüfsumme eine vertrauenswürdige Herkunft beweist. [2] [5]

Im idealen Verfahren liefern weniger als k vollständige Anteile keine neue Information über S, selbst bei unbegrenzter Rechenleistung. Ein Anteil ist also kein sichtbares Drittel der ursprünglichen Wörter. Das setzt richtigen Zufall voraus: Die Zahlen zur Aufteilung werden unabhängig und gleichverteilt gewählt. Vorhersehbare Zahlen, ihre Wiederverwendung oder ein Abfluss geheimer Daten aus dem Gerätespeicher ändern die Lage. Auch zusätzliche Prüfdaten wie der digest in SLIP-39 müssen gesondert betrachtet werden. Und ein schwaches ursprüngliches Passwort bleibt über andere Wege erratbar, selbst wenn seine Sicherung aufgeteilt wurde. [1] [2]

Nehmen wir das kleine Geheimnis S=5 und die Vorschrift f(x)=5+3*x mod 17. mod 17 bedeutet, den Rest nach Division durch 17 zu nehmen. Drei Anteile sind die Paare (1,8), (2,11), (3,14): Die erste Zahl bezeichnet eine Position, die zweite den berechneten Wert. Aus den ersten beiden ergeben sich der Zuwachs 3 und das ursprüngliche Geheimnis 8−3=5. Jede der drei möglichen Punktpaarungen ergibt dieselbe Fünf. Der einzelne Punkt (1,8) passt hingegen zu jedem S von 0 bis 16, wenn der Zuwachs a=8−S mod 17 gewählt wird. Diese kleinen Zahlen dienen nur der Anschauung, nicht als Sicherungskonzept für eine echte Wallet. [1]

Allgemein lautet die Vorschrift f(x)=S+a1*x+…+a(k−1)*x^(k−1). Dieser Ausdruck ist ein Polynom; S ist das Geheimnis, die übrigen Koeffizienten sind unabhängige, gleichverteilte Zufallselemente eines endlichen Körpers, eines Rechenbereichs mit genauen Regeln für Addition und Multiplikation. Ein Anteil besteht aus (x,f(x)); jedes x muss verschieden und ungleich null sein: x=0 würde S direkt verraten. Aus k Punkten berechnet die Lagrange-Interpolation f(0), also das Geheimnis. Zwei Kopien desselben Punktes liefern nichts Neues. Im Primkörper GF(p) ersetzt die Multiplikation mit einem modularen Inversen die gewöhnliche Division; sein Produkt mit dem Divisor ist 1. GF(256) verwendet außerdem andere Rechenregeln als bloße Reste modulo 256. Diese Operationen dürfen nicht verwechselt werden. [1]