Die Unizitätslänge und die Gödel-Nummer
In England haben sie neulich die Überreste einer Brieftaube aus dem zweiten Weltkrieg gefunden, die noch eine Kapsel mit einer verschlüsselten Botschaft dabei hatte. Sie meinen aber, sie wäre nicht zu knacken. Was naheliegend ist und informationstheoretische Gründe hat.
In der Kryptographie gibt es den (übrigens von Shannon eingeführten) Begriff der Unizitätslänge. Die Unizitätslänge ist – vereinfacht gesagt – die Menge an Text einer gewissen Redundanzdichte (beispielsweise eben normale Sprache mit ihrer Redundanz, anhand derer man Schreibfehler, unsinnige oder nicht zur Sprache gehörende Texte usw. erkennt), bei der die Redundanz der Schlüsselentropie entspricht. Wenn also der Text genug Redundanz enthält, dass nur noch ein Schlüssel „passt”. Denn bei symmetrischen Verfahren ist es nicht so, dass ein Schlüssel algorithmisch passt und die anderen zu Fehlermeldungen führen, sondern man kann ein Chiffrat mit jedem beliebigen Schlüssel aus dem Schlüsselraum „entschlüsseln”, nur dass es eben mit den meisten (und bei ordentlichen Chiffren allen außer dem richtigen) Schlüsseln nicht zum Klartext sondern zu falschen, unsinnigen Ergebnissen kommt. Selbst wenn man genug Rechenleistung für eine Brute-Force-Attacke hat, steht man immer noch vor dem Problem erkennen zu können, welche dieser Entschlüsselungen vernünftigen Text ergeben und welche nur Unsinn, also die Erfolgsdetektion. Erst wenn genug Text vorliegt, eben wenn die Unizitätslänge erreicht ist, bleibt im Suchraum (statistisch) nur noch eine Nachricht, die man als zum Klartextraum (z. B. deutsche Sprache) gehörig erkennt. Fängt man beispielsweise eine Nachricht aus nur 5 Byte ab und weiß, dass der Klartext ein deutsches Wort ist, aber ein Verfahren mit 128 Bit Schlüssellänge eingesetzt wird, ist die Unizitätslänge nicht erreicht. 5 Byte, die je ein Zeichen enthalten, haben nur eine Redundanz von ungefähr 10-15 Bit. (Es ist sehr schwer zu schätzen, aber normalsprachliche Klartexte liegen ganz grob bei ungefähr 1-3 Bit Redundanz pro Zeichen. Kommt sehr darauf an, wass man über den Text weiß. Militärische Texte enthalten etwa keine Kindersprache.) Bei einer vollen Suche könnte man also Schlüssel finden, die als Klartext etwa „Apfel”, „Birne”, „Pferd” oder „Musik” liefern, weshalb man nicht erkennen kann, welches der Schlüssel war. Erst wenn der Text lang genug ist, also ungefähr 40-80 Zeichen, ist genug Redundanz im Text, dass (statistisch gesehen) nur noch ein Schlüssel einen plausiblen deutschsprachigen Text liefert. Deshalb kann man beispielsweise den One-Time-Pad nicht brechen, weil da der Schlüssel immer so lang wie der Text ist und deshalb die Unizitätslänge nicht erreicht werden kann. (Entgegen der Ansicht der allermeisten Kryptologen ist der One-Time-Pad aber nicht absolut sicher. Das behaupten die zwar alle, aber da quatscht nur einer dem anderen nach. Denn der One-Time-Pad ist längenerhaltend, das Chiffrat ist so lang wie der Quelltext und verrät damit dessen Länge. Und damit kommen eben nicht mehr alle möglichen Klartexte in Frage, sondern nur noch die der jeweiligen Länge. Da hilft auch kein Padding usw., denn man kann (siehe den Link) nachweisen, dass es eine solche Abbildung von Klartexten auf Chiffrate, die auch die Länge verbirgt, nicht geben kann. Entgegen der Behauptung vieler Kryptologen gibt es die perfekte Verschlüsselung nicht. Dass es trotzdem so oft behauptet wird, liegt an der Schlampigkeit bei der Definition und Spezifikation. Labert sich halt so leicht im Hörsaal.)
Dabei machen die Kryptologen aber noch einen weiteren Denkfehler. Denn man geht immer davon aus, dass das Verfahren bekannt, nur der Schlüssel unbekannt ist. Das hängt mit der Kerckhoffs’schen Maxime zusammen, wonach die Sicherheit eines Verfahrens nur von der Geheimhaltung des Schlüssels und nicht der Geheimhaltung des Verfahrens selbst abhängen darf. Was völlig richtig ist.
Nur darf man daraus nicht den Fehler machen, kryptographisch nur den Fall eines offengelegten Verfahrens zu unterstellen, bei dem lediglich der Schlüssel nicht bekannt ist. Denn aus dem Umstand, dass der Verteidiger das Verfahren veröffentlichen können müsste ohne es zu schwächen, folgt noch lange nicht, dass es ratsam ist, es zu veröffentlichen, oder dass es tatsächlich veröffentlicht worden ist. Denn effektiv, gerade im Kriegsfall, hat der Verteidiger ja auch nichts davon, dem Angreifer das Verfahren mitzuteilen. Zumal ja immer das Risiko besteht, dass das Verfahren doch irgendeine Schwäche hat. Kerckhoffs’s Maxime ist eine Anforderung an das Verfahren, kein Handlungsanweisung für den Verteidiger. Krypto-sportlich ist es sicherlich ratsam, ein Verfahren der Öffentlichkeit vorzustellen und die Krypto-Elite drauf rumhacken zu lassen. Im Hochsicherheitsbereich kann die Abwägung aber durchaus zugunsten der Geheimhaltung des Verfahrens hinauslaufen, auch wenn eine Vielzahl von Leuten aus dem Security-Dunst behauptet, dass ein nicht offengelegtes Verfahren per se nicht sicher sei. Das ist halt auch so leicht dahergeschwafelt, einer der üblichen Allgemeinplätze und Bauernregeln.
Egal ob’s ratsam ist oder nicht, muss man krypto-akademisch auch den Fall betrachten, dass der Angreifer – aus welchen Gründen auch immer – nicht nur den Schlüssel, sondern auch das Verfahren nicht kennt. Man müsste also – theoretisch – auch die Gödel-Nummer des kürzestmöglichen Algorithmus/Programms, das die Entschlüsselung leistet, zur Schlüssellänge addieren um die nötige Redundanz des Klartextes und damit die Unizitätslänge zu bestimmen. Und diese Gödel-Nummern sind im Allgemeinen heftig lang, im Prinzip die Textdarstellung des Programms, das entschlüsselt. Man bräuchte also schon theoretisch mindestens so viel Redundanz im Text, wie Schlüssel und Programm zusammen lang sind.
Dass es in der Vergangenheit mehrfach schon gelungen ist, Chiffren auch ohne genaue Kenntnis des Verfahrens zu brechen, liegt daran, dass die Grundelemente der Verfahren bekannt waren. Viele der alten Verfahren sind einfache Handchiffren, die aus denselben Grundelementen (Würfel, Permutationen, Substitutionen usw.) bestehen. Damit kann man sich ein Maschinenmodell bilden, dass nur aus diesen alten Krypto-Primitiv-Operationen besteht und damit „Programme” erlaubt, die diese Primitive aufrufen und damit sehr kurz sind, also kurze Gödel-Nummern haben. Deshalb ist es durchaus möglich, und ist ja auch Teil der Kryptoausbildung, Chiffren auch ohne Kenntnisse der Verfahren zu knacken. Nur dass das eben immer Verfahren sind, die aus wenigen Arbeitsschritten einer kleinen Auswahl von Grundoperationen bestehen, also eben kurze Gödel-Nummern haben. Die Texte sind dann lang genug um als Unizitätslänge auch beides, Schlüssel und Verfahren, abzudecken.
Bei der Taube ist die Nachricht nun ziemlich kurz und über das Verfahren ist überhaupt nichts bekannt, außer eben dem Wissen, welche kryptographischen Grundtechniken damals bekannt und üblich waren. Bei einem One-Time-Pad hat man keine Chance mehr, aber auch bei der Suche nach dem Verfahren wird es schwierig, weil das Verfahren hier quasi selbst wie ein One-Time-Pad wirkt, wenn man nur eine Nachricht hat.
Selbst wenn jemand das Ding „brechen” würde – man könnte bei einem so kurzen Chiffrat nicht sicher sein, ob man das Verfahren wirklich gebrochen hat, oder ob man nicht Algorithmus und Schlüssel eben so gewählt hat, dass aus dem Chiffrat eine „plausible” Nachricht herauskommt, die sich nach Englisch anhört, aber nicht dem echten Klartext entspricht. Denn wenn die Unizitätslänge nicht erreicht ist, gibt es nicht nur verschiedene Schlüssel, die zu anscheinend zulässigen Klartexten führen, sondern eben auch verschiedene Algorithmen.
Die Chancen, dieses Ding zu brechen, sind also, wie auch das GCHQ einräumt, gering. Selbst wenn jemand mit einer Lösung daherkommt, müsste man sich überlegen, ob die überhaupt echt sein kann oder nur das Verfahren so geschnitzt ist, dass eben eine vermeintlich richtiger Text herauskommt.
Der Ansatz zum Brechen wäre hier also die Taktik, die Gödel-Nummer möglichst zu kürzen und damit möglichst viel Wissen über die damals bei Agenten gängigen Handchiffren in Erfahrung zu bringen. Es ist aber zweifelhaft, ob man die so stark kürzen kann, dass die Unizitätslänge erreicht wird. Und GCHQ hat ja wohl auch schon die Wahrscheinlichkeit in Betracht gezogen, dass es ein OTP (oder etwas, was dem nahe kommt, beispielsweise einfach eine Textseite aus irgendeinem Buch als Schlüssel) verwendet wurde.
11 Kommentare (RSS-Feed)
Das beruht aber auf zwei Fehlüberlegungen:
Man sollte Verfahren natürlich von möglichst vielen erfahrenen Kryptologen prüfen lassen. Das ist aber nicht gleichbedeutend mit einer Offenlegung gegenüber der Öffentlichkeit.
Zweitens gehst Du von Friedenszeiten aus und unterstellst, dass jeder, der Schwächen findet, diese auch dem Urheber der Chiffre mitteilt.
Das gilt aber im Krieg nicht, da kann es auch gut sein, dass entdeckte Schwächen nur dem Gegner mitgeteilt werden. Siehe Enigma. Da hat man von der Offenlegung also nichts mehr.
Auch in unseren Zeiten gilt die Annahme nicht mehr, dass die “Öffentlichkeit” gefundene Schwächen auch veröffentlicht. Gefundene Schwächen in Software werden auch immer öfter nicht mehr publiziert, sondern verkauft. Manchmal an die Hersteller, oft aber auch auf dem kriminellen Markt.
Die Veröffentlichung von Kryptoverfahren beruht damit auf der Annahme, dass man ehrliches und offenes Feedback bekommt, was eben nicht immer und eigentlich auch schon lange nicht mehr zutrifft.
Wenn ich ein Verfahren einer Hand voll Kryptologen vorlege, ist es dann noch wirklich geheim? Wann spreche ich von Veröffentlichung? Formal und offiziell veröffentlicht ist etwas Anderes, als es zehn Leuten gezeigt zu haben, im Kontext des Szenarios eines wirklich geheimhaltungsbedürftigen Algorithmus aber auch schon ziemlich kritisch.
Insofern du die Fehlüberlegung darin siehst, es der breiten Öffentlichkeit preis zu geben, hast du Recht – davon habe ich aber auch nie gesprochen. Ich habe mich auch nie speziell auf das Kriegsszenario bezogen.
Was dieses betrifft besteht aber das selbe Problem. Das Risiko, das Verfahren, oder Teile davon, einem Maulwurf vor die Füße zu werfen steigt erheblich, je mehr Leute es kennen und je weiter du aus dem innersten Kreis deines Geheimdienstes heraustrittst. Dafür steigt aber auch die Chance, dass einer der dir freundlich Gesinnten einen Fehler aufzeigt, den der Feind ohne Kenntnis des Verfahrens hätte nutzen können.
Zudem musst du ganz besonders im Kriegsfall damit rechnen, dass der Feind den Algorithmus selbst sehr schnell in die Hände bekommt. Das ist ja auch bei der Enigma passiert. Die ersten Maschinen waren schnell in Feindeshand und damit die Sicherheit nur noch vom Algorithmus selbst, nicht von seiner Geheimhaltung, abhängig.
Bei der Frage, wie sich die Öffentlichkeit verhält, wird es kompliziert und es hängt sehr wahrscheinlich auch davon ab, um was es geht. Wenn man gefundene Fehler monetarisieren kann ist das immer kritisch, aber für Algorithmen, die noch nirgendwo verwendet werden (und die nicht speziell für kritische Bereiche gedacht sind) und bei denen man sich mit gefundenen Fehlern vor allem profilieren kann funktioniert das sehr wahrscheinlich doch relativ gut.
Was die Enigma angeht war das Verfahren auch gar nicht soo wahnsinnig geheim. Wenn mich die Erinnerung nicht trügt, war das Grundprinzip in einem frei verkäuflichen Produkt vorher zu haben, der Algorithmus selbst also nicht wirklich geheim.
Und das Genick gebrochen hat den Deutschen ja vor allem der falsche Umgang. Es gab afaik sogar Anweisungen, keine aufeinanderfolgenden Nachrichten gleich zu beginnen oder auch keine Anrede zu verwenden. Natürlich stand trotzdem immer “An die oberste Heeresleitung” als erstes in jeder Nachricht und die Uboote haben fröhlich den Wetterbericht gefunkt. Neben dieser Bereitstellung recht guten Materials für Angriffsversuche, hat man ja auch durch die Verwendungsanweisungen den Schlüsselraum deutlich eingeschränkt.
Beim Clipper-Chip hat man das damals gemacht, unter NDA. Einige der Top-Kryptologen hatten Zugang dazu. Trotzdem haben sie die wesentliche Lücke übersehen.
Matt Blaze hat damals den wesentlichen Fehler entdeckt. Woher aber nimmt man die Gewissheit, dass Leute wie er das selbst publizieren und nicht an die Mafia verkaufen?
Bei der Enigma war das Verfahren ja auch nicht neu, das System gab’s ja schon vorher, wurde nur etwas aufgepeppt. Den Deutschen hat nicht nur der falsche Umgang das Genick gebrochen, sondern auch die Kombination mit einem schweren Konstruktionsfehler der Enigma, nämlich dem Reflektor, dessentwegen kein Buchstabe auf sich selbst abgebildet wurde. Die Schwäche war übrigens vom Jefferson Wheel schon bekannt. Vor allem durch diese Schwäche war es möglich, solche Floskeln und die Wetterberichte an die passende Stelle zu schieben und Known Plaintext anzugreifen. Übrigens haben die Allierten auch völlig unsinnige Angriffe auf bekannte Positionen gemacht, weil sie so die Deutschen dazu brachten, bekannte Positionen durchzufunken.
Gerade bei der Enigma kann man aber sehr schön darüber diskutieren, ob die Verdrahtung der Walzen Teil des Verfahrens oder Teil des Schlüssels sind. Bei den meisten Blockchiffren sind die Boxen Teil des Verfahrens.
“das Chiffrat ist so lang wie der Quelltext”
Das ist wie so oft Implementierungssache.
Man kann im fertigen Protokoll auch komprimieren(sofern es der Klartext zulässt) oder das Chiffrat mit Schlüssel-/Müllbits auffüllen um es künstlich zu verlängern, aber das ist Sache der Implementierung/des Protokolls nicht Sache des Algorithmus.
Mir fällt was Schreckliches ein : Beim OTP sollte man kein Buch verwenden, sondern die Buchstaben per Urne ziehen (gleiche Verteilung aller Buchstaben). Sonst könnte man aus der Häufigkeit der Buchstaben und von Wörtern (z.B. die, das, ein …) relativ leicht auf den Originaltext und Text der Verschlüsselung kommen.
P.S.: Meine Verehrung für Marian Rejewski, der ohne weitere Hinweise seines Chefs, die Enigma geknackt hat.
Ja, sonst ist es eben eine Vernam-Chiffre und nicht gleich ein OTP.
Die ist aber – je nach dem Verrechnungsverfahren – auch schon ziemlich schwierig und dieser Text auf dem Zettel so kurz, dass es schwer werden dürfte, das auseinanderzufummeln. Normalerweise bricht man solche Verfahren mit Klartext als Schlüssel so ohne weiteres auch nur dann, wenn das Verfahren bekannt oder trivial ist. Wenn da noch irgendein Würfel oder irgendeine Permutation dazukommt, ist mit einem so kurzen Text und so ganz ohne Hinweise kaum etwas auszurichten.
Die Geheimhaltung des Verfahrens muß natürlich nicht ein völlig neues Verfahren verbergen, sondern kann auch nur eine Kombination bekannter Verfahren sein. AKA Kompression durch Codetabelle und dann folgende Verschlüsselung durch Verfahren X aus der Liste geprüfter Verfahren. Da kann man immer noch beim Schlüsselaustausch verkacken, aber auch da gibt es genügend Prozesse in der Schublade.
Was ich nicht mitbekommen habe ist, warum der Text englisch sein soll. Hat man das an der Taubensorte oder der Kapsel festgemacht ? Wenn es eine militärische Nachricht ist, wird es ohnehin schwierig, da die fast sicher nach Handbuch codiert ist, um Platz zu sparen.
Das war doch mal ein richtig interessanter Beitrag.
Unizitätslänge, kannte ich noch nicht… bin aber auch kein Krypto-Spezi.
Das dahnterliegende Problem, daß man aber im Prinzip alles als Resulttat bekommen kann, wenn man keine weiteren Anhaltspunkte hat, entspricht aber auch meinem Verständnis dieser Problematik.
Den Rundumschlag gegen die “Experten” der verschiedenen Zirkel, fand ich ganz amüsant. 🙂
Vielleicht steht hinter dem Text ja auch garnichts sinnvolles.
Könnte janauch einfach Bullshitnsein, den man verschickt hat, um beim Codeknacken falsche Inputs zu verbreiten.
Hat sowas auch einen eigenen Begriff in der Kryptowelt?
… oder …vielleicht war es auch das Kind eines brieftaubenzüchters, das bloß Agent und Krieg spielen wollte, und die Kryptoforscher rätseln, obwohl es nichts zu entschlüsseln gibt… 😉
Habe mal nachbUnizitätdlänge gegoogelt und das hier gefunden:
“Im Hochsicherheitsbereich kann die Abwägung aber durchaus zugunsten der Geheimhaltung des Verfahrens hinauslaufen, auch wenn eine Vielzahl von Leuten aus dem Security-Dunst behauptet, dass ein nicht offengelegtes Verfahren per se nicht sicher sei. Das ist halt auch so leicht dahergeschwafelt, einer der üblichen Allgemeinplätze und Bauernregeln.”
Ich stimme dir ja grundsätzlich zu, aber ganz so dahergeschwafelt ist das nicht. Natürlich ist es nicht per se unsicher, aber man tut sehr gut daran, ihm grundsätzlich zu misstrauen. Die Telekom hatte da mal was, was sie sogar veröffentlicht haben, und bei dem sie sich wohl auch recht sicher waren, dass es taugt.
http://de.wikipedia.org/wiki/Magenta_(Algorithmus)
Ging fürchterlich in die Hose 😀
Spätestens wenn man damit rechnen muss, dass der Feind einen Alan Turing herumsitzen hat, sollte man sich verdammt sicher sein, dass die Eigenentwicklung wirklich keine Schwachstellen hat. Das läuft auf die beschriebene Abwägung hinaus, bei der die enorme Schwierigkeit einen guten Algorithmus zu entwerfen und nicht der eigenen Blindheit zu erliegen, sicher nicht dahergeschwafelt ist…