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?
Dazu gibt es doch sicher irgendeine Diplomarbeit, danach würde ich mal suchen.
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.
:
Bearbeitet durch Moderator
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.
:
Bearbeitet durch User
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: > Mach Xorshift, Nein, XORshift ist unzuverlässig und fällt bei Statistik-Tests durch: https://arxiv.org/abs/1810.05313
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.
Angehängte Dateien:
-
LM393-on.png
29 KB
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.
Thread beobachten
Seitenaufteilung abschaltenBitte melde dich an um einen Beitrag zu schreiben. Anmeldung ist kostenlos und dauert nur eine Minute.
Bestehender Account
Schon ein Account bei Google/GoogleMail? Keine Anmeldung erforderlich!
Mit Google-Account einloggen
Mit Google-Account einloggen
Noch kein Account? Hier anmelden.