Generatorpolynome für PRNGs

[ChrisV (Gast)]

Hallo,

über rückgekoppelte Schieberegister kann ich ja Pseudozufallszahlen 
generieren.
Wie ich das Schieberegister aufbaue sagt mir das Generatorpolynom.

Nun möchte ich beispielsweise ein PRNG aus 20 Registern aufbauen, das 
mir alle Werte durchläuft (bzw. (2^20)-1 Werte).

Die Frage ist nun, wie komme ich an die Generatorpolynome, also an den 
Aufbau der Schieberegister, die die Forderung erfüllen.

Ziel ist es nicht, eine möglichst gute Folge an Zufallszahlen zu 
bekommen, sondern eine berechenbare Folge zu bekommen, deren Geheimnis 
der Aufbau des PRNG ist.

Grüße,
Christof

[Zacc (Gast)]

Siehe Appnote 110 oder so bei Xilinx.

[Detlef _. (detlef_a)]

110 ist die Polizei.

http://www.xilinx.com/support/documentation/application_notes/xapp210.pdf

Cheers
Detlef

[Tassilo B. (big_t)]

http://homepage.mac.com/afj/lfsr.html bzw.
http://homepage.mac.com/afj/taplist.html sollte helfen.

Tassilo

[ChrisV (Gast)]

Ha!

Perfekt. Danke für die links.

Grüße,
Christof

[ChrisV (Gast)]

Sooo...

eine Frage hätte ich da noch an die Kryptologen bzw. Mathematiker unter 
euch.

Angenommen ich bin Eve und höre mir einen Bitstrom an.
Weiterhin habe ich die Vermutung, dass dieser von einem PRNG generiert 
wird.

Wie lange muss ich zuhören um rauszubekommen wie der PRNG aussieht, 
sprich ab wann bin ich in der Lage die Folge selber zu berechnen.

Gruß Christof

[Jakob L. (jakob)]

Hallo,

bei einem 20 bit Schieberegister kann man durch Brute Force mit 
vertretbaren Aufwand alle möglichen Generatorpolynome (ca. 2^20 
Möglichkeiten) mit allen möglichen Anfangszustände ( ebenfalls 2^20 
Möglichkeiten ) ausprobieren. Der Aufwand ist insgesamt etwa 2^40. Auf 
einem PC dauert das je nach Implementierung wahrscheinlich nicht mehr 
als ein paar Stunden. Durch Vergleichen mit dem abgehörten Bitstrom kann 
man überprüfen, ob das Ergebnis stimmt. Um aus den 2^40 Möglichkeiten 
mit hoher Wahrscheinlichkeit die richtige Lösung auszuwählen, muss man 
nur wenig mehr als 40 bit abhören.

Wenn du etwas mehr Sicherheit willst und 256 Byte freien Ram hast, dann 
kannst du auch RC4 verwenden. Dieser Algorithmus ist bei korrekter 
Verwendung trotz der Einfachheit immer noch relativ sicher.

Gruss
Jakob

[Christoph db1uq K. (christoph_kessler)]

Hier ist auch eine Tabelle:
Beitrag "Zufallsgenerator"
http://www.mikrocontroller.net/attachment/13236/Pseudozufall.png

[ChrisV (Gast)]

>> Wenn du etwas mehr Sicherheit willst und 256 Byte freien Ram hast, dann
>> kannst du auch RC4 verwenden. Dieser Algorithmus ist bei korrekter
>> Verwendung trotz der Einfachheit immer noch relativ sicher.

Stimmt. Das wäre auch eine Möglichkeit. Ist die generierte Zufallsfolge 
bei RC4 denn zyklisch?

Hat für mich den Nachteil, dass ich dann noch eine Schlüsselaushandlung 
implementieren müsste. Das wird vermutlich zu viel Aufwand für meinen 
Zweck.

Auf jeden Fall danke für den Tip.

Gruß Chris

[Zacc (Gast)]

Der Aufwand steigt schnell an. Ich hab hier eine LFSR mit 32bit am 
Testen.
Eine Erweiterung auf 40, oder 48 bit waere schnell moeglich. Man muss 
sich fragen ob sich Leute mit Geheimdienst-Wissen, -Ausruestung (und 
-Vorgaben) mit einem Bootloader oder sonst einer embedded Uebertragung 
herumschlagen.

[Jakob L. (jakob)]

Hallo,

RC4 ist wie jeder andere PRNG natürlich zyklisch. Allerdings ist die 
Länge eines Zykluses so gross, dass man in der Praxis niemals einen 
kompletten Zyklus durchlaufen kann. Mit Schieberegistern grösserer Länge 
kann man den Aufwand für einen Brute-Force-Angriff natürlich enorm 
steigen. Allerdings ist Brute-Force bei so etwas nicht unbedingt der 
effektivste Angriff.

Gruss
Jakob

[ChrisV (Gast)]

>> Allerdings ist Brute-Force bei so etwas
>> nicht unbedingt der effektivste Angriff.

Sind denn (dir) da andere Angriffsmöglichkeiten bekannt?

[Zacc (Gast)]

Sehr effektiv ist der Differentialangriff, wenn man den denn machen 
kann. Der Beruht darauf, dann der angreifer, die zu verschluesselnden 
Daten aendern kann. Dann kann man untersuchen, welche Aenderung am 
Eingang zu welcher Aenderung am Ausgang fuehrt.
Sehr effektiv ist die Korrelation, dh den Vergleich mit Erwartetem. Wenn 
ich zB weiss, dass ein Brief immer mit 'Sehr geehrter ..' beginnt, oder 
dass ein Bootloader zuerst die Interrupt tabelle mit Jumps enthaelt, so 
schraenkt das den Coderaum stark ein.
Gibt noch weitere Methoden, je nach Randbedingungen.