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/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 :-)
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.
@Wiebel: Dann ist es aber so zufällig, dass die Gegenstelle immer andere Zahlen hat...
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 ?
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
Mit Google-Account einloggen
Noch kein Account? Hier anmelden.