Die Jentzsch-Chiffre – gibt’s die noch?

Vor einiger Zeit tauchte auf den Webseiten des CrypTool, die laut Impressum von der Professorin Claudia Eckert am “Fachgebiet Sicherheit in der Informationstechnik” an der TU Darmstadt gehostet werden, ein dubioser Kryptowettbewerb auf, bei dem 10.000 Euro auf das Brechen eines gegebenen Chiffrats ausgesetzt wurden.

Freilich verschwand der Wettbewerb sofort wieder, nachdem das Institut eine Menge Buh-Rufe erhalten und sich quasi blamiert hatte. Der Wettbewerb ist noch unter www.krypto-sida.de zu erreichen. Zu dem Wettbewerb und den Reaktionen darauf gab es zwei Meldungen im Newsticker.

Seltsam war (siehe zweiten Heise-Artikel), daß die Professorin erklärte, daß man die Seiten nur gehostet habe, aber nicht Veranstalter war, und dem Wettbewerb wegen der “Geheimniskrämerei” sowieso ablehnend gegenüber gestanden habe. Fremde Seiten zu hosten ist eine meines Erachtens höchst seltsame Weise, seiner Ablehnung Ausdruck zu verleihen. Das scheint eher so, als ob die Professorin und die Macher des “Cryptool” nicht gemerkt haben, wie dubios das ist, und dann schnell die Meinung gewechselt haben. Fähnchen im Wind.

Eine Chiffre, die auf Geheimhaltung des Verfahrens und nicht allein des Schlüssels beruht, taugt nicht viel, weil jeder, der einmal (befugt) eine Nachricht erhalten hat, das Verfahren dauerhaft kompromittieren kann. Man kann es nicht mehr durch Schlüsselwechsel wieder zur vollen Stärke bringen. Schon daher gehört eine Chiffre, die man selbst geheimhalten muß, gleich auf den Kompost. Unter Kryptologen oder allgemein Sicherheitsspezialisten nennt man es die Kerckhoffs’sche Maxime (Kerckhoffs’ principle), oder negativ ausgedrückt Security by Obscurity.

Werfen wir einen Blick in Eckerts eigenes Buch IT-Sicherheit (Seite 282 in der 4. Auflage):

“…das bekannte Kerckhoffs-Prinzip, das besagt, dass die Sicherheit eines kryptografischen Verfahrens allein von den verwendeten Schlüsseln abhängen sollte.”

Wußte sie das nicht, obwohl es in ihrem Buch steht?

Oder war die Versuchung, sich auch mit fragwürdigen Wettbewerben Publizität zu verschaffen, stärker?

Sei’s drum. Man kann es ja trotzdem sportlich sehen. Die klassische Kriegs-Kryptoanalyse stand ja meist auch vor dem Problem, die gegnerische Chiffre nicht zu kennen. Es gab Fälle (wie etwa bei der Agenten-Chiffre, mit der der Kanzler-Spion Günter Guillaume seine Anweisungen erhielt), in der zwar nicht bekannt war, welche Chiffre verwendet wird, aber einfach aufgrund guter Kenntnis des Gegners einige typische Verfahren und deren Kombination ausprobiert wurde und zum Ergebnis führte. Das sind Ausnahmen. Die klassische Vorgehensweise ist, sich durch Bestechung oder Gewalt Kenntnis von der Chiffre selbst zu verschaffen. Am besten murkst man gegnerische Agenten ab und läßt sie so verschwinden, daß der Gegner an einen Unfall glaubt und nicht merkt, daß man die Chiffre hat. Die Methode hat was für sich, scheidet hier aber leider aus.

Also könnte man ja zwecks Übung tatsächlich mal ohne Kenntnis der Chiffre an die Sache gehen.

Könnte man?

Jedenfalls nicht ohne einige Kenntnisse oder Vermutungen über das Umfeld des Chiffrenautors zu haben und Vermutungen zu haben, was er verwendet hat. Und zwar aus einem frappierenden Grund: Es ist zu wenig Chiffrat da, um die Unizitätslänge für den allgemeinen Fall zu erreichen.

Die Unizitätslänge ist erreicht, wenn das Chiffrat bzw. der zugehörige Klartext lang genug sind, damit die enthaltene Redundanz (z. B. bei natürlicher Sprache) länger als der Schlüssel ist, daß man also bei gegeben Chiffrat über dem Schlüsselraum (statistisch) nur noch einen Klartext erhält, der etwa der deutschen Sprache angehört. Wieviel Entropie und Redundanz ein Text enthält, ist aber sehr schwierig zu bestimmen, denn kontext- und sprecherabhängig. Zumal hier noch die Angabe dabei war, daß es sich um einen Lebenslauf handelt. So grob und wüst über den Daumen gepeilt, kann man von etwa 0,8-1,5 Bit Entropie pro Zeichen deutscher Sprache ausgehen, wobei noch Sonderzeichen, Groß- und Kleinschreibung usw. einen erheblichen Einfluß haben.

Das mitgegebene Chiffrat hatte 1107 Zeichen, im Alphabet waren 66 verschiedene Zeichen zu finden, wobei aber / und möglicherweise . als Kontrollzeichen auftauchen.

Geht man von 64 Zeichen im Alphabet aus, könnte es sich um Groß- und Kleinbuchstaben, 10 Ziffern und zwei Satzzeichen handeln (26+26+10+2). Eher wäre aber damit zu rechnen, daß mehr Satzzeichen (Leerzeichen, Komma, Punkt,…), eventuell Umlaute vorkommen, aber dafür nicht alle Zeichen verwendet wurden (x,X,Q), falls überhaupt einzelne Zeichen und nicht Zeichengruppen umgesetzt werden. Tun wir mal so als ob und vermuten, daß der Klartext so lang wie das Chiffrat ist, also ungefähr 1100 Zeichen. Bei einer Schätzung von 3 Bit Redundanz pro Zeichen trüge das Chiffrat also rund 3300 bit Redundanz in sich.

Die Unizitätslänge wäre dann erreicht, wenn diese Redundanz sowohl den Schlüssel, als auch den Chiffre-Algorithmus eindeutig festlegen würden. Wobei man den Algorithmus z. B. durch seine Gödel-Nummer darstellen würde. Das wird aber schon deshalb schwierig, weil Programme und deren Gödel-Nummern ja im Gegensatz zu den Schlüsseln nicht längenbeschränkt sind. Selbst bei gegebenem Chiffretext und Klartext gibt es etwa unendlich viele Programme, die dieses Chiffrat erzeugten. Die Unizitätslänge könnte nie erreicht werden, der Algorithmus nie eindeutig bestimmt. Beispielsweise könnten verschiedene Algorithmen zwar bei diesem Quelltext und zum verwendeten Schlüssel dasselbe Chiffrat erzeugen, aber schon bei Änderung von Schlüssel oder Klartext voneinander abweichen.

Hier liegt die Sache aber wieder anders: Denn wir müssen aus dem Chiffrat ja gleich drei Informationen bestimmen: Chiffre, Schlüssel und den Klartext (mal unter der Annahme, daß das Verfahren überhaupt einen Schlüssel verwendet und nicht ein fester Algorithmus ist). Der Klartext ist aber kein einfacher deutscher Prosa-Text, sondern ein Lebenslauf, in dem viele Zahlen vorkommen dürften. Da kommen dann Zeichen vor, die nicht in einen Zusammenhang mit den Nachbarzeichen zu bringen sind, etwa ob jemand sein Abitur am 12. oder am 25. eines Monats gemacht, ob er die Note 1,3 oder 2,4 hatte und ob er im Juni oder Oktober geboren wurde. Es kann gut sein, daß es gleich eine ganze Klasse von Chiffren und Lebensläufen gibt, sich sich nur in den Ziffern unterscheiden.

Informations- und berechenbareitstheoretisch könnte man das auf die Spitze treiben und einfach statt eines Algorithmus eine willkürlich gefüllte Tabelle nehmen, die einfach jedem Klartext-/Schlüsselpaar irgendeine beliebige, aber eindeutige Zeichenfolge zuordnet, der nicht einmal mit der Länge übereinstimmen muß. Damit ist schon theoretisch bewiesen, daß man zu einem gegebenen Chiffrat den Algorithmus nicht herausfinden kann. Ein etwas einfacheres Beispiel wäre, daß man selbst dann, wenn man Chiffrat, Klartext und Schlüssel hat, etwa DES nicht vollständig rekonstruieren kann, weil man ja nicht weiß, ob überhaupt alle Programmteile und Parameter der Boxen verwendet wurden. Vielleicht gibt es ja auch verschiedene Boxen, die für diese Daten diesselben Ergebnisse liefern. Oder wieder anders gesagt: Gegeben sei folgendes Chiffrat der Länge 1 Bit:

1

Wie lauten Klartext und Algorithmus?

Aber man könnte man es sportlich sehen und danach fragen, ob jemand einen beliebigen Algorithmus plausibler Länge (sprich: mit damaligen DDR-Mitteln durchführbar) findet, der mit beliebigem Schlüssel einen beliebigen Text, der als Lebenslauf durchgeht, zu diesem Chiffrat verarbeitet. Klar: Schreibe einen beliebigen Lebenslauf und gib einen Algorithmus dazu, der unabhängig von der Eingabe immer nur exakt dieses Chiffrat ausgibt. Also nur eine einzige Print-Anweisung. Umgekehrt den Lebenslauf ausdrucken (eine besondere Form des oben genannten Tabellen-Algorithmus).

Die gegebene Redundanz von vielleicht 3300 bit reicht vielleicht gerade, um einen kurzen Algorithmus hinreichend zu beschreiben (Achtung: Auch das Schlüssel-Setup muß berücksichtigt werden!). Vielleicht ist der Programmcode sogar wirklich kürzer. Wenn man es darauf anlegt und die richtige Sprache wählt, könnte man einen Doppelwürfel oder eine ähnliche Handchiffre sicherlich mit 3000 Bit schreiben. Eine Caesar-Chiffre wäre auch trivial hinzuschreiben. Vor einigen Jahren machte mal ein RSA in einer Zeile Perl die Runde. (Was “geschummelt” war, denn tatsächlich steckt viel in den eingebauten Bibliotheken und externen Programmen, die natürlich zu berücksichtigen sind.) Nur weil es kurz hinzuschreiben ist, ist RSA ja auch noch nicht unsicher. Aber man muß RSA auch nicht geheimhalten.

Ist die Jentzsch-Chiffre also mit dieser Aufgabenstellung knackbar?

Ausgeschlossen ist es nicht, vielleicht ist sie wirklich schwach genug, um sie zu brechen. Aber sicher ist es eben auch nicht. Und wenn man schon einen Kryptowettbewerb ausschreibt, sollte man sich auf jeden Fall vergewissern, daß er zumindest prinzipiell lösbar ist. Denn sonst besteht die Gefahr, daß man hinterher die Sicherheit darauf zurückführt, daß man sagt, daß die Chiffre auch im Wettbewerb nicht gebrochen wurde, nicht einmal bei Preisgeld. Dabei könnte das daran liegen, daß nicht die Chiffre, sondern die Aufgabenstellung nicht zu brechen ist. Oder sich die seriösen Leute von vornherein abwenden. Das ist ungefähr so ähnlich, als wollte man die Unfallsicherheit eines Autos damit beweisen, daß man seit 10 Jahren damit gesund fährt, in Wirklichkeit aber keinen Unfall hatte – also nicht weiß, wie sich das Auto beim Crash verhält. Schon aufgrund dieser vagen Ergebnisse verbietet sich ein solcher Wettbewerb, weil er eben auf Leute, die so etwas nicht einzuschätzen wissen, eine höchst gefährliche Wirkung hat.

Sehr gut scheint die Chiffre jedoch nicht zu sein. Die Zeichenwahrscheinlichkeiten sind ziemlich ungleichmäßig verteilt. Während das v 55 mal vorkommt und das L 48 mal, kommt das R nur einmal und das V nur zweimal vor.

Auch bei Zweiergruppen ergeben sich deutliche Unterschiede: 3D kommt neunmal, Eh siebenmal, aber ab oder 31 nur einmal vor.

Bei Dreiergruppen fällt nicht mehr viel auf. Einige kommen doppelt vor, mehr ist nicht. Ab Vierergruppen ist gar nichts mehr da.

Es gibt weitere Auffälligkeiten: Die Zeichenhäufigkeit hängt von der Position ab. Beispielsweise kommt das kleine h an den geraden Stellen 33mal vor, an den ungeraden Stellen jedoch gar nicht. L kommt auf den ungeraden 35mal, auf den geraden Stellen aber nur 13mal vor. Obwohl 3D neunmal vorkommt, kommt es nur auf den geraden Positionen vor. Davon nur zweimal auf den durch vier teilbaren.

Dafür kommt Lw fünfmal vor, jedoch nur auf den ungeraden Positionen. Davon viermal eine Stelle vor einer durch vier teilbaren Position.

3L und PL kommen fünfmal, LL viermal vor, aber nur auf geraden Positionen.

Aber wenn man weiter sucht, läuft man schon gegen den zu kurzen Chiffretext. Nähere Untersuchungen der Zeichenwahrscheinlichkeiten verlieren sich in den kleinen Häufigkeiten, die sich dann nicht mehr vom “thermischen Rauschen” unterscheiden lassen.

Auffällig ist aber die Signifikanz von Zweiergruppen. Nach der Zahl der Zeichen könnte es sein, daß immer zwei Zeichen zusammen verschlüsselt werden. Würde sich die Ungleichverteilung nur an den geraden Stellen zeigen, könnte man einen Würfel oder Doppelwürfel vermuten, was auch dazu paßt, daß die Chiffre in der DDR entstanden ist. Sie könnte gewisse Ähnlichkeit mit der Agentenhandchiffre aufweisen, von der der Autor vielleicht irgendwo gehört hat.

Störend daran ist, daß sich auch auf den ungeraden Stellen signifikante Zweierfolgen häufen. Etwas ungewöhnliche Häufigkeiten zeigen sich auch, wenn man Zweiergruppen auf Positionen Modulo 6 auszählt. Dazu kommt, daß der Chiffretext aus zwei Teilen zu bestehen scheint und die Endungen aus . und / eine Art Auslaufen eines Automaten zu sein scheint. Damit scheint die Chiffre auf einem zustandsbasierten Automaten (oder positionsabhängiger Verschlüsselung) zu beruhen.

Und da kommt man dann doch in die kryptoanalytischen Probleme, daß einfach zu wenig Substanz da ist. Ob die Auffälligkeiten der Zweiergruppen und der Vierer- und evtl. der Sechserabstände aber vom Algorithmus stammt oder mit dem gewählten Schlüssel zusammenhängt (vgl. Vigenère-Chiffre) ist eigentlich nicht abzuschätzen, weil eben nur ein einziges Chiffrat vorliegt und damit eine Unterscheidung zwischen Schlüssel und Algorithmus kaum möglich ist. Beispielsweise könnten solche Muster auch durch Schlüssel wie aabbcc verursacht werden.

Stellt sich die Frage, ob man von der Jetzsch-Chiffre noch etwas gehört hat…