Mir kam gerade zufällig eine Idee wie man einen Zufallszahlengenerator
implementierten könnte:
1. Man misst Rauschen eines offenen ADCs
2. Man füttert dieses Rauschen als Ausgangsmessung in einen
Kalman-Filter, der für ein instabiles System (z.B. Van-der-Pol)
ausgelegt ist.
3. Die Ausgänge des Filters sind dann die Zufallszahlen.
Evtl. Probleme:
1. Rauschen des ADC korreliert mit von außen beeinflussbaren Größen
2. Die Dynamik des Filters beeinflusst die Zufallszahlen so stark, dass
diese nicht mehr zufällig sind. Hängt aber auch davon ab, wie stark das
Rauschen mit der Filterdynamik korreliert.
Denkt ihr die Idee ist halbwegs zu gebrauchen?
Danish schrieb:> Denkt ihr die Idee ist halbwegs zu gebrauchen?
Nö. Du hast schlichtweg keinen Nachweis darüber, wie zufällig dein
Zufall ist.
Mach Xorshift, der geht schnell, liefert sehr guten Zufall im Vergleich
zu den vielfach verwendeten LFSR (die sind wirklich grottig wenn man da
mal Tupel- und Tripeltest macht), dürfte für die meisten
Zufallanwendungen auf dem µC ausreichen und ist leicht implementierbar.
https://de.wikipedia.org/wiki/Xorshift
Danish schrieb:> Denkt ihr die Idee ist halbwegs zu gebrauchen?
Kommt auf den ADC an, auf das "Rauschen", das er einfängt und auf so
viel mehr. Vieles davon kann zufällig sein, vieles auch systematisch.
Und wenn das dann wie gewünscht alles "zufällig" funktioniert, aber der
Controllerhersteller eine Maskenänderung macht, guckst du nett aus der
Wäsche.
Ich nehme gern ein gaaaaaaanz langes LFSR und einen zufälligen
Startwert.
Die Qualität der Zufallszahlen aus dem LFSR kann man untersuchen und auf
Tauglichkeit bewerten. Einen zufälligen Startwert bekomme ich z.B. von
einen schnellen Zähler dessen Zählerstand bei einem Tastendruck oder
spnst einem Eingangssignal (Endschalter) aus der realen Welt als Seed
genommen wird.
Lothar M. schrieb:> Ich nehme gern ein gaaaaaaanz langes LFSR und einen zufälligen> Startwert.
Du schummelst.
Der Knackpunkt ist üblicherweise: woher nehme ich in einer
determinstischen Maschine einen wirklich zufälligen Seed...
Das LFSR ist trivial und gut untersucht, sogar jeder Arduidiot kann ein
gutes C&P'en, wenn er mit Google umgehen kann.
Karl K. schrieb:> Du hast schlichtweg keinen Nachweis darüber, wie zufällig dein> Zufall ist.
Dafür gibt es Tests, mit denen man die Verteilungsfunktion und andere
Kriterien bewerten kann:
https://nvlpubs.nist.gov/nistpubs/Legacy/SP/nistspecialpublication800-22r1a.pdf
Das Problem mit den ganzen LFSRs, XORs und sonstigen PRNGs ist, dass sie
zwar eine gute Verteilungsfunktion haben, aber eben nicht zufällig,
sondern deterministisch sind. Das bedeutet, wenn man einen Funtionswert
kennt, dann kennt man alle zukünftigen. Um PRNGs kryptographisch sicher
zu machen, muss man eine Hashfunktion nachschalten, und dann sind sie
immernoch anfällig gegen Sideband-Attacks, weil die Zufallsvariable eben
digital berechnet wird.
Wenn es also wirklich eine indeterministisch erzeugte Zufallsvariable
sein soll, dann führt kein weg an einem analogen TRNG vorbei. Manche
SoCs haben auch schon so einen an Bord.
Spaßeshalber mal eine Denkaufgabe, die ein Prof uns mal vor ewigen
Zeiten gestellt hat: Zwei gleiche PRNGs liefern exakt die gleiche
Zahlenfolge, wenn sie den gleichen Seed verwenden. Die
Wahrscheinlichkeit, dass zwei PRNGs die gleiche Zahlenfolgen der Länge n
Bits erzeugen, hängt also nur ab von der Anzahl der möglichen Seeds und
nicht von n selbst. Wie groß ist die Wahrscheinlichkeit zweier
identischer Zahlenfolgen der Läge n bei TRNGs? In allen Fällen soll eine
Gleichverteilung angenommen werden.
Wenn Du mit wenigen Komponenten einen guten TRNG möchtest, dann empfehle
ich den hier:
http://www.jtxp.org/tech/xr232usb.htm
Natürlich brauchst Du den FTDI und Attiny nicht, das kannst Du auch
anders machen. Spannend sind nur die beiden Komparator-Einheiten des
LM393 und deren Beschaltung.
c-hater schrieb:> Der Knackpunkt ist üblicherweise: woher nehme ich in einer> determinstischen Maschine einen wirklich zufälligen Seed...
Richtig: der muss von "aussen" in die Maschine kommen. Aber dann
reicht es, ein einziges Mal einen zufälligen Wert zu haben.
Vancouver schrieb:> Spaßeshalber mal eine Denkaufgabe, die ein Prof uns mal vor ewigen> Zeiten gestellt hat: Zwei gleiche PRNGs
Mich hindert im Prinzip aber auch keiner daran, das Polynom zufällig
umzuschalten oder es zufällig wieder mit einem neuen Seed zu starten.
Vancouver schrieb:> dann führt kein weg an einem analogen TRNG vorbei. Manche SoCs haben> auch schon so einen an Bord.
Dann sollte der aber nachweislich besser sein. Ich habe schon einige
"trickreiche" Verfahren mit ADC und wilden Oszillatoren ausprobiert. Im
Klimaschrank und bei bestimmten Spannungen benehmen die sich dann
manchmal erstaunlich deterministisch...
Gerd E. schrieb:> Spannend sind nur die beiden Komparator-Einheiten des LM393 und deren> Beschaltung.
Leider schon mit einer Pinzette ganz leicht zu hacken... ;-)
Danish schrieb:> Denkt ihr die Idee ist halbwegs zu gebrauchen?
Nein, denn das ist schon mal falsch:
> 2. Die Dynamik des Filters beeinflusst die Zufallszahlen so stark, dass> diese nicht mehr zufällig sind.
Erstens wäre es nicht die Dynamik sondern die Ü-Funktion des Filters,
also das diskrete Spektralverhalten und zweitens bliebe es zufällig.
Du müsstest auch anders herum argumentieren, dass das nichtzufällige aus
Deinem Punkt 1 noch zufällliger werden müsste. Aber auch das ist nicht
der Fall.
Deine Idee krankt leider an den typischen Denkfehlern die in dem Umfeld
gemacht werden.
Lothar M. schrieb:> Mich hindert im Prinzip aber auch keiner daran, das Polynom zufällig> umzuschalten oder es zufällig wieder mit einem neuen Seed zu starten.
Wenn du das ebenfalls mit einem PRNG machst, der einen Seed braucht,
verschiebst du das Problem nur an eine andere Stelle.
Lothar M. schrieb:> Im> Klimaschrank und bei bestimmten Spannungen benehmen die sich dann> manchmal erstaunlich deterministisch...
Naja, die physikalischen Randbedingungen sind nochmal ein eigenes Thema.
Auch ein Mersenne-Twister in einem commercial-grade FPGA wird bei 200°C
keine brauchbaren Werte mehr liefern (und vermutlich nie wieder :-)
Aber um zuverlässige Zufallsvariablen zu generieren, ohne irgendwelche
Verfahren verschleiern zu müssen, gibt es keinen anderen Weg als das
indeterministische Verhalten realer physikalischer Prozesse. Kommt halt
immer drauf an, was man damit machen will. Wenn man ein weißes Rauschen
braucht, um eine Signalverarbeitung zu testen, dann kann man auf
kryptografische Sicherheit und langfristige perfekte Gleichverteilung
verzichten, und dann ist ein guter PRNG das Mittel der Wahl.
Uwe B. schrieb:> Was spricht gegen den True RNG Generator in einem STM32?
Die Tatsache, dass nicht offengelegt ist, wie er funktioniert. Wenn bei
solchen Sachen nicht offengelegt wird, wie es funktioniert, dann ist
damit zu rechnen, dass der Zufall nur wie Zufall aussieht, aber nicht
wirklich Zufall ist, sondern immer noch bestimmten (nichtöffentlichen)
Gesetzen folgt, die es Angreifern mit Kenntnis dieser Gesetze den
Angriff massiv erleichtert.
Das ist ein Problem aller Architekturen, die irgendwelchen Zufall in
Hardware anbieten. Es ist praktisch immer damit zu rechnen, dass dieser
Zufall nicht wirklich zufällig ist. Der jeweils die staatliche Macht
ausübende Geheimdienst wird das mit Sicherheit unterbunden haben. Hätte
er das nicht getan, wäre er nicht das Steuergeld wert, was er kostet.
Man kann also diesen Scheiß als Entropiequelle benutzen, aber sicher
nicht als alleinige, das wäre ziemlich dumm...
c-hater schrieb:>> Was spricht gegen den True RNG Generator in einem STM32?>> Die Tatsache, dass nicht offengelegt ist, wie er funktioniert. Wenn bei> solchen Sachen nicht offengelegt wird, wie es funktioniert, dann ist> damit zu rechnen, dass der Zufall nur wie Zufall aussieht, aber nicht> wirklich Zufall ist, sondern immer noch bestimmten (nichtöffentlichen)> Gesetzen folgt, die es Angreifern mit Kenntnis dieser Gesetze den> Angriff massiv erleichtert.
Naja, das "offengelegt, wie er funktioniert" hilft Dir auch nicht soo
viel, da der Herstellungsprozess relativ komplex ist und schon kleine
Manipulationen einen deutlichen Einfluss haben können.
Der TRNG der STM32 ist aber im Vergleich zu ähnlichen Implementationen
(z.B. der Intel Prozessoren) deutlich besser, da er es ermöglichst alles
Post-Processing und Conditioning abzuschalten und damit Zugriff auf die
Rohdaten ermöglicht.
Wenn es also wirklich darauf ankommt, kann man die Rohdaten
entsprechenden Tests unterziehen.
Wenn man dagegen RDRAND oder RDSEED auf Intel Prozessoren verwendet, hat
man wegen dem nicht abschaltbaren Post-processing keine Chance zu
ermitteln ob die Zufallszahlen wirklich gut oder evtl. manipuliert sind.
Tobias N. schrieb:> Erstens wäre es nicht die Dynamik sondern die Ü-Funktion des Filters,> also das diskrete Spektralverhalten und zweitens bliebe es zufällig.
Was soll der Filter an Zufall rausholen aus einem ADC, der
kurzgeschlossen nur Nullen liefert oder bei übersteuertem Eingang am
oberen Endwert rumhängt?
Gerd E. schrieb:> Wenn Du mit wenigen Komponenten einen guten TRNG möchtest, dann empfehle> ich den hier:
Oh man, das ist ja noch einfältiger als der ADC. Wenn schon dann eine
ordentliche Rauschquelle, aber kein IC der sich bei bißchen Abkühlung
komplett anders verhalten kann.
Vancouver schrieb:> Wenn es also wirklich eine indeterministisch erzeugte Zufallsvariable> sein soll, dann führt kein weg an einem analogen TRNG vorbei.
Ja, und dann gehts um ein Flackerlicht auf der Modellbahnanlage...
Karl K. schrieb:> Gerd E. schrieb:>> Wenn Du mit wenigen Komponenten einen guten TRNG möchtest, dann empfehle>> ich den hier:>> Oh man, das ist ja noch einfältiger als der ADC. Wenn schon dann eine> ordentliche Rauschquelle, aber kein IC der sich bei bißchen Abkühlung> komplett anders verhalten kann.
Meine Tests mit Eisspray und Heißluftlötstation haben keine signifikante
Änderung am Rauschen gezeigt.
Deine Kritik an der Schaltung kann ich so jedenfalls nicht
nachvollziehen.
Gerd E. schrieb:> Deine Kritik an der Schaltung kann ich so jedenfalls nicht> nachvollziehen.
Die Kritik ist, dass das überhaupt nicht den Specs entspricht und
jederzeit unter irgendwelchen Bedingungen sonstwas passieren kann.
Da liegt +IN auf V+, das Datenblatt sagt: VIN < V+-1.5V. Die
Innenschaltung gibt auch nicht her, was +IN auf V+ bezwecken soll, außer
irgendwelche parasitären Effekte irgendwelcher Übergänge auszulösen.
"Ich habs probiert und es geht" mag für Bastler ok sein, aber wenn hier
jemand einen RNG sucht und schon mit einem Xorshift nicht zufrieden ist,
wird er sich kaum auf eine "zufällig" funktionierende Schaltung
außerhalb der Herstellerspecs verlassen wollen.
Anderer Punkt ist dann die Angreifbarkeit - die auch der Autor
beschreibt - durch HF. Wenn ich da mit einem brauchbaren 100kHz Sender
rangehe, dürfte ich ziemlich gut den Zufall darauf synchronisieren
können. Und 100kHz kann heute jedes billige Handynetzteil oder
LED-Lampe.
was wollt Ihr eigendlich absichern?
Ne Atombombe?
Würde nicht ne ganz triviale Z-Diode
mit nachgeschalteten Schmitt Trigger nicht reichen?
Wenn nötig verdrosselt und im Thermostaten?
mfg
Gibts hier jemanden, der mir erklären kann, weshalb die
LM393-Schaltung (gezeigt von Gerd E. (robberknight))
soooo gut sein soll?
Echter (!) Zufall (mit wenigen/billigen Bauelementen) ist für
mich bis heute: Gute Abschirmung + passend verstärktes Z-Dioden-
Rauschen. Revers gepolte B-E-Strecken von Transistoren bringen
auch schönes Rauschen.
Nachteil: Man braucht UB > 5 V.
Mit UB < 5 V wird es dann wohl doch wieder ein LFSR...
~Mercedes~ schrieb:> Würde nicht ne ganz triviale Z-Diode> mit nachgeschalteten Schmitt Trigger nicht reichen?
Braucht aber min. 8V. Ich hab das mal mit nem Transistor und BE-Strecke
gebaut, das Problem ist halt den Schmitt-Trigger so einzustellen dass er
die geringe Rauschspannung sauber aufnimmt. Und dann nicht mit
Temperaturdrift abhaut.
Danish schrieb:> Mir kam gerade zufällig eine Idee wie man einen Zufallszahlengenerator> implementierten könnte:>> 1. Man misst Rauschen eines offenen ADCs> 2. Man füttert dieses Rauschen als Ausgangsmessung in einen> Kalman-Filter, der für ein instabiles System (z.B. Van-der-Pol)> ausgelegt ist.> 3. Die Ausgänge des Filters sind dann die Zufallszahlen.> Denkt ihr die Idee ist halbwegs zu gebrauchen?
Nein.
Eine Rauschquelle als Zufallsgenerator zu nehmen, ist einfach das, was
alle machen. Der Knackpunkt ist eher, eine gute Rauschquelle zu finden.
Und die dann auch so weit vom Rest des Systems zu isolieren, daß
überlagerte Störungen (z.B. von der Betriebsspannung) nicht
durchschlagen.
Wenn die Rauschquelle gut ist, ist der ganze Filterkram dahinter unnütz.
Zumal der am Ende ja auch nur pseudo-zufällig ist. Was dir da
vorschwebt, ist am Ende nur ein PRNG, der von einem TRNG geseedet wird.
Außer daß dein TRNG praktisch nicht spezifiziert ist. Und dein PRNG
schlecht untersucht (wenn man mit LFSR oder LCG vergleicht).
Karl K. schrieb:> Mach Xorshift, der geht schnell, liefert sehr guten Zufall im Vergleich> zu den vielfach verwendeten LFSR
Albern. Schieben und XORen ist die Basis eines LFSR. Dieses komische
XOR-Shift ist damit genau die gleiche Klasse von PRNG. Inklusive der
Einschränkung, daß 0 ein verbotener Zustand ist.
Ungeachtet dessen, sind alle PRNG in der gleichen Klasse. Wenn sie
einen internen Zustand mit N Bits haben, dann sind sie periodisch mit
Periode von höchstens 2^N. Und natürlich gibt man aus einem PRNG
niemals den gesamten internen Zustand raus, sondern immer nur ein paar
Bits. Auch unter diesem Gesichtspunkt ist XOR-Shift als höchst
fragwürdig einzustufen.
Karl K. schrieb:> Die Kritik ist, dass das überhaupt nicht den Specs entspricht und> jederzeit unter irgendwelchen Bedingungen sonstwas passieren kann.
Ein rückwärts gepolter Transistor hat auch kein im Datenblatt
spezifiziertes Rauschen. Wenn Du eine solche Schaltung aufbaust, musst
Du Dich also auf beobachtete/bekannte Effekte verlassen und nicht aufs
Datenblatt. Du musst ein paar Versuche machen und solltest danach dann
bei den gewählten Teilen und Herstellern bleiben.
Das gilt für den Transistor genau wie für den LM393.
> Anderer Punkt ist dann die Angreifbarkeit - die auch der Autor> beschreibt - durch HF. Wenn ich da mit einem brauchbaren 100kHz Sender> rangehe, dürfte ich ziemlich gut den Zufall darauf synchronisieren> können. Und 100kHz kann heute jedes billige Handynetzteil oder> LED-Lampe.
Da solltest Du Dir zuerst über Angriffsszenarien Gedanken machen. Wenn
ein Angreifer das Teil in der Hand hat und da sorgfältig seine Antenne
drumwickeln kann, kann er normalerweise auch ganz andere und einfachere
Angriffe ausführen.
Mit einem einfachen Blechgehäuse bekommst Du das Teil aber gut genug
geschirmt daß der Angreifer von außerhalb des Hauses schon extrem viel
Sendeenergie aufwenden müsste um einen Effekt zu erzeugen. Ein solch
starkes Feld könnte man z.B. auch ganz einfach außerhalb des TRNG messen
und dann Alarm schlagen oder ähnliches.
Die Z-Dioden-Methode ist für RF übrigens ähnlich empfindlich.
> und einen zufälligen Startwert.
Und wie zufällig ist Dein zufälliger Startwert?
Ich hätte übrigens auch eine Idee für ein neues Rad. Es sollte rund sein
und außen Gummi, damit die Kutsche nicht so rumpelt.
Irgendwie verstehe ich die Diskussion nicht:
Wenn Methode X einen ausreichend guten Seed liefert, ... dann bin ich
doch fertig. Jeder Zufalls-Zahlen Algorithmus danach doch blos
schlechter werden. OK: schneller oder mit weniger Ressourcen, aber
trotzdem in keinem Fall einen besseren Wert.
Ben B. schrieb:> Es sollte rund sein> und außen Gummi, damit die Kutsche nicht so rumpelt.
Rund ist rumpelmäßig nicht ideal. mach es dreieckig. dann rumpelt es
immer nur 3 mal.
Axel S. schrieb:> Albern. Schieben und XORen ist die Basis eines LFSR. Dieses komische> XOR-Shift ist damit genau die gleiche Klasse von PRNG.
Ähm: Nein. Wenn du es dir angeschaut hättest, hättest du gesehen dass es
eben sehr anders als ein LFSR ist - und deren Schwächen vor allem
bezüglich aufeinanderfolgender Zahlenpaarungen nicht hat.
Axel S. schrieb:> Wenn sie> einen internen Zustand mit N Bits haben, dann sind sie periodisch mit> Periode von höchstens 2^N.
Ja und? Nochmal: Welche Anwendung? Willst du One-Time-Pads erstellen?
Oder brauchst du einen RNG für einen elektronischen Würfel? Oder ein
Flackerlicht für die Modellbahn?
Ich glaub kaum, dass du erkennst dass das Modellbahnlicht mit einer
Periodenlänge von 2^32 flackert.
Und dieses ganze Verschlüsselungs-Gedöns ist in ein paar Jahren eh tot,
wenn Quantencomputer allgemein verfügbar werden.
Gerd E. schrieb:> Das gilt für den Transistor genau wie für den LM393.
Beim Transistor ist der Mechanismus der Rauscherzeugung nachvollziehbar.
Erzähl doch mal, was da in der Schaltung des LM393 die Rauschquelle ist.
Der Komperator wie im Link behauptet kanns nicht sein, wenn +IN auf V+
liegt ist der Komperatorteil Q8, Q9 tot.
Karl K. schrieb:> Axel S. schrieb:>> Albern. Schieben und XORen ist die Basis eines LFSR. Dieses komische>> XOR-Shift ist damit genau die gleiche Klasse von PRNG.>> Ähm: Nein. Wenn du es dir angeschaut hättest, hättest du gesehen
<seufz>
Und wenn du meinen Post aufmerksam gesesen hättest, dann wäre dir
aufgefallen, daß ich nirgendwo geschrieben habe, es wäre das gleiche.
>> Wenn sie>> einen internen Zustand mit N Bits haben, dann sind sie periodisch mit>> Periode von höchstens 2^N.>> Ja und? Nochmal: Welche Anwendung? Willst du One-Time-Pads erstellen?
Ich will gar nichts. Das ist nicht mein Thread. Auch das wäre dir bei
aufmerksamem Lesen aufgefallen. Aber wer über einen Hardware-TRNG
nachdenkt, der hat Anforderungen, die ein PRNG nicht erfüllen kann.
> Oder brauchst du einen RNG für einen elektronischen Würfel? Oder ein> Flackerlicht für die Modellbahn?>> Ich glaub kaum, dass du erkennst dass das Modellbahnlicht mit einer> Periodenlänge von 2^32 flackert.
Und ich glaube nicht, daß du in so einer Anwendung den Unterschied
zwischen einem LFSR und deinem geliebten XOR-Shift sehen kannst. Oder
irgendeinem anderen PRNG.
Axel S. schrieb:> Und ich glaube nicht, daß du in so einer Anwendung den Unterschied> zwischen einem LFSR und deinem geliebten XOR-Shift sehen kannst.
Ähm: Doch.
Das Problem beim LFSR ist, dass nahe beieinander liegende Werte
voneinander abhängig sind, deswegen sind die im Tupel- und Tripeltest so
schlecht.
Und das kann schon auffallen, wenn sich Musterfolgen in kurzer Zeit
wiederholen.
Die komplette Sequenz wird man nicht sehen, dazu ist die zu lang, aber
die Muster sieht man unter bestimmten Bedingungen.
> in ein paar Jahren [..] wenn Quantencomputer allgemein verfügbar werden.
Das glaube ich erst, wenn ich es sehe.
Kommt wahrscheinlich drauf an, wie man "paar" definiert.
