Betrachten wir das Szenario, in dem die Sicherheit des Bankschließfachs gewährleistet werden muss. Es gilt als völlig unzugänglich ohne den Schlüssel, den Sie am ersten Arbeitstag erhalten. Ihr Ziel ist es, den Schlüssel sicher aufzubewahren.

Angenommen, Sie haben beschlossen, den Schlüssel immer bei sich zu tragen und den Zugang zum Schließfach nach Bedarf zu gewähren. Aber Sie werden schnell feststellen, dass diese Lösung in der Praxis nicht gut skalierbar ist, da Sie jedes Mal physisch anwesend sein müssen, um das Schließfach zu öffnen. Und was ist mit dem Urlaub, der Ihnen versprochen wurde? Außerdem stellt sich die noch beunruhigendere Frage: Was passiert, wenn Sie den einzigen Schlüssel verlieren?

Mit dem Gedanken an den Urlaub haben Sie beschlossen, eine Kopie des Schlüssels zu machen und diese einem anderen Mitarbeiter anzuvertrauen. Doch Sie verstehen, dass dies auch nicht ideal ist. Indem Sie die Anzahl der Schlüssel verdoppeln, haben Sie auch die Möglichkeiten für Diebstahl des Schlüssels verdoppelt.

Verzweifelt zerstören Sie das Duplikat und beschließen, den ursprünglichen Schlüssel in zwei Hälften zu teilen. Jetzt denken Sie, dass zwei vertrauenswürdige Personen mit den Teilen des Schlüssels physisch anwesend sein müssen, um den Schlüssel zusammenzusetzen und das Schließfach zu öffnen. Das bedeutet, dass der Dieb zwei Teile stehlen müsste, was doppelt so schwierig ist wie der Diebstahl eines einzelnen Schlüssels. Allerdings stellen Sie bald fest, dass dieses System nicht viel besser ist als nur ein Schlüssel, denn wenn jemand die Hälfte des Schlüssels verliert, kann der gesamte Schlüssel nicht wiederhergestellt werden.

Das Problem kann durch eine Reihe zusätzlicher Schlüssel und Schlösser gelöst werden, aber dieser Ansatz erfordert schnell viele Schlüssel und Schlösser. Sie beschließen, dass in einem idealen Schema der Schlüssel geteilt werden sollte, damit die Sicherheit nicht vollständig von einer einzelnen Person abhängt. Sie kommen auch zu dem Schluss, dass es eine bestimmte Schwelle an Fragmenten geben sollte, damit bei Verlust eines Fragments (oder wenn die Person im Urlaub ist) der gesamte Schlüssel funktionsfähig bleibt.

Wie man ein Geheimnis teilt

Über diesen Typ von Schlüsselverwaltungssystem dachte Adi Shamir im Jahr 1979, als er seine Arbeit veröffentlichte „Wie man ein Geheimnis teilt“. In dem Artikel wird die sogenannte Schwellenschema für die effektive Aufteilung eines geheimen Wertes (z. B. eines kryptografischen Schlüssels) in Teile erklärt. Danach kann das Geheimnis leicht wiederhergestellt werden, wenn und nur wenn mindestens aus Teile zusammengebracht werden. .

Aus sicherheitstechnischer Sicht ist eine wichtige Eigenschaft dieses Schemas, dass ein Angreifer absolut nichts erfahren sollte, wenn er nicht mindestens Teile hat. Selbst das Vorhandensein von Teilen sollte keine Informationen liefern. Wir nennen dieses Merkmal semantische Sicherheit.

Polynominterpolation

Das Shamir-Schema basiert auf dem Konzept der Polynominterpolation. Wenn Sie mit diesem Konzept nicht vertraut sind, ist es tatsächlich ziemlich einfach. Im Grunde genommen, wenn Sie jemals Punkte auf einem Diagramm gezeichnet haben und dann diese mit Linien oder Kurven verbunden haben, haben Sie es bereits verwendet!

Durch zwei Punkte kann eine unbegrenzte Anzahl von Polynomen zweiten Grades geführt werden. Um eines von ihnen auszuwählen, benötigt man einen dritten Punkt. Illustration: Wikipedia

Betrachten wir ein Polynom ersten Grades, . Wenn Sie diese Funktion auf einem Diagramm darstellen möchten, wie viele Punkte benötigen Sie? Nun, wir wissen, dass es sich um eine lineare Funktion handelt, die eine Linie bildet, und daher sind mindestens zwei Punkte erforderlich. Lassen Sie uns nun eine polynomiale Funktion zweiten Grades betrachten, . Das ist eine quadratische Funktion, daher benötigt man für die Erstellung des Diagramms mindestens drei Punkte. Wie sieht es mit einem Polynom dritten Grades aus? Mindestens vier Punkte. Und so weiter.

Das wirklich Tolle an dieser Eigenschaft ist, dass wir, wenn wir den Grad der polynomialen Funktion und mindestens Punkte berücksichtigen, zusätzliche Punkte für diese polynomiale Funktion ableiten können. Die Extrapolation dieser zusätzlichen Punkte nennen wir Polynominterpolation.

Geheimnisbildung

Möglicherweise haben Sie bereits erkannt, dass hier das clevere Shamir-Schema ins Spiel kommt. Nehmen wir an, unser Geheimnis ist sind . Wir können in einen Punkt auf einem Diagramm umwandeln und eine polynomiale Funktion vom Grad erfinden, die diesem Punkt entspricht. Denken Sie daran, dass unser Schwellenwert für erforderliche Teile sein wird, sodass wir, wenn wir den Schwellenwert auf drei Teile setzen, eine polynomiale Funktion zweiten Grades wählen müssen.

Unser Polynom wird die Form haben von

und – zufällig ausgewählte positive ganze Zahlen. Wir erstellen lediglich ein Polynom vom Grad , wobei der freie Koeffizient  unser Geheimnis ist , und jeder der folgenden Es gibt einen zufällig ausgewählten positiven Koeffizienten. Wenn wir zu unserem ursprünglichen Beispiel zurückkehren und annehmen, dass , dann erhalten wir die Funktion .

An diesem Punkt können wir Fragmente generieren, indem wir einzigartige ganze Zahlen in

(weil das unser Geheimnis ist). In diesem Beispiel möchten wir vier Fragmente mit einer Schwelle von drei verteilen, also generieren wir zufällig Punkte und senden jeweils einen Punkt an jede der vier vertrauenswürdigen Personen, den Schlüsselspeichern. Wir teilen den Leuten auch mit, dass , da dies als öffentliche Information angesehen wird und zur Wiederherstellung erforderlich ist. .

Wiederherstellung des Geheimnisses

Wir haben bereits das Konzept der polynomialen Interpolation und deren Grundlage für das Shamir-Schema besprochen. Wenn drei beliebige der vier vertrauenswürdigen Personen wiederherstellen möchten , müssen sie nur interpolieren mit ihren einzigartigen Punkten. Sie können dazu ihre Punkte festlegen und das Interpolationspolynom von Lagrange anhand der folgenden Formel berechnen. Wenn Programmierung für Sie verständlicher ist als Mathematik, ist Pi im Grunde genommen der Operator for, der alle Ergebnisse multipliziert, und Sigma ist das for, das alles addiert.

Bei Wir können das wie folgt lösen und unsere ursprüngliche polynomial Funktion zurückgeben:

Da wir wissen, dass , erfolgt die Wiederherstellung einfach:

Verwendung von unsicherer ganzzahliger Arithmetik

Obwohl wir die Hauptidee von Shamir erfolgreich angewendet haben , haben wir ein Problem, das wir bis zu diesem Zeitpunkt ignoriert haben. Unsere polynomiale Funktion verwendet unsichere ganzzahlige Arithmetik. Denken Sie daran, dass für jeden zusätzlichen Punkt, den der Angreifer auf dem Graphen unserer Funktion erhält, weniger Möglichkeiten für andere Punkte bleiben. Sie können dies selbst sehen, wenn Sie einen Graphen mit zunehmender Anzahl an Punkten für die polynomial Funktion mit ganzzahliger Arithmetik erstellen. Es ist kontraproduktiv für unser angegebenes Sicherheitsziel, weil ein Angreifer absolut nichts wissen sollte, bis er mindestens Fragmente hat.

Um zu demonstrieren, wie schwach das Schema mit ganzzahliger Arithmetik ist, betrachten wir ein Szenario, in dem der Angreifer zwei Punkte erhalten hat und die öffentliche Information kennt, dass . Aus dieser Information kann er ableiten , die gleich zwei beträgt, und bekannte Werte in die Formel einfügen und .

Dann kann der Angreifer herausfinden , indem er berechnet :

Da wir definiert haben als zufällig ausgewählte positive ganze Zahlen, gibt es eine begrenzte Anzahl möglicher . Mit diesen Informationen kann der Angreifer ableiten , da alles, was größer als 5 ist, dazu führt, dass negativ wird. Das stellt sich als wahr heraus, da wir definiert haben

Dann kann der Angreifer mögliche Werte berechnen , indem er ersetzt in :

Mit einer begrenzten Auswahl an Optionen für wird klar, wie einfach es ist, Werte zu erraten und zu überprüfen . Hier gibt es insgesamt fünf Optionen.

Das Problem mit unsicherer ganzzahliger Arithmetik lösen

Um diese Schwachstelle zu beseitigen, schlägt Shamir vor, modulare Arithmetik zu verwenden, indem er auf

und – die Menge aller Primzahlen.

Erinnern wir uns schnell, wie die modulare Arithmetik funktioniert. Uhren mit Zeigern sind ein bereits bekanntes Konzept. Sie verwenden Uhren, die . Sobald der Stundenzeiger vorbei an zwölf ist, kehrt er zurück zu eins. Eine interessante Eigenschaft dieses Systems ist, dass wir einfach durch Blick auf die Uhr nicht ableiten können, wie viele Umdrehungen der Stundenzeiger gemacht hat. Wenn wir jedoch wissen, dass der Stundenzeiger viermal an 12 vorbeigekommen ist, können wir die Anzahl der vergangenen Stunden mit einer einfachen Formel vollständig bestimmen

 – das ist unser Teiler (hier ),  – der Quotient (wie oft der Teiler ohne Rest in die ursprüngliche Zahl passt, hier ), und  – der Rest, der normalerweise vom Modulo-Operator zurückgegeben wird (hier ). Das Wissen um all diese Werte ermöglicht es uns, die Gleichung für zu lösen, aber wenn wir den Quotienten weglassen, können wir den Ausgangswert niemals wiederherstellen.

Es kann gezeigt werden, wie dies die Sicherheit unseres Schemas verbessert, indem wir das Schema auf unser vorheriges Beispiel anwenden und . Unsere neue polynomialfunktion , und die neuen Punkte . Jetzt können die Schlüsselhalter die polynomialen Interpolation erneut verwenden, um unsere Funktion wiederherzustellen, nur dass die Operationen Addition und Multiplikation jetzt mit Reduktion modulo durchgeführt werden müssen (z.B. ).

Angenommen, in diesem neuen Beispiel hat der Angreifer zwei dieser neuen Punkte herausgefunden, , und öffentliche Informationen . Diesmal leitet der Angreifer basierend auf allen ihm vorliegenden Informationen die folgenden Funktionen ab, in denen  eine Menge aller positiven ganzen Zahlen und den Modulkoeffizienten darstellt. .

Jetzt findet unser Angreifer wieder , indem er berechnet, :

Dann versucht er erneut, abzuleiten, , indem er ersetzt in :

Diesmal hat er ein ernsthaftes Problem. In der Formel fehlen Werte , und . Da es unendlich viele Kombinationen dieser Variablen gibt, kann er keine zusätzlichen Informationen erhalten.

Sicherheitsüberlegungen

Das Shamir-Schema zur Geheimnisaufteilung bietet Sicherheit aus informationstheoretischer Sicht. Das bedeutet, dass die Mathematik auch gegen einen Angreifer mit unbegrenzter Rechenleistung robust ist. Das Schema hat jedoch mehrere bekannte Probleme.

Zum Beispiel erzeugt das Shamir-Schema keine prüfbaren Fragmente,das heißt, Menschen können problemlos gefälschte Fragmente vorlegen und die Wiederherstellung des richtigen Geheimnisses stören. Ein feindlicher Fragmentverwalter mit ausreichenden Informationen kann sogar ein anderes Fragment erzeugen und nach Belieben verändern. Dieses Problem wird durch prüfbare Geheimnisaufteilungsschemata, wie das Feldman-Schema, gelöst.

Ein weiteres Problem ist, dass die Länge jedes Fragments der Länge des entsprechenden Geheimnisses entspricht, sodass die Länge des Geheimnisses leicht ermittelt werden kann. Dieses Problem wird durch triviales Padding des Geheimnisses mit beliebigen Zahlen auf eine feste Länge gelöst.

Schließlich ist es wichtig zu beachten, dass unsere Bedenken hinsichtlich der Sicherheit über das Schema selbst hinausgehen können. In realen kryptografischen Anwendungen besteht oft die Bedrohung von Seitenkanalangriffen, bei denen ein Angreifer versucht, nützliche Informationen aus der Laufzeitleistung der Anwendung, dem Caching, Abstürzen usw. zu extrahieren. Wenn dies Bedenken aufwirft, sollten während der Entwicklung Schutzmaßnahmen wie Funktionen und Suchen mit konstanter Laufzeit in Betracht gezogen werden, um das Speichern von Daten auf der Festplatte zu verhindern und eine Reihe anderer Faktoren zu bedenken, die über diesen Artikel hinausgehen.

Demo

Auf dieser Seite Es gibt eine interaktive Demo des Shamir-G geheimnisaufteilungsschemas. Die Demo basiert auf der Bibliothek ssss-js, die selbst ein JavaScript-Port des beliebten Programms ist ssssBitte beachten Sie, dass die Berechnung großer Werte , und eine gewisse Zeit in Anspruch nehmen kann.

Quelle: habr.com