Das Problem der Geheimnisaufteilung

Sie haben einen Master-Schlüssel, der erhalten bleiben und in Notfällen zugänglich sein muss, aber niemals von einer einzelnen Person kompromittiert werden darf. Wie speichern Sie ihn? Wenn Sie mehreren Personen den vollständigen Schlüssel geben, kann jede von ihnen ihn missbrauchen. Eine einzelne Kopie zu behalten, schafft einen Single Point of Failure.

Das Aufteilen eines 128-Bit-Schlüssels in zwei 64-Bit-Hälften und die Übergabe je einer Hälfte an zwei Personen scheint clever, ist aber unsicher: Dadurch sinkt der Brute-Force-Aufwand von 2^128 auf 2^64. Ein Angreifer, der eine Person kompromittiert, erhält einen Vorsprung von 64 Bit.

Ein geeignetes Secret-Sharing-Verfahren muss folgende Eigenschaften haben: (1) Schwellenwert: Beliebige k von n Anteilen rekonstruieren das Geheimnis. (2) Sicherheit: Beliebige k-1 Anteile verraten keinerlei Information über das Geheimnis. (3) Perfekt: Es sind keine rechnerischen Annahmen erforderlich.

Bitcoin-Wallets, HSM-Masterschlüssel, private Schlüssel von Zertifizierungsstellen, Startcodes für Nuklearwaffen und Cold Wallets von Kryptowährungsbörsen benötigen alle Zugriff per Schwellenwert. Der Verlust des einzigen Schlüssels wäre katastrophal; eine Kompromittierung durch einen einzelnen Insider ebenfalls.

Um das Geheimnis S zwischen zwei Parteien aufzuteilen: Generieren Sie ein zufälliges R. Geben Sie share1=R an Partei 1 und share2=S XOR R an Partei 2. Zur Rekonstruktion gilt: share1 XOR share2 = R XOR (S XOR R) = S. Jeder Anteil für sich ist perfekt zufällig – er verrät nichts über S.

Die XOR-Aufteilung ist perfekt für 2 von 2, lässt sich aber nicht auf Schwellenwertschemata k von n verallgemeinern. Sie können kein 3-von-5-Schema erstellen, bei dem beliebige 3 Anteile das Geheimnis rekonstruieren, aber beliebige 2 keinerlei Informationen verraten. Polynominterpolation löst dieses Problem.

Perfekte Geheimhaltung bedeutet, dass die Anteile bei weniger als k Anteilen keinerlei gegenseitige Information über das Geheimnis enthalten. Dies ist stärker als rechnerische Sicherheit — selbst ein rechnerisch unbeschränkter Angreifer lernt aus k-1 Anteilen nichts.

AWS CloudHSM verwendet Quorum-Authentifizierung nach dem M-von-N-Prinzip. PGP-Schlüsselverwahrung teilt Masterschlüssel auf. Anbieter von Kryptowährungsverwahrung (Fireblocks, BitGo) verwenden MPC oder Shamir Secret Sharing für Hot-Wallet-Schlüssel. Offline-Schlüssel von Zertifizierungsstellen werden in 5-von-7-Zeremonien verwendet.

Eine Schlüsselzeremonie ist ein formaler, geprüfter Prozess zur Erzeugung und Aufteilung eines Masterschlüssels. Beispiel: 7 Schlüsselinhaber befinden sich in einem gesicherten Raum, und jeder erhält ein Hardware-Token mit einem Anteil. Die Zeremonie wird auf Video aufgezeichnet, zwei Prüfer sind anwesend und jeder Schritt wird dokumentiert.

Secret Sharing rekonstruiert das vollständige Geheimnis (Risiko: ein Single Point of Failure zum Zeitpunkt der Rekonstruktion). Multisig verteilt das Signieren: Jede Partei signiert unabhängig, und die Signaturen werden kombiniert. Threshold-Signaturen (TSS) wenden Secret Sharing direkt auf den Signiervorgang an.

Secure Multi-Party Computation (MPC) macht den Rekonstruktionsschritt vollständig überflüssig — die Parteien führen gemeinsam Berechnungen mit ihren Anteilen durch, ohne das Geheimnis offenzulegen. Threshold ECDSA und Threshold BLS werden in produktiven Verwahrungssystemen eingesetzt.

Wie viele Anteile benötigt ein Angreifer bei einem 2-von-2-XOR-Secret-Sharing-Verfahren, um das Geheimnis zu erfahren?

Naives Aufteilen von Schlüsseln ist unsicher. Geeignetes Secret Sharing erfordert Zugriff per Schwellenwert und perfekte Geheimhaltung. XOR eignet sich für 2 von 2; Polynominterpolation für k von n. Als Nächstes: die Mathematik von Shamir's Secret Sharing.