IT-SicherheitKapitel 2 -

Symmetrische Kryptographie

Prof. Dr. Michael Braun

Wintersemester 2010/2011

Einführung

Historie

Die klassische Kryptographie diente der Geheimhaltung von Nachrichten und wurde hauptsächlich von Militärs, Geheimdiensten und Diplomaten genutzt.Die moderne Kryptographie (etwa seit 1975) beschäftigt sich mit erheblich weitergehenden Kommunikations- und Sicherheitsproblemen.

Beispiele aus der Geschichte

Ziel

• Ziel der klassischen Kryptographie war es zunächst die Vertraulichkeit zu gewährleisten.

Klassische Verfahren

Skytala Caesar Chiffre

Vigenere

1 2 3 4 5

1 A B C D E

2 F G H I,J K

3 L M N O P

4 Q R S T U

5 V W X Y Z

Polybios

Rotor-Chiffriermaschinen• Edward Hugh Hebern (1869-

1952) erfand 1917 die erste Rotor-Chiffriermaschine, die Electric Code Machine.

Zeichnung aus der Original-Patentschrift

Weitere Maschinen

Die britische TypeX, eingesetzt im 2.

Weltkrieg

Die sowjetische Fialka, auch in der DDR am 1968 eingesetzt

Die schweizerische NEMA, eingesetzt ab 1946

Die amerikanische SIGABA

eingesetzt im 2. Weltkrieg

Die deutsche ENIGMAeingesetzt im 2.

Weltkrieg

Symmetrische Verschlüsselung

Das Prinzip nach Kerckhoff

• Die Sicherheit einer Verschlüsselung soll nicht auf der Geheimhaltung des Verschlüsselungsalgorithmus basieren, sondern auf der Geheimhaltung eines Eingabeparameters, dem sogenannten Schlüssel.

• „No Security by Obscurity“

k

Nachricht

Nachrichtenc dec

k

vertraulicher + authentischer

Kanal

offenerKanal

Kommunikationsmodell

Blockchiffren

Blockchiffren• Der Klartext wird in Blöcke kurzer Länge aufgeteilt

und jeder Block wird mittels einer komplizierten Funktion mit einem Schlüssel fester Länge verknüpft.

encenc

SchlüsselSchlüssel

GeheimtextblocGeheimtextblockkKlartextblockKlartextblock

SPNSS11 SS22 SS33 SS44

PermutationPermutation

SS11 SS22 SS33 SS44

PermutationPermutation

SS11 SS22 SS33 SS44

PermutationPermutation

kk11

kk22

kkr-1r-1

kkrr

...

Klartextblock

Geheimtextblock

• Ein Substitutions-Permutations-Netzwerk (= SPN) ist eine alternierende Kombination von Substitution und Permutation über mehrere Runden.

Idee geht auf Claude Shannon aus dem Jahr 1949 zurück.

Diffusion und Konfusion

• Wichtige Eigenschaften für eine sichere Chiffre sind:

Diffusion: Verteilen der im Klartext enthaltenen Information über den Geheimtext(durch Permutation)Konfusion: Verschleierung des Zusammenhangs zwischen Klartext- und Geheimtextzeichen(durch Substitution)

Feistel Chiffre

FF kkii

LLi-1i-1 RRi-1i-1

LLii RRii

Horst Feistel entwickelte das Prinzip der Feistel-Chiffre in den 1970ern bei IBM im Projekt „Luzifer“

m RundenF ist die Rundenfunktion, bestehend aus Permutationen und Substitutionen

Data Encryption Standard

DESDES

Schlüssel(56 Bit)

Klartextblock(64 Bit)

Geheimtextblock(64 Bit)

Struktur des DES

perm

ki

Li

Li-1

Ri

Ri-1

expand32 Bit

32 Bit 48 Bit48 Bit

48 Bit

32 Bit

32 Bit

32 Bit

32 Bit

Sicherheit des DESDie große Schwäche des DES ist die kurze Schlüssellänge von 56 Bit.Eine vollständige Schlüsselsuche ist mittels spezieller Hardware zeitnah möglich (z.B. Deep Crack, 22 Stunden im Jahr 1999).Der DES ist für den praktischen Einsatz nicht mehr empfehlenswert.Mittels 3DES (Triple-DES) kann man Sicherheit auf 112 Bit erhöhen, hat aber hohe Performanzverluste, da man den DES dreimal ausführen muss bei jedem Block.

Advanced Encryption Standard

AESAES

Schlüssel(128, 192 oder 256 Bit)

Klartextblock(128 Bit)

Geheimtextblock(128 Bit)

• Ziele: sicherer und effizienter als Triple-DES

Struktur des AES

SS++ ++

Key Addition

SubstituteBytes

Shift Rows

Mix Column*

KeyAddition

Klartext

Geheimtext

nächste Runde

* in der letzten Runde kein Mix Column

Weitere BlockchiffrenMARS unbalancierte Feistel-

Chiffre mit 32 Runden

sehr langsam in Hardware; für billige Chipkarten nicht geeignet; bedingt schnell in Software (abhängig von CPU)

RC6

Feistel-Chiffre mit 20 Runden; datenabhängige Rotation in den Runden

etwas langsam in Hardware; für billige Chipkarten nicht geeignet; bedingt schnell in Software (abhängig von CPU)

TwofishFeistel-Chiffre mit 16 Runden; schlüsselabhängige S-Boxen

schnell in Hardware; schnell in Software

Serpent iterierte Chiffre mit 32 Runden

schnell in Hardware; langsam in Software; besonders konservativ im Design

Verwendung von Blockchiffren• Blockchiffren können nur Nachrichten verarbeiten,

deren Länge der Blocklänge entspricht. Daher werden Nachrichten in einzelne Blöcke aufgeteilt und zu Geheimtextblöcke verarbeitet:

Electronic Codebook (ECB)Cipher Block Chaining (CBC)Counter (CTR)Cipher Feedback (CFB)Output Feedback (OFB)

Electronic Codebook (ECB)

mm11 mm22 mm33

enc(k,-enc(k,-))

mmrr

cc11 cc22 cc33 ccrr

enc(k,-enc(k,-))

enc(k,-enc(k,-))

enc(k,-enc(k,-)). . .

Cipher Block Chaining (CBC)

mm11 mm22 mm33

enc(k,-enc(k,-))

mmrr

cc11 cc22 cc33 ccrr

enc(k,-enc(k,-))

enc(k,-enc(k,-))

enc(k,-enc(k,-)). . .

IVIV

Counter (CTR)

mm11 mm22

enc(k,-enc(k,-))

cc11 cc22

enc(k,-enc(k,-))

. . .mm33

cc33

enc(k,-enc(k,-))

mmrr

ccrr

enc(k,-enc(k,-))

IV+2IV+2IV+1IV+1 IV+3IV+3 IV+rIV+r

Output Feedback (OFB)

mm11 mm22

enc(k,-enc(k,-))

cc11 cc22

enc(k,-enc(k,-))

. . .

IVIV

mm33

cc33

enc(k,-enc(k,-))

mmrr

ccrr

enc(k,-enc(k,-))

Cipher Feedback (CFB)

mm11 mm22

enc(k,-enc(k,-))

cc11 cc22

enc(k,-enc(k,-))

. . .

IVIV

mmrr

ccrr

enc(k,-enc(k,-))

Stromchiffren

One-Time-Pad

• Bei dem One-Time-Pad wird der Klartext mit einem genauso langen Schlüssel XOR-verknüpft.

• Das One-Time-Pad ist die einzige beweisbar sichere Chiffre.

Schlüsselstrom

Klartextstrom Geheimtextstrom

Stromchiffren• Nachbildung des One-Time-Pads: Aus einem kurzen

Schlüssel wird ein pseudozufälliger Schlüssel gewählt.

pseudozufälliger

Schlüsselstrom

Klartextstrom Geheimtextstrom

SchlüsselstroSchlüsselstrom-erzeugungm-erzeugung SchlüsselSchlüssel

Shrinking-Generator

y/ny/n Ausgabe

Takt ATakt A

Takt ATakt A

Summations-Generator

Ausgabe

Takt ATakt A

Takt BTakt B

RC4

Schlüssel-byte

RC4 weist statistische Schwächen auf.

A5/1

MajoritätsfunktionMajoritätsfunktion

Takt ATakt A

Takt BTakt B

Takt CTakt C

eSTREAM

Im Rahmen des Network of Excellence ECRYPT der EU gab es das Projekt eSTREAM (2004-2008), wo in einer öffentlichen Ausschreibung starke Stromchiffren gesucht wurden.Es wurde dabei nach zwei verschiedenen Profilen gesucht: Software- und Hardwareanwendungen.

eSTREAM (Forts.)• Softwareanwendung:

HC-128RabbitSalsa20/12SOSEMANUK

• Hardwareanwendung:F-FCSR-H v2Grain v1Mickey v2Trivium

Output Feedback (OFB)

mm11 mm22

enc(k,-enc(k,-))

cc11 cc22

enc(k,-enc(k,-))

. . .

IVIV

mm33

cc33

enc(k,-enc(k,-))

mmrr

ccrr

enc(k,-enc(k,-))

Schlüsselstromerzeugung

Counter (CTR)

mm11 mm22

enc(k,-enc(k,-))

cc11 cc22

enc(k,-enc(k,-))

. . .mm33

cc33

enc(k,-enc(k,-))

mmrr

ccrr

enc(k,-enc(k,-))

IV+2IV+2IV+1IV+1 IV+3IV+3 IV+rIV+r

Schlüsselstromerzeugung

Hashfunktionen

Hashfunktion

Eine Hashfunktion ist eine effizient berechenbare Abbildung h: {0, 1}* -> {0, 1}n.Ziel ist die Konstruktion von kollisionsfreien Hashfunktionen.Anwendung: Integritätsschutz, Message Authentication Codes, Digitale Signatur.

Konstruktion einer Hashfunktion

mm11

ff

IVIVmm22

ff

mm33

ff

mmrr

ff...hash valuehash value

mittels iterierter Kompressionsfunktion

Beispiele für HashfunktionenMD4: 128 Bit; Kollision in 220

MD5: 128 Bit; Kollision in 230, Wang, 2005SHA0: 160 Bit, Kollision in 239, Wang, 2005SHA1: 160 Bit, Kollision in 263, Wang, 2005SHA2: 224, 256, 384, 512 Bit, noch sicherRIPEMD128: 128 Bit, Kollision in 264

RIPEMD160: 160 Bit, noch sicherDerzeit Suche nach SHA3 bis Ende 2012

Message Authentication

Codes

Message Authentication Code• Ein Message Authentication Code liefert einen

digitalen Fingerabdruck in Abhängigkeit eines Schlüssels zum Schutze der Nachrichtenauthentizität.

AA BB

t := mac(k, m)m, t

t‘ := mac(k, m)IF t = t‘ ACCEPTELSE REJECT

secret ksecret k

Beispiele für MACs

HMAC: Hashfunktionen basiertXOR-MAC: Blockchiffren basiertCBC-MAC: Blockchiffren basiert

HMAC

ipad, opad: konstante Wertek: geheimer Schlüsselhmac(k, m) := h(k XOR opad || h(k XOR ipad || m))

XOR-MAC

x0 := 0 || IVxi := 1 || <i-1> || mi, für alle 1 ≤ i ≤ r<i-1>: binäre Darstellung der Zahl i-1k: geheimer Schlüsselmac(k, m) := enc(k, x0) XOR ... XOR enc(k, xr)

CBC-MAC

mm11 mm22 mm33

enc(k,-enc(k,-))

mmrr

macmac

enc(k,-enc(k,-))

enc(k,-enc(k,-))

enc(k,-enc(k,-)). . .

IVIV

Sichere KanäleVertrauliche und authentische Kanäle nennt man sichere Kanäle:1) Zuerst Verschlüsseln des Klartextes und danach

MAC über den Geheimtext (z.B. bei IPsec).2) Zuerst MAC über den Klartext und danach

Verschlüsseln des Klartextes (z.B. bei SSH).3) Zuerst MAC über den Klartext und danach

Verschlüsseln des Klartextes und des MACs (z.B. bei SSL).

Den einzig beweisbar sicheren Kanal bietet die erste Variante (Krawczyk, 2001).