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.
     • XOR-Verschlüsselung mit perfekt zufälligem Bitstrom als einmaligem (!) Schlüssel der Länge n = Länge der Nachricht.
   • Design-Kriterien:
     • Konfusion: möglichst komplexer, nicht-linearer Zusammenhang zwischen Klartext, Schlüssel und Geheimtext.
     • Diffusion: »Verschmieren der Klartextbits«: Änderung eines Klartextbits ändert » 50% der Geheimtextbits (Lawinen-Effekt, avalanche criterion).
     • Beides soll die Entropie der Geheimtexte erhöhen.
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 (man kann das Problem formulieren, aber es ist nicht lösbar).
   • Verwirklicht durch RSA und perfekte Zufallsgeneratoren (reduzierbar auf Primfaktorisierung).
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ß, dass die vollständige Suche alle beim Gegner vorhandenen, evtl. sogar alle Ressourcen des Universums überfordert.
   Aber Achtung: Die Größe des Schlüsselraums bzw. Schlüssellänge ist als Sicherheitsmaß nur sehr bedingt aussagekräftig.

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.
   • Jede Vorschrift zur Passwortwahl reduziert den Suchraum.
2. »Klassische« Zufallsgeneratoren (32-bit-Startwert):
   • Der Suchraum hat die Größ;e 2³² ~ 4 × 10⁹.
   • Solche »Zufallsgeneratoren« werden in den Bibliotheken der gängigen Programmiersprachen verwendet (rand).
3. DES-Schlüssel:
   • Der Suchraum hat die Größe 2⁵⁶ (= die Größe des Schlüsselraums).

Größenordnungen

Vollständige Suche - physikalische Grenzen

[nach: Louis K. Scheffer in sci.crypt]

• Höchstens 10⁹⁰ Elementarteilchen im Universum (Schranke für Zahl der CPUs),
• 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),

Engere Schätzung: Schon Rechner für 2²⁵⁶ Operationen würden zu einem schwarzen Loch kollabieren.

===> 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] (Sicher also auch vor »Quantencomputern«.)

Realistische Sicherheitsgrenze heute: ca. 90-Bit-Schlüssel (alle Rechnerkapazität der Erde zusammengenommen). Damit ist man vermutlich auch vor der NSA sicher. Für die Leistung von Rechnern (PC, Supercomputer) außerhalb der NSA siehe auch hier.

Praktische Schlüssellänge: 128 Bit.

• DES ist nicht mehr sicher [Schlüssellänge 56 Bit].
• AES hat breite Sicherheitsreserve und kann noch zulegen [Schlüssellängen 128, 196 oder 256 Bit].

• [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 damaliger Technologie (1993) -

• 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 (1993) 35 Stunden, (2004) < 1 Stunde.

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.
• Resistenz gegen bekannte Attacken (bewiesen, oder auf anderes vermutlich hartes Problem reduziert).
• Algorithmus öffentlich bekannt und jahrelang von der »kryptographischen Öffentlichkeit« geprüft.