Wie Shamir Secret Sharing funktioniert

 (ente.com)
3 Punkte von GN⁺ 9 시간 전 | 1 Kommentare | Auf WhatsApp teilen
  • Shamir Secret Sharing teilt ein Geheimnis in mehrere Fragmente auf, stellt es nur wieder her, wenn mindestens der Schwellenwert zusammenkommt, und gibt bei weniger Fragmenten keinerlei Informationen preis
  • Nützlich in Fällen wie dem Master-Schlüssel eines Unternehmens, der Wiederherstellung eines Familienkontos oder Team-Backups, wenn es schwierig ist, einer einzelnen Person das gesamte Geheimnis anzuvertrauen, und eine Wiederherstellung auch bei Verlust einzelner Fragmente nötig ist
  • Das Kernmodell verbirgt das Geheimnis als Wert an der Stelle 0 eines Polynoms und verteilt jedes Fragment als einen Punkt auf der Kurve
  • Für den Schwellenwert k wird ein Polynom vom Grad k - 1 verwendet: zwei Fragmente entsprechen einer Geraden, drei einer Parabel und vier einer kubischen Kurve
  • Ente Legacy Kit nutzt diesen Ansatz als eine Schicht, damit eine Karte nicht zu einem dauerhaften Wiederherstellungsschlüssel wird und ausgegebene Karten widerrufen werden können

Wie man ein Geheimnis in Punkte und Polynome aufteilt

  • Das Verfahren wurde 1979 von Adi Shamir veröffentlicht. Der Kernpunkt ist nicht einfach nur, dass es „schwer zu knacken“ ist, sondern dass bei zu wenigen nötigen Fragmenten überhaupt keine Informationen preisgegeben werden
  • Zwei verschiedene Punkte bestimmen genau eine Gerade. Hat man jedoch nur einen Punkt, gibt es unendlich viele Geraden, die durch ihn verlaufen, und jede trifft die vertikale Achse an einer anderen Stelle
  • Wenn das Geheimnis die Zahl 7 ist, kann dieser Wert an der Stelle verborgen werden, an der die Gerade die vertikale Achse schneidet
  • Die Steigung ist nicht das Geheimnis selbst, sondern dient als Zufälligkeit, um das Geheimnis zu verbergen
  • Gibt man jeder Person einen Punkt auf der Geraden, dann reichen die Daten einer einzelnen Person nicht aus: Zu diesem einen Punkt passen unendlich viele mögliche Geraden und damit auch unterschiedliche mögliche Geheimnisse
  • Kombiniert man zwei Punkte, ist die Gerade festgelegt, und man kann das Geheimnis wiederherstellen, indem man den Wert der Geraden bei 0 abliest
  • Diese Struktur ist ein 2-of-n-Verfahren zur Geheimnisteilung: Man kann beliebig viele Punkte erzeugen, aber jedes beliebige Paar von Punkten rekonstruiert die Gerade
  • Wenn der Schwellenwert steigt, verwendet man Kurven höheren Grades
    • Eine Parabel wird erst durch drei Punkte bestimmt. Verbirgt man das Geheimnis also an der Stelle, an der die Parabel die vertikale Achse schneidet, ist eine Wiederherstellung mit beliebigen drei Fragmenten möglich, mit zwei jedoch nicht
    • Allgemein verwendet man für einen Schwellenwert k ein Polynom vom Grad k - 1
    • 2 Fragmente entsprechen einer Geraden, 3 einer Parabel und 4 einer kubischen Kurve
    • Reale Implementierungen verwenden kein Millimeterpapier, sondern Arithmetik in endlichen Körpern, aber die Struktur bleibt gleich: Das Geheimnis ist der Wert bei 0, zufällige Koeffizienten verbergen es, und jedes Fragment ist ein Punkt auf dem Polynom
    • Wichtig ist: Fehlen Fragmente, ist das Geheimnis nicht nur schwer zu berechnen, sondern jedes mögliche Geheimnis bleibt weiterhin möglich

Ente Legacy Kit und weiterführende Materialien

  • Ente verwendet diese Idee im Legacy Kit
  • Das Ziel besteht nicht nur darin, ein Geheimnis aufzuteilen, sondern auch darin, die aufgeteilten Fragmente nicht zu einem dauerhaften Wiederherstellungsschlüssel werden zu lassen und trotzdem eine Wiederherstellung zu ermöglichen
  • Legacy Kit verwendet das Shamir-Verfahren als eine Schicht innerhalb eines größeren Ablaufs
  • Die Karten enthalten nicht den Wiederherstellungsschlüssel selbst, sondern rekonstruieren lokal ein separates Geheimnis und nehmen dann an einer serververmittelten Wiederherstellung teil
  • Durch diese Struktur können ausgegebene Karten widerrufen werden, und verlorene Karten bleiben nicht als dauerhafte Belastung bestehen
  • Weiterführende Materialien

Verwandte Beiträge

1 Kommentare

 
GN⁺ 9 시간 전
Hacker-News-Kommentare

  • Ich habe zu diesem Thema meine Masterarbeit geschrieben. Ich habe eine App gebaut, die Daten auf mehrere gewöhnliche Speicheranbieter wie Dropbox, Google Drive und OneDrive verteilt speichert und dabei Secret Sharing zur Unterstützung der Verschlüsselung verwendet.
    Die Vorteile waren, dass die Anbieter die Daten nicht mehr lesen konnten, dass durch die Anforderung, dass nur 2 Standorte verfügbar sein müssen, zusätzliche Redundanz entstand und dass man im Gegensatz zu anderen sicheren Speicher-Apps, bei denen alles verloren ist, wenn man das Master-Passwort vergisst, weiterhin die bestehenden Kontowiederherstellungsverfahren nutzen konnte.

    • Die Idee klingt gut; ich würde gern wissen, ob daraus später ein Produkt oder eine Open-Source-App geworden ist.

  • Ich frage mich, ob es eine Möglichkeit gibt, mehrere Schlüssel/Wert-Paare zu einem einzelnen Ciphertext zusammenzufassen, ohne sie einfach nur aneinanderzuhängen oder die Ergebnisgröße explodieren zu lassen, sodass alle, die Informationen in dieses Schema einspeisen, denselben verschlüsselten Block speichern, aber mit ihrem jeweiligen Schlüssel unterschiedliche Werte entschlüsseln. So könnten Leute gegenseitig als Backup fungieren und hätten zugleich plausible Abstreitbarkeit darüber, was gespeichert ist.

  • In meiner Masterarbeit habe ich Shamir Secret Sharing auf ein Mesh-Netzwerk angewendet. Die Idee war, dass selbst dann, wenn ein einzelner Knoten im Mesh von einem Angreifer kompromittiert und das Geheimnis dieses Knotens ausgelesen wird, die gesamte Verschlüsselung dadurch nicht gebrochen werden kann.

  • Unser Team nutzt diese Technik, um die Passphrase für einen sekundären Secret Store auf „demokratisch sichere“ Weise zu verteilen. Dieser sekundäre Store enthält die Informationen, wie man auf den primären Secret Store zugreift.
    https://packages.debian.org/trixie/ssss ist eine gute und ziemlich intuitive Implementierung.

  • Shamir hat mir einmal wirklich den Hintern gerettet. Ich musste dringend ein fast vergessenes Backup wiederherstellen und konnte das damals verwendete zufällige Passwort rekonstruieren.
    Zum Glück hatte ich die verteilten Anteile „für alle Fälle“ an Familienmitglieder verteilt.

  • Der Teil „Das Nützliche daran ist nicht, dass es bei zu wenigen Anteilen schwierig ist, das Geheimnis zu berechnen. Es ist vielmehr so, dass bei zu wenigen Anteilen überhaupt keine Information über das Geheimnis vorliegt. Wenn ein Anteil fehlt, bleibt jedes mögliche Geheimnis weiterhin möglich“ erinnert mich an das Faktorisieren von Zahlen mit quadratischen Sieben oder Varianten davon.
    Man findet ein System von Kongruenzen mod n und berechnet am Ende die Primfaktoren, aber bevor genügend davon zusammenkommen, ist es unmöglich. Jede einzelne Kongruenz enthält doch irgendeine Information, und ich habe mich immer gefragt, in welchem Raum wir dabei Freiheitsgrade reduzieren.
    Auch hier schränkt jeder Anteil den Raum der Polynome ein, aber nicht genug, um zu verraten, wo der Schlüssel die Achse schneidet.

  • Eine wirklich tolle Technik und interessant genug, dass man sie sogar in der Sekundarstufe unterrichten könnte, als Beispiel dafür, was Informatiker mit Polynomen alles anstellen können.

    • Ich bin Mathematiklehrer in der Sekundarstufe und unterrichte das tatsächlich so.
      In einer Unterrichtseinheit zum Wiederherstellen der Gleichung einer linearen Funktion stelle ich Shamir vor: Die Schüler wählen eine geheime PIN als Steigung, erzeugen zwei Punkte und geben sie an zwei andere Schüler weiter. Diese beiden müssen sich zusammentun, um die PIN wiederzufinden, und die Schüler sind immer sehr engagiert dabei.

  • Bruce Schneier hat das in seinem klassischen Buch Applied Cryptography erklärt, und auch HashiCorp Vault hatte eine Go-Implementierung. Praktisch habe ich mich immer gefragt, wie viele Bits die verteilten Anteile haben sollten.
    Die Antwort, die ich damals in einer Newsgroup gehört habe, war: „1 Bit mehr als die tatsächliche Schlüssellänge.“ Heute frage ich mich, welchen Einfluss die Bedrohung durch Quantencomputing auf 1) die Wahl der Anteilgröße und 2) die Vor- und Nachteile von Secret Sharing insgesamt haben wird.

    • Das grundlegende Shamir-Verfahren ist informationstheoretisch sicher und wird von Quantencomputern überhaupt nicht beeinflusst.
      Wenn man aus einem 1-Byte-Geheimnis Shamir-Anteile mit einem Schwellenwert „10 aus n“ erzeugt und davon 9 Anteile zu je 1 Byte weitergibt, kann kein Computer im Universum das Geheimnis herausfinden. In realen Implementierungen kommen für Integritätsprüfungen noch ein paar Byte für einen Message Authentication Code oder eine Prüfsumme dazu.
    • Normalerweise macht man Secret Sharing über einem endlichen Körper, weil Computer Fehler nicht besonders mögen. Ein Anteil ist ein Punkt (x, y); x kann klein sein und liegt üblicherweise bei etwa log n, wenn es n Teilnehmer gibt, und y ist ein beliebiger Punkt im Körper.
      Shamir Secret Sharing ist informationstheoretisch sicher, sodass bei einem k-aus-n-Geheimnis ohne k Punkte selbst Brute Force jedes Geheimnis als gleich plausibel erscheinen lässt. Daher kann man die Bitgröße des Körpers grundsätzlich frei wählen, sie muss natürlich nur größer sein als die Bitgröße des Geheimnisses. In einem endlichen Körper mit nur 5 Elementen kann man keine 100 Bit verstecken.
      Üblicherweise muss man verhindern, dass ein Angreifer das Geheimnis selbst per Brute Force errät, denn auch wenn das Verfahren informationstheoretisch sicher ist, gilt das für das Geheimnis selbst meistens nicht. Ein Wallet-Seed ist dafür ein gutes Beispiel; deshalb fügt man dem Geheimnis zusätzliche Zufälligkeit hinzu und wählt die Bitgröße des Körpers groß genug, um solche Angriffe zu verhindern.
      Je nach Angriffsmodell sind 80-Bit- oder 128-Bit-Körper ausreichend sicher, und die Anteilgröße liegt dann nur wenig über 80 bzw. 128 Bit. Was Quantencomputer betrifft: Da das Verfahren informationstheoretisch sicher ist, kann es hier keinen Angriff geben.
    • Soweit ich weiß, hat HashiCorp die Implementierung für den seal/unseal-Prozess von Vault noch immer, sofern sich da nichts geändert hat.
    • Das Shamir-Verfahren basiert auf dem Hauptsatz der Algebra. Vereinfacht gesagt braucht man n+1 Punkte, um ein Polynom n-ten Grades eindeutig festzulegen.
      Um also eine n-aus-k-Konfiguration zu erstellen, konstruiert man ein Polynom p(x) vom Grad n-1 und wählt daraus k beliebige Punkte. Der i-te Anteil ist dann einfach (xi, yi), und die Bitanzahl wird durch den Körper bestimmt, über dem das Polynom definiert ist.
      Der Körper muss groß genug sein, um das gesamte Geheimnis aufzunehmen, und da man sowohl x als auch y speichern muss, ist die Anteilgröße mindestens doppelt so groß wie das Geheimnis. Außerdem braucht man eine Integritätsprüfung, um festzustellen, ob ein Anteil beschädigt wurde.
      Soweit ich es verstehe, ändert Quantencomputing hier nichts. Sobald auch nur ein Punkt fehlt, kann dieser letzte Punkt das Geheimnis beliebig verändern, und es gibt keine Möglichkeit, das zu unterscheiden.
    • Das gesamte Geheimnis muss nicht zwingend ein einzelnes Element des zugrunde liegenden Körpers sein. Es kann auch ein n-Tupel kleinerer Körperelemente sein.
      Wenn man nicht mit absurd vielen Anteilen rechnet, ist GF(2^8) eine ziemlich natürliche Wahl, und man muss nicht mit großen Ganzzahloperationen hantieren.

  • Hier ist die Implementierung von Ente: (https://2of3.ente.com/)

    • Das gefällt mir von allem, was ich bisher gesehen habe, am besten, und es ist sehr benutzerfreundlich. Ich wünschte nur, es wäre etwas konfigurierbarer.
      Ideal wäre, wenn man Konfigurationen wie 3 of 4: A B C D, 2 of 3: E F G und 1 of 1: H anlegen könnte.
      Es wäre auch gut, Karten benennen zu können, damit bei der Wiederherstellung klar ist, was genau benötigt wird. Natürlich ist die Einfachheit des aktuellen Designs auch ein Vorteil.
    • Es gibt auch eine Implementierung, die in den meisten Linux-Distributionen paketiert ist: http://point-at-infinity.org/ssss
    • Es gibt mehrere browserbasierte Versionen, die man online verwenden oder herunterladen und offline nutzen kann.
      https://bs.parity.io/ -- http://passguardian.com/ -- https://iancoleman.io/shamir/

  • Vor ein paar Jahren habe ich ein kleines Tool gebaut, das Shamir Secret Sharing im Browser ausführt. Wenn man die Seite herunterlädt, kann man es auch vollständig offline verwenden.
    https://simon-frey.com/s4/

    • Ich habe diese Seite vor ein paar Jahren heruntergeladen, auf ein paar USB-Laufwerken gespeichert und dort zusammen mit einer KeePass-Datenbank und Passwort-Anteilen abgelegt.
      Ich habe sie an einige Familienmitglieder verteilt und ihnen gesagt, sie sollen sie meiner Frau geben, falls ich sterbe.