8.2.3. Betriebsmodi von Blockchiffren

Bisher haben wir nur darüber gesprochen, daß Blockchiffren einen Bitblock bestimmter Länge (z.B. 64 Bit bei DES, Triple DES und IDEA) ver- bzw. entschlüsseln. Jetzt wollen wir uns ansehen, auf welche Weise man in der Praxis auftretende Nachrichten verschlüsseln kann, die manchmal weniger, in der Regel aber deutlich mehr als 64 Bit umfassen, wobei die Bitanzahl oft kein ganzzahliges Vielfaches der Blocklänge ist.

Für den DES wurden in der 1980 veröffentlichten NBS FIPS PUB 81 (DES Modes of Operation) folgende vier Betriebsmodi definiert:

Sie sind nicht auf DES beschränkt, sondern bei allen blockorientierten Verfahren anwendbar. Es ist generell ratsam, sich in eigenen Applikationen auf die Nutzung dieser genormten, nicht übermäßig komplexen Modi zu beschränken und keine eigenen zu kreieren, da man sonst immer Gefahr läuft, die Sicherheit des Gesamtsystems zu reduzieren bzw. die Komplexität unnötig zu erhöhen. Ein Beispiel hierfür ist der in Version 4 des Authentifizierungssystems Kerberos zur Integritätssicherung eingesetzte, nicht standardisierte Modus PCBC (Propagating Cipher Block Chaining), der dem CBC ähnelt. PCBC enthielt einen subtilen Fehler, weswegen er in Kerberos Version 5 durch den CBC ersetzt wurde.

ECB

ECB ist die wohl naheliegendste Form der Nutzung eines Blockalgorithmus. Man zerlegt die gesamte Nachricht in n-Bit-Blöcke und verschlüsselt jeden Block separat mit demselben geheimen Key. Die Zahl n entspricht der Blocklänge der jeweiligen Chiffre, z.B. 64 bei DES und IDEA. Der letzte Block wird bei Bedarf auf volle n Bit aufgefüllt. Dies bezeichnet man als Padding.

Grafisch läßt sich die Verschlüsselung so veranschaulichen:

Die Entschlüsselung erfolgt analog:

Die Symbole E und D stehen wie gewohnt für encryption und decryption.

Solange man einen konstanten Key verwendet, wird derselbe Klartextblock immer wieder auf denselben Geheimtext abgebildet. Man könnte also theoretisch ein riesiges Code-Buch (daher der Name ECB) vorausberechnen, das alle möglichen Paare von Klar- und Geheimtext enthält. Dieses Vorhaben scheitert in der Praxis allerdings am zeitlichen Aufwand sowie am benötigten Speicherplatz, da bei 64 Bit Blocklänge 264 solche Paare existieren. Dazu wäre für alle Schlüssel (256 bei DES, 2112 bzw. 2168 bei Triple DES und 2128 bei IDEA) ein eigenes Code-Buch nötig.

Da identische Klartexte identische Chiffrate erzeugen, gestattet die Analyse des Geheimtextes in der Regel viele Rückschlüsse auf den Klartext. Weiß der Angreifer z.B., daß eine Tabelle mit einer regelmäßigen Spalten- und Zeilenstruktur übertragen wird, kann er u.U. sehr einfach übereinstimmende Werte herausfinden.

Sobald der Kryptoanalytiker einige Klartexte und die zugehörigen Chiffrate kennt, hat er gute Chancen, mit Hilfe eines Code-Buches Teile weiterer Nachrichten zu entschlüsseln, ohne dazu den Key zu benötigen. Oft haben Nachrichten eine sehr regelmäßige Struktur und weisen viele Redundanzen auf. Tendenziell widerspiegeln sich derartige Eigenschaften in den Geheimtexten und ermöglichen unabhängig von der Stärke der zugrunde liegenden Blockchiffre verschiedene statistische Attacken.

Hauptsächlich aus diesem Grund wird der ECB so gut wie nie zur Verschlüsselung von Nachrichten eingesetzt, die länger als ein Block sind.

Manche Autoren nennen noch einen weiteren Nachteil: Man kann ohne weiteres Blöcke umordnen oder auch modifizieren, ohne daß der Empfänger dies sofort bemerkt, da es ja keine Abhängigkeiten zwischen den Blöcken gibt. Wenn die Struktur der Nachricht bekannt ist, lassen sich möglicherweise relativ gezielte Manipulationen realisieren, indem man einen Block des Geheimtextes gegen einen anderen ersetzt.

Nehmen wir an, die Nachricht enthält eine Aufstellung der aktuellen Preise bestimmter Waren, wobei der Angreifer die Reihenfolge der Angaben sowie die Position der Preise innerhalb der identisch strukturierten Zeilen kennt. So kann er ohne Probleme ganz gezielt eine Gleichsetzung ausgewählter Werte vornehmen.

Diese Tatsache stellt allerdings kein ernstes Problem dar, da eine zum Zwecke der Geheimhaltung vorgenommene Verschlüsselung ohnehin nicht implizit zum Schutz der Integrität der Nachrichten verwendet werden sollte. Dies werden wir weiter unten noch genauer diskutieren.

CBC

CBC sorgt dafür, daß wiederholt auftretende Klartextteile jeweils verschiedene Chiffrate erzeugen. Dies erreicht man sehr einfach durch eine Verkettung (daher der Begriff Chaining) der Verschlüsselungsoperationen: Der aktuelle Klartextblock wird vor seiner Chiffrierung mit dem Geheimtext des vorangegangenen Blocks XOR-verknüpft. Damit hängt das Resultat nicht mehr wie beim ECB ausschließlich vom gerade verarbeiteten Klartextblock, sondern zusätzlich von all seinen Vorgängern ab. Auf diese Weise gelingt es, den schwerwiegendsten Nachteil des ECB zu beseitigen.

Bei der Chiffrierung ergibt sich folgendes Bild:

Die Umkehrung dieser Operation, d.h. die Dechiffrierung, ist sehr leicht zu realisieren:

Da der erste Block keinen Vorgänger hat, wird er mit einem als Initialisierungsvektor IV (initialization vector) bezeichneten Block XOR-verknüpft. Schneier empfiehlt, für alle mit demselben Key durchgeführten CBC-Verschlüsselungen unterschiedliche (unique) IVs zu verwenden, da dies zu dem sehr wünschenswerten Effekt führt, daß das wiederholte Chiffrieren ein und desselben Klartextes jeweils verschiedene Geheimtexte erzeugt. In der Praxis nutzt man sehr häufig Zeitstempel oder zufällig gewählte Bitfolgen als IV.

Um eine maximale Sicherheit erreichen zu können, raten verschiedene Autoren dazu, den IV genau wie den Key geheimzuhalten. Hierzu bietet sich dessen ECB-Verschlüsselung an. Wird der IV offen übermittelt, kann ihn ein Angreifer während des Transports zum Empfänger gezielt verändern und so ausgewählte Bits des ersten Klartextblocks (m1) invertieren. Zunächst existiert bei CBC folgender Zusammenhang:

c1 = EK(IV  XOR  m1)
m1 = IV  XOR  DK(c1)
Betrachten wir nun die Dechiffrierung der einzelnen Bits, wobei der Ausdruck x[i] das Bit Nr. i symbolisieren soll:
m1[i] = IV[i]  XOR  DK(c1)[i]
Unter Ausnutzung der Eigenschaften von XOR ergibt sich, daß die Invertierung eines Bits von IV die Invertierung des korrespondierenden Bits des Klartextes zur Folge hat. Die Invertierung wird durch einen Apostroph gekennzeichnet:
m1[i]' = IV[i]'  XOR  DK(c1)[i]

Obwohl die genannte Bedrohung zweifelsohne existiert, vertritt Schneier zu diesem Thema eine andere Position. Er betrachtet den IV als Dummy-Chiffratblock und argumentiert, daß die in der obigen Abbildung gezeigten Geheimtextblöcke c1 bis c4 in bezug auf die Klartextblöcke m2 bis m5 diesselbe Wirkung haben wie der IV auf m1. Da man die ci nicht speziell schützt, ist dieser Schutz auch für IV überflüssig. Man kann ihn also getrost im Klartext übertragen.

Dieser Argumentation ist zuzustimmen. Man sollte generell beachten, daß es sich bei CBC um einen Mechanismus handelt, der Vertraulichkeit, nicht aber die Integrität der Nachrichten gewährleistet. Angreifer sind wie bei ECB in der Lage, einzelne Blöcke zu modifizieren bzw. umzuordnen.

Man könnte nun einwenden, daß durch die bei CBC vorgenommene Verkettung der Operationen eine gezielte Manipulation des Klartextes sehr erschwert wird und daß durch sie (falls sie gelingt) andere Teile der Nachricht in Mitleidenschaft gezogen werden, so daß man die Attacke doch bemerkt. Dabei ist allerdings zu bedenken, daß vielleicht ein Mensch solche Manipulationen erkennt, allerdings meist auch nur, wenn es sich um relativ kleine, textuelle Informationen mit bekannter Struktur handelt. Spätestens dann, wenn Computer miteinander kommunizieren und dabei sehr große Mengen von Binärdaten austauschen, versagt diese Art des Integritäts-Checks endgültig.

In seiner 1995 geäußerten Kritik der Drafts zur IP-Sicherheits-Architektur [http://wwwcsif.cs.ucdavis.edu/~rogaway/papers/draft-rogaway-ipsec-comments-00.txt] hat der Kryptologe Phil Rogaway unter der Überschrift Encryption does not guarantee integrity deutlich darauf hingewiesen, daß es sich bei Vertraulichkeit und Authentizität (Rogaway versteht Authentizität und Integrität als Synonyme) um zwei separate Ziele handelt, die man unabhängig voneinander durch unterschiedliche Mechanismen erreicht. DES-CBC findet dabei sogar eine spezielle Erwähnung:

A (secure) encryption scheme is any mechanism that achieves privacy. A (secure) message authentication scheme is any mechanism that achieves authenticity. In practice, encryption schemes never achieve authenticity. For example, the "ideal" encryption scheme --a one time pad-- does not achieve authenticity. Nor does DES-CBC encryption. For example, it is trivial, given the DES-CBC encryptions of a set of known messages, to assemble the DES-CBC encryptions of an enormous number of known, new messages.
"Großmeister" Ron Rivest (Mitautor des RSA-Algorithmus sowie Entwickler des MD5 und einer ganzen Reihe anderer kryptographischer Verfahren) stimmte Rogaway in einem News-Artikel voll zu:
Again, Phil is on target here. The proposed documents have a confused and ambiguous discussion as to how authenticity is to be achieved. The confidentiality and authenticity techniques should be cleanly separated orthogonal mechanisms.

Wir hatten an anderer Stelle bereits gesagt, daß sich die Integrität einer Nachricht durch eine kryptographische Prüfsumme (MAC) sicherstellen läßt und daß zu deren Berechnung symmetrische Algorithmen verwendet werden können. Da die CBC-Chiffrierung unabhängig von der konkret eingesetzten Blockchiffre bereits eine schlüsselabhängige Einweg-Hashfunktion darstellt, bietet sie sich als ein sehr einfaches Verfahren zur MAC-Berechnung an.

Dieser sog. CBC-MAC ist u.a. in der NBS FIPS PUB 113 (Computer Data Authentication) aus dem Jahre 1985 sowie dem ANSI-Standard X9.9 beschrieben. Er wird in der Praxis weltweit sehr häufig genutzt, z.B. durch Banken zur Absicherung elektronischer Transaktionen. Als Hashwert verwendet man einen bestimmten Teil (n Bits) des letzten Geheimtextblocks. Der IV besteht in der Regel nur aus Null-Bits und kann daher weggelassen werden:

Sofern der letzte Klartextblock kürzer als die Blocklänge ist, wird er mit Null-Bits aufgefüllt. Bei Menezes findet sich der Hinweis, daß man die kryptographische Stärke des Verfahrens noch erhöhen kann, indem man den MAC nicht direkt aus dem letzten Geheimtextblock ci, sondern aus

EK(DK1(ci))
ableitet (im obigen Beispiel hat i den Wert 5). Dabei ist K der für den CBC verwendete geheime Schlüssel und K1 ein von diesem verschiedener Key. Das Chiffrat ci wird also zunächst mit K1 dechiffriert und danach mit K chiffriert, bevor man die n Bits für den MAC entnimmt. D.h., der MAC entstammt einem Geheimtextblock, der mit der vom Triple DES her bekannten Methode EDE erzeugt wurde.

In vielen neueren Protokollen und Anwendungen (u.a. SSL/TLS und SSH) basiert die MAC-Berechnung nicht mehr auf symmetrischen Chiffren, sondern auf speziell konstruierten Einweg-Hashfunktionen, momentan hauptsächlich MD5 und SHA-1. Details dazu werden wir später noch kennenlernen.

Zusammenfassend läßt sich sagen, daß der CBC wegen der dabei realisierten Verkettung ein geeigneter Modus zur Verschlüsselung von Nachrichten (und auch Dateiinhalten) ist, deren Längen die Blocklänge der zugrunde liegenden Chiffre übersteigen. Möchte man sowohl die Vertraulichkeit als auch die Integrität einer Nachricht mittels CBC sichern, so wird empfohlen, zwei unterschiedliche Keys zu nutzen: einen für die Datenverschlüsselung und den anderen für den MAC. Dies hat natürlich die etwas unangenehme Konsequenz, den CBC-Algorithmus zwei Mal anwenden zu müssen.

Sofern die Länge des Klartextes kein ganzzahliges Vielfaches der Blocklänge ist, füllt man den letzten, kürzeren, j Bits umfassenden Block mi in der Regel durch Padding entsprechend auf. Daraus resultiert natürlich, daß das Chiffrat länger als der Klartext wird. Sollte dies in einer bestimmten Situation inakzeptabel sein, besteht ein möglicher Ausweg darin, den vorletzten Geheimtextblock nochmals zu verschlüsseln (EK(ci-1)) und dessen j höchstwertige Bits mit mi über XOR zu verknüpfen, so daß ci eine Länge von genau j Bits hat.

Für den Einsatz des Triple DES existieren verschiedene CBC-Varianten. Zwei der bekanntesten sind die häufig als Inner-CBC und Outer-CBC bezeichneten Modi, die sich in der Art der Verkettung (innen oder außen) unterscheiden. Beim Inner-CBC wird die komplette Nachricht in drei Schritten verschlüsselt, entschlüsselt und wieder verschlüsselt, jeweils natürlich im CBC-Modus. In der Praxis kommen dabei meist zwei Schlüssel zum Einsatz, K1 für Schritt 1 und 3 sowie K2 für Schritt 2:

In der Praxis nutzt man meist den Outer-CBC, bei dem der Verschlüsselungsschritt E durch EDE (also die bekannte Folge Verschlüsselung, Entschlüsselung, Verschlüsselung) ersetzt wird, wobei gewöhnlich wieder zwei Keys zur Anwendung kommen:

Der Inner-CBC ist die prinzipiell effizientere Variante, da man durch den Einsatz von drei verschiedenen Verschlüsselungs-Chips und deren geeignete Verkettung erreichen kann, daß die gesamte Operation genauso schnell wie bei einfacher (DES-)Verschlüsselung abläuft. Beim Outer-CBC besteht diese Möglichkeit nicht. Dafür ist dieser Modus, wie Untersuchungen von Eli Biham gezeigt haben, wesentlich resistenter gegen die differentielle Kryptoanalyse.

Anmerkung:

Der Draft des neuen ANSI-Standards X9.52 (Triple Data Encryption Algorithm Modes of Operation) enthält die Spezifikation einer als CBCM bezeichneten Variation des Outer-CBC, die mit dem Ziel konstruiert wurde, zwei bekannten, von Eli Biham entwickelten Attacken zu widerstehen. Eine Beschreibung des CBCM sowie eine kryptoanalytische Untersuchung, die eine neue Attacke vorstellt, finden Sie in dem von Eli Biham und Lars R. Knudsen publizierten Paper Cryptanalysis of the ANSI X9.52 CBCM Mode http://www.cs.technion.ac.il/users/wwwb/cgi-bin/tr-get.cgi/1998/CS/CS0928.ps.gz.

CFB

Beim CFB nutzt man eine Blockchiffre zur Konstruktion eines Pseudozufallszahlen-Generators und verknüpft dessen Ausgabe über XOR mit der Nachricht, wie wir das schon beim One-time Pad gesehen hatten (dort allerdings mit einer echt zufälligen Bitfolge). Auf diese Weise entsteht eine Stromchiffre.

Der CFB gestattet es, Dateneinheiten zu verarbeiten, deren Bitanzahl n kleiner als die Blocklänge der verwendeten Chiffre ist. Deshalb spricht man allgemein auch vom n-Bit CFB. Bei den drei betrachteten Algorithmen DES, Triple DES und IDEA kann n jeden Wert von 1 bis 64 annehmen. Da man in der Praxis typischerweise Bytes überträgt, wird der Wert von n in der Regel ein Vielfaches von 8 sein, meist konkret 8 oder 64.

Die jeweils anfallenden Daten können beim CFB ohne zusätzliche Vorkehrungen sofort ver- bzw. entschlüsselt und weitergeleitet werden. Im Gegensatz dazu benötigen CBC und ECB immer volle Blöcke. Das bedeutet, man muß beim Chiffrieren entweder warten, bis genug Daten zusammengekommen sind, oder diese Daten selbst durch Padding bereitstellen. Letzteres hat den Nachteil, daß das Chiffrat länger wird. Ersteres ist in vielen Applikationen inakzeptabel, da z.B. ein Anwender bei der entfernten Rechnernutzung erwartet bzw. darauf angewiesen ist, daß seine Eingaben mit minimaler Verzögerung übertragen werden.

Zur Realisierung des oben erwähnten Pseudozufallszahlen-Generators operiert die Blockchiffre beim CFB über einem Schieberegister, dessen Breite der Blocklänge entspricht (also häufig 64 Bit) und in dem durch zyklische Verschlüsselung nach und nach die Zufallszahlen entstehen (wir meinen mit Zufallszahlen natürlich Pseudozufallszahlen). Um eine definierte Ausgangssituation zu schaffen, wird das Register zu Beginn mit einem Initialisierungsvektor IV gefüllt, der sowohl dem Sender als auch dem Empfänger bekannt sein muß, um sicherzustellen, daß beide Partner identische Zufallsfolgen erzeugen.

Der IV ist nicht geheim. Schneier fordert aber, für alle mit demselben Schlüssel durchgeführten CFB-Verschlüsselungen unterschiedliche (unique) Initialisierungsvektoren einzusetzen, da anderenfalls der Klartext auf kryptoanalytischem Wege zurückgewonnen werden kann. Als IV eignet sich z.B. die fortlaufende Nummer der jeweils zu chiffrierenden Nachricht. Beachten Sie bitte den Unterschied: Beim CBC wurde lediglich empfohlen, unterschiedliche IV zu wählen, hier wird es gefordert.

Ver- und Entschlüsselung verlaufen bei CFB prinzipiell identisch. Der einzige Unterschied besteht darin, daß Klar- und Geheimtexteinheiten ihre Rollen vertauschen. Betrachten wir hier zunächst den Verschlüsselungsprozeß. Er umfaßt die wiederholte Ausführung folgender Schritte:

  1. Der aktuelle Registerinhalt (anfangs der IV) wird mit dem geheimen Key K verschlüsselt. Als Resultat ergibt sich die nächste Zufallszahl.

  2. Sobald eine neue (n Bit umfassende) Dateneinheit mi des Klartextes bereitsteht, wird sie mit den n höchstwertigen Bits des Schieberegisters XOR-verknüpft. Dadurch entsteht das zugehörige Chiffrat ci.

  3. ci wird abgesendet und außerdem von rechts in das Schieberegister hineingeschoben, wodurch die zuvor für XOR verwendeten n höchstwertigen Bits verlorengehen. Hier findet also über den jeweils erzeugten Geheimtext eine Rückkopplung (deswegen Cipher Feedback) vom Ausgang der Blockchiffre auf deren Eingang statt.

    Dies hat wie bei CBC eine Verkettung der Operationen zur Folge, d.h., ci hängt vom gesamten Klartext bis einschließlich mi ab. Aus diesem Grunde ist der CFB auch für die Berechnung von MACs nutzbar. Als Hashwert verwendet man dabei in der Regel den Wert, der nach der Verschlüsselung der gesamten Nachricht im Schieberegister steht (also nicht die letzte Geheimtexteinheit, sondern die erste nach ihr erzeugte Zufallszahl).

Grafisch läßt sich der beschriebene Ablauf so darstellen:

Die Dechiffrierung muß obige Operation umkehren. Da die Verschlüsselungsfunktion für jedes mi die schon bekannte Form

   ci = f(mi) = mi  XOR  zzi
aufweist, kennen wir sofort die zugehörige inverse Funktion:
   mi = f(ci) = ci  XOR  zzi
Das heißt, wir müssen dieselbe Folge von Zufallszahlen zzi wie bei der Chiffrierung erzeugen, diese aber jetzt mit den Geheim- statt mit den Klartexteinheiten XOR-verknüpfen. Weitere Änderungen sind nicht erforderlich. Die Blockchiffre wird also beide Male ausschließlich zur Ver- und niemals zur Entschlüsselung benutzt.

Bei der Dechiffrierung ergibt sich somit folgendes Bild:

OFB

Der OFB ist dem CFB sehr ähnlich. Beide unterscheiden sich dadurch, daß man zur Rückkopplung nicht das aktuell über die XOR-Verknüpfung mit mi gebildete Chiffrat ci, sondern n Bits vom linken Rand des Schieberegisters und damit unmittelbar vom Ergebnis (Output) der Blockchiffrierung verwendet (daher der Begriff Output Feedback). Er erfolgt also eine Linksrotation des Registerinhalts.

Chiffrierung:

Dechiffrierung:

Da beim OFB im Gegensatz zum CFB die erzeugte Zufallsfolge nicht vom Chiffrat abhängt, läßt sie sich beliebig weit vorausberechnen. Dadurch kann man die Geschwindigkeit der Ver- bzw. Entschlüsselung (natürlich auf Kosten von entsprechend viel Speicher) deutlich erhöhen, da dann nur noch die sehr einfache Operation XOR aussteht.

Die fehlende Verkettung hat zur Folge, daß jemand, der den zu einem Geheimtext C gehörenden Klartext M kennt, die Nachricht ganz gezielt verändern kann, indem er C sowohl mit M als auch mit dem von ihm gewählten neuen Inhalt XOR-verknüpft.

Für alle Verschlüsselungen mit demselben Key sollten wieder unterschiedliche IVs verwendet werden. Anderenfalls ist z.B. ein Angreifer, der den zum Chiffrat C gehörigen Klartext M in Erfahrung gebracht hat, in der Lage ist, die zur Verschlüsselung genutzte Zufallsfolge ZF zu rekonstruieren. Diese ist durch Key und IV eindeutig bestimmt und ergibt sich bei der XOR-Verknüpfung von C und P. Die Kenntnis von ZF gestattet es, jeden Klartext zu ermitteln, der mit ihr chiffriert wurde. Bei unterschiedlichen IVs betrifft dies nur genau den einen Klartext, den der Angreifer sowieso schon kennt.

Fehlerfortpflanzung

Die Diskussion der vier Betriebsmodi wollen wir mit einigen kurzen Bemerkungen dazu abschließen, wie sich im Chiffrat enthaltene Fehler auf den bei der Dechiffrierung erzeugten Klartext auswirken. Man unterscheidet dabei zwischen einer Bitmodifikation (aus 0 wird 1 und umgekehrt) und Synchronisationsfehlern (Löschen oder Einfügen einer bestimmten Anzahl von Bits).


© Holger Trapp, 13.10.1998