Kryptologie "Generation Woodstock"

Kryptologie „Generation Woodstock“

Bei „GC2EEC4 - Kryptologie auf dem Holzweg“ ging es um frühmittelalterliche Kryptografie und Kryptoanalyse.

Darum geht es hier in gewisser Weise auch - allerdings eher um das frühe Mittelalter unserer Eltern und Großeltern. Gemeint ist die Zeit der Hippies, Flower-Power, Woodstock und Co.

Während die Blumenkinder noch die bessere Welt suchten, mit Blumen in den Haaren, stieß man nämlich in Behörden und Unternehmen auf ein (nicht ganz) neues Problem. Der Mikroprozessor wurde erfunden; der Computer wurde bezahlbar. Er fand weite Verbreitung und ersetzte Karteien und Archive, berechnete Börsentrends oder wurde zum Werkzeug für Finanztransaktionen.

Der Computer verarbeitete und produzierte Daten - Daten, die mit anderen Computern ausgetauscht werden mussten. Sensible Daten, die vor dem Blick unbefugter Dritter geschützt werden mussten. Die digitale Kryptographie wurde geboren. 1971 veröffentliche Horst Feistel - ein IBM-Mann - ein Verfahren, welches auch heute noch verwendet wird (z.B. bei Blowfish) und unter dem Namen "Feistel-Netzwerk" bekannt ist.

Ein zunächst abstraktes Verfahren, welches die Verknüpfung und Vertauschung der Daten innerhalb eines Datenblocks beschreibt. Zum Leben erwacht das Verfahren, wenn man dessen Funktionsblock füllt, z.B. mit Substitutions-Tabellen oder nichtlinearen mathematischen Funktionen. Im Idealfall erfüllt ein solcher Algorithmus dann daß sogenannte Avalanche-Kriterium (Lawineneffekt). Das heißt: Die Änderung eines einzelnen Klartext-Bits würde jedes chiffrierte Bit (- der z.B. 64 Bits in einem Block -) mit einer Wahrscheinlichkeit von 50% ändern. Der Vollständigkeit halber sei noch erwähnt: Es handelt sich hier um ein sogenanntes symmetrisches Verfahren. Soll heißen: Ver- und Entschlüsselung geschehen mit dem selben Algorithmus und dem selben Schlüssel.

Ein solcher Algorithmus (respektive die so verschlüsselten Daten) wären dann relativ widerstandsfähig gegen Kryptoanalyse; auch gegen moderne Methoden, wie lineare oder differentielle Kryptoanalyse. Als einzige praktikable Angriffsmethode bleibt so nur "Brute Force" - rohe Gewalt; das Durchprobieren aller in Frage kommender Schlüssel.

Derzeit übliche Verfahren verwenden Schlüssellängen von 128 bit. In seinem Buch "Codeknacker gegen Codemacher" rechnet der Autor Klaus Schmeh vor: Ein Brute Force-Angriff gegen eine 128 bit-Chiffre würde selbst unter bestmöglichen Randbedingungen die Lebensdauer unseres Universums überschreiten.

Soviel Zeit bleibt uns nicht, darum wurde in dieser Chiffre nur ein 32 bit-Schlüssel (rund 4 Milliarden Möglichkeiten) gewählt:

17425A43:3FC871C2
B112A679:586F187D
75FCF037:B6BC889D
76111F41:10A7ACC2
FE3A9024:73F57DDC
87200213:82709577
C4650C79:59545103
EF705900:0D5D9460
32261928:6BB18825
D435F787:FB087695

Feistel-Netzwerk

Verschlüsselt wurde die Chiffre nach dem folgenden Schema:
Die ersten 64 Bit sind der Initialisierungsvektor und gehören nicht zur Nachricht – dazu später mehr. Diese 64 Bit sind NICHT verschlüsselt. Die restlichen 64 Bit-Böcke wurden mit einem Feistel-Netzwerk wie unten dargestellt verschlüsselt.

Ein 64 Bit-Datenblock wird in zwei 32 bit-Blöcke geteilt und durchläuft das Netzwerk 10 mal (i = 1..10). Im ersten Durchlauf (i=1) wird der Schlüssel K (- der oben erwähnte 32 bit-Schlüssel -) nicht verändert; bei jeder weiteren Runde wird der Schlüssel wie folgt modifiziert:

Die Schlüssel-Funktion:

Die Runden-Funktion:

Die Runden-Funktion besteht aus zwei Schritten. Als erstes wird folgendes Polynom verwendet:

Was geschieht hier? Bereits für relativ kleine Werte, z.B. K=4 und R=4, bewirkt die Modulo-Funktion eine Sprungstelle und das Ergebnis verläuft nicht mehr linear mit K und R. Anders gesagt: Das Ergebnis springt „wild hin und her“; ein einfacher Rückschluss auf K und R ist nicht möglich (da mehrere Kombinationen von K und R zum gleichen Ergebnis führen). Man spricht hier auch von Konfusion, einem in der Kryptografie durchaus erwünschten Effekt.

Anschließend durchläuft das Ergebnis eine Substitutions-Tabelle (S-Box) der Größe 10x256. Die Tabelle ist zeilenweise (2ter Index, 0..255) mit den hexadezimalen Nachkommastellen (- byteweise angeordnet -) der Zahl π gefüllt. Die Substitution sieht (in C notiert) wie folgt aus:

Erster Index (i): Nummer der Feistel-Runde
Zweiter Index: Byte 3/2/1/0 des Ergebnisses aus f(Ri, Ki)

Warum die Zahl π? Einerseits ist hier durch eine einfache Vereinbarung eine (praktisch unendlich lange) Folge von Ziffern genau definiert. Andererseits können diese Ziffern näherungsweise als Zufallszahlen betrachtet werden.

Die Werte L10 und R10 werden (nach der letzten Runde) wieder zu einem 64 bit-Block zusammen gesetzt; die Block-Verschlüsselung ist abgeschlossen.

Cipher Block Chaining Mode

Die 64 bit-Böcke werden dann im „Cipher Block Chaining Mode“ (CBC) miteinander verkettet. (Vermeidung von Regelmäßigkeiten in der Chiffre, falls mehrere Klartextblöcke den selben Inhalt haben.)

Hierzu wird der Initialisierungsvektor (beim ersten Block) bzw. der vorherige chiffrierte Block (alle weiteren Blöcke) mit dem Klartext-Block vor der eigentlichen Block-Chiffrierung XOR-verknüpft.

Zu guter Letzt

Das oben beschriebene Verfahren ist weder besonders sicher (zu kurzer Schlüssel) noch ist es besonders effizient (aufwendige und langsame Arithmetik wg. Polynomen 8ten Grades) oder besonders trickreich (kryptografische Stärken der S-Boxen werden nur zu einem Bruchteil genutzt). Es bietet jedoch dem Hobby-Kryptologen einen (verglichen z.B. mit AES) relativ einfachen Einstieg in das Gebiet der digitalen Kryptologie und enthält die wesentlichen Elemente, wie sie auch in ernstzunehmenden Verfahren verwendet werden.

Hier noch ein Beispiel-Text für die Erprobung Eurer Implementierung:

Initialisierungsvektor: 0x82EF296A:A4A64469

Schlüssel: 0x00EC654F

Der Klartext: Dies ist ein Test-Text ohne Umlaute.

Der gleiche Text im ANSI-ASCII-Code (8bit), 8 Byte jeweils notiert als 64 Bit-Hex-Wert, mit Initialisierungsvektor und Bit-Padding:

82EF296A:A4A64469
44696573:20697374
2065696E:20546573
742D5465:7874206F
686E6520:556D6C61
7574652E:00000000

Der verschlüsselte Text:

82EF296A:A4A64469
04346F05:D4933C00
1BC351A2:6CDA1184
20A5B95B:1E3E2F84
E651C6A3:B1813287
20748033:5FDF24FA

Die Örtlichkeit

Wer „GC2EEC4 - Kryptologie auf dem Holzweg“ oder „GC2ME0M - Abete Rosso avec Acero corrugado“ mochte, der wird auch dieses Versteck lieben: Harzfrei, mäßig hoch und für routinierte Baumkraxler ohne Hilfsmittel erreichbar. (Dieses Bäumchen hat mich förmlich angefleht: "Bitte häng ein Döschen in meine Krone".) Dem weniger Geübten würde ich zum kleinen Besteck „PSA gegen Absturz“ zur Sicherung während des loggens raten, und wenn die Sonne sich mal wieder rar macht (Feuchtigkeit!) wäre evtl. die klassiche Vorstiegssicherung mit ein paar Zwischensicherungen (Bandschlingen) ratsam. (Überschätzt Euch nicht; es geht ca. 12 m nach oben - oder nach unten; je nach Sichtweise.)

Bis zur nächsten Parkmöglichkeit sind es je nach Platzwahl 1,5-2 km Fußmarsch; mit dem Radl kann man direkt bis an den Baum fahren. Der Cache ist aus westlicher Richtung über einen zweispurigen Forstweg erreichbar (auch wenn dieser in nicht in allen Karten verzeichnet ist). Schont das Wild und geht diese Dose nicht in der Dämmerung an. (Das erspart auch Diskussionen mit dem Jagdpächter, der gerne mal in der Nähe nach dem Rechten sieht.)