Unterschied zwischen java.util.Random und java.security.SecureRandom

202

Mein Team hat einen serverseitigen Code (in Java) erhalten, der zufällige Token generiert, und ich habe eine Frage dazu -

Der Zweck dieser Token ist ziemlich sensibel - sie werden für Sitzungs-IDs, Links zum Zurücksetzen von Passwörtern usw. verwendet. Sie müssen also kryptografisch zufällig sein, um zu vermeiden, dass jemand sie errät oder brutal erzwingt. Das Token ist "lang", also 64 Bit lang.

Der Code verwendet derzeit die java.util.RandomKlasse, um diese Token zu generieren. In der Dokumentation zu heißt es java.util.Randomeindeutig:

Instanzen von java.util.Random sind nicht kryptografisch sicher. Verwenden Sie stattdessen SecureRandom, um einen kryptografisch sicheren Pseudozufallszahlengenerator für sicherheitsrelevante Anwendungen zu erhalten.

Der Code verwendet derzeit jedoch Folgendes java.util.Random: Er instanziiert die java.security.SecureRandomKlasse und verwendet dann die SecureRandom.nextLong()Methode, um den Startwert zu erhalten, der zum Instanziieren der java.util.RandomKlasse verwendet wird. Anschließend java.util.Random.nextLong()wird das Token mithilfe der Methode generiert.

Also meine Frage jetzt - Ist es immer noch unsicher, wenn man bedenkt, dass das java.util.Randommit ausgesät wird java.security.SecureRandom? Muss ich den Code so ändern, dass er java.security.SecureRandomausschließlich zum Generieren der Token verwendet wird?

Derzeit ist der Code-Seed der Randomeinmalige Start

user967973
quelle
14
Einmal ausgesät, ist die Ausgabe von java.util.Random eine deterministische Folge von Zahlen. Das willst du vielleicht nicht.
Peter Štibraný
1
Setzt der Code Randombeim Start einmal oder setzt er für jedes Token einen neuen? Hoffentlich ist das eine dumme Frage, aber ich dachte, ich würde es überprüfen.
Tom Anderson
8
Random hat nur einen 48-Bit internen Zustand und wird nach 2 ^ 48 Anrufe nextLong repeat () , was bedeutet , dass es nicht möglich produzieren longoder doubleWerte.
Peter Lawrey
3
Es gibt ein weiteres schwerwiegendes Problem. 64 Bit bedeuten 1,84 * 10 ^ 19 mögliche Kombinationen, was zu wenig ist, um einem ausgeklügelten Angriff standzuhalten. Es gibt Maschinen, die einen 56-Bit-DES-Code (Faktor 256 weniger) mit 90 * 10 ^ 9 Schlüsseln pro Sekunde in 60 Stunden geknackt haben. Verwenden Sie 128 Bit oder zwei Longs!
Thorsten S.

Antworten:

232

Die Standardimplementierung von Oracle JDK 7 verwendet einen sogenannten linearen Kongruenzgenerator, um zufällige Werte in zu erzeugen java.util.Random.

Entnommen aus dem java.util.RandomQuellcode (JDK 7u2), aus einem Kommentar zur Methode protected int next(int bits), die die Zufallswerte generiert:

Dies ist ein linearer kongruenter Pseudozufallszahlengenerator, wie er von DH Lehmer definiert und von Donald E. Knuth in Die Kunst der Computerprogrammierung, Band 3: Seminumerische Algorithmen , Abschnitt 3.2.1 beschrieben wurde.

Vorhersagbarkeit linearer Kongruenzgeneratoren

Hugo Krawczyk hat ein ziemlich gutes Papier darüber geschrieben, wie diese LCGs vorhergesagt werden können ("Wie man kongruente Generatoren vorhersagt"). Wenn Sie Glück haben und interessiert sind, finden Sie möglicherweise immer noch eine kostenlose, herunterladbare Version davon im Internet. Und es gibt noch viele weitere Untersuchungen, die eindeutig zeigen, dass Sie ein LCG niemals für sicherheitskritische Zwecke verwenden sollten. Dies bedeutet auch, dass Ihre Zufallszahlen derzeit vorhersehbar sind , was Sie für Sitzungs-IDs und dergleichen nicht möchten.

So brechen Sie einen linearen Kongruenzgenerator

Die Annahme, dass ein Angreifer nach einem vollständigen Zyklus auf die Wiederholung der LCG warten müsste, ist falsch. Selbst mit einem optimalen Zyklus (dem Modul m in seiner Wiederholungsrelation) ist es sehr einfach, zukünftige Werte in viel kürzerer Zeit als ein vollständiger Zyklus vorherzusagen. Schließlich müssen nur einige modulare Gleichungen gelöst werden, was einfach wird, sobald Sie genügend Ausgabewerte des LCG beobachtet haben.

Die Sicherheit verbessert sich nicht mit einem "besseren" Samen. Es spielt einfach keine Rolle, ob Sie mit einem zufälligen Wert säen SecureRandom, der von einem Würfel erzeugt wird, oder diesen sogar durch mehrmaliges Würfeln erzeugen.

Ein Angreifer berechnet einfach den Startwert aus den beobachteten Ausgabewerten. Dies dauert im Fall von deutlich weniger Zeit als 2 ^ 48 java.util.Random. Ungläubige können dieses Experiment ausprobieren , bei dem gezeigt wird, dass Sie zukünftige RandomAusgaben vorhersagen können , indem Sie nur zwei (!) Ausgabewerte in der Zeit von ungefähr 2 ^ 16 beobachten. Auf einem modernen Computer dauert es nicht einmal eine Sekunde, um die Ausgabe Ihrer Zufallszahlen vorherzusagen.

Fazit

Ersetzen Sie Ihren aktuellen Code. Verwenden Sie SecureRandomausschließlich. Dann haben Sie zumindest eine kleine Garantie dafür, dass das Ergebnis schwer vorherzusagen ist. Wenn Sie die Eigenschaften eines kryptografisch sicheren PRNG wünschen (in Ihrem Fall ist es das, was Sie wollen), müssen Sie nur mit gehen SecureRandom. Wenn Sie klug sind, die Art und Weise zu ändern, wie es verwendet werden sollte, führt dies fast immer zu etwas weniger Sicherem ...

prägen
quelle
4
Sehr hilfreich, vielleicht können Sie auch erklären, wie SecureRandom funktioniert (genau wie Sie erklären, wie Random funktioniert).
Gresdiplitude
4
Das macht den Zweck von SecureRandom
Azulflame am
Ich weiß, habe diese Lektion auf die harte Tour gelernt. Aber eine harte Chiffre und eine schwer zu findende Quelle funktionieren gut. Notch konnte etwas darüber lernen (er verschlüsselt das Passwort seines Benutzers in einer .lastlogin-Datei, die mit grundlegender Verschlüsselung unter Verwendung von "passwordfile" als Schlüssel
verschlüsselt ist
1
Die eigentliche Frage hier: Wenn Java mit einer ähnlichen API ein sichereres Programm erstellen kann, warum haben sie dann nicht einfach das defekte ersetzt?
Joel Coehoorn
11
@JoelCoehoorn Es ist nicht so, dass Randomes kaputt ist - es sollte nur in verschiedenen Szenarien verwendet werden. Natürlich können Sie jederzeit SecureRandom verwenden. Aber im Allgemeinen SecureRandomist merklich langsamer als rein Random. Und es gibt Fälle, in denen Sie nur an guten statistischen Eigenschaften und einer hervorragenden Leistung interessiert sind, sich aber nicht wirklich um die Sicherheit kümmern: Monte-Carlo-Simulationen sind ein gutes Beispiel. Ich habe dies in einer ähnlichen Antwort kommentiert , vielleicht finden Sie es nützlich.
Präge
72

Ein Zufall hat nur 48 Bit, während SecureRandom bis zu 128 Bit haben kann. Die Wahrscheinlichkeit, sich im Securerandom zu wiederholen, ist daher sehr gering.

Random verwendet das system clockals Startwert / oder, um den Startwert zu generieren. Sie können also leicht reproduziert werden, wenn der Angreifer den Zeitpunkt kennt, zu dem der Samen erzeugt wurde. Aber SecureRandom nimmt Random Datavon Ihrem os(sie können Intervalle zwischen Tastenanschlägen usw. sein - die meisten Betriebssysteme sammeln diese Daten, speichern sie in Dateien - /dev/random and /dev/urandom in case of linux/solaris) und verwendet dies als Startwert.
Wenn die kleine Tokengröße in Ordnung ist (im Fall von Random), können Sie Ihren Code ohne Änderungen weiter verwenden, da Sie SecureRandom zum Generieren des Seeds verwenden. Wenn Sie jedoch größere Token möchten (die nicht unterliegen können brute force attacks), wählen Sie SecureRandom -
Wenn nur zufällige 2^48Versuche erforderlich sind, ist es mit den heutigen fortgeschrittenen CPUs möglich, diese in der praktischen Zeit zu brechen. Für die Sicherung 2^128sind jedoch zufällige Versuche erforderlich, die Jahre und Jahre dauern werden, um mit den heutigen fortschrittlichen Maschinen die Gewinnschwelle zu erreichen.

Siehe diesen Link für weitere Details.
BEARBEITEN
Nach dem Lesen der von @emboss bereitgestellten Links ist klar, dass der Startwert, wie zufällig er auch sein mag, nicht mit java.util.Random verwendet werden sollte. Es ist sehr einfach, den Startwert durch Beobachtung der Ausgabe zu berechnen.

Entscheiden Sie sich für SecureRandom - Verwenden Sie natives PRNG (wie im obigen Link angegeben), da /dev/randomfür jeden Aufruf von zufällige Werte aus der Datei verwendet werdennextBytes(). Auf diese Weise kann ein Angreifer, der die Ausgabe beobachtet, nur dann etwas erkennen, wenn er den Inhalt der /dev/randomDatei kontrolliert (was sehr unwahrscheinlich ist).
Der sha1 prng- Algorithmus berechnet den Startwert nur einmal und wenn Ihre VM monatelang mit derselben ausgeführt wird Samen, es könnte von einem Angreifer geknackt werden, der die Ausgabe passiv beobachtet.

HINWEIS - Wenn Sie nextBytes()schneller anrufen , als Ihr Betriebssystem zufällige Bytes (Entropie) in das schreiben kann /dev/random, kann es bei Verwendung von NATIVE PRNG zu Problemen kommen . Verwenden Sie in diesem Fall eine SHA1 PRNG-Instanz von SecureRandom und setzen Sie diese Instanz alle paar Minuten (oder in einem bestimmten Intervall) mit dem Wert vonnextBytes()einer NATIVE PRNG-Instanz von SecureRandom. Wenn Sie diese beiden Optionen parallel ausführen, wird sichergestellt, dass Sie regelmäßig mit echten Zufallswerten säen, ohne die vom Betriebssystem erhaltene Entropie zu erschöpfen.

Ashwin
quelle
Es erfordert viel weniger als 2 ^ 48, um a vorherzusagen Random, das OP sollte überhaupt nicht verwendet werden Random.
Prägen
@emboss: Ich spreche von Bruteforce.
Ashwin
1
Seien Sie vorsichtig mit Linux: Es kann zu Entropieerschöpfung führen (mehr in VM als mit Hardware)! Schauen Sie sich an /proc/sys/kernel/random/entropy_availund überprüfen Sie mit einigen Thread-Dumps, dass beim Lesen nicht zu lange gewartet wird/dev/random
Yves Martin
2
Beachten Sie, dass Oracle JRE (mindestens 1.7) standardmäßig mit / dev / urandom und nicht mit / dev / random arbeitet, sodass das Suffix Ihrer Antwort nicht mehr korrekt ist. Überprüfen Sie $ JAVA_HOME / lib / security / java.security für die Eigenschaft securerandom.source
Boaz
1
Unsere Datei java.security hatte securerandom.source = file: / dev / urandom anstelle von file: /// dev / urandom (zwei Schrägstriche nach dem Doppelpunkt für das Dateiprotokoll, dann ein weiterer Schrägstrich für das Stammverzeichnis des Dateisystems), wodurch es zurückfiel to / dev / random, was Probleme mit der Erschöpfung des Entropiepools verursachte. Konnte es nicht bearbeiten, musste also beim Starten der App eine Systemeigenschaft java.security.egd auf die richtige setzen.
Maxpolk
11

Wenn Sie zweimal java.util.Random.nextLong()mit demselben Samen laufen , wird dieselbe Zahl erzeugt. Aus Sicherheitsgründen möchten Sie dabei bleiben, java.security.SecureRandomda dies viel weniger vorhersehbar ist.

Die 2 Klassen sind ähnlich. Ich denke, Sie müssen nur mit einem Refactoring-Tool wechseln Random, SecureRandomund der größte Teil Ihres vorhandenen Codes funktioniert.

Mualig
quelle
11
Wenn Sie zwei Instanzen eines PRNG nehmen und es mit demselben Wert setzen, erhalten Sie immer dieselben Zufallszahlen, auch wenn SecureRandom dies nicht ändert. Alle PRNGs sind deterministisch und daher vorhersehbar, wenn Sie den Samen kennen.
Robert
1
Es gibt verschiedene SecureRandom-Implementierungen, einige sind PRNGs, andere nicht. Auf der anderen Seite ist java.util.Random immer PRNG (wie in seinem Javadoc definiert).
Peter Štibraný
3

Wenn das Ändern Ihres vorhandenen Codes eine kostengünstige Aufgabe ist, empfehlen wir Ihnen, die in Javadoc vorgeschlagene SecureRandom-Klasse zu verwenden.

Selbst wenn Sie feststellen, dass die Implementierung der Random-Klasse die SecureRandom-Klasse intern verwendet. Sie sollten es nicht als selbstverständlich ansehen, dass:

  1. Andere VM-Implementierungen machen dasselbe.
  2. Die Implementierung der Random-Klasse in zukünftigen Versionen des JDK verwendet weiterhin die SecureRandom-Klasse

Es ist daher eine bessere Wahl, dem Dokumentationsvorschlag zu folgen und direkt mit SecureRandom zu arbeiten.

Andrea Parodi
quelle
Ich glaube nicht, dass die ursprüngliche Frage besagt, dass die java.util.RandomImplementierung SecureRandomintern verwendet wird, sondern dass ihr Code verwendet wird, SecureRandomum die zu setzen Random. Trotzdem stimme ich beiden bisherigen Antworten zu; Es ist am besten, SecureRandomeine explizit deterministische Lösung zu vermeiden.
Palpatim
2

Die aktuelle Referenzimplementierung von java.util.Random.nextLong()führt zwei Aufrufe der Methode durch, next(int)die 32 Bit des aktuellen Startwerts direkt verfügbar macht :

protected int next(int bits) {
    long nextseed;
    // calculate next seed: ...
    // and store it in the private "seed" field.
    return (int)(nextseed >>> (48 - bits));
}

public long nextLong() {
    // it's okay that the bottom word remains signed.
    return ((long)(next(32)) << 32) + next(32);
}

Die oberen 32 Bit des Ergebnisses von nextLong()sind die Bits des Startwerts zu der Zeit. Da die Breite des Startwerts 48 Bit beträgt (sagt der Javadoc), reicht es aus, * über die verbleibenden 16 Bit zu iterieren (das sind nur 65,536 Versuche), um den Startwert zu bestimmen, der die zweiten 32 Bit erzeugt hat.

Sobald der Samen bekannt ist, können alle folgenden Token leicht berechnet werden.

Unter Verwendung der Ausgabe von nextLong()direkt, teilweise dem Geheimnis des PNG in einem Ausmaß, dass das gesamte Geheimnis mit sehr wenig Aufwand berechnet werden kann. Gefährlich!

* Es sind einige Anstrengungen erforderlich, wenn die zweiten 32 Bit negativ sind, aber das kann man herausfinden.

Matt
quelle
Richtig. Unter jazzy.id.au/default/2010/09/20/… erfahren Sie, wie Sie schnell java.util.random knacken können !
Ingyhere
2

Der Same ist bedeutungslos. Ein guter Zufallsgenerator unterscheidet sich in der gewählten Primzahl. Jeder Zufallsgenerator beginnt mit einer Zahl und durchläuft einen 'Ring'. Das heißt, Sie kommen mit dem alten internen Wert von einer Zahl zur nächsten. Aber nach einer Weile erreichen Sie wieder den Anfang und beginnen von vorne. Sie laufen also Zyklen. (Der Rückgabewert eines Zufallsgenerators ist nicht der interne Wert.)

Wenn Sie zum Erstellen eines Rings eine Primzahl verwenden, werden alle Zahlen in diesem Ring ausgewählt, bevor Sie einen vollständigen Zyklus durch alle möglichen Zahlen abschließen. Wenn Sie Nicht-Primzahlen verwenden, werden nicht alle Zahlen ausgewählt und Sie erhalten kürzere Zyklen.

Höhere Primzahlen bedeuten längere Zyklen, bevor Sie wieder zum ersten Element zurückkehren. Der sichere Zufallsgenerator hat also nur einen längeren Zyklus, bevor er wieder am Anfang ankommt. Deshalb ist er sicherer. Sie können die Zahlengenerierung nicht so einfach vorhersagen wie bei kürzeren Zyklen.

Mit anderen Worten: Sie müssen alle ersetzen.

Nicolas
quelle
0

Ich werde versuchen, sehr einfache Wörter zu verwenden, damit Sie den Unterschied zwischen Random und SecureRandom und die Bedeutung der SecureRandom-Klasse leicht verstehen können.

Haben Sie sich jemals gefragt, wie OTP (Einmalpasswort) generiert wird? Um ein OTP zu generieren, verwenden wir auch die Klassen Random und SecureRandom. Um Ihr OTP jetzt stark zu machen, ist SecureRandom besser, da es 2 ^ 128 Versuche dauerte, das OTP zu knacken, was auf dem gegenwärtigen Computer fast unmöglich ist. Wenn Sie jedoch Random Class verwenden, kann Ihr OTP von jemandem geknackt werden, der Ihre Daten beschädigen kann, weil es nötig war nur 2 ^ 48 versuchen, zu knacken.

Sachin Pathak
quelle