Drei Stufen der Sicherheit von Chiffrierverfahren

1. Perfekte Sicherheit (informationstheoretischer Ansatz) -
   • Ein Geheimtext enthüllt keinerlei Information über Klartext und Schlüssel.
   • Verwirklicht im One-Time-Pad.
   • Design-Kriterien: Konfusion und Diffusion (===> Erhöhung der Entropie der Geheimtexte).
2. Mathematische Sicherheit (komplexitätstheoretischer Ansatz) -
   • Der kryptoanalytische Ansatz führt auf ein »hartes« (z. B. NP-vollständiges) Problem.
   • Mathematische Beweisbarkeit prinzipiell gegeben, aber mit den gegenwärtigen Methoden nicht durchführbar.
   • Verwirklicht durch RSA und perfekte Zufallsgeneratoren.
3. Pragmatische Sicherheit (empirischer Ansatz) -
   • Das Chiffrierverfahren kann
     • durch die bekannten Angriffe
     • mit den verfügbaren Ressourcen
     • mit vertretbarem Aufwand
     nicht gebrochen werden.
   • Es ist keine Analyse-Methode bekannt, die »wesentlich« schneller ist als die vollständige Suche. Der Schlüsselraum ist so groß, daß die vollständige Suche alle beim Gegner vorhandenen, evtl. sogar alle Ressourcen des Universums überfordert.

Beispiele für Suchräume

1. 8-Byte-Passwörter:
   • Suchraum der Größe 256⁸= 2⁶⁴ ~ 18 × 10¹⁸ (theoretisch);
   • werden aber nur druckbare Zeichen (ASCII 32 bis 126) verwendet, hat der effektive Suchraum nur 93⁸ ~ 5.5 × 10¹⁵ Elemente.
   • Durch die Verwendung »merkbarer« Passwörter schrumpft er drastisch weiter.
2. »Klassische« Zufallsgeneratoren (32-bit-Startwert):
   • Der Suchraum hat die Größe 2³² ~ 4 × 10⁹.
3. DES-Schlüssel:
   • Suchraum hat Größe 2⁵⁶ (= die Größe des Schlüsselraums).

Immer den effektiven Suchraum berücksichtigen!

Größenordnungen

Vollständige Suche - physikalische Grenzen

• höchstens 10⁹⁰ Elementarteilchen im Universum (Schranke für Zahl der CPU's),
• mindestens 10^-35 Sekunden, um ein Elementarteilchen mit Lichtgeschwindigkeit zu durchqueren (Zeitschranke für eine Operation),
• höchstens 10¹⁸ Sekunden Lebensdauer des Universums (~ 30 × 10⁹ Jahre) (Schranke für verfügbare Zeit),

===> 500-Bit-Schlüssel sind sicher vor vollständiger Suche ...

... until such time as computers are built from something other than matter, and occupy something other than space. (Paul Ciszek)

Praktische Sicherheitsgrenze heute: ca. 90-Bit-Schlüssel. Damit ist man vermutlich auch vor der NSA sicher.

• [Stellungnahme angesehener Experten]
• [Selecting Cryptographic Key Sizes (Arjen Lenstra, Eric Verheul)]

Vollständige Suche - der Stand der Technik

• Michael J. Wiener: Efficient DES Key Search. Preprint 1993; ftp://ftp.ox.ac.uk/pub/crypto/cryptanalysis/des_key_search.ps.gz.
• The DES Key Search Project.

Bauanleitung für einen Chip mit heutiger Technologie -

• Produktionskosten ca $10,
• Leistung: 1 DES-Verschlüsselung pro 50-MHz-Takt (16 Schaltkreise in Pipeline für 16 Runden),
• Vergleich mit bekanntem Klartext intern (ohne I/O).

Daraus wird gebaut eine DES-Entschlüsselungsmaschine:

• Baukosten $ 1 Million,
• einmalige Entwicklungskosten $ 500 000, Entwicklungszeit < 1 Jahr,
• Durchschnittliche Suchzeit 3.5 Stunden.

Billiglösung:

• 5760 Chips mit hierarchisch angeordneter Steuerungslogik, von PC gesteuert, für $100 000, Suchzeit 35 Stunden.

Die Methode greift grundsätzlich für jedes Verschlüsselungsverfahren, die Suchzeit ist proportional zu

• Verschlüsselungszeit,
• 1/(Zahl der Chips),
• Größe des Schlüsselraums.

Kriterien für ein gutes Verschlüsselungsverfahren

• Gute Implementierbarkeit.
• Hinreichende Geschwindigkeit.
• Großer Schlüsselraum; »schwache Schlüssel« leicht zu vermeiden.
• Gute Diffusion der Klartext- und Schlüssel-Bits.
• Bestehen statistischer Tests; z. B. OFB erzeugt gute Pseudozufallszahlen.
• Spezifische Kriterien je nach Art des Verfahrens; z. B. bei Blockverschlüsselung: Die f_k, wobei k den Schlüsselraum K durchläuft, erzeugen die volle symmetrische oder alternierende Gruppe auf der Menge der Blöcke.
• Resistenz gegen bekannte Attacken (bewiesen, oder auf anderes vermutlich hartes Problem reduziert).
• Algorithmus öffentlich bekannt und jahrelang von der »kryptographischen Öffentlichkeit« geprüft.