Die Sicherheit kryptographischer Verfahren

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.
• Insbesondere: Kryptoanalyse durch Adi Shamir erfolglos.

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. Praktische Sicherheit (komplexitätstheoretischer Ansatz) -
   • Das Chiffrierverfahren kann
     • durch die bekannten Angriffe
     • mit den verfügbaren Ressourcen
     • mit vertretbarem Aufwand
     nicht gebrochen werden.
   • Verwirklicht durch RSA und perfekte Zufallsgeneratoren.
   • Mathematische Beweisbarkeit prinzipiell gegeben, aber mit den gegenwärtigen Methoden nicht durchführbar.
   • Theoretischer Standpunkt: Der kryptoanalytische Ansatz führt auf ein »hartes« (z. B. NP-vollständiges) Problem.
   • Praktischer Standpunkt: Es gibt keine Analyse-Methode, die »wesentlich« schneller ist als die vollständige Suche. Der Schlüsselraum ist so groß, daß die vollständige Suche alle Ressourcen des Universums überfordert.

Kryptoanalytische Attacken

... oder der unbefugten Entschlüsselung (»illegale Kryptoanalyse«).

Der Geheimtext wird stets als bekannt angenommen.

• Vollständige Suche (`brute force attack') - Der Schlüsselraum wird vollständig durchgesucht, bis der passende Schlüssel gefunden ist.
• Geheimtextanalyse (`ciphertext only attack', siehe obiges Bild) - Statistische oder zahlentheoretische Methoden; Beispiel: Bei monoalphabetischer Substitution über einer »natürlichen« Sprache (deutsch, englisch, ...) entspricht das häufigste Zeichen im Geheimtext in der Regel dem Buchstaben `e'.
• Klartextraten (`known plaintext attack') - Aus Kenntnis (oder Vermutung) über einen Teil des Klartexts werden Informationen über den Schlüssel gezogen.
• Wörterbuchattacke - Systematisches Klartextraten nach der Fischzugmethode.
• Probeverschlüsselung (`chosen plaintext attack') - Bei asymmetrischen oder Einweg-Verfahren kann der Angreifer beliebige Texte selbst verschlüsseln und das Ergebnis analysieren. Sonst kann diese Methode etwa nach Analyse eines Verschlüsselungs-Chips oder Fälschen eines `Challenge-Response-Dialogs' angewendet werden.

(Kriminelle Gewaltanwendung [`social engineering'] wird nicht zu den kryptoanalytischen Attacken gerechnet! Ebensowenig die Ausnutzung von Systemschwächen, wie z. B. diverse Abhörmöglichkeiten)

Chiffriermethoden und Schlüssel

• Die Chiffriermethode wird als bekannt angenommen.
• Der Schlüssel wird als geheim betrachtet. Die Sicherheit des Verfahrens beruht auf der Geheimhaltung des Schlüssels.

• Der Beweis der Sicherheit des Verfahrens ist nicht öffentlich möglich, ohne das Verfahren zu kompromittieren.
• Die Information über die Art des Verfahrens, also den Algorithmus, ist schwerer geheim zu halten als ein zufällig gewählter Schlüssel. (Einsatz in Netzen, Entwickler des Verfahrens, Spionage, Eroberung, Erpressung, siehe Geschichte der Kryptologie).
• Bei einem Geheimnisbruch sind viele Anwender betroffen.
• Der Wechsel eines Verfahrens ist sehr aufwendig, der Wechsel eines Schlüssels dagegen leicht.
• Asymmetrische Verschlüsselungsverfahren setzen sowieso voraus, daß der Algorithmus öffentlich bekannt ist.

Vollständige Suche - der Stand der Technik

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.

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

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

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. 80-Bit-Schlüssel. Damit ist man vermutlich auch vor der NSA sicher.

Zurück zum Inhaltsverzeichnis

E-Mail an Pommerening@imsd.uni-mainz.de.