@virtus:
Die von dir vorgeschlagene Konstruktion (OTP+PRG) nennt sich "
Stream Cipher". Dabei wird, wie du korrekt beschrieben hast, ein Zufallszahlen-Generator (Pseudorandom Generator = PRG [oder PRNG]) verwendet, dessen Ausgabe mit den eigentlichen Daten ver-xor-t wird (analog zum One-Time-Pad). "Schlüssel" ist dabei der Seed des PRG, also die Zahlenfolge, mit der der Generator initialisiert wird. Bei gleicher Initialisierung gibt der Generator immer die gleichen Zufallszahlen zurück.
In der Praxis werden Stream-Cipher nicht mehr oft verwendet, da sie eben nicht die Sicherheit bieten, die ein (korrekt eingesetzter) Blockcipher bietet. RC4 ist ein Beispiel für einen ehemals populären Streamcipher, der bspw. in der WEP / WPA1-Verschlüsselung für WLANs eingesetzt wurde. Auch wenn die Konstruktion auf dem OTP basiert, bietet sie durch den PRG eben nicht die gleiche Sicherheit.
Das Hauptproblem einer Konstruktion wie oben beschrieben ist, dass jeder Schlüssel nur ein einziges Mal benutzt werden sollte. Außerdem kann ein Mitleser Abhängigkeiten zwischen den einzelnen Nachrichten feststellen (damit gilt der Algorithmus schon als "gebrochen"), und je nach Zweck auch Nachrichten direkt entschlüsseln (damit ist der Algorithmus auch praktisch gebrochen). Das wurde in der Praxis umgangen, indem man einen Initialisierungsvektor (IV) eingeführt hat, der bei jeder Benutzung zufällig gewählt und mit übertragen wurde. Geht aber spätestens dann in die Hose, wenn man einen durchschnittlichen Programmierer das implementieren lässt.
Stream Cipher bieten gegenüber Brute-Force jedoch nicht mehr Sicherheit, als die gängigen Blockcipher. Die Fachliteratur unterscheidet da zwischen "computational security" (=sicher unter der Annahme, dass die Rechenleistung realistisch bleibt) und "information-theoretical security" (=sicher unabhängig von der Rechenleistung eines Angreifers).
Den Grund, warum die Konstruktion mit PRG durch Brute-Force angreifbar ist, hat Metal_Warrior schon beschrieben.
Beispiel:
Crypto-Algorithmen betrachtet man immer unter Worst-Case-Bedingungen, da sie ja auch für jeden Anwendungszweck funktionieren müssen. Der schlimmste Fall ist wohl: Es gibt nur zwei mögliche Nachrichten (m1 und m2), ein Angreifer muss also nur zwischen beiden unterscheiden. Beispiel: Die Antwort ist entweder "Ja" oder "Nein". [*]
Unser Beispiel-PRG ist RC4 und nimmt 48bit-Seeds als Eingabe, unsere Nachrichten sind 256 bit lang.
OTP:
Im OTP ist auch jeder mögliche Schlüssel genau 256 bits lang. Sieht ein Angreifer nun eine verschlüsselte Nachricht c, dann weiß er:
- m1 wäre eine mögliche Nachricht, dann wäre der Schlüssel k = c xor m1 .
- m2 wäre eine mögliche Nachricht, dann wäre der Schlüssel k = c xor m2 . Der Ciphertext kann also zu beiden Nachrichten gehören, selbst durch Ausprobieren aller Schlüssel kann der Angreifer nichts Näheres dazu sagen (da es eben für jede andere mögliche Nachricht einen möglichen Schlüssel gibt). Unabhängig vom Rechenpower wäre die Konstruktion in dieser Situation also sicher.
OTP + PRG
Angenommen die Nachricht ist m1. Der Angreifer bekommt also c = m1 xor RC4(k) . Anstatt (wie beim OTP) alle möglichen Ausgaben von RC4() auszuprobieren, kann der Angreifer jetzt direkt alle Schlüssel durchprobieren.
- Dabei wird er sicher auf k stoßen, sodass c xor RC4(k) = m1. Er weiß also, dass m1 möglich ist.
- RC4() hat 2^48 mögliche Eingaben, nämlich alle 48-bit-Folgen. Daher gibt es auch nur 2^48 mögliche Ausgaben, die aber jeweils 256 bits lang sind. D.h. die Mehrheit der möglichen Zufallsfolgen kann von dem Generator gar nicht generiert worden sein (so viele verschiedene Eingaben gibt es nicht). In diesem Fall besteht die Wahrscheinlichkeit von 2^48 / 2^256 = 1 / 2^208 , dass das System zu m2 entschlüsselt (also die richtige Zufallsfolge dafür getroffen wird). Das ist verdammt unwahrscheinlich.
Genug Rechenpower vorausgesetzt, kann eine solche Stream-Cipher-Verschlüsselung also geknackt werden. Nur unter der Annahme, dass nicht genug Leistung zur Verfügung steht, kann das System als sicher gelten.
Tatsächlich gibt es dazu auch einen Satz, der besagt, dass eine Verschlüsselung nur dann sicher gegen Brute-force sein kann (=information-theoretical secure), wenn |K| >= |M|, es also mindestens so viele mögliche Schlüssel wie mögliche Nachrichten gibt. Daraus folgt, das ein Schlüssel auch mindestens so lang sein muss, wie die entsprechende Nachricht. Für einen Beweis verweise ich an entsprechende Literatur.
Gruß
Rakorium
[*] Tatsächlich nimmt man meist noch viel härtere Annahmen (z.B. eine "Choosen Plaintext Attack"). Dabei macht auch das OTP keine gute Figur mehr.
, aber nicht zwangsweise f(x) = f