Der Recherchekompass
[ home | anleitungen | recherchen | hilfe | sitemap | index | suchen ]

Verschlüsselte Botschaften Moderne symmetrische Verfahren

Genauer gesagt handelt es sich bei modernen symmetrischen Verfahren, um Verfahren die auf symmetrischen Kryptosystemen basieren. Wie bereits in der Einführung dargelegt, zeichnet sich ein symmetrisches Kryptosystem dadurch aus, dass der Chiffrierschlüssel und der Schlüssel zur Dechiffrierung gleich sind oder zumindest in einem so einfachen Zusammenhang stehen, dass sich der eine ohne nennenswerten Aufwand aus dem anderen ableiten lässt. Beide Schlüssel sind also äquivalent, es kann daher von nur einem Schlüssel gesprochen werden.

Abbildung: Kryptografisches System (symmetrisch)

Weil für die Verschlüsselung der gleiche Schlüssel wie für die Entschlüsselung zum Einsatz kommt, ist es unbedingt erforderlich, dass dieser Schlüssel geheim bleibt. Es dürfen also nur Sender und Empfänger im Besitz dieses Schlüssels sein. Daher muss immer wenn Sender und Empfänger zum ersten Mal in Kontakt treten ein eigener geheimer Schlüssel erzeugt und vorab über einen sicheren Kanal zwischen Beiden ausgetauscht werden.

Die meisten der heute eingesetzten symmetrischen Verfahren sind Produktalgorithmen zur Blockchiffrierung. Eine spezielle Gruppe davon wird Feistel-Netzwerke genannt (Horst Feistel, 1970). Dabei wird:

• Zunächst jeder Block in zwei gleich große (linke und rechte) Hälften geteilt.
• Dann werden hintereinander zumeist einfache Schritte ausgeführt, sogenannte Runden. Für jede dieser Runden wird ein eigener Rundenschlüssel verwendet.
  • Der Rundenschlüssel wird mit der rechten Hälfte des Blocks verknüpft.
  • Das Ergebnis wird mittels bitweiser Addition (xor) mit der linken Hälfte verknüpft.
  • Das Ergebnis bildet die neue rechte Hälfte des Blockes und die alte rechte Hälfte wird zur neuen linken Blockhälfte für die nächste Runde.

Bei den modernen, symmetrischen Verfahren hat sich vor allem der Data Encryption Standard (DES) durchgesetzt. Durch fortschreiten der Technik wird die Sicherheit dieses Verfahrens immer fraglicher. Auch die Erweiterung zum Triple-DES, wobei mehrfach überschlüsselt wird, wird nicht mehr als wirklich sicher betrachtet. Ein neues Verfahren, der Advanced Encryption Standard (AES) soll zukünftig für mehr Sicherheit sorgen.

 

• Data Encryption Standard (DES)

  Der Data Encryption Standard (DES) wurde von IBM entwickelt und 1974 beim NBS (heute NIST) eingereicht. 1976 wurde DES als US-Bundesstandard anerkannt. Trotz des Einflusses auf einige ISO-Standards, vollzog kein weiteres Land diesen Schritt. Dies lag sicherlich auch daran, dass der Vorschlag der IBM durch das NSA (National Security Agency) der USA überarbeitet wurde, bevor es zum Standard gemacht wurde. (Dies lässt darauf schließen, dass das NSA bereits zu diesem Zeitpunkt in der Lage war, diesen Code zu knacken.)

  Abbildung: Ablauf der Verschlüsselung mit DES. Der Algorithmus wird 16 Mal durchlaufen, bevor die Ausgangspermutation durchgeführt wird.

  Beim DES handelt es sich um eine Blockchiffre, die auf Blöcken mit 64 Bits arbeitet. Aus den 64 Bit großen Blöcken des Klartextes und erzeugt der symmetrische Algorithmus 64 Bit große Chiffretexte, der Ablauf ist in der Abbildung dargestellt. Der dazu verwendete Schlüssel ist ebenfalls 64 Bit lang, allerdings ist jedes achte Bit ein Paritätsbit ist, so dass nur 56 Bit zur Ver- und Entschlüsselung benutzt werden. (Einige Schlüssel gelten zudem als schwache Schlüssel.)

  Die Sicherheit des Verfahrens beruht auf einer Kombination von Permutationen und Substitutionen. Die Ver- bzw. Entschlüsselung eines 64-Bit-Blocks kann grob in die folgenden drei Schritte zerlegt werden:

  1. Der Eingabeblock wird der Eingangspermutation unterworfen. Hierdurch wird die Reihenfolge der Bits verändert (Transposition). Das Ergebnis wird in zwei 32-Bit-Register geschrieben. Mit den 64 Bit des Schlüssels wird ebenso verfahren, nachdem die 56 relevanten Bits bestimmt worden sind, werden diese ebenfalls transponiert und in zwei 28-Bit-Register geschrieben.

  2. In diesem Schritt werden 16 Mal die gleichen Rechenschritte wiederholt (Runden), wobei in jeder Runde der Schlüssel neu bestimmt wird:
     • Zunächst werden die Bits der "Schlüsselregister" zyklisch um ein bzw. zwei Bit verschoben und 48 der 56 Bit als Rundenschlüssel bestimmt. [1]
     • Das "rechte" Datenregister (R-Block) wird mittels einer Expansion von 32 auf 48 Bit vergrößert.
     • Daten- und Schlüsselblock werden durch logisches XOR miteinander kombiniert.
     • Das Resultat wird in 6 Bit große Abschnitte aufgeteilt und durch acht S-Boxen (Substitutionsboxen) gesandt, die hieraus wiederum 32 neue Bits erzeugen.
     • Zum Schluss werden der Block nochmals einer Transposition unterzogen.
     Der so erzeugte 32-Bit-Datenblock wird mittels XOR mit den Daten des "linken" Datenregisters verknüpft. Das Ergebnis dieser Operationen bildet den neuen Inhalt des rechte Registers, wobei der alte R-Block zuvor ins linke Register geschoben wird.

  3. Nach der 16. Runde werden das linke und rechte Register wieder zu einem 64-Bit-Block zusammengefügt, bevor die zur Eingangspermutation inverse Ausgangspermutation angewendet wird. (Da Eingangs- und Ausgangspermutation zu einander invers sind und nur zu Beginn und am Ende durchgeführt werden, haben sie auf die kryptografische Sicherheit des Verfahrens keinen Einfluss.)

  Beim DES unterscheidet sich die Entschlüsselung nur geringfügig von der Verschlüsselung. Lediglich die Teilschlüssel der 16 Runden müssen in umgekehrter Reihenfolge verwendet werden, der Rest des Algorithmus bleibt unverändert.

  Auch wenn Zweifel angebracht sind (Die Aktivitäten des NSA), so galt der DES lange Zeit als sehr sicher, durch immer bessere Computertechnik kann das Verfahren heute nicht mehr als sicher betrachtet werden, weshalb vom NIST auch die Suche nach dem AES (Advanced Encryption Standard) ausgeschrieben wurde. Die Sicherheit des Verfahrens ist durch die Schlüssel begründet und hier liegen auch die Probleme:

  • Es existieren schwache bzw. semischwache Schlüssel. Bei diesen werden durch die Schlüsselpermutation die Bits so gesetzt, dass die 16 generierten Teilschlüssel nahezu identisch werden.
  • Der gravierendste Schwachpunkt ist aber die geringe Mächtigkeit des Schlüsselraumes von 2⁵⁶, welcher heutzutage einem Brute-Force-Angriff nicht mehr standhalten kann.

  Mit Triple-DES wurde der Versuch unternommen, die Sicherheit des Verfahrens weit genug zu erhöhen, um den Zeitraum bis zur Verfügbarkeit eines besseren Verfahrens zu überbrücken. Triple-DES ist nichts weiter, als dass eine dreimalige Verschlüsselung mit DES vorgenommen wird, dabei werden zwei unterschiedliche Schlüssel wie folgt eingesetzt:

  C = DES(K₁, DES^-1(K₂, DES(K₁, M)))

  Trotz der Schlüssellänge von 156 Bit ist die erreichte Sicherheit nur knapp mit der einer Verwendung eines 128-Bit-Schlüssels vergleichbar.

  Zusammenfassend ist festzustellen, dass die Mängel von DES mittlerweile so schwerwiegend sind, dass das Verfahren heute nicht mehr als sicher einzustufen ist. Auch Triple-DES stellt allenfalls eine Notlösung dar.

  [seitenanfang] [verweise]

   

• International Data Encryption Algorithm (IDEA)

  Als Alternative zum unsicher gewordenen DES entwickelten Xuejia Lai und James L. Massey eine Blockchiffre, die neben einer höheren Sicherheit, vor allem einen größeren Schlüsselraum bot und sowohl besonders in Software eine effizientere Implementierung ermöglichte. Die 1990 vorgestellte Version ließ sich mittels gerade entwickelter Kryptoanalytischer Verfahren brechen, so dass eine Überarbeitung notwendig war, welche ab 1992 den Namen IDEA trug.

  Genau wie beim Data Encryption Standard handelt es sich bei IDEA um eine 64 Bit Blockchiffre, die aber mit einem 128-Bit-Schlüssel arbeitet. Wie beim DES werden die Daten durch wiederholte Anwendung der gleichen Operationen (Runden) verschlüsselt, allerdings benötigt IDEA nur 8 statt 16 Runden. Durch die Verringerung der Runden auf die Hälfte und dadurch, dass es keine Permutationen gibt, bleibt die Rechenzeit bei gleichzeitiger Steigerung der Sicherheit unter der von DES. Besonders bemerkenswert ist, dass keine Bitoperationen verwendet werden, sondern dass stattdessen drei verschiedene Operationen auf 16-Bit-Blöcken verwendet werden:

  		Das bitweise "exklusive oder" (XOR), welches auch der Addition zweier Zahlen ohne (bitweisen) Übertrag entspricht.
  		Die Addition zweier Zahlen modulo 216, das Ergebnis bleibt auf einen 16-Bit-Wert beschränkt. [2]
  		Die Multiplikation zweier Zahlen modulo 216 + 1. Die Randbereiche werden besonders behandelt. (So ist gewährleistet, dass für die Multiplikation ein Inverses existiert, da es sich bei 216 + 1 um eine Primzahl handelt.)

  Mit diesen Operationen ist besonders die Realisierung in maschinenunabhängiger Software wesentlich einfacher. Dadurch wurde der Algorithmus unabhängig von der Hardware, welches beim DES vor allem bei einem Bedarf an schneller Verschlüsselung nahezu unumgänglich war. Durch die Verwendung eines 128-Bit-Schlüssels (DES: 56 Bit) ist IDEA zudem erheblich sicherer.

  Abbildung: Ablauf der Verschlüsselung mit IDEA, dargestellt ist die erste Runde sowie die Abschlusstransformation. Die Runden 2 bis 7 sind gleich der Ersten aufgebaut.

  Die Funktionsweise von IDEA ist aus nebenstehender Abbildung ersichtlich. Jeder 64 Bit große Klartextblock wird zunächst in vier Teilblöcke M1 bis M4 zu je 16 Bit aufgeteilt. Beeinflusst von jeweils 6 Teilschlüsseln werden die Teilblöcke in jeder der acht Runden mit den oben genannten Operationen gemäß Darstellung bearbeitet. Vor Beginn der nächsten Runden werden zudem die "inneren" Teilblöcke vertauscht. In einer abschließenden neunten Runde (Ausgangstransformation) werden die Eingangsoperationen einer Runde ausgeführt, bevor die vier Teilblöcke zum 64-Bit-Chiffreblock zusammengesetzt werden.

  Die erforderlichen 52 Teilschlüssel (6 für jede der acht Runden und 4 für die Abschlusstransformation) werden aus dem 128-Bit-Schlüssel wie folgt gebildet:

  • Die ersten acht 16 Bit langen Teilschlüssel werden direkt durch Zerlegung des Ausgangsschlüssels erzeugt.
  • Danach wird der Schlüssel zyklisch um 25 Bit verschoben und der permutierte Schlüssel erneut in acht Teilschlüssel zerlegt.
  • So wird weiterverfahren, bis die erforderlichen 52 Schlüssel vorliegen.

  Die Entschlüsselung benutzt den gleichen Algorithmus, allerdings werden die Schlüssel in umgekehrter, rundenbezogener Reihenfolge verwendet; d.h. in der ersten Runde der Entschlüsselung werden die gleichen Teilschlüssel verwendet, wie in der neunten Runde der Verschlüsselung (Ausgangstransformation). Die ersten vier Teilschlüssel einer Runde müssen zudem invertiert werden, die beiden anderen Schlüssel sind selbstinvers.

  Wie beim DES existieren auch bei IDEA schwache Schlüssel, bei denen interne Teilschlüssel den Wert Null oder Eins annehmen. (Null zeigt bei der Addition und XOR-Verknüpfung keine Wirkung, ein Teilschlüssel mit dem Wert 1 hat bei der Multiplikation keinen Effekt.) Andere Schwächen sind bislang nicht bekannt. IDEA unterliegt in Europa dem Patentschutz, kann jedoch für nicht kommerzielle Zwecke frei verwendet werden. Trotz der Einschränkung hinsichtlich des kommerziellen Einsatzes, ist IDEA als verbreitetes Verfahren anzusehen, zumal es in PGP (Pretty Good Privacy) eingesetzt wird.
  

  [seitenanfang] [verweise]

   

• Advanced Encryption Standard (AES): Rijndael

  Nach öffentlicher Prüfung wurde im Oktober 2000 Rijndael (gesprochen "reindal"), eine Entwicklung der belgischen Kryptologen Joan Daemen und Vincent Rijmen, in einem mehr als dreijährigen Prozess als Advanced Encryption Standard (AES) ausgewählt. Dieser Algorithmus soll die Nachfolge des DES antreten. Das NIST (National Institute of Standards and Technology) geht von einer Lebensdauer von 20 bis 30 Jahren für den AES aus. Erfahrungen mit Standards zeigen jedoch, dass mit einer weit längeren Lebensdauer zu rechnen ist.

  Bereits im neunzehnten Jahrhundert ging man davon ab, die Stärke eines Algorithmus in seiner Geheimhaltung zu suchen. Heute wird mehr Wert auf Transparenz gelegt, um einen Algorithmen von möglichst vielen Fachleuten untersuchen und b(esp)rechen zu lassen. Daher wurde die Auswahl des AES in einem weltweiten, öffentlichen Wettbewerb zur Entwicklung eines neuen Standards zur symmetrischen Blockchiffrierung von Daten ausgeschrieben.

  Anzahl Runden  Blocklänge in Bit  Schlüssellänge in Bit 128 192 256 128 10 12 14 192 12 12 14 256 14 14 14

  Tabelle: Anzahl der Runden in Abhängigkeit von Block- und Schlüssellänge

  Beim neuen Advanced Encryption Standard handelt es sich um eine symmetrische Blockchiffre mit variablen Block- und Schlüssellängen von 128 bis 256 Bit. Die Verschlüsselung eines Klartextblockes wird in mehreren Runden durchgeführt, wobei deren Anzahl (n) von der Schlüssel- und Blocklänge abhängig ist (siehe Tabelle).

  Für die Ver- und Entschlüsselung muss für jede Runden ein Rundenschlüssel erzeugt werden. Hierzu wird der geheime Schlüssel des Anwenders expandiert, indem rekursiv abgeleitete 4-Byte-Wörter an diesen Anwenderschlüssel angehängt werden. Die Verschlüsselung läuft dann wie folgt ab:

  1. Zunächst wird der Klartextblock mit dem - gegebenenfalls erweiterten - Anwenderschlüssel durch XOR (bitweise Addition) verknüpft.

  2. Dann werden n-1 reguläre Runden durchlaufen, wobei in jeder Runde die folgenden Einzelschritte durchgeführt werden:
     • Substitution:
       Zu Beginn einer Runde wird jedes Byte eines Blockes durch Anwendung einer S-Box ersetzt.
     • Permutation:
       Die Bytes eines Blockes werden in einer vierzeiligen Matrix eingetragen und durch die ShiftRows-Transformation reihenweise zyklisch verschoben.
     • Diffusion:
       Die Bytes der pernmutierten vierzeiligen Matrix des Blockes werden durch die MixColumns-Transformation nochmals spaltenweise permutiert.
     • Schlüsselverknüpfung:
       Zum Abschluss einer Runde wird der Block durch XOR mit dem jeweiligen Rundenschlüssel verknüpft.

  3. Abschließend wird eine weitere Runde durchgeführt, in der allerdings die Diffusionsoperation (MixColumns) ausgelassen wird.

  Beim Entwurf von Rijndael wurde auf alle bekannten Attacken, wie lineare und differenzielle Kryptoanalyse eingegangen, so dass ein Angriff mit allen herkömmlichen Verfahren nicht effizienter sein sollte als ein Brute-Force-Angriff. In den Prüfungen wurde auf das Verfahren viele kryptoanalytische Angriffe durchgeführt. Es konnten keine Sicherheitslücken festgestellt werden. Gemäß Berechnungen des NIST braucht ein Rechner, der DES in einer Sekunde knacken könnte, für Rijndael mit 128-Bit-Schlüssel ca. 149 Billionen Jahre Rechenzeit. (Das Universum ist keine 20 Milliarden Jahre alt.)

  Wie bei allen praktischen kryptografischen Verfahren, kann die Sicherheit jedoch nicht bewiesen werden, auch den anderen Mitbewerbern konnten keine Sicherheitslücken nachgewiesen werden. Der Algorithmus Rijndael überzeugte in der Gesamtbewertung. Ausschlaggebend war einfach die optimale Kombination von Sicherheit mit Geschwindigkeit, der Flexibilität in Schlüssel- und Blocklänge und der effiziente Ressourcenbedarf sowie die einfache Implementierbarkeit in Hard- und Software.

  [seitenanfang] [verweise]

   

• RC4^TM: Rivest Cipher N^o4

  Bei Ron's Code oder der Rivest Cipher No. 4 handelt es sich nun endlich um ein Verfahren zur Stromchiffrierung. Es wurde bereits 1987 von Ronald L. Rivest für RSA Data Security Inc. (heute RSA Security Inc.) entwickelt und lange Jahre geheimgehalten. Im September 1994 veröffentlichte eine anonyme Person in einer Mailing-Liste einen Algorithmus, der zu RC4 identische Ergebnisse erzeugte und daher als "apparantly RC4" gelten kann. Dieser Quelltext verbreitete sich schnell und wurde ausgiebig analysiert und diskutiert. Der hier beschriebene Algorithmus basiert auf Informationen aus dem Internet. Es ist nicht sicher, ob es sich wirklich um den Algorithmus der RSA handelt.

  Schlüssel:
  Klartext: Dies ist ein Klartext.
  Geheimtext:
  [quelltext] Tabelle: Chiffrierung mit "apparantly RC4". [3]

  Im Gegensatz zu DES ist die Schlüssellänge bei RC4 variabel und kann bis zu 2048 Bit (256 Zeichen) betragen, wobei bereits 128 Bit als sicher gelten. Es wird immer ein Byte (ein Zeichen) auf einmal verschlüsselt. Der Algorithmus ist sowohl einfach wie auch sicher und kann besonders einfach und effizient programmiert werden. Bestechend ist der Algorithmus insbesondere, weil er unverändert sowohl zur Ver- wie auch zu Entschlüsselung genutzt werden kann. (Apparantly) RC4 läuft in drei Schritten ab:

  • Zunächst wird eine S-Box initialisiert. Dazu wird ein Feld (Array) mit 256 Zeichen gefüllt und die Feldelemente mittels des Schlüssels untereinander vertauscht.

  • Dann wird für jeden Buchstaben des Eingabetextes ein Zufallsbyte aus der S-Box ermittelt, wobei die Elemente des Feldes - wie im vorangegangenen Schritt - jedes Mal vertauscht werden.

  • Schließlich werden das ermittelte Zufallsbyte und das Textzeichen durch xor miteinander verknüpft.

  Trotz seiner Einfachheit wurden bisher keine Schwächen im Algorithmus entgedeckt. Da die Verschlüsselung in keiner Form vom zu verschlüsselnden Text abhängig ist, ist der Algorithmus für Klar- oder Geheimtextangriffe anfällig. Es ist daher zu empfehlen einen Schlüssel nicht zu oft zu verwenden.
  

  [seitenanfang] [verweise]