Russische Kryptographie

Ach herrje, aus dem Thema bin ich schon so lange draußen.

Ich habe zwar noch immer auch mit Kryptographie zu tun, weil in der IT-Sicherheit, aber so mit den Innereien habe ich mich seit meinem damaligen Weggang von der Uni nicht mehr befasst. Irgendwie war mir die Lust vergangen, aber ich bin durch den Doktor-Crash auch nicht mehr an die Jobs bekommen, in denen man das weiter machen kann, weil man dafür bezahlt wird. Damals habe ich da allerdings ziemlich tief dringesteckt.

Eine Chiffre, mit der ich mich damals mal auseinandergesetzt hatte, war der russische Gost. Hatte damals den Ruf eines Traktors. Denn während die Struktur nicht so sonderlich komplex oder rafiniert war, schlagen sie es einfach mit mehr Runden. Ich weiß es nicht mehr genau, aber wenn ich mich recht erinnere, war das Ding feistelchiffren-ähnlich, aber mit 32 Runden. Was mir damals schon auffiel, war, dass ich die Stärke des Verfahrens eigentlich gar nicht beurteilen konnte, weil nämlich nur ein Teil offengelegt worden war. Die S-Boxen darin waren nicht Teil der Specs, die ich bekommen hatte. Und das war dann schon klar, dass die Güte des Gesamtverfahrens von der Güte der Boxen abhängt, und es nicht so ganz auf den ersten Blick offensichtlich war, was gute Boxen sind (also quasi Tabellen, nach denen Werte per lookup substituiert werden). Ich hatte mir damals mal testweise Software geschrieben, die per vollständiger Iteration alle möglichen Boxen aufzählt und dabei die ausgibt, die eine Liste von Kriterien erfüllt, die ich mir überlegt hatte. Also beispielsweise keine linearen oder statistischen Zusammehänge zwischen Aus- und Eingabebits, dass die Bits untereinander möglichst wenig abhängig sind und sowas noch alles. Beispielsweise, dass die Hintereinanderausführung durch mehrere Runden tatsächlich komplexer ist als eine Runde oder nur weniger Runden, damit keine Scheinkomplexität besteht und sich die Boxen nicht genseitig wieder kompensieren. Ich kann mich nicht mehr dran erinnern, was ich mir damals als Kriterien ausgedacht hatte, aber es waren im Ergebnis nur relativ wenige der möglichen aufgezählten Boxen, die diese Kriterien alle erfüllten. Deshalb hatte ich die Chiffre damals zwar als für den akademischen Lehrbetrieb interessant eingestuft und in die Vorlesung mit reingepackt, weil mal was anderes, aber für den praktischen Einsatz unbrauchbar, weil man sich erst mal Entwurfskriterien für Boxen überlegen und hinreichend geeignete Boxen suchen muss. War übrigens als Software auch auf meiner Workstation, von der einen Kopie an den BND ging.

Ein Leser schrieb mich neulich an und fragte, was ich von einem verschlüsselten Telefon halten würde, das die Russen jetzt anbieten. Tut mir leid, aber das kann ich anhand eines Fotos des Telefons einfach nicht beurteilen.

Auf Golem bin ich gerade über einen Artikel über russische Chiffren gestoßen:

Russische Verschlüsselungsalgorithmen infrage gestellt

Ein Kryptograph weist darauf hin, dass die sogenannten S-Boxen in russischen Verschlüsselungsstandards eine seltsame Struktur aufweisen und dass nirgendwo erklärt ist, wie es dazu kam. Handelt es sich um eine Hintertür?

Eine E-Mail an die Verschlüsselungsarbeitsgruppe der IETF wirft einige Fragen zum Verschlüsselungsalgorithmus Kuznyechik und dem damit eng verwandten Hashalgorithmus Streebog auf. Léo Perrin, ein Kryptograph, der am französischen Forschungsinstitut Inria arbeitet, berichtet darin, dass er die Struktur der sogenannten S-Boxen sehr verdächtig findet.

Kuznyechik und Streebog sind Teil der sogenannten GOST-Standards, die von der russischen Föderation herausgegeben werden. Von der IETF gibt es Spezifikationsdokumente für diese Algorithmen, sie sind als RFC 7801 und RFC 6986 veröffentlicht.

Oh. RFCs von 2013 und 2016. Rund 20 Jahre nach meiner Arbeit damals. Anscheinend sind jetzt S-Boxen veröffentlich worden, damals fehlen sie in der Beschreibungen, waren anscheinend geheim.

S-Box mit unerklärbarer Struktur

S-Boxen sind ein gängiger Baustein von symmetrischen Verschlüsselungsalgorithmen, sie spielen eine wichtige Rolle für die Sicherheit. Die beiden Algorithmen Kuznyechik und Streebog verwenden beide eine S-Box namens Pi, von der nirgendwo erklärt wird, wie sie generiert wurde und welche Überlegungen ihr zugrunde liegen.

Laut Perrin besitzt diese S-Box eine Struktur, die es so nirgendwo anders in der kryptographischen Literatur gibt und die auch kein Zufall sein kann. Bei derartigen Eigenschaften müsste man laut Perrin analysieren, welche Auswirkungen das auf die Sicherheit hat, aber eine solche Analyse gibt es nicht.

Perrin deutet an, dass er sich vorstellen kann, dass es sich hier um eine Hintertür handelt. Er verweist auf eine frühere Forschungsarbeit zu Verschlüsselungsalgorithmen mit Hintertüren, die eine Struktur verwenden, die der hier vorgefundenen ähnlich ist. Allerdings betont Perrin auch, dass er bisher keine Möglichkeit gefunden hat, die gefundenen Eigenschaften anzugreifen.

Ich finde es frappierend, wenn Themen, an denen ich vor über 20 Jahren mal dran war (und abgesägt wurde) und die als tot galten, plötzlich wieder hochpoppen. Denn die Überlegung war damals schon, die russische Chiffre nicht trotz, sondern gerade wegen ihrer skurrilen Herkunft als Alternative zu amerikanischen Chiffren, denen man auch nicht trauen konnte, in Reserve zu halten, weil die sicherlich etwas unabhängiger arbeiten, und in Mathe und Crypto sind die Russen verdammt gut. Vor allem war GOST wegen seiner einfacheren Struktur und stärkeren Durchmischung über die Runden vielleicht nicht unbedingt der schnellste, aber einfacher zu verstehen, und erschien über die vielen Runden als etwas unempfindlicher gegen leichte Schwächen, weil die Durchmischung einfach weitgehend war. Der Knackpunkt waren einfach die S-Boxen. Die zu konstruieren war die Kunst, und das war etwas, an dem ich damals dran war.

Wie gesagt, seit 1998 habe ich mich damit nicht mehr beschäftigt.