Datenverschlüsselungsstandard

DES ( Datenverschlüsselungsstandard )

DES-F-Funktion. Zusammenfassung

Designer	IBM
Erstveröffentlichung	1975 ( 1977 für den Standard)
Abgeleitet von	Luzifer
Verschlüsselung (en) basierend auf diesem Algorithmus	Dreifaches DES , G-DES , DES-X , LOKI89 , ICE

Eigenschaften

Blockgröße (n)	64 Bit
Schlüssellänge (n)	56 Bit
Struktur	Feistel-Schema
Anzahl der Züge	16 Runden des DES

Bessere Kryptoanalyse

lineare Kryptoanalyse , differentielle Kryptoanalyse , Brute-Force-Angriffe jetzt möglich

Der Datenverschlüsselungsstandard ( DES , pronounce / d ɛ s /) ist ein symmetrischer Verschlüsselungsalgorithmus ( Blockverschlüsselung ) unter Verwendung von 56- Bit- Schlüsseln . Die Verwendung wird heute nicht mehr empfohlen, da die Ausführung langsam ist und der Schlüsselraum zu klein ist, um einen systematischen Angriff in angemessener Zeit zu ermöglichen. Wenn es noch verwendet wird, ist es normalerweise in Triple DES , was nichts zur Verbesserung seiner Leistung beiträgt. DES wurde insbesondere im UNIX- Passwortsystem verwendet .

Der erste DES-Standard wird von FIPS am veröffentlicht15. Januar 1977 unter dem Namen FIPS PUB 46. Die letzte Version vor der Veralterung stammt aus 25. Oktober 1999.

Geschichte

Im Mai 1973Das American National Bureau of Standards fordert die Schaffung eines Verschlüsselungsalgorithmus, der von Unternehmen verwendet werden kann. Zu diesem Zeitpunkt verfügte IBM bereits über einen Algorithmus namens Lucifer , der 1971 von Horst Feistel entwickelt wurde .

Logischerweise sollte dieser Algorithmus vom NBS ausgewählt worden sein. In der Praxis war dies fast der Fall: Die NSA forderte, dass Luzifer von ihm geändert wird. So entstand das DES, das im November 1976 als Standard übernommen wurde . Dies ließ den Verdacht aufkommen, dass die NSA den Algorithmus absichtlich geschwächt hatte, um ihn brechen zu können. Seltsamerweise hat sich DES als resistent gegen mehrere Angriffe erwiesen, von denen erst viel später erwartet wurde, dass sie in der akademischen Gemeinschaft auftreten. Noch erstaunlicher war, dass Luzifer ihm weniger gut widerstand. Dies deutet darauf hin, dass die NSA zu diesem Zeitpunkt über diese Kryptoanalysetechniken informiert war und DES daher in Wirklichkeit widerstandsfähiger gemacht hätte.

Operation

Der DES-Algorithmus transformiert einen 64-Bit-Block in einen anderen 64-Bit-Block. Es verarbeitet einzelne 56-Bit-Schlüssel, die durch 64 Bit dargestellt werden (wobei ein Bit in jedem Byte zur Paritätsprüfung verwendet wird ). Dieses symmetrische Verschlüsselungssystem gehört zur Familie der iterativen Blockchiffren, insbesondere ist es ein Feistel-Schema (benannt nach Horst Feistel am Ursprung der Luzifer- Chiffre ).

Im Allgemeinen können wir sagen, dass DES in drei Schritten arbeitet:

anfängliche und feste Permutation eines Blocks (ohne Auswirkungen auf die Sicherheitsstufe);
Das Ergebnis wird 16 Iterationen einer Transformation unterzogen. Diese Iterationen hängen bei jeder Umdrehung von einem anderen Teilschlüssel von 48 Bit ab. Dieser schlüsselfertige Zwischenschlüssel wird aus dem Anfangsschlüssel des Benutzers berechnet (dank eines Netzwerks von Substitutionstabellen und XOR- Operatoren ). Während jeder Runde wird der 64-Bit-Block in zwei 32-Bit-Blöcke aufgeteilt, und diese Blöcke werden gemäß einem Feistel-Schema miteinander ausgetauscht. Der höchstwertige 32-Bit-Block (der sich von 32 Bit auf 64 Bit erstreckt) wird einer Transformation unterzogen.
Das Ergebnis der letzten Runde wird durch die Umkehrfunktion der anfänglichen Permutation transformiert.

DES verwendet acht Substitutionstabellen (die S-Boxen ), die inhaltlich kontrovers diskutiert wurden. Wir vermuteten eine Schwäche, die von den Designern absichtlich eingefügt wurde. Diese Gerüchte wurden Anfang der neunziger Jahre durch die Entdeckung der differentiellen Kryptoanalyse zerstreut, die zeigte, dass die Tabellen gut gestaltet waren.

Anschläge

Auf DES wurden mehrere Angriffe entdeckt. Sie ermöglichen es, die Kosten einer umfassenden Suche nach Schlüsseln zu senken, die im Durchschnitt Operationen entspricht. Einige dieser Methoden sind mit neueren Verschlüsselungsalgorithmen aufgrund der Einführung eines Lawineneffekts nicht mehr effizient . $2 ^ {{55}}$

Die differentielle Kryptoanalyse entdeckt von Eli Biham und Adi Shamir in 1991 macht es möglich , den Schlüssel zu finden Klartext. Das Prinzip besteht darin, ein DES in einer hermetischen Blackbox mit einem geheimen Schlüssel zu implementieren. Indem wir genügend Text als Eingabe bereitstellen, können wir das Verhalten der Ausgaben anhand der Eingaben statistisch analysieren und den Schlüssel finden. Die für diesen Angriff verwendeten Eingänge müssen sich geringfügig voneinander unterscheiden (z. B. ein sich änderndes Bit). Indem Sie untersuchen, wie sich der Unterschied auf die Ausgabe auswirkt, können Sie Statistiken erstellen und durch Erhöhen der Anzahl der Eingaben die Zuverlässigkeit des Angriffs verbessern. $2 ^ {{47}}$
Der T-Angriff ( Tickling-Angriff ) ist eine Variante der differentiellen Kryptoanalyse , die 1974 während des DES-Entwurfs von IBM-Forschern entdeckt wurde. Zwanzig Jahre lang herrschte völlige Stille über diese Entdeckung. Es ist Don Coppersmith, der das Geheimnis 1994 enthüllen wird. Zu dieser Zeit hatte sie die Designer von DES ermutigt, den Inhalt der Substitutionstabellen zu verbessern (anstatt ihn zu schwächen, wie das Gerücht andeutete).
Die lineare Kryptoanalyse , erfunden von Henry Gilbert und unabhängig von Mitsuru Matsui in 1993 ist effektiver , aber weniger bequem aus dem einfachen Grunde , dass der Angreifer nicht die Black Box hat und er kann seine eigenen Texte nicht einreichen. Dieser Angriff erfordert Paare (alle mit demselben Schlüssel verschlüsselt), die der Angreifer auf die eine oder andere Weise wiederherstellen konnte. Es besteht darin, eine lineare Annäherung an DES durch Vereinfachung vorzunehmen. Durch Erhöhen der Anzahl verfügbarer Paare wird die Genauigkeit der Approximation verbessert und der Schlüssel kann extrahiert werden. $2 ^ {{43}}$
Der Zeit-Speicher-Kompromiss ist ein Konzept, das Martin Hellman Anfang der 1980er Jahre erfunden hat . Unter der Annahme, dass dieselbe Nachricht mehrmals mit unterschiedlichen Schlüsseln verschlüsselt wird, könnten wir eine riesige Tabelle berechnen, die alle verschlüsselten Versionen dieser Nachricht enthält. Wenn wir eine verschlüsselte Nachricht abfangen, können wir sie in der Tabelle finden und den Schlüssel erhalten, der zum Codieren verwendet wurde. Dieser Angriff ist natürlich nicht durchführbar, da wir eine Tabelle in der Größenordnung von einer Milliarde GB benötigen. Hellmans Genie bestand darin, einen Weg zu finden, diese Tabelle auf etwa 1 Terabyte (oder 1 Million Mal weniger als die vollständige Tabelle) zu reduzieren , was heutzutage machbar ist.
Bei den anderen Angriffen handelt es sich um spezifische Implementierungen, die nicht unbedingt DES-spezifisch sind. Im Fall eines in Hardware implementierten DES könnte man den Stromverbrauch analysieren und einige Informationen über den Schlüssel ableiten (ein erhöhter Verbrauch zeigt aktive Bits an ). Dieselbe Angriffsart kann auch auf einem Computer verwendet werden, indem die Zeit berechnet wird, die zum Verschlüsseln mit verschiedenen Texten benötigt wird, oder indem der verwendete Speicher analysiert wird.
Alle anderen DES-Angriffe zielen darauf ab, die Rechenzeit einer umfassenden Suche durch die Verwendung von Maschinen zu verkürzen, die speziell für diese Aufgabe entwickelt wurden ( z. B. dank paralleler FPGAs ). Eine solche Maschine wurde 1998 gebaut . Deep Crack kostete rund 200.000 US- Dollar und könnte den Schlüssel in weniger als einer Woche brechen. Das verteilte Rechnen mit den Computern von Einzelpersonen ( Distributed.net ) hat sich als effektiv erwiesen, um einen Schlüssel in weniger als 24 Stunden zu brechen .

Status

Der ursprünglich von IBM entwickelte Algorithmus verwendete einen 112-Bit-Schlüssel. Durch die NSA- Intervention wurde die Schlüsselgröße auf 56 Bit reduziert. Heutzutage ist Triple DES immer noch sehr beliebt, und „einfaches“ DES gibt es nur in älteren Anwendungen. Der DES-Standard wurde 2001 durch den AES (Advanced Encryption Standard) ersetzt.

Anmerkungen und Referenzen

Anmerkungen

Verweise

(in) " Datenverschlüsselungsstandard (DES) " [PDF] ,25. Oktober 1999(Zugriff auf den 20. Oktober 2015 ) .
Beteiligung der NSA an der Entwicklung des Datenverschlüsselungsstandards
(in) Don Coppersmith , " Der Datenverschlüsselungsstandard (DES) und seine Stärke gegen Angriffe " , IBM Journal of Research and Development , Vol. 3 , No. 38, n o 3, Mai 1994, p. 243 ( online lesen [PDF] )

Anhänge

Zum Thema passende Artikel

Externe Links

(en) Ein Tutorial zur linearen und differentiellen Kryptoanalyse von Howard M. Heys: Dokument mit einer Zusammenfassung der linearen und differentiellen Analyse