Hallo, ich möchte eine Zufallszahl in Assembler erzeugen. Ist sowas überhaupt möglich? Danke im Vorraus
"Echte" Zufallszahlen kann man z.B. durch ADC-Messung von Rauschquellen erzeugen. I.d.R. verwendet man aber Pseudozufallszahl-Generatoren (PNG) und erzeugt nur die seed über echten Zufall (z.B. Messung der Zeit zwischen mehreren Tastendrücken). Ein gebräuchliches und auf µC gut implementierbares Verfahren sind LFSR (Linear Feedback Shift Register). PNG haben gegenüber echtem Zufall mehrere Vorteile: Sie sind effizient zu programmieren, die Algorithmen sind wohluntersucht und erzeugen statistisch nahezu ideal verteile Werte, und die Reproduzierbarkeit (d.h. Verwendung der gleichen seed in mehreren Programmläufen) kann das Debugging sehr erleichtern. MfG Olaf
Hallo Olaf, Ein gebräuchliches und auf µC gut implementierbares Verfahren sind LFSR (Linear Feedback Shift Register). PNG haben gegenüber echtem Zufall mehrere Vorteile: Sie sind effizient zu programmieren, die Algorithmen sind wohluntersucht und erzeugen statistisch nahezu ideal verteile Werte, und die Reproduzierbarkeit (d.h. Verwendung der gleichen seed in mehreren Programmläufen) kann das Debugging sehr erleichtern. Zu beachten ist aber, dass sie per Prinzip deterministisch sind und man trotzdem einen zufälligen Startwert braucht. Sonst erhält man nach einem Neustart immer die exakt gleichen "Zufallszahlenfolgen". Jörg
Diese RNGs sind immer für uns von Vorteil gegenüber einem echten HW RNG. Denn beweise mir mathm. das der Output von zb. 1024 Nullen eines Dioden Rauschens wirklich echter Zufall war. D.h. wenn wir 2 RNGs haben, einmal ein Pseudo-RNG basierend auf einem LFSR und damit per mathematischen Formeln exakt beweisebar und reproduzierbar. Dieser wird verglichen mit einem echten HW-RNG wie dem Rauschen einer Diode. Nun produzieren wir durch "Zufall" zb. exakt 1024 mal hintereinander mit beiden RNG immer nur die Zahl 0. Gut, bei 1024 Bits ist die Wahrscheinlichkeit das man 1024 0'en erzeugt mit 1 zu 2^1024 durchaus eine gültige aber sehr unwahrscheinliche Sequenz von Bits. Allerdings könnte man nun annehmen das lauter 0'Bits bei einer Diode anzeigt das diese physikalisch nicht mehr funktioniert. Da wir aber aus Sicht unserer Bits nur diese kennen und die Diode nicht direkt prüfen können müssen wir annehmen das diese nicht defekt ist, denn selbst Millionen von 0 Bits, also das ständige Low-Signal einer Diode ist ein wahrscheinliches Resultat das zufällig sein könnte, denn selbst unendlich viele 0'bits wären eine gültige Lösung als Sequenz die per zufall erzeugt werden kann. Zwar ist es so das die Wahrscheinlichkeit mit jedem erzeugten Bit weiter gegen unendlich klein tendiert, aber sie wir eben niemals ganz gegen Null tendieren können. So..., bei einem Pseudo-RNG nehmen wir den Startwert, und unser Freund nimmt diesen auf seiner CPU implementation des gleichen Pseudo-RNGs und wenn alles korekt war wird er die exakt gleiche Sequenz von Nullen erzeugen wie unserer RNG. Dh. erst durch diese Reproduzierbarkeit können wir nicht nur metaphysisch==imateriell=philosophisch mathematisch, sondern ganz praktisch und technologisch beweisen das unser RNG mit einem spez. Startwert unsere Sequenz aus 1024 Nullen erzeugen muß. Das heist: jeder mathem. Pseudo-Zufalls-Generator ist in seiner Beweisbarkeit für uns Menschen jedem RNG, der auf "echten" externen aber niemals beweisbaren Phenomänen basiert, vorzuziehen. Die Fragestellung ob man beweisen kann das ein RNG wirklich "zufällig" ist hängt also nur davon ab ob wir den einmal erzeugten Zufallsstrom jeder Zeit reproduzieren können. Da wir bei echten RNGs dies eben nicht können können wir auch nicht praktisch beweisen ob dieser Zufall auch wirklich Zufällig ist. Ergo: immer einen beweisbaren Pseudo-RNG benutzen und wenn dann nur den Startwert dieses RNGs entsprechend zufällig initialisieren, ist aber aus statistischer Sicht eigentlich nicht notwendig. Die Zufälligkeit solcher PRNGs definiert sich nun aus der Komplexität der math. Formel und die verwendete Datengröße. Würde man zb. einen Quadratischen Reste Generator benutzen (Blum Blum Shub Generator) mit entsprechend großen Paramatern > 1024 Bits, und wir erzeugen mit einem Seed eine Sequenz von 1024 Bits dann ist: 1.) für uns dieser Zufallsstrom jederzeit deterministisch und reproduzierbar da WIR den Startwert kennen 2.) für andere Personen die NICHT den Startwert kennen ist die Komplexität derart hoch das er defato niemals in der Lage sein kann den Zufallsstrom vorhersagen zu können. Unser Pseudo-RNG verhält sich damit aus Sicht dieser Person wie ein echter Zufallsgenerator, für uns ist er somit beweisbar sicher. Es gibt also keine hinreichende Begründung keine Pseudo-RNGs benutzen zu wollen und sich auf unbeweisbare physikalische Phenomäne zu verlassen wie bei einer Diode. Gruß Hagen
Hagen, das ist mir zuviel Text.Kannst das nochmal in 1-2 Sätzen für mich zusammenfassen? Dankeschön schonma!
Wenn man die Wahl hat zwischen - Pseudo RNGs basierend auf einer math. bewiesenen Formel, oder - einem beliebigen Hardware RNG basierend auf physikalischen Eigenschaften dann ist es per logik beweisbar das man immer einen Pseudo RNG benutzen sollte. Dies trifft auf die Anwendung in der Statistik, Mathematik und auch Kryptographie zu. Und warum? Einfach weil man einen Hardware RNG niemals als 100%'tig korrekt beweisen kann da man deren Zufallsoutput nicht reproduzieren kann. Das ist aber eine wichtige Grundbedingung um zb. Fehler in Software oder Hardware erkennen zu können. Um math. die Korrekheit eines solchen HW RNGs beweisen zu können benötigen wir 2 Dinge: a) die Formel mit der dieser RNG arbeitet b) alle Startparameter die der RNG benutzt Kennen wir diese Formel und den Startwert dann degradiert dieser HW-RNG defakto zu einem Pseudo-RNG, wir kennen ja bei beiden die Formeln und Paramter, es existiert dann kein Unterschied mehr. Kennen wir diese Formeln aber nicht so können wir auch niemals mit Sicherheit beweisen/wissen das dieser HW-RNG auch wirklich zufällig ist. Der Große Unterschied des HW-RNG besteht eben darin das man sich auf physikalische Annahmen stützt. Das ist ein grundsätzlicher Fehler im Konzept. Denn defakto können wir nicht beeisen ob unser System in dem wir leben auch wirklich so funktioniert wie wir es annehmen. HW-RNGs basieren also nur auf Annahmen, SW-RNGs basieren ausschließlich auf Mathematik und die kümmert sich einen Schit um unsere Realität. In der Mathemtik existieren nur Axiome/Behauptungen und davon strikt logisch abgeleitete Erkenntnisse. So lange das postulierte System der Axiome gültig ist so lange können wir die Eigenschaften eines SW-RNGs auch beweisen. Gruß Hagen
> dann ist es per logik beweisbar das man immer einen Pseudo RNG > benutzen sollte. Dies trifft auf die Anwendung in der Statistik, > Mathematik und auch Kryptographie zu. Gerade in der Kryptographie setzt man aber lieber richtige Zufallszahlen ein. Einigermaßen moderne PCs haben einen Hardware-Zufallsgenerator, der dafür zuständig ist und bevorzugt dafür eingesetzt wrid. Warum? > da man deren Zufallsoutput nicht reproduzieren kann. und genau das soll man auch nicht können, denn das wäre ein möglicher Angriffspunkt zum Knacken der Verschlüsselung.
@Hagen: Ist es nicht vielleicht etwas gar philosophisch, was du schreibst? Klar hast du grunsätzlich Recht, aber in der Praxis sollte man einen HW-RNG doch so eingehend testen können, dass man danach seine Eigenschaften ähnlich gut kennt, wie die eines SW-RNG. Wenn man mehrere Millionen Zufallszahlen würfelt, und die den geforderten Bedingungen entsprechen, dann sehe ich keinen Grund, warum man dem HW-RNG nicht vertrauen soll, nur weil man ihn nicht vollständig versteht.
Vieleicht oder auch nicht. Ich vertrete hier nur meine Sichtweise der Dinge und das dann vorrangig als Kryptograph. Ich meine aber das es eine ganz praktisch und eben dogmatische Sichtweise ist. Man kann zwar bei einem HW-RNG dessen statistische Egenschaften analysieren und dann postulieren -> ist Zufall. Aber das könnte ich auch von einer 1 Gb großen und gepackten Datei behaupten -> statisch ist es Zufall. Bei einem PRNG kenne ich aber alle Fakten, ich kenne die Formel, ich kenne die Komplexität des Verfahrens und damit dessen Sicherheitsschranken und ich kenne für Reproduktions-zwecke auch den Startwert. Wenn alles stimmig ist dann ist 1.) das Verfahren math. beweisbar korrekt 2.) die Komplexität des Verfahrens math. beweisbar 3.) die Komplexität so hoch gewählt das man math. ausrechnen kann wie sicher das Verfahren in der Anwendung sein wird, auch für die Zukunft und als letzten Punkt eben 4.) durch das Geheimhalten der Startwerte haben wir nun eine Funktion die entweder berechnebar ist oder aber nicht berechnbar sein kann. UNd derjenige der das Geheimnis=Sartwert kennt der kontrolliert die Verteilung und den Zugriff auf diese Daten. Und dies ist ja das Ziel der Kryptographie -> Kontrolle durch Wissen oder Unwissen. Es gibt aber auch ganz praktische Unterschiede: Ein HW-RNG basierend auf zb. dem LSB eines ADCs. Wir werden niemals in der Lage sein beweisen zu können ob dieser Zufallsstrom nun eine Eigenschaft der EMV Strahlung oder Wärmestrahlung zu einem Zeitpunkt an einem Ort sein kann, oder ob es nur Eigenrauschen auf Grund der verwendeten technolgischen Struktren darstellt. All diese 3 Einflüsse könnten für sich genommen statist zufällig wirken sind es aber defakto nicht. Bewegen wir unser Board/Hardwrae an einen andern Ort zu einem anderen Zeitpunkt dan wird er wenn er zb. auf EMV reagiert auch anderen Zufall erzeugen. Ergo: in diesem Falle haben wir also keinen echten Zufall mehr. Aber bei einem PseudoRNG der ja als Formel in eine Software impleemntiert wird können wir diesen auf ganz unterschiedlichen Technologien integrieren. Mit gleichem Startwert unabhängig von Raum und Zeit MUSS immer der gleiche Zufall erzeugt werden. Wir können als bei PRNGs 1.) die Formel == ergo das Wissen was drinnensteckt 2.) den Ouput==Zufallsstrom weil gleicher Startwert 3.) unabhängig von Raum und Zeit 4.) unabhängig von der verwendeten Technologie=Hardware das Ding reproduzieren und erlangen damit beweisbare Veefahrenssicherheit. Um einen RNG einschätzen/beweisen zu können reicht es eben nicht nur eine statistische Analyse anzuführen. Man muß sich das mal vorstellen. Wir konstruieren ein kryptographisches System und beweisen das es sicher sein wird. Die einzigste Schwachstelle sind also schlechte Passwörter oder notwendige Zufallsdaten. Und exakt an dieser Stelle bauen wir Technologie ein bei der wir eben nicht wissen ob sie tatsächlich an jedem Ort und zu jeder Zeit immer korrekt arbeiten wird. Gut, das ich hier OT immer die Kryptograhie herranziehe hat einen einfachen Grund. Es ist die einzisgte Wissenschaft die sich eben exatkt mit solchen Dingen tiefgründiger auseinandersetzt. Sie ist sogar fast die einzigste Wissenschaft der Mathematik die sich überhaupt mit praktisch anwendbaren Dingen befasst und dabei aber rein ist, dh. keinerlei physikalische Phenomäne berücksichtigen MUSS. Gruß Hagen
Gut zurück zum Thema, denn praktisch gesehen heist dies: Möchtest du von Anfang an sicher stellen das du guten Zufall erzeugst oder willst du dich auf physikalische Eigenheiten einer Hardware verlassen müssen. Der Aufwand wäre einerseits eine simples Stückchen Software oder eben zb. eine Diode und ein ADC mit ihren in unserem Bereich notwendigen Eigenrauschen. Das erste ist unabhängig vom AVR und Diode immer reproduzierbar und funktionabel, beim zweiten hängt es vom Produktionsprozess der Technologie ab und wo/wann wir das Board dann einsetzen. Ich meine: nimm einen Software-RNG dann weist du das es funktionen muß und ersparst dir Ärger. Gruß Hagen
""
> da man deren Zufallsoutput nicht reproduzieren kann.
und genau das soll man auch nicht können, denn das wäre ein möglicher
Angriffspunkt zum Knacken der Verschlüsselung.
""
Falsch, absolut falsch. Denn was wissen wir dann ? Wir wissen das wir
eben nicht wissen was da abläuft und somit existiert ein möglicher
Angriffspunkt in unserem Design. Das ist in der Kryptographie fatal
denn die Sicherheit in der Kryptographie basiert ausschließlich nur
darauf das wir WISSEN.
Ein möglicher Angriffspunkt in der Kryptographie zeichnet sich immer
dadurch aus das wir weniger Wissen besitzen als der Angreifer !! Also
müssen wir jeden Schritt beweisen können und das führt dazu das dieser
Beweis auch für einen Angreifer gültig ist. Können wir dies und setzen
die Schranken der Komplexität so enorm hoch dann kann auch ein
Angreifer mit gleichem Wissen nichts knacken. Wir können es ihm sogar
beweisen das es so sein wird.
Man muß es mal so betrachten: es geht darum mit hilfe der Mathematik
exakt beweisen zu können das ein Angeifer nicht die geringste Chance
haben kann an unsere Daten zu kommen. Um das beweisen zu können müssen
wir uns in unseren Technologien auf die Teilmenge beschränken die wir
absolut exakt verstehen und beweisen können. Das ist bei einem HW.RNG
eben nicht der Fall.
Gruß Hagen
Ohne deinen ganzen Text gelesen zu haben (heb ich mir für's WE auf) bleibt als Frage, wo der Startwert herkommt. Denn wie du ja so schön erklärt hast, ist es mit Kenntnis des Startwertes möglich, die komplette Folge zu berechnen (bei manchen Algorithmen sogar bestimmte Elemente der Folge, ohne die vorhergehenden berechnen zu müssen). Also muss ein zufälliger Startwert her -> nehmen wir nun hier einen P-RNG oder einen HW-RNG? Gruss, Dominic
Die Wahrscheinlichkeit bei einer (Normalverteilten) Zufallszahl 1024x eine 0 zu erhalten ist bestimmt geringer als die Wahrscheinlichkeit das ein Hardwaredefekt vorliegt. Und wenn man nun nicht gerade staatsgeheimnisse verschlüsseln möchte sondern vieleicht einfach nur "zufällig" ein neues Lied bei einem MP3 Player wählen will ist das doch in Ordnung. Der Landläufige "Zufall" dekt sich eh nicht mit dem was man unter Wahrscheinlichkeittheoretischen aspekten dadrunter versteht.
bei entsprechener Komplexität des RNGs ist das wurscht ;) Wichtig ist nur das der Startwert geheim bleibt. Der Startwert ist ja nur wichtig um eine andere Folge von Zufall zu erzeugen. Ich mache es am liebsten so das ich eine Serialnummer und ein Startwert Register benutze. Beim Powerup der CPU nehme ich beides und füttere damit den RNG. Der RNG produziert nun ein par Bytes die so groß sind wie das Startwert Register. Diese Bytes speichere ich dann als neuen Startwert im Register. Die Serialnummer ist hardcoded im FLASH und das Startwert Register das sich ja bei jedem Powerup verändert speichere ich im EEPROM. Um sicher zu gehen das sich keine wiederholenden Folgen von Startwerten einstellen besteht ein Teil dieses Startwert Register aus einem Zähler. Bei jedem Powerup wird dieser Zähler um +1 inkrementiert. Formal entsteht sowas wie eine Hashfunktion aus der Kryptographie bekannt. Zb. in Verfahren wie die KDF -> Key Derivation Functions oder MGFs -> Mask Genration Function. Gruß Hagen
Tut mir echt leid, aber genau da beisst sich die Katze in den eigenen Schwanz. Da dein Angreifer ja prinzipiell alles wissen könnte, was du weisst, kann er auch deine Seriennummer und den Startwert wissen. Kryptographische Verfahren beruhen aber eben genau darauf, dass Zufall eine nicht-deterministische Komponente einführt. Da vollkommen zufällige Systeme aufgrund physikalischer Randbedingungen nicht realisierbar sind, beschränkt man sich auf beherrschbare Systeme -> bekannte HW-RNG Systeme Ob da nun ein Zwinkern ist oder nicht, die Kompexität des RNG spielt beim Zufall keine Rolle, und "ernst" gemeint war meine Frage auch nie ;)
Um das Problem Takashi noch mal aufzugreifen und Olaf Kindels Antwort auszuführen: Wenn dein µC einen A/D-Wandler hat, dann hol' einfach ein paar analoge "Meßwerte" von einem unbeschalteten Pin ab. An den offenen Pins tritt genügend Rauschen auf, um zufällig zu sein. Das ist besser, als jedes komplizierte mathematische Verfahren, da es echter Zufall ist.
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.