Der One-Time-Pad ist nicht sicher!
Immer wieder liest man – selbst von den “besten” Kryptologen – daß der One-Time-Pad die informationstheoretisch beweisbar sichere und unbrechbare Chiffre sei. Das stimmt so nicht. Von Mythen, Legenden und dem Nachplappern in der Kryptographie…
Der One-Time-Pad kann unter gewissen Voraussetzungen eine solche sichere Verschlüsselung sein. Diese Voraussetzungen werden in der Regel aber nicht erfüllt, nicht genannt und auch nicht erkannt.
Ein einführendes Beispiel:
Eine Chiffre gilt als informationstheoretisch sicher, unbrechbar (und was da im Einzelfall immer aufgeführt wird) wenn der Angreifer in Kenntnis des Chiffrats und mit unbegrenzter Rechenleistung überhaupts nichts über den Klartext in Erfahrung bringen kann, also nicht einmal sagen kann, ob ein Klartext wahrscheinlicher ist als ein anderer. Der Angreifer darf in Kenntnis des Chiffrats nicht mehr über den Klartext wissen, als wenn er das Chiffrat nicht kennt.
Nehmen wir an, wir suchen verschlüsselte Nachrichten, die unerlaubte Inhalte enthalten, beispielsweise eine Raubkopie eines Kinofilms. Nun fangen wir eine One-Time-Pad-Verschlüsselte Nachricht der Länge 5 Bit auf. Nun kann man auch ohne große Rechenleistung sagen, daß diese Nachricht jedenfalls nicht die gesuchten Daten enthalten kann – oder es jedenfalls sehr unwahrscheinlich ist. Was soll daran informationstheoretisch sicher sein?
Das genaue Problem ist, daß der One-Time-Pad nicht die Länge der Nachricht verbirgt, das Chiffrat ist so lang wie der Klartext. Und damit weiß man – ohne irgendetwas zu entschlüsseln – sehr viel über den Klartext.
Und das Problem ist auch nicht ohne weiteres zu lösen. Betrachtet man nämlich über der Menge aller Nachrichten K beliebiger Länge aus einem Alphabet die Abbildungen, die K x K -> K abbilden (wozu eben auch Chiffren gehören), dann gibt es keine solche Abbildung, deren Projektion auf die Eingangswerte gleichverteilt ist. Anders gesagt: Für Nachrichten variabler Länge kann es keine Abbildung, also auch keine Chiffre geben, die die Länge verbirgt. Es geht nicht.
Andererseits gibt es solche Abbildungen für zwei bestimmte Nachrichtentypen:
- Ist die Nachrichtenmenge der möglichen Klartexte endlich, haben also alle Klartexte effektiv dieselbe Länge, dann ist es möglich, weil die Länge des Chiffrats dann nichts mehr darüber sagt, welcher Klartext möglich ist. Die Lotto-Zahlen der nächsten Woche oder meinen Kontostand kann ich damit also verschlüsseln.
- Sind alle Nachrichten unendlich lang und die Menge der Nachrichten daher überabzahlbar unendlich, dann geht’s auch wieder.
Und der One-Time-Pad taugt offensichtlich für diese beiden Nachrichtentypen.
Will man also “normale” Nachrichten, also irgendwelche Daten beliebiger Länge, informationssicher verschlüsseln, dann muß man sie zunächst in einen Nachrichtentyp konvertieren, für den solche Abbildungen existieren können.
Kann man das (Beispiel Lotto-Zahlen, Geburtsdatum, Telefonnummer), dann kann man den ersten Typ verwenden und ein Format fester Breite vorgeben. Dann baut man im Prinzip ein (2,2)-Shared-Secret-Schema aus Schlüssel und Chiffrat.
Kann man das nicht, was in der Regel der Fall ist, bleibt einem nichts anderes übrig, als die endliche Nachricht durch “Stopfen” (d.h. Versehen mit Escape- und Stop-Zeichen) in eine unendliche Zeichenfolge zu verpacken. (Über solche Stopfverfahren gibt es sogar irgendein Paper, find ich aber gerade nicht, ist aber auch nicht schwer, in der Telematik werden solche Verfahren auch verwendet). Dann kann ich sie mit dem One-Time-Pad sicher verschlüsseln.
Das letztere Verfahren hat natürlich einen Haken: Wenn ich einmal angefangen habe zu senden, darf ich nie wieder damit aufhören und muß bis in alle Ewigkeit weitersenden. Nur so ist gewährleistet, daß der Angreifer nichts über die Länge der Nachricht in Erfahrung bringen kann. Oder jedenfalls nichts, solange ich lebe, und danach ist es mir eh wurscht.
Zeigt aber mal wieder, wie gerne in der Wissenschaft nachgeplappert und abgeschrieben wird. Zumindest aus dem Stehgreif fällt mir gerade kein Buch ein, in dem das korrekt dargestellt würde. Bücher, Papers, Vorlesungen und so Zeugs, in denen das falsch behauptet wird, hab ich aber schon oft gesehen.
Man soll halt nicht alles glauben, was (selbst- oder vom Wissenschaftsministerium ernannte) Kryptologen so schreiben… Beware of Snake Oil.
Nachtrag (weil jemand gefragt hat): Auch wenn ich das etwas flapsig formuliert habe, hat meine Aussage einen harten informationstheoretischen Hintergrund: Es gibt keine “perfekte” oder “informationstheroetisch sichere” Verschlüsselung (bei der also ein Angreifer mit unbegrenzter Rechenleistung in Kenntnis des Chiffrats nicht mehr über den Klartext weiß als ohne Kenntnis des Chiffrats) für Nachrichten variabler Länge, weil es nicht möglich ist, die Länge des Klartextes völlig zu verbergen. Der Angreifer kann in jedem Fall Rückschlüsse auf die Länge des Klartextes treffen und damit sehen, daß aus der Menge aller Klartexte die mit entsprechender Länge wahrscheinlicher sind als die mit anderer Länge.
Erst dann, wenn entweder alle möglichen Klartexte dieselbe Länge haben (und damit der Nachrichtenraum endliche Größe hat) oder die Nachrichten alle unendlich lang und die Menge der Nachrichten überabzählbar sind, kann der Angreifer aus der Länge des Chiffrats keine Wahrscheinlichkeiten für den Klartext mehr ableiten.
Wer sich für die Theorie interessiert, möge dazu das Paper Benny Chor, Eyal Kushilevitz: Secret Sharing Over Infinite Domains, Crypto 89, Seite 299, lesen, in dem bewiesen wird, daß es über dem kartesischen Produkt zweier abzählbar unendlicher Mengen keine Wahrscheinlichkeitsverteilung gibt, die in den Projektionen auf die Eingabewerte gleichverteilt ist. Das Beispiel mit den 5-Bit-Nachrichten von oben war halt nur mal wieder in meinem Stil etwas überflapsig ausgedrückt um den Kern der Aussage auch für die darzustellen und zu plausibilisieren, die das nicht vorher studiert haben.
Chor und Kushilevitz beweisen, daß es allgemein keine Shared-Secret-Schemas für aufzählbare Klartext- und Chiffrat-Mengen und deshalb auch keine perfekte symmetrische Verschlüsselung für Nachrichten beliebiger Länge existiert.
Mein 5-Bit gegen Raubkopie-Beispiel sollte einfach den Gedankengang dahinter allgemeinverständlich und Blog-tauglich ausdrücken.
Obwohl eigentlich schon 1989 bewiesen und veröffentlicht wurde, daß das so nicht geht, hält sich die Behauptung, daß der One-Time-Pad allgemein beweisbar perfekt sicher sei, noch heute, fast 20 Jahre später.
Zu fachlichen Diskussionen bin ich – im Rahmen meiner Zeit – immer gerne aufgelegt. 🙂
Nachtrag 2: Da bin ich mal im Rahmen meines Promotionsstreites mit der Universität Karlsruhe bzw. dem Prüfer Beth drauf gestoßen. Der hatte nämlich gerügt, daß ich in ein neues Verschlüsselungsverfahren keine probabilistische Abbildung eingebaut habe. Ein anderer Professor als Sachverständiger hatte Beths Behauptung ungeprüft bestätigt. Ich hatte mit diesem o.g. Paper nachgewiesen, daß es eine solche Erweiterung, wie sie von mir als unbedingt notwendig verlangt und deren Fehlen in meinem Verfahren als Ablehnungsgrund für eine Dissertation herangezogen wurde, mathematisch nicht geben kann. Die Universität Karlsruhe hatte einfach willkürliche Forderungen als Vorwand für eine Bewertung aufgestellt, die mathematisch unerfüllbar sind. Und bei der Recherche dazu bin ich auf dieses Paper gestoßen, zu dem sich die Karlsruher Fakultät nicht erklären konnte. Sie sagte, sie habe keinen sachkundigen Professor und stellt lieber weiterhin die Behauptung auf, der One-Time-Pad sei eine beweisbar perfekt sichere Verschlüsselung. Da stecken auch wirtschaftliche Interessen dahinter.
24 Kommentare (RSS-Feed)
Nein, da hast Du was falsch verstanden.
Für Nachrichten beliebiger, endlicher aber unbegrenzter Länge (also prinzipiell das, womit wir hier so allgemein arbeiten) gibt es keine Verschlüsselung, die das leistet, was man als “perfekt” oder “informationstheoretisch sicher” bezeichnet, daß also P(p)=P(p|c) ist. Und weil es allgemein eine solche Verschlüsselung nicht gibt, kann es der One-Time-Pad auch nicht sein. Ich finde aber, daß man es auch mit einem einfachen, drastischen Beispiel gut plausibel machen kann.
Dann, wenn die Menge der möglichen Klartexte aufzählbar ist, also letztlich endliche aber in der Länge unbegrenzte Nachrichten (z. B. 0,1,00,01,10,11,000,…) dann gibt es keine perfekte Verschlüsselung.
Nur dann, wenn man die Nachrichtenmenge von vornherein auf eine endliche Nachrichtenmenge und damit effektiv auf Nachrichten einer festen Länge eingrenzt, oder aber dann, wenn alle Nachrichten unendlich lang sind, ist der One-Time-Pad auch informationstheoretisch sicher, d.h. der Angreifer kann keine Rückschlüsse auf die Länge des Klartextes ziehen und damit wahrscheinlichere Nachrichten erkennen.
Ja eben. Der Unterschied liegt hier in der Definition der verwendeten Alphabete fuer p und c.
Meine Argumentation ist, dass es unsinnig ist, unendlich lange Nachrichten mit in das Alphabet aufzunehmen, *weil* es dann keinen Algorithmus gibt, der die Definition von inf.theor. Sicherheit erfuellt.
Eine nachweisbar unerfuellbare Definition ist sinnlos.
(der zusammenhang zu probabilistischer Verschl. ist mir auch nicht ganz klar. Ich wuerde behaupten dass der OTP nicht-prob. ist, denn selber key+text gibt immer den selben cipher. gerade daher will man nie den selben key benutzen…)
Nein, das hast Du immer noch nicht verstanden. Lies es Dir erst mal in Ruhe durch, bevor Du dagegen wetterst.
Außerdem verwechselst Du das was mit den Alphabeten.
Die Alphabete werden hier in jedem Fall als endlich angenommen, meist redet man sogar von |A|=2, z. B. {0,1}. Die Klartexte, Chiffrate und Schlüssel stammen dabei aber nicht aus A, sondern aus AN, wobei N die natürlichen Zahlen sind. Überleg Dir auch mal den Unterschied zwischen unendlich langen und endlichen aber unbegrenzten Nachrichten. Weißt Du, was aufzählbar bedeutet?
Der zweite Punkt ist, daß Deine Argumentation falsch ist. Es ist doch durchaus möglich, auch in der Mathematik nicht selten, daß man eine Anforderung definiert, die einem nützlich erscheint, und sodann erkennt und nachweist, daß es nichts gibt, was die Anforderung erfüllt. Manchmal verwendet man die Definition auch nur zur Diskussions oder zur Erkenntnis, daß etwas nicht geht. Die Definition löst sich aber doch nicht selbst auf wenn jemand beweist, daß sie nicht erfüllbar ist.
Willst Du etwa argumentieren, daß der One-Time-Pad allein deshalb schon sicher sein muß, weil sonst die Definition für perfekte Sicherheit nicht erfüllbar ist? Das ist doch Unsinn. Bloß weil die Definition in Deinen Augen “sinnlos” ist, kannst Du doch nicht einfach irgendwas als zwangs-sicher erklären.
Nach Deiner Logik dürfte es auch rationale Zahlen nicht geben, weil man sie nicht explizit hinschreiben kann, ohne unendlich lange zu schreiben. Und, gibt es rationale Zahlen?
Außerdem ist die Definition nicht unsinnig. Es ist eine sehr wichtige Definition zur Diskussion von kryptographischen Sicherheitsanforderungen.
Und in der Kodierungstheorie betrachtet man durchaus oft auch unendlich lange Zeichenfolgen. Quellen sind normalerweise so definiert, daß sie eine unendlich lange Zeichenfolge ausgeben. Und auch viele Erkenntnisse, etwa der Satz von Shannon oder die Shannon-Codierung beruhen auf der Annahme, daß die Quelle unendlich viele Zeichen ausspuckt.
Davon abgesehen ist die Anforderungen auch nicht unerfüllbar: Wenn die Klartextmenge endlich und damit die Nachrichten gleich lang sind, dann ist der One-Time-Pad sicher. Deshalb kann man ja auch ein Shared-Secret-Schema bauen. Das geht. Oder Coin-Flipping.
Nur wenn man, wie im Internet so üblich, Nachrichten ohne definierte Längenbegrenzung betrachtet, dann funktioniert der One-Time-Pad nicht mehr als perfekt sicher.
Natürlich könnte man argumentieren, daß auch die Nachrichten im Internet “endlich” sind, weil wir mit den Atomen auf der Erde nur begrenzt Informationen darstellen können, und in der Zeit des Universums oder eine Menschenslebens auch nur begrenzt Informationen übertragen können, womit eine natürliche obere Schranke existiert. Selbst wenn man an diese obere Schranke glaubt, müßte man alle Nachrichten auf deren Länge normalisieren, um perfekt sicher zu sein. Und wenn man diese obere Schranke für den Klartext ausnutzt: Wo will man dann Schlüssel und das Chiffrat noch unterbringen?
Die Konsequenz ist, daß man sich nicht, wie fast alles in der Kryptographie es tun, hinstellen und pauschal behaupten kann, der OTP wäre perfekt sicher. Das plappert einer dem anderen nach ohne es nachgeprüft zu haben. Wenn man so etwas sagt, muß man dazusagen, daß man sich auf die Nachrichtentypen beschränkt, von denen man es weiß.
Laß das mit der prob. Verschlüsselung hier erst mal weg, das hab ich nur reingeschrieben, damit die, die den Streit mitverfolgen, ersehen, wie und warum ich auf das Paper gestoßen bin.
Ach, und was Du zu probabilistischer Verschlüsselung ansprichst: Du meinst eine Randomisierung, nicht eine probabilistische Verschlüsselung.
Der Punkt ist doch, dass der OTP perfekt sicher ist, wenn vorher bekannt ist, wie lange die Nachricht ist.
Ja, aber wer sagt das schon dazu? Und wieviele wissen das?
> Die Alphabete werden hier in jedem Fall als endlich
> angenommen, meist redet man sogar von |A|=2, z. B.
> {0,1}.
Ich meinte hier die “Menge moeglicher plain/ciphertexte” wie in der wikipedia formuliert. Ich hab das mit unendlicher Symbolmenge vs. unendlichen Symbolverkettungen nicht so genau genommen, entschuldige.
> Willst Du etwa argumentieren, daß der One-Time-Pad
> allein deshalb schon sicher sein muß, weil sonst
> die Definition für perfekte Sicherheit nicht
> erfüllbar ist?
Nein. Ein anderer Cipher koennte dann ja die Definition erfuellen. Aber es wurde bewiesen(und ist auch offensichtlich), dass die Definition nicht erfuellbar ist, wenn unendlich lange Nachrichten betrachtet werden. Das ist ein Grund.
Ich wehre mich gegen deine Argumentation: Der OTP inf.theor. nicht sicher, weil man die Definition inf.theor. Sicherheit so auslegen kann, dass sie durch nichts erfuellt werden kann.
Wenn man verlangt, dass alle *moeglichen* Klartexte gleichwahrscheinlich sind gegeben einen Ciphertext, dann sind die offensichtlich unmoeglichen Nachrichten(die zB einfach laenger sind als der Ciphertext) schon *a priori* nicht Teil dieser “moeglichen” Klartexte.
Fragt sich, wieso sollten a priori bestimmte Klartexte ausgeschlossen werden? Wegen der Definition des betrachteten Ciphers an sich. Der wird nicht mit “OTP” definiert sondern durch eine mathematische Abbildung, die entweder mit endlichen Nachrichten arbeitet oder nicht. Egal wie einfach der OTP ist, eine Definition der Eingabewerte und daraus folgende Menge moeglicher Ausgabewerte gehoert dazu. Und wenn ich mich nicht irre ist es moeglich, einen *korrekten* OTP fuer beliebige Ein/Ausgabe-Mengen zu definieren, der auch inf.theor. sicher ist.
“randomisiert” finde ich bei google nicht so sehr, ich kenne nur prabilistische verschl. als essentielle Eigenschaft heutiger cipher. Bei zB Blockciphern wird sie nachtraeglich durch den Ciphermode hinzugefuegt. Asymetrische haben sie integriert weil ja jedermann ciphertext erzeugen und vergleichen kann.
Wann immer man die Idee des OTP benutzt, um in der kryptographie einen Teilaspekt zu beweisen, betrachtet man auch endliche, meist gleichlange strings. Also ich denke schon dass das den meisten bewusst ist, dass es sonst schief geht 🙂
Codierung ist nicht mein Gebiet, aber ich glaube man benutzt dort die unendlich langen Nachrichten vor allem, weil es die Berechnungen vereinfacht.
Ach, das ist doch jetzt Käse, jetzt widersprichst Du dir ständig. Bei unendlich langen Nachrichten ist die Definition erfüllbar, nur bei variabel unbegrenzt langen nicht. Das ist was anderes!
Bevor Du hier jetzt ewig lange Diskussion anzettelst und hier Riesen-Dinger in mein Blog schreibst, denk doch bitte erst mal drüber nach und lies nach. Außerdem verstehe ich bei einigen Deiner Formulierungen nicht (auf Anhieb), was Du damit eigentlich sagen willst.
Außerdem geht es hier nicht um “Auslegungen” von Definitionen.
Es gibt keine Chiffre, die diese Bedingung erfüllt.
Und ob Du dich gegen meine Argumentation “wehrst” interessiert mich ehrlich gesagt auch nicht so wirklich. Ich will Dich ja gar nicht angreifen.
Und den meisten ist so, wie sie den OTP beschreiben, diese Anforderung sicher nicht bewußt.
Ok, ich bin nichtakademischer normalgebildeter EDVler, mit Fachhochschulreife – daber bitte nicht gleich totmachen – aber:
Angenommen ich will nur ein Zeichen verschlüsseln -> Endliche Nachricht, die z.B. eine Antwort ist, Ja, Nein 0-9, A-z …
Mit einem OTP mache ich ein XOR mit einem beliebigen Schlüssel, z.B. ein GZIP -9 einer CD die mit dem Empfänger ausgemacht ist (so hab ich OTP verstanden, nur ich und der Empfänger haben den Schlüssel der auf einem separaten Kanal (z.B. bei einem persönlichen Treffen) übermittelt wurde).
Wenn ich streng Byteweise arbeite habe ich also ein Zeichen, das Chifrat (heist das so?) ist ein weiteres Zeichen (0-255 Dez)). Da mein Schlüssel aus allen Zeichen (Zahlenwerten) zwischen 0 und 255 bestehen kann ist nur mit einer Wahrscheinlichkeit von 1 zu 255 meine Antwort zu erraten. Wenn sie z.B. J oder N bzw. 0 oder 1 bzw. gerade/ungerade, da keine Nachricht nur für sich steht sondern immer auf einer bisherigen Korrespondenz beruht ist alles möglich…
Ok – ich sehe jetzt keine Möglichkeit meine Nachricht (J/N) zu erraten.
Wenn das schon bei einer 1Byte Nachricht unmöglich ist, wie soll dann eine beliebig lange Nachricht unsicherer sein?.
Wenn ich 400kB übertrage, so weiss der Angreifer nur, dass es 400kB sind. Das kann ein JPG Bild sein, ein .xls ein .odt ein Programm, Schillers Glocke in einer kommentierten Version oder (noch schlimmer) ein individuell erstellter Text.
Diese 400kB lassen keinen Rückschluss darauf zu was es sein könnte – genau so wenig wie mein Byte von vorher. Diese 400kB sind die Antwort auf die Vornachricht. Ein Schlachtplan, eine CAD Zeichnung, die Spesenabrechnung, das PDF des Flughandbuchs des A310 …
Wenn ich meine Ursprungsdaten von Hex00 und anderen verräterischen Bereichen (z.B. Metadaten, Huellformate), die ein erraten des Schlüssels ermöglichen befreie, also diese zuerst durch den gzip schicke (auch bei JPG und anderen gepackten Inhalten) und als Schlüssel `weisses oder rosa’ 🙂 Rauschen oder noch besser den lzh einer handelsüblichen CD verwende (Rauschen ist statistisch auswertbar, bei einem nicht streng statistisch sauberen Schlüssel und einem nicht streng statistisch sauberen Inhalt ist beides nicht trennbar, der Angreifer kann die Auffälligkeiten nicht dem Schlüssel bzw. dem Inhalt zuordnen) – sch**** langer Satz.
Was ich sagen will. Nur mit der abgefangenen Nachricht ist es einfach unmöglich bei einem OTP auf den Inhalt der Nachricht zu kommen wenn nicht massive Fehler, z. .xls verschlüsselt mit dem .wav von Madonnas ‘Ray of Light’ gemacht werden.
Egal ob das ein Byte oder 4 Terra (ok, da reicht Madonna nicht, da müsste man schon den Mitschnitt des RTL seit dem 1.1…. (zu faul um nachzurechnen) oder 100 ausgemachte DVDs haben) sind.
Richtig ist immer nur eine einzige Lösung während (bei einem Byte) 256 bist unendlich viele Lösungen möglich sind.
Als Angreifer habe ich keinen Hinweis darauf welche dieser möglichen Antworten die richtige ist und damit keine Chance sie zu erraten.
Schlagt mich tot, aber das ist für mich (auch wenn ich die Theorie der perfekten Verschlüsselung nicht verstehe) einfach ausreichen sichere Übermittlung.
Ach, wieso totmachen. Mir ging das nur bei diesem pepe etwas über die Hutschnur, daß der nicht sachlich argumentiert sondern allein damit, daß es nicht sein kann weil ihm das Ergebnis nicht gefällt.
OTP hast Du soweit verstanden, nur daß der Schlüssel wirklich zufällig sein muß, was ein gzip einer Musik-CD eben nicht ist.
OTP arbeit normalerweise bitweise, aber natürlich kannst Du das auch byteweise betrachten. Dann ist eben |A|=256.
Und tatsächlich ist in Deinem Beispiel die Wahrscheinlichkeit, ein Zeichen des Klartextes zu erraten, 1:256. Die gleiche Chance, nämlich 1:256, hast Du aber auch schon ohne das Chiffrat wenn Du gar nichts weißt. Also bringt Dir die Kenntnis des Chiffrats keinen Vorteil und damit ist die Chiffre informationstheoretisch sicher.
Dabei hast Du aber von vornherein die Nachrichtenlänge auf 1 begrenzt bzw. jedes Byte einzeln betrachtet. Für feste Nachrichtellängen geht’s ja auch.
Wie Du selbst schreibst, weiß der Angreifer, daß die Nachricht 400kB lang ist, wenn du 400kB überträgst. Und das ist genau der Knackpunkt: Bei Nachrichten variabler Länge ist der Nachrichtenraum AN, allso Nachrichten aller bzw. verschiedener Längen – und nicht nur ein Zeichen oder Byte. Wenn der Angreifer nun weiß, daß der Klartext 400kB lang ist, dann fallen doch schon fast alle Klartexte weg, nämlich die mit anderer Länge. Also weiß der Angreifer damit doch schon viel über den Klartext. Nur innerhalb der Untermenge der Klartexte mit 400kB weiß er nicht, welches der Klartext ist.
Und tatsächlich kann man auch bei verschüsselten Mails nach bestimmten Nachrichten suchen, wenn etwa eine gesuchte Datei als Anhang gewisse Nachrichtengrößen nach sich zieht. Es ist erstaunlich, was man anhand einer Verkehrsdatenanalyse ohne Entschlüsselung alles entdecken kann. Das sollte man nicht unterschätzen.
Daß Dir die normale Verschlüsselung reicht, ist in den meisten Fällen ja auch angebracht, wer nutzt schon den OTP, der ja auch viele Nachteile hat.
Als Software-Ingenieur muß man sich aber schon ab und zu mal Gedanken machen, wie man die Verkehrsanalyse erschwert und solche Daten schützt. Es gibt einen Angriff gegen verschlüsselte Skype-Telefonate, der allein auf der Größe der Datenpakete beruht, weil die Sprachkompression bei Skype variabel große Datenpakete verwendet und man schon aus der Paketgröße auf Sprache, womöglich auch Sprecher und Inhalt schließen kann, auch mit OTP.
Außerdem ging es mir einfach darum mal aufzuzeigen, wieviel Zeugs in der Kryptographie als vermeintlich wissenschaftlich und bewiesen herumerzählt wird. Da perfekte Sicherheit auf den Angreifer mit unbegrenzter Rechenleistung abzielt, ist es sowieso eher theoretisch orientiert.
Ok, jetzt hab ich’s verstanden.
Bei Traffic wird immer wieder und wieder etwas geschickt. Wenn ich nicht verbergen kann, dass ich z.B. “Bilder” schicke bin ich wesentlich angreifbarer.
BTW: EnBW wirbt massiv für seinen neuen Stromzähler. Der ‘hilft den Verbrauch senken’ und schickt laufen Zählerstände zu EnBW. Dass nur über die Auswertung der Verbrauchsdaten ein recht gutes Bild eines Haushaltes (Wieviele sind wann wach, wann steht der erste auf, geht der letzte schlafen, wird Mittags oder abends gekocht (oder nur Mikrowelle)…) entsteht glaubt kaum ein Normalverbraucher.
Apropos ENBW/Yello: Ich hatte mit denen auf der CeBIT versucht über das Thema Sicherheit dieser Geräte mehr zu erfahren. Abgesehen davon, daß ich von mehreren vertröstet wurde, daß der technische versierte Mitarbeiter nicht da ist, konnte der mir dann nicht viel außer folgendem sagen:
ENBW/Yello erwarten, daß Du die Kiste in dein LAN hängst und diese dann über deinen Router und Internetzugang Kontakt zu deinem Anbieter aufnimmt.
Du darfst die Daten nicht selbst “ablesen” und auswerten.
Die datebn werden alle zentral abgeliefert und als Benutzer/Kunde kann man nur üebr eine spezielle Website auf die Auswetungen zugreifen (kein Zugriff auf die Rohdaten).
Bei der Demo am Stand konnte man sich sehr leckeren Kaffe/Cappucino machne lassen und hat dann im Diagramm sehr deutlich sehen könnten, wann udn wieviel die Maschine verbraucht hat. Man konnte sich sogar “hochrechnen” lassen, wieviel Stromkosten eine Kaffemaschnie so im Jahr erzeugt und ob es wirtschaftlicher ist, die Maschine durchlaufen zu lassen und damit die (nicht abschaltbare) Warmhalteplatte zu betreiben, die nebenbei erwähnt, sehr viel Strom braucht, oder die Maschine auszuschalten udn jedesmal für einen Kaffe wieder einzuschalten. Es war deutlich billiger die Maschine aus/und einzzuschalten, jedenfalls was die Stromkosten angeht. Ob die An-Auszyklen sich negativ auf die Lebensdauer auswirken war nicht zu erfahren.
Worauf ich aber hinauswollte: Mit den Daten, die die aus dem Ding bekommen, können die im Prinzip einen relativ sicher in der Wohnung orten, wenn man entsprechend gedankenlos die elektrischen Geräte in der Wohnung bedient.
Weiterhin ist mit dem Ding ein Trojaner im Haus, wie ihn sich Schäuble nicht besser wünschen könnte (Lokale Zugriffsmöglichkeiten im LAN). Es ist nicht vorgesehen, daß diese Ding einen eigene Leitung (ggf übers Stromnetz) bekommt, und die wenigsten “Anwender” dürften eine Firewall zwischen dem Stromzähler rund Ihrem LAN schalten.
Meiner Ansicht nach gehört das Ding Datenschutzrechtlich verboten.
Womit dann die Stromanbieter gleich noch Daten über die dynamischen IP-Adressen haben, die beim TK-Anbieter nach Vorratsdatenspeicherung unter strengem Schutz stünden.
Wow.
Ich kann deine Kritik ehrlich gesagt nicht nachvollziehen. Der one time pad verschleiert also nicht die Länge der Nachricht. Und? Kein ernstzunehmender Kryptologe wird das behaupten. Wie jedes andere Verschlüsselungsverfahren schützt der OTP den *Inhalt* der Nachricht, gewährleistet also *Vertraulichkeit*. Für sichere Kommunikation fehlen mindestens noch Checks für Integrität und Authentizität der Nachricht.
Für verdeckte Kommunikation will man noch die Menge der übermittelten Daten (bzw. gar den Akt der Kommunikation an sich) verschleiern. Das ist aber *nicht* die Aufgabe des Verschlüsselungs-Algorithmus.
Historisch verwendet man dazu Techniken wie das weglasn redndntr zeichn, dieunterdrückungdeswortzwischenraums etc. Moderner ist die Komprimierung des Geheimtextes und das optionale Auffüllen mit Blendern, z.B. um bei Blockchiffren auf volle Blöcke zu kommen. Noch etwas ausgefeilter sind steganographische Verfahren. Oder das Einbetten verschlüsselter Nachrichten in einen stetigen Strom von Zufallsdaten.
Dessen ungeachtet ist der OTP *kein* praktisch anwendbares Verfahren, da der Schlüsselaustausch ein großes Problem darstellt. Der OTP illustriert nur eine der größten Schwächen der damals üblichen Verfahren wie z.B. Vigenere. Das Problem dieser Verfahren ist die Verwendung eines periodischen, oft memorierbaren Schlüssels. Unter diesen Umständen kann man die Plausibilität eines “geratenen” Klartexts ziemlich zweifelsfrei feststellen. Beim OTP klappt das nicht mehr, weil jeder geratene (oder unterstellte) Klartext gleich wahrscheinlich ist.
@XL: Wenn eine Chiffre die Länge nicht verbergen kann und es Klartexte unterschiedlicher Länge gibt, dann hat man den Inhalt eben nicht “perfekt” geschützt, weil der Angreifer weiß, daß alle Klartexte mit unpassender Länge rausfallen. “Perfekte Sicherheit” bedeutet aber, daß der Angreifer auch in Kenntnis des Chiffrats nichts über den Klartext sagen kann – also auch nicht die Länge.
Was soll daran jetzt eigentlich so schwer zu verstehen sein?
@Hadmut: was ist eigentlich so schwer daran zu verstehen, daß perfekte Sicherheit eines kryptographischen Algorithmus *nicht* beinhaltet, daß die Länge der Nachricht verborgen wird?
Es ist unmittelbar einsichtig, daß (bei gleichem Alphabet) der Output eines Krypto-Algorithmus nicht kürzer sein kann als der Input. Es hat in der Vergangenheit Systeme gegeben, bei denen der Output länger war – durch Verwendung von Homophonen und einem erweiterten Ausgabe-Alphabet. Moderne Kryptoverfahren sind stets längenerhaltend (abgesehen von der Blockgröße bei Block-Chiffren) weil das für die meisten Anwendungen am praktischsten ist. Sie überlassen das Verbergen der Nachrichtenlänge – falls das gewünscht wird – höheren Schichten. Dieser “Mangel” trifft also praktisch auf alle etablierten Krypto-Algorithmen zu.
Was du bemängelst, ist die Abwesenheit eines Merkmals, das schlicht nicht garantiert ist. Und du belegst das mit “Definitionen” von perfekter Sicherheit, die schlicht falsch sind.
Ganz allgemein geht es dir nicht mehr um Verschlüsselung, sondern um Verschleierung von Kommunikation. Das sind zwei verschiedene Baustellen.
Wie ich schon weiter oben geschrieben habe: Verschlüsselung ist nur *ein* Baustein für sichere Kommunikation.
@XL: Perfekte Sicherheit ist einfach anderes definiert.
Die richtet sich ja nicht nach dem, was Chiffren in der Natur so tun, sondern hat eine theoretische Grundlage.
Ich glaub, Du hast Dich da ziemlich in einer verbalen Interpretation verrant. Guck mal in
Claude Shannon, Communication Theory of Secrecy Systems, 1949, Abschnitt 1 und 10.
Da findest Du die exakten Definitionen, die Grundlagen und die Theoreme dazu, insb. Theorem 6. Dann siehst Du auch, warum eine normale Chiffre das nicht für variable Nachrichten erfüllen kann und wie das definiert ist.
Das Chiffrat muß dazu völlig verbergen, welche Nachricht aus der Menge der möglichen Nachrichten der Klartext ist.
Und wenn die Nachrichten unterschiedliche Länge haben, dann müßte die Chiffre auch die Länge verbergen, weil sie ja sonst zeigen würde, welcher Untermenge der Nachrichten der Klartext entstammt.
Grüße
Hadmut
@Hadmut:
> Perfekte Sicherheit ist einfach anderes definiert.
Dann legst du entweder die Definition falsch aus oder die Definition ist Müll.
Meine Argumentation ist wie folgt: es ist offensichtlich, daß die Entropie des Chiffrats nicht kleiner sein kann als die des Klartexts. Wenn also ein OTP Chiffrat der Länge N bits aufgefangen wird, kann der Klartext höchstens N bits Entropie haben (Entropie und Länge des Chiffrats stimmen per Definition überein, weil der Schlüssel ja echt zufällig ist). Diese Information über den Klartext *kann* der OTP prinzipiell nicht verbergen. Jede Forderung dahingehend ist sinnlos.
Bleibt die Frage, ob der OTP auch alle Klartexte mit geringerer Entropie (vulgo: Länge) zuverlässig ununterscheidbar macht. Und die Antwort darauf ist ja. Denn auch ein kürzerer Klartext, der mit bspw. Nullbits aufgefüllt ist, ist im Chiffrat *nicht* unterscheidbar von einem der die volle Länge für echte Informationen nutzt.
*Jeder* mögliche Klartext, der auf die Länge paßt ist gleich wahrscheinlich. Auch der leere Klartext, der nur mit Nullen aufgefüllt ist.
Die Grenze für die Sicherheit des OTP liefert Shannon mit seiner Entropie-Definition selber. Wirklich umgehen kann man diese Grenze auch nur, indem man möglichst viel Füllmaterial um die echte Information packt. Wenn man vor dem OTP padded hat man halt die angenehme Eigenschaft, beliebiges Füllmateriel verwenden zu können. Nicht daß das viel nützen würde. Man erkauft es damit, mehr (teures) Schlüsselmaterial zu verbraten.
Ob Du die Definition für Müll hältst, bleibt Dir überlassen, dazu kann man durchaus seine Meinung haben. Aber deshalb kann man sie nicht einfach nach Gutdünken uminterpretieren oder sagen, daß eine Chiffre eine Bedingung schon deshalb erfüllt, weil sie ja sonst unerfüllbar wäre.
Genauso wenig kann man als kryptographisches Argument bringen, daß eine Forderung sinnlos wäre. Sinnlos oder nicht, erfüllt ist sie damit noch lange nicht.
Deine Argumentation für kürzere Klartexte stimmt, aber nur, weil Du schleichend und stillschweigend unterstellst, daß es eine Höchstlänge gibt, bis zu der aufgefüllt wurde und der das Chiffrat entspricht. Dann aber hat man Nachrichten fester länge bzw. einen endlichen Nachrichtenraum – und dann funktionert der OTP ja auch, wie schon gesagt. Du mußt da höllisch auf solche Kleinigkeiten achten und präzise arbeiten.
In dem Moment, wo Du sagst, daß es nur für kürzere funktioniert, hast Du entweder die Nachrichtenlänge beschränkt oder zugegeben, daß es nicht funktioniert.
Gruß
Hadmut
@Hadmut:
> Ob Du die Definition für Müll hälst, bleibt Dir überlassen
Nach reiflicher Überlegung tendiere ich zu der Ansicht, daß du die Definition für absolute Sicherheit einfach falsch auslegst.
Unter der Bedingung, daß die Entschlüsselung eindeutig ist, muß jeder Verschlüsselungsalgorithmus eine Chiffre mit gleicher oder größerer Entropie liefern als der Klartext hat. Bei bekannter Chiffre hat man also *immer* eine obere Grenze für die Entropie des Klartexts. Diese Zusatzinformation verliert erst dann an Wert, wenn die Länge der Chiffre gegen unendlich geht.
Kein Kryptoverfahren der Welt kann also die Entropie (vulgo: Länge) des Klartexts vollständig verbergen. Es sei denn, es würde *jeden* Klartext auf eine unendlich lange Chiffre abbilden. Das ist offensichtlich sinnlos.
Die Forderung ist schlicht nicht erfüllbar. Und ich bin mir sehr sicher, daß auch Shannon das gewußt hat, als er seine Definition aufschrieb. Schließlich stammt die Theorie über Entropie in Informationen verarbeitenden Systemen von ihm.
Eine Definition aber für ein Ding, das es beweisbar nicht geben kann, ist lediglich eine weitere Definition der leeren Menge. Also hat entweder Shannon da einen Denkfehler, oder du 😉
Was heißt da “Nach reiflicher Überlegung”? Hast Du Dir die Definition denn überhaupt mal angesehen? Und eine Begründung lieferst Du auch nicht. Hört sich für mich an wie “ich habs mir überlegt, aber verrate niemand, was ich überlegt habe…”.
Das mit der Entropie ist eine heikle Angelegenheit. Entropie definiert sich wieder ganz anders, zumal das Chiffrat ja auch noch die Entropie des Schlüssels enthält. Ich glaube, Du bringst da einige Sachen ziemlich durcheinander.
Im übrigen: Ist Dir schon mal aufgefallen, daß die PGP-verschlüsselte Darstellung eines normalsprachlichen Textes kürzer als der Klartext ist? Rat mal, wie die das machen. 😉
Deine Argumentation ist ziemlich emotional. Es gibt Chiffren, die das können, und das wird auch bei Shared-Secret-Schemen so verwendet, aber eben nur für feste Nachrichtenlängen. z. B. Coin-Flipping.
Nach Deiner Argumentation dürfte man auch die Lichtgeschwindigkeit nicht festlegen, weil man sie ja selbst nicht erreichen kann. Außerdem betrachtet man in der Mathematik ständig irgendwelche Sachen von denen man dann beweist, daß es sie nicht geben kann. Das ist halt einfach Denkübung und Ergebnis einer Untersuchung. Außerdem gibt es ja z. B. auch das erwähnte Paper von Chor und Kushilevitz, die auch beweisen, daß es so etwas nicht gibt.
Aber diese Autoren, Shannon, ich, alle haben in Deinen Augen einen Denkfehler, nur Du erkennst, daß die Definition unsinnig sein soll.
Aber selbst wenn Du Recht hättest: Nur weil eine Definition nicht erfüllbar sein soll, verändert sie sich doch nicht auf magische Weise in irgendwas, was Dir sinnvoll erscheint.
Hör bitte mal auf mit diesem emotionalen “Ich find das so unsinnig, also kann es gar nicht sein.” Lies Dir mal das Paper von Shannon, 1949, durch und dann argumentier mal sauber. Aber dieses – Tschuldigung, wenn ich das mal so sage – unkonkrete und substanzlose “Ich-will-einfach-nicht-weil-es-mir-nicht-gefällt”-Geschwafel bringt überhaupts nichts und ist mathematisch/kryptographisch sehr gefährlich.
> Hast Du Dir die Definition denn überhaupt mal angesehen?
Hast du eine frei zugängliche Quelle?
> Das mit der Entropie ist eine heikle Angelegenheit. Entropie definiert sich wieder ganz anders, zumal das Chiffrat ja auch noch die Entropie des Schlüssels enthält.
Mitnichten. Die Entropie ist ein Maß für den Informationsgehalt. Eine ideal komprimierte Darstellung hat Länge = Entropie. Für praktisch vorkommende Klartexte ist Länge > Entropie. Sogar bei .MP3 und ähnlichem, weil da i.d.R. noch unkomprimierte Meta-Information drin steckt.
Ein Chiffrat ist i.d.R. nicht komprimierbar. Da ist Länge == Entropie. Das allgemein zu beweisen dürfte recht schwer sein, aber beim OTP ist es unmittelbar einsichtig. Der Schlüssel selber ist per Definition unkomprimierbar. Das XOR aus dem Klartext und dem (wiederum per Definition) unkorrelierten Schlüssel ebenso.
> Im übrigen: Ist Dir schon mal aufgefallen, daß die PGP-verschlüsselte Darstellung eines normalsprachlichen Textes kürzer als der Klartext ist? Rat mal, wie die das machen.
Mit Kompression. Das ist genau der Grund, warum ich argumentativ zwischen Länge und Entropie unterscheide.
Ist dir schon aufgefallen, daß die Verkürzung bei PGP nicht mehr funktioniert, wenn der Klartext unkomprimierbar ist?
Und ist dir auch klar, daß die vorherige Komprimierung in PGP *nichts* mit der Stärke der Verschlüsselung zu tun hat?
Manche Kryptologen argumentieren, daß Verschlüsselung den Vorteil bietet, leicht erratbare Teile des Klartexts zu verbergen (etwa den Header einer AVI Datei) und dadurch eine partielle Klartext/Geheimtext-Komprimittierung verhindert. Das ist zwar im Prinzip richtig, aber für aktuelle Krypto-Verfahren und insbesondere den OTP ist eine solche Kompromittierung kein Problem.
Ich hab es schon mal gesagt und wiederhole es gerne nochmal: der springende Punkt beim OTP ist, daß selbst eine komplette Klartex/Geheimtext-Kompromittierung dem Angreifer nicht hilft. Er kann aus dem vorliegenden Geheimtext nicht beweisen, daß *dieser* Klartext der richtige ist.
> Deine Argumentation ist ziemlich emotional.
Dito.
> Es gibt Chiffren, die das können, und das wird auch bei Shared-Secret-Schemen so verwendet, aber eben nur für feste Nachrichtenlängen. z. B. Coin-Flipping.
Du vergleichst Äpfel mit Birnen. Obiges ist ein Protokoll. Ein Verschlüsselungsverfahren ist nur *ein* Baustein in einem Protokoll. Auch das sagte ich bereits.
Ich sagte ebenfalls, das die von dir als fehlend bezeichnete Eigenschaft, die Länge des Klartexts (und zwischen den Zeilen: den Akt der Kommunikation an sich) zu verschleiern, unabhängig vom verwendeten Krypto-Verfahren gelöst werden kann und üblicherweise auch unabhängig davon gelöst wird. Es gibt sehr gute Gründe für eine solche Aufteilung.
> Nach Deiner Argumentation dürfte man auch die Lichtgeschwindigkeit nicht festlegen
Jetzt wirds langsam blöd. Gehen dir die Argumente aus, oder was?
> Nur weil eine Definition nicht erfüllbar sein soll
Eine solche Definition ist schlicht nutzlos. Und es ist noch viel nutzloser, darüber zu jammern daß ein existierendes Ding eine Definition nicht erfüllt, die es gar nicht erfüllen kann.
Es gibt eine Anekdote über einen Mathematiker, der ein bestimmtes Konstrukt (irgendeine algebraische Struktur) definiert und untersucht hatte. Mit absolut sauberer Argumentation konnte er die fantastischsten Eigenschaften seiner Objekte beweisen. Bis dann irgendwann mal ein anderer daherkam und zeigte, daß seine Definition nicht erfüllbar, also lediglich eine komplizierte Definition der Nullmenge war. Für die Elemente der Nullmenge kann man aber beliebige Eigenschaften “beweisen”.
Soviel zum Thema Gefährlichkeit.
Erstmal für die gemeinsame Diskussionsgrundlage, das Shannon-Paper gibt es hier:
http://www.apprendre-en-ligne.net/crypto/bibliotheque/PDF/shannon1949.pdf
Shannon behandelt endlichen Nachrichten, über die ja hier Einigkeit herrscht. Bei der ersten Nennung von unendlichen Nachrichten schreibt Shannon: “The situation is somewhat more complicated if the number of messages
is infinite. Suppose, for example, that they are generated as infinite sequences
of letters by a suitable Markoff process.”
Diese Definition ändert Shannon im Laufe des Papers auch nicht mehr. Er redet also in der Tat nur von echt unendlichen Sequenzen. Er schließt den von Hadmut genannten Fall nicht explizit ein oder aus. Man kann sich nun selbst überlegen, ob man diesen Fall als “im Geiste Shannons” so oder so sieht, weil Shannon nicht direkt darüber gesprochen hat.
Ich persönlich vermute, dass Shannon diesen Fall trotzdem als perfekt sicher bezeichnet hätte, und zwar wegen dieser Fußnote:
“A purist might object that the enemy has obtained some information in that he knows a message
was sent. This may be answered by having among the messages a “blank” corresponding to “no
message.” If no message is originated the blank is enciphered and sent as a cryptogram. Then even
this modicum of remaining information is eliminated.”
Wenn Shannon sagt, dass die Nachricht als solche keine Information ist, würde ich sagen, dass die Länge auch keine ist. Wenn Shannon sagt, dass man “keine Nachricht” theoretisch als Nachricht gelten lassen kann, kann man “kein Zeichen” theoretisch auch als Zeichen empfinden.
Streng genommen hat Shannon diesen Fall aber nun mal nicht direkt definiert und das ganze ist entsprechend Glaubensfrage. Fakt ist, dass die Länge eines Chiffrats vielfach eine schützenswerte Information ist und Fakt ist, dass die meisten Wissenschaftler sich darüber im klaren sind.
http://d0mber.blogspot.com/2008/10/otp-oder-was.html ist anderer Meinung, auch wenn die Begruendung weniger ueberzeugend wirkt. Aber wenn man nochmal hier schaut:
http://de.wikibooks.org/wiki/Beweisarchiv:_Kryptografie:_Sicherheitsdefinitionen:_Äquivalente_Definitionen_informationstheoretischer_Sicherheit
Da ist IMO der springende Punkt versteckt. Die Frage ist, fuer welche Alphabete man inf.theor. Sicherheit verlangt. Der Wikipedia-Link nimmt die Menge aller “moeglichen” Klar/Ciphertexte. Du waehlst Nachrichten beliebiger(unendlicher!) Laenge und stellst fest, dass man so keine inform.theor. Sicherheit erreichen kann.
Damit hast du Recht, aber…wenn nichts die Definition erfuellt, welchen Sinn hat sie dann?
Es ist richtig, praktisch gesehen muss man darauf achten, neben dem Inhalt auch Meta-Daten hinreichend zu verstecken. Aber Angriffe, die auf sowas aufbauen, kennt man als ‘traffic analysis’. Und side-channel attacks werden ueblicherweise seperat betrachtet.