Forum: Mikrocontroller und Digitale Elektronik Pseudozufall vorhersehbar?


von BernhardS (Gast)


Lesenswert?

Hallo!

Ich hab nun zwar schon einiges zu Pseudozufall gelesen, aber so ganz bin 
ich noch nicht dahintergestiegen.

Zur Anwendung: Es geht um eine Fernbedienung in einer Applikation 
mittlerer Sicherheitsstufe, sagen wir mal für eine Alarmanlage.

Sender und Empfänger besitzen einen AVR Mikrocontroller, in dem auf 
gleiche Weise Pseudozufallszahlen generiert werden, zum Beispiel über 
random() aus der avr-libc. Der Sender schickt nun also seine 
Pseudozufallszahl, und wenn diese Zahl im Empfänger mit dessen Zahl 
übereinstimmt, wird eine Aktion ausgeführt, die Sendung quittiert und 
beide errechnen fürs nächste mal eine neue Pseudozufallszahl.

Nun frage ich mich, wenn jemand mehrere Verbindungen mithört, inwiefern 
er aus den verwendeten Zahlen auf den Algorithmus schließen kann. Wenn 
zum Beispiel die random()-Funktion 32-Bit-Werte ausgibt, rechnet sie 
intern dann auch nur mit 32 Bit und nach 2^32 Zufallszahlen wiederholt 
sich die Reihe? Und kommt jede Zahl (oder eine Folge aus wenige Zahlen) 
darin nur einmal vor? In dem Fall bräuchte man ja nur mal den 
"Standard-Pseudozufallsgenerator" so lange laufen lassen, bis er bei der 
zuletzt gesendeten Zufallszahl angekommen ist und schon wüsste man die 
nächste - bei 2^32 dauerts nicht lange.

Kann mal jemand erklären, wie das wirklich läuft?
Danke, Bernhard.

von DeepCrack (Gast)


Lesenswert?

>bei 2^32 dauerts nicht lange

Einfaches hochzählen und ein XOR vielleicht, aber es gibt in der 
Kryptographie ja spezielle Einwegfunktionen, die durch hohe Rundenzahlen 
zudem noch sehr Rechenintensiv sind und extra so konstruiert wurden, 
dass es zumindest zum Zeitpunkt der Veröffentlichung keine allgemein 
bekannte Abkürzung gibt. Da benötigt man dann schon extrem schnelle und 
parallel arbeitende FPGAs, um so ein System durch systematisches 
Ausprobieren in vertretbarer Zeit zu knacken. Da FPGAs aber immer 
günstiger werden und dessen Programmierung so langsam auch für 
normalbegabte Menschen eine durchaus lösbare Aufgabe darstellt, werden 
diese "relativ" unsicheren Rollcodes vermutlich schon sehr bald der 
Vergangenheit angehören. Die neue Generation von 
Funkübertragungssystemen wird dann vermutlich AES-Verschlüsselte 
Kommunikation verwenden (HomeMatic von ELV verwendet das laut Katalog 
bereits).

von Micha (Gast)


Lesenswert?

>> Wenn zum Beispiel die random()-Funktion 32-Bit-Werte ausgibt, rechnet sie
>> intern dann auch nur mit 32 Bit und nach 2^32 Zufallszahlen wiederholt
>> sich die Reihe? Und kommt jede Zahl (oder eine Folge aus wenige Zahlen)
>> darin nur einmal vor? In dem Fall bräuchte man ja nur mal den
>> "Standard-Pseudozufallsgenerator" so lange laufen lassen, bis er bei der
>> zuletzt gesendeten Zufallszahl angekommen ist und schon wüsste man die
>> nächste - bei 2^32 dauerts nicht lange.

Erst mal sind Pseudozufallszahlen absolut berechenbar, ja sogar bei 
Kenntniss des Generators und dessen Start-Bedingung absolut 
reproduzierbar. Allerdings hat die erstellte Zahlenfolge eben 
Zufalls-Charakter, d.h. die Frequenz eines Ergebnisses sollte der 
zugrundeliegenden Zufallsverteilung entsprechen (damit kann eine Zahl 
mehrmals vorkommen), aber es sollte nicht vorhersagbar sein, welche Zahl 
als nächstes dran ist. Irgendwann wiederholt sich die generierte 
Zahlenfolge. Die Länge wird IMHO Periodizität des Generators genannt. 
Die Güte (Vorhersagbarkeit, Periodizität) der generierten Zahlenfolge 
-besser Bitfolge) ist dabei stark vom verwendeten Generator und dessen 
Ausgangsbedingungen abhängig. Hier weitere Lesesstoff.
Du kannst Dir auch mal das entsprechende Kapitel in "Numerical Recipies" 
oder bei Sedwick (oder Knuth) durchlesen, wenn Du das Buch in einer 
(Uni-)-Bib ausleihst.

http://de.wikipedia.org/wiki/Pseudozufallszahl
http://de.wikipedia.org/wiki/Zufallsgenerator

Wenn Du soetwas realisieren möchtest, ist die Wahrscheinlichkeit dass 
jemand durch mithören/protokollieren deinen Code knackt umso besser, je 
mehr er über Dein System weis. Daher solltest Du überlegen, nicht den 
Standard-Generator zu nehmen. Das hat bei einem Wechsel des Compilers 
(kann auch schon Versionswechsel sein!) oder des Systems den Vorteil, 
dass alle Komponenten immer noch miteinander reden können :-)

von None (Gast)


Lesenswert?

Es gibt solch Pseudozufallszahlen und andere. Betrachten wir ein 
Ruckgekoppeltes Schieberegister. Das hat eine definierte Zykluslaenge 
und ist in Hardware realisierbar. Dann gibt es die mathematischen 
Pseudozufallszahlengeneratoren, die ueblicherweise float benoetigen. Der 
Repetierbarkeit ist gegeben, aber die Periode ist nicht so streng 
definiert. Und in Hardware sind die nicht baubar.
Fuer deinen Anwendungszweck scheint mit ein rueckgekoppeltes 
Schieberegister besser geeingnet, da es schneller gerechnet ist. Es gibt 
solche mit Perioden ueber 32 bit.

von Winfried (Gast)


Lesenswert?

Es ist grundsätzlich ein beliebter Fehler, Sicherheit durch 
verheimlichen von Algorithmen zu erreichen. Eine Methode sollte vielmehr 
auch dann sicher bleiben, wenn der Algorithmus vollständig bekannt ist. 
Mehr dazu findet man bei Bruce Schneier (http://www.schneier.com/)

von Michael W. (wiebel42)


Lesenswert?

könnte man nicht einfach einen ADC an einen sehr hochohmigen 
Sannungsteiler (>10 MOhm) hängen und das "echt" zufällige 
Widerstandsrauschen noch mit einarbeiten, dan ist es Essig mit 
vorhersagbarkeit jeder Form. Nur so als Idee. -wiebel

von AVRFan (Gast)


Lesenswert?

>Da FPGAs aber immer
>günstiger werden und dessen Programmierung so langsam auch für
>normalbegabte Menschen eine durchaus lösbare Aufgabe darstellt, werden
>diese "relativ" unsicheren Rollcodes vermutlich schon sehr bald der
>Vergangenheit angehören.

Ich denke nicht, denn um die Sicherheit der Rollcodes zu gewährleisten, 
reicht es ja aus, einfach die Schlüssel länger zu machen.

von Andreas S. (andreas) (Admin) Benutzerseite


Lesenswert?

Bei der random()-Funktion der avr-libc ist es trivial die Folge 
nachzubilden, weil die Zufallszahl dem Zustand des Generators 
entspricht. Man kann natürlich die Zahl vor dem Verschicken mit einem 
Sender und Empfänger bekannten Geheimnis verXORen o.ä., aber da kommt 
man schnell in Bereiche wo man nur noch nach Gefühl rumbastelt ohne zu 
wissen ob es wirklich etwas bringt. Eine bessere Lösung für deinen Fall 
wäre eine Hash-Funktion wie MD5: der Sender schickt eine Nachricht, eine 
Sequenznummer und eine Signatur die durch hash(nachricht + passwort + 
sequenznummer) erzeugt wird. Der Empfänger überprüft die Signatur indem 
er selber hash(nachricht + passwort + sequenznummer) berechnet und mit 
der empfangenen Signatur vergleicht. Die Sequenznummer wird nach 
erfolgreicher Bestätigung von Sender und Empfänger erhöht, um zu 
verhindern dass ein Angreifer einfach eine Übertragung ("Alarmanlage 
deaktivieren") inkl. Signatur aufzeichnen und nochmal neu senden kann.

von Karl (Gast)


Lesenswert?

@Wiebel: Dann ist es aber so zufällig, dass die Gegenstelle immer andere 
Zahlen hat...

von Michael G. (linuxgeek) Benutzerseite


Lesenswert?

Ein Sicherheitsthread... cool ;)

> Zur Anwendung: Es geht um eine Fernbedienung in einer Applikation
> mittlerer Sicherheitsstufe, sagen wir mal für eine Alarmanlage.

Na das is ja mal ne Aussage :D Soll es nun sicher sein oder nicht?

> Der Empfänger überprüft die Signatur indem
> er selber hash(nachricht + passwort + sequenznummer) berechnet und mit
> der empfangenen Signatur vergleicht.

Ja Andreas... tolle Sache, nur dass man die gesendete Signatur korrekt 
mitfaelschen kann so dass dieser Ansatz leider garnichts bringt ;) Und 
schon garnicht mit MD5, das ohnehin als gebrochen gilt.

Edit: OK Du bringst da noch ein Geheimnis ein... das macht die Sache 
zwar schon leicht besser aber nicht wirklich sicher, da auch nur 
security by obscurity... und wie gesagt MD5 ist gebrochen so dass sich 
hier eindeutig SHA, besser noch SHA2 empfiehlt.

> Es ist grundsätzlich ein beliebter Fehler, Sicherheit durch
> verheimlichen von Algorithmen zu erreichen.

Security by Obscurity heisst das Prizip ;) Schaust Du mal noch 
"Kerckhoff principle"...

Und noch ein Thema zu Zufallszahlen: Einfache, periodische 
Zufallsgeneratoren sind fuer kryptographische Zwecke vollkommen 
ungegeignet, da sie ja mit Zufall nichts zu tun haben.

Gruesse,
Michael

von der mechatroniker (Gast)


Lesenswert?

Du brauchst kurz gesagt einen Pseudozufallsgenerator, dessen Folge sich 
genau dann reproduzieren läßt, wenn dem Empfänger ein geheimer Schlüssel 
bekannt ist. Das hört sich ziemlich exakt nach diesem hier an:

http://de.wikipedia.org/wiki/Blum-Blum-Shub-Generator

von Michael G. (linuxgeek) Benutzerseite


Lesenswert?

Da ist wohl eher die Rede von einem Seed... den Seed koennte man z.B. 
aus einem Geheimnis berechnen.

Das grundsaetzliche Problem bei solchen Ansaetzen ist doch: Wie haelt 
man das Geheimnis auch geheim? Es auf dem Controller irgendwo abzulegen 
bzw. es im Programmcode zu "verstecken" ist nen dumpfsinniger Ansatz, 
siehe Blue-Ray-Disc, geknackt noch bevor das Medium auf dem Markt war. 
Und warum? Weil da ein symmetrischer Chiffre vollkommen falsch 
angewendet wurde...

> Nun frage ich mich, wenn jemand mehrere Verbindungen mithört, inwiefern
> er aus den verwendeten Zahlen auf den Algorithmus schließen kann. Wenn
> zum Beispiel die random()-Funktion 32-Bit-Werte ausgibt, rechnet sie
> intern dann auch nur mit 32 Bit und nach 2^32 Zufallszahlen wiederholt
> sich die Reihe?

Du musst davon ausgehen, dass solche Pseudozufallsreihen sehr leicht 
bestimmbar sind wenn man die Grundstrukturen kennt. Mit anderen Worten: 
nicht sicher und ferner bekannt.

Michael

von Andreas S. (andreas) (Admin) Benutzerseite


Lesenswert?

Michael G. wrote:
>> Zur Anwendung: Es geht um eine Fernbedienung in einer Applikation
>> mittlerer Sicherheitsstufe, sagen wir mal für eine Alarmanlage.
>
> Na das is ja mal ne Aussage :D Soll es nun sicher sein oder nicht?

Absolute Sicherheit gibt es nicht, man muss immer einen Kompromiss 
zwischen Bequemlichkeit (hier Lern- und Implementierungsaufwand) und 
Sicherheit eingehen.

>> Der Empfänger überprüft die Signatur indem
>> er selber hash(nachricht + passwort + sequenznummer) berechnet und mit
>> der empfangenen Signatur vergleicht.
>
> Ja Andreas... tolle Sache, nur dass man die gesendete Signatur korrekt
> mitfaelschen kann so dass dieser Ansatz leider garnichts bringt ;) Und
> schon garnicht mit MD5, das ohnehin als gebrochen gilt.
>
> Edit: OK Du bringst da noch ein Geheimnis ein...

"Auch noch" ist gut, das ist das zentrale Element.

> das macht die Sache zwar schon leicht besser aber nicht wirklich sicher,
> da auch nur security by obscurity...

Das ist gängige Praxis und wird als HMAC u.a. bei IPSEC verwendet, ein 
wenig modifiziert um extension attacks zu verhindern (die bei fester 
Nachrichtenlänge aber keine Rolle spielen). Siehe z.B. 
http://web.cecs.pdx.edu/~teshrim/spring06/slides/hmac-slides.pdf.

> und wie gesagt MD5 ist gebrochen so dass sich
> hier eindeutig SHA, besser noch SHA2 empfiehlt.

Bei der Länge der Nachrichten um die es hier geht ist es extrem 
unwahrscheinlich dass jemand eine gültige Nachricht der gleichen Länge 
findet die den gleichen Hash ergibt. Trotzdem wäre eine der neueren 
SHA-Versionen natürlich besser.

von BernhardS (Gast)


Lesenswert?

Hallo und vielen Dank für die rege Diskussion!


Michael G.:

>> Zur Anwendung: Es geht um eine Fernbedienung in einer Applikation
>> mittlerer Sicherheitsstufe, sagen wir mal für eine Alarmanlage.

> Na das is ja mal ne Aussage :D Soll es nun sicher sein oder nicht?

Es ist weder für ein Hochsicherheitsgefängnis noch für ne Bank, und es 
wird auch nicht millionenfach verkauft, daß irgendjemand einen Sender 
oder Empfänger analysieren könnte. Es wird genau ein Exemplar der Anlage 
geben: Meins.

Insofern ist der Kreis potentieller Angreifer sicher überschaubar. Nur 
wenn ein paar Zeilen Code das System noch deutlich sicherer machen 
können als es sonst wäre, warum dann nicht?


Winfried:

> Es ist grundsätzlich ein beliebter Fehler, Sicherheit durch
> verheimlichen von Algorithmen zu erreichen. Eine Methode sollte vielmehr
> auch dann sicher bleiben, wenn der Algorithmus vollständig bekannt ist.

Dies trifft zu, sofern jemand Zugriff auf den Algorithmus bekommen 
könnte, beispielsweise weil Geräte oder Software in der Welt kursieren. 
Im Fall eines einzelnen Systems ist das aber irrelevant, der Algorithmus 
bleibt dem Angreifer so unerreichbar wie der Schlüssel.


Micha:

> Erst mal sind Pseudozufallszahlen absolut berechenbar, ja sogar bei
> Kenntniss des Generators und dessen Start-Bedingung absolut
> reproduzierbar.

Das müssen sie auch sein, damit der Sender und Empfänger die gleiche 
Zahl sendet/erwartet.

> Allerdings hat die erstellte Zahlenfolge eben
> Zufalls-Charakter, d.h. die Frequenz eines Ergebnisses sollte der
> zugrundeliegenden Zufallsverteilung entsprechen (damit kann eine Zahl
> mehrmals vorkommen)

Ich habe schon darüber nachgedacht, von den z.B. 32 Bit einer 
Pseudozufallszahl nur z.B. 24 zu benutzen, damit jede Zahl in diesem 
Fall mindestens 256 mal vorkommt bis sich die Reihe wiederholt. Die 
Periodizität wird dadurch zwar nicht länger, aber verschleiert.

> http://de.wikipedia.org/wiki/Pseudozufallszahl
> http://de.wikipedia.org/wiki/Zufallsgenerator

Leider sehr theoretisch...

> Wenn Du soetwas realisieren möchtest, ist die Wahrscheinlichkeit dass
> jemand durch mithören/protokollieren deinen Code knackt umso besser, je
> mehr er über Dein System weis. Daher solltest Du überlegen, nicht den
> Standard-Generator zu nehmen. Das hat bei einem Wechsel des Compilers
> (kann auch schon Versionswechsel sein!) oder des Systems den Vorteil,
> dass alle Komponenten immer noch miteinander reden können :-)

Ja, und es hat noch einen entscheidenden Vorteil: Der vom Compiler kann 
nur eine Pseudozufallsreihe gleichzeitig. Benutze ich mehrere Sender, 
brauche ich mehrere unabhängige Generatoren im Empfänger, da ich nicht 
davon ausgehen kann, daß alle Sender mitbekommen, wenn eine Zahl 
"verbraucht" wurde. Also muss ich die wohl selbst programmieren.
Stattdessen überall die gleiche Reihe zu benutzen und den Sender an der 
Stelle so lange nochmal alle inzwischen "verbrauchten" senden zu lassen, 
bis die "neue" kommt, auf die der Empfänger eigentlich wartet, 
vereinfacht nur das Abhören.


Andreas Schwarz:

> Bei der random()-Funktion der avr-libc ist es trivial die Folge
> nachzubilden, weil die Zufallszahl dem Zustand des Generators
> entspricht.

Das hieße dann, daß die Periodizität ebenfalls auf 2^31 (da random nur 
positive Zahlen aus signed long benutzt) begrenzt ist und jeder Wert nur 
einmal vorkommt. Damit fällt diese Lösung endgültig aus.


DeepCrack:

> es gibt in der
> Kryptographie ja spezielle Einwegfunktionen, die durch hohe Rundenzahlen
> zudem noch sehr Rechenintensiv sind und extra so konstruiert wurden,
> dass es zumindest zum Zeitpunkt der Veröffentlichung keine allgemein
> bekannte Abkürzung gibt.

Gibts da passende google-Stichwörter?


None:

> Fuer deinen Anwendungszweck scheint mit ein rueckgekoppeltes
> Schieberegister besser geeingnet, da es schneller gerechnet ist. Es gibt
> solche mit Perioden ueber 32 bit.

Laut wikipedia gibts die maximale Periode mit 2^n bei n Stufen nur mit 
"geeigneter Wahl" der Rückkopplung. Ist bei willkürlicher Wahl die 
"geeignete" eher Regel oder Ausnahme?


der mechatroniker:

> Du brauchst kurz gesagt einen Pseudozufallsgenerator, dessen Folge sich
> genau dann reproduzieren läßt, wenn dem Empfänger ein geheimer Schlüssel
> bekannt ist. Das hört sich ziemlich exakt nach diesem hier an:
> http://de.wikipedia.org/wiki/Blum-Blum-Shub-Generator

Oh.. Ob ich im Mikrocontroller mit 200 Dezimalstellen rechnen will?

Nochmals vielen Dank,
Bernhard.

von madler (Gast)


Lesenswert?

Ich denke Du suchst sowas wie das : 
http://de.wikipedia.org/wiki/Einmalkennwort#Verwendete_Technik_in_den_meisten_Generatoren
Also prinzipiell geht es darum aus einem geheimen Passwort und einer 
Anfrage des Senders eine gültige Antwort zu erzeugen. Dazu wird die 
Anfrage mit dem geheimen Passwort kombiniert und dann zu einer 
eindeutigen Prüfsumme berechnet (damit man das Passwort nicht ermitteln 
kann).
Gut wäre dafür zB MD5, aber vielleicht reicht für Deine Anwendung ja 
auch etwas simpleres ? Vielleicht MD4 ? CRC32 ?

von Andreas S. (andreas) (Admin) Benutzerseite


Lesenswert?

Wie das geht hab ich oben schon beschrieben (Stichwort HMAC). Fertiger 
Code:
HMAC-SHA256: Beitrag "Crypto avr lib (diverse Kryptographie Algorithmen)"
HMAC-SHA1: Beitrag "SHA-1 und HMAC-SHA-1 in C für uC (GPL)"

Bitte 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
Noch kein Account? Hier anmelden.