Schafgarbe Algorithmus - Yarrow algorithm
Der Yarrow-Algorithmus ist eine Familie von kryptografischen Pseudozufallszahlengeneratoren (CPRNG), die von John Kelsey , Bruce Schneier und Niels Ferguson entwickelt und 1999 veröffentlicht wurden. Der Yarrow-Algorithmus ist explizit nicht patentiert, gebührenfrei und Open Source; Es ist keine Lizenz erforderlich, um es zu verwenden. Ein verbessertes Design von Ferguson und Schneier, Fortuna , wird in ihrem Buch Praktische Kryptographie beschrieben
Yarrow wurde in FreeBSD verwendet , wird aber jetzt von Fortuna abgelöst. Yarrow wurde auch in iOS und macOS für ihre /dev/random- Geräte integriert, aber Apple ist seit 2020 Q1 auf Fortuna umgestiegen.
Name
Der Name Schafgarbe spielt auf die Verwendung der Schafgarbe im zufälligen Erzeugungsprozess der I Ging-Wahrsagung an . Seit der Xia-Dynastie (ca. 2070 bis ca. 1600 v. Chr.) verwenden Chinesen Schafgarbenstengel zur Weissagung. Wahrsager teilen einen Satz von 50 Schafgarbenhalmen in Häufchen auf und verwenden modulare Arithmetik rekursiv, um zwei zufällige Informationen zu generieren, die eine ungleichmäßige Verteilung haben .
Grundsätze
Die wichtigsten Designprinzipien von Yarrow sind: Widerstandsfähigkeit gegen Angriffe, einfache Verwendung durch Programmierer ohne Kryptographie-Hintergrund und Wiederverwendbarkeit vorhandener Bausteine. Die ehemals weit verbreiteten Designs wie ANSI X9.17 und RSAREF 2.0 PRNG weisen Schlupflöcher auf, die unter Umständen Angriffsmöglichkeiten bieten. Einige von ihnen sind nicht für reale Angriffe konzipiert. Yarrow zielt auch auf eine einfache Integration ab, um Systemdesignern mit geringen Kenntnissen der PRNG-Funktionalität zu ermöglichen.
Design
Komponenten
Das Design von Yarrow besteht aus vier Hauptkomponenten: einem Entropiespeicher , einem Re-Seed- Mechanismus, einem Generationsmechanismus und einer Re-Seed-Steuerung.
Schafgarbe akkumuliert Entropie in zwei Pools: dem schnellen Pool, der häufige Neuausbringungen des Schlüssels ermöglicht , um die Dauer von Schlüsselkompromittierungen so kurz wie möglich zu halten; der langsame Pool, der seltene, aber konservative Nachsaat des Schlüssels liefert. Dies stellt sicher, dass der Reseed auch bei sehr optimistischen Entropieschätzungen gesichert ist.
Der Re-Seed-Mechanismus verbindet den Entropie-Akkumulator mit dem Erzeugungsmechanismus. Das erneute Seeding aus dem Fast-Pool verwendet den aktuellen Schlüssel und den Hash aller Eingaben in den Fast-Pool seit dem Start, um einen neuen Schlüssel zu generieren; Das erneute Seeding aus dem Slow-Pool verhält sich ähnlich, verwendet jedoch auch den Hash aller Eingaben in den Slow-Pool, um einen neuen Schlüssel zu generieren. Beide Reseedings setzen die Entropieschätzung des schnellen Pools auf null zurück, aber die letzte setzt auch die Schätzung des langsamen Pools auf null. Der Reseeding-Mechanismus aktualisiert den Schlüssel ständig, so dass, selbst wenn der Schlüssel der Pool-Informationen dem Angreifer vor dem Reseeding bekannt ist, sie dem Angreifer nach dem Reseeding unbekannt sind.
Die Reseeding-Steuerungskomponente nutzt zwischen häufigem Reseeding, das wünschenswert ist, aber iterative Rateing- Angriffe ermöglichen könnte , und seltenem Reseeding, das mehr Informationen für einen Angreifer mit dem Schlüssel gefährdet. Yarrow verwendet den schnellen Pool zum erneuten Seeding, wenn die Quelle einige Schwellenwerte überschreitet, und verwendet den langsamen Pool zum erneuten Seeding, wenn mindestens zwei seiner Quellen einen anderen Schwellenwert überschreiten. Die spezifischen Schwellenwerte sind im Abschnitt Schafgarbe-160 erwähnt .
Design-Philosophie
Yarrow geht davon aus, dass genügend Entropie akkumuliert werden kann, um sicherzustellen, dass sich das PRNG in einem unvorhersehbaren Zustand befindet. Die Designer akkumulieren Entropie mit dem Ziel, die Fähigkeit zur Wiederherstellung des PRNG auch dann aufrechtzuerhalten, wenn der Schlüssel kompromittiert ist. Eine ähnliche Designphilosophie wird von RSAREF, DSA und ANSI X9.17 PRNGs verfolgt.
Schafgarbe-160
Die Schafgarbe verwendet zwei wichtige Algorithmen: eine Einweg-Hash-Funktion und eine Blockchiffre . Die spezifische Beschreibung und Eigenschaften sind in der folgenden Tabelle aufgeführt.
| Algorithmen | Eigenschaften | Was Schafgarbe-160 verwendet |
|---|---|---|
| Hash-Funktion h(x) |
Bei gegebenen M Eingabewerten ist |M| Auswahlen von Ausgabewerten werden gleichmäßig über m- Bit-Werte verteilt. |
SHA-1- Hash-Funktion |
| Blockchiffre E() |
Hohe statistische Leistung der Ausgaben bei stark gemusterten Eingaben. |
Drei-Tasten- Triple DES |
Generation
Yarrow-160 verwendet Drei-Tasten- Triple DES im Zählermodus, um Ausgaben zu generieren. C ein n- Bit-Zählerwert ist; K ist der Schlüssel. Um den nächsten Ausgabeblock zu generieren, folgt Yarrow den hier gezeigten Funktionen.
Yarrow zählt den Ausgabeblock mit, denn sobald der Schlüssel kompromittiert ist, kann das Durchsickern der alten Ausgabe vor der kompromittierten sofort gestoppt werden. Sobald ein gewisser Systemsicherheitsparameter P g erreicht ist, erzeugt der Algorithmus k Bits der PRNG-Ausgabe und verwendet sie als den neuen Schlüssel. In Yarrow-160 wird der Systemsicherheitsparameter auf 10 gesetzt , was P g = 10 bedeutet . Der Parameter ist absichtlich niedrig eingestellt, um die Anzahl der Ausgänge, die zurückverfolgt werden können, zu minimieren.
Neu aussäen
Der Re-Seed-Mechanismus von Yarrow-160 verwendet SHA-1 und Triple DES als Hash-Funktion und Blockchiffre. Die Detailschritte sind im Originalpapier.
Implementierung von Schafgarbe-160
Yarrow-160 wurde in Java und für FreeBSD implementiert . Die Beispiele finden Sie in "An Implementation of the Yarrow PRNG for FreeBSD" von Mark RV Murray.
Vor- und Nachteile von Schafgarbe
Vorteile
- Schafgarbe verwendet bestehende Bausteine wieder.
- Im Vergleich zu früheren PRNGs ist Yarrow einigermaßen effizient.
- Yarrow kann von Programmierern ohne kryptografischen Hintergrund auf relativ sichere Weise verwendet werden. Schafgarbe ist tragbar und genau definiert. Die Schnittstelle ist einfach und klar. Diese Funktionen verringern die Wahrscheinlichkeit von Implementierungsfehlern etwas.
- Yarrow wurde mit einem angriffsorientierten Designprozess erstellt.
- Die Entropie-Schätzung von Yarrow ist sehr konservativ, wodurch erschöpfende Suchangriffe verhindert werden . Es kommt sehr häufig vor, dass PRNGs in realen Anwendungen aufgrund von Entropieüberschätzung und schätzbaren Ausgangspunkten versagen.
- Der Reseeding-Prozess von Yarrow ist relativ rechenaufwendig, daher sind die Kosten für den Versuch, den Schlüssel des PRNG zu erraten, höher.
- Yarrow verwendet Funktionen, um die Verwaltung von Seed-Dateien zu vereinfachen, sodass die Dateien ständig aktualisiert werden.
- Um kryptanalytische Angriffe abzuwehren, basiert Yarrow auf einer gesicherten Blockchiffre. Das Sicherheitsniveau des Generierungsmechanismus hängt von der Blockchiffre ab.
- Yarrow versucht, datenabhängige Ausführungspfade zu vermeiden. Dies geschieht, um Seitenkanalangriffe wie Timing-Angriffe und Leistungsanalysen zu verhindern . Dies ist eine Verbesserung gegenüber früheren PRNGs, zum Beispiel RSAREF 2.0 PRNG, die komplett auseinander fallen, sobald zusätzliche Informationen über die internen Vorgänge nicht mehr gesichert sind.
- Yarrow verwendet kryptografische Hashfunktionen, um Eingabemuster zu verarbeiten, und verwendet dann eine sichere Aktualisierungsfunktion, um die Muster mit dem vorhandenen Schlüssel zu kombinieren. Dadurch wird sichergestellt, dass der Angreifer die Eingabe-Samples nicht einfach manipulieren kann. PRNGs wie RSAREF 2.0 PRNG können dieser Art von Angriffen mit gewählter Eingabe nicht widerstehen.
- Im Gegensatz zu ANSI X9.17 PRNG hat Yarrow die Fähigkeit, sich nach einer Schlüsselkompromittierung zu erholen. Dies bedeutet, dass der Angreifer selbst bei einer Kompromittierung des Schlüssels zukünftige Ausgaben nicht für immer vorhersagen kann. Dies ist auf den Nachsaatmechanismus von Schafgarbe zurückzuführen.
- Yarrow hat den Entropie-Sample-Pool vom Schlüssel getrennt und setzt den Schlüssel nur dann erneut ein, wenn der Entropie-Pool-Inhalt völlig unvorhersehbar ist. Dieses Design verhindert iterative Rateing-Angriffe, bei denen ein Angreifer mit dem Schlüssel die nächste Stichprobe errät und das Ergebnis durch Beobachten der nächsten Ausgabe überprüft.
Nachteile
- Da die Ausgaben von Yarrow kryptographisch abgeleitet werden, können die Systeme, die diese Ausgaben verwenden, nur so sicher sein wie der Erzeugungsmechanismus selbst. Das bedeutet, dass der Angreifer, der den Generierungsmechanismus durchbrechen kann, leicht ein System zerstören kann, das von Yarrows Outputs abhängt. Dieses Problem kann nicht durch eine Erhöhung der Entropieakkumulation gelöst werden.
- Schafgarbe erfordert eine Entropieschätzung, was eine sehr große Herausforderung für Implementierungen darstellt. Es ist schwer zu sagen, wie viel Entropie gesammelt werden muss, bevor das PRNG erneut ausgesät wird. Dieses Problem wird von Fortuna (PRNG) gelöst , einer Verbesserung von Yarrow. Fortuna hat 32 Pools zum Sammeln von Entropie und hat den Entropieschätzer vollständig entfernt.
- Die Stärke der Schafgarbe wird durch die Größe des Schlüssels begrenzt. Yarrow-160 hat beispielsweise eine effektive Schlüsselgröße von 160 Bit. Wenn die Sicherheit 256 Bit erfordert, ist Yarrow-160 nicht in der Lage, die Aufgabe zu erfüllen.
- Yarrow-160 verwendet SHA-1, das aufgrund seiner ersten öffentlichen Kollision weithin als veraltet gilt.
