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.
>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).
>> 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/Pseudozufallszahlhttp://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 :-)
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.
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/)
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
>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.
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.
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
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
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
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.
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.
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 ?
