Modul

Kryptographie 1

Studienbrief 1: Einführung und StromchiffrenStudienbrief 2: DESStudienbrief 3: AESStudienbrief 4: More about block ciphersStudienbrief 5: Message Authentication Codes

Autoren:Christof PaarJan Pelzl

1. Auflage

Ruhr - Universität Bochum

© 2014 Christof PaarRuhr - Universität BochumUniversitätsstraße 15044801 Bochum

1. Auflage (10. Januar 2014)

Didaktische und redaktionelle Bearbeitung:Christoph Bader, Romy Rahnfeld

Das Werk einschließlich seiner Teile ist urheberrechtlich geschützt. Jede Ver-wendung außerhalb der engen Grenzen des Urheberrechtsgesetzes ist ohneZustimmung der Verfasser unzulässig und strafbar. Das gilt insbesonderefür Vervielfältigungen, Übersetzungen,Mikroverfilmungen und die Einspei-cherung und Verarbeitung in elektronischen Systemen.

Inhaltsverzeichnis Seite 3

Inhaltsverzeichnis

Einleitung zu den Studienbriefen 4I. Abkürzungen der Randsymbole und Farbkodierungen . . . . . . . . . . . . . . . . . . . . . . 4II. Zu den Autoren . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5III. Modullehrziele . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6

Studienbrief 1 Einführung und Stromchiffren 71.1 Lernziele . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 71.2 Übungen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7

Studienbrief 2 DES 132.1 Lernziele . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 132.2 Übungen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13

Studienbrief 3 AES 183.1 Lernziele . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 183.2 Übungen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18

Studienbrief 4 More about block ciphers 214.1 Lernziele . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 214.2 Übungen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21

Studienbrief 5 Message Authentication Codes 245.1 Lernziele . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 245.2 Übungen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24

Verzeichnisse 30I. Abbildungen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 30II. Tabellen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 30

Seite 4 Einleitung zu den Studienbriefen

Einleitung zu den Studienbriefen

I. Abkürzungen der Randsymbole und Farbkodierungen

Axiom A

Beispiel B

Definition D

Exkurs E

Kontrollaufgabe K

Merksatz M

Quelle Q

Satz S

Übung Ü

Zu den Autoren Seite 5

II. Zu den Autoren

Christof Paar ist Inhaber des Lehrstuhls Embedded Security an der Ruhr-Universität Bochum und ist außerplanmäßiger Professor an der University ofMassachusetts at Amherst, USA. Er arbeitet seit 1995 im Bereich der angewandtenKryptographie.Dr. Paar lehrt seit über 15 Jahren an Universitäten, sowohl in Europa als auch inden USA, zu Themen der Kryptographie und Datensicherheit. Darüber hinausgibt er Kurse für Teilnehmer/-innen aus der Industrie, u.a. für Motorola Rese-arch, die NASA und Philips Research. Dr. Paar hat mehr als 150 Publikationen imBereich der angewandten Kryptographie und ist Mitgründer des Workshop onCryptographic Hardware and Embedded Systems (CHES).

Jan Pelzl hat in angewandter Kryptologie promoviert und ist Hauptgeschäftsfüh-rer der ESCRYPT - Embedded Sedurity, einer führenden Firma im Bereich derSicherheitsbereatung. Er hat erfolgreich zahlreiche nationale und internationaleIndustrieprojekte geleitet und tiefgehende Kenntnisse über Sicherheitsbedürfnis-se in echten Systemen.Dr. Pelzl hat praktische Aspekte der Kryptographie und Kryptanalyses von el-liptischen Kurven erforscht. Seine theoretischen und praktischen Ergebnisse hater auf/ in international führenden Konferenzen/ Zeitschriften veröffentlicht. Dr.Pelzl hat viele Jahre Kurse über Kryptographie und IT-Sicherheit in Industriekrei-sen gehalten.

Seite 6 Einleitung zu den Studienbriefen

III. Modullehrziele

Kryptographie ist heutzutage allgegenwärtig - während sie lange Zeit nur von Regierungen, Geheimdiens-ten und Banken verwendet wurde, werden kryptographische Techniken mittlerweile u.a. in Web-Browsern,E-Mail-Programmen, Handys, industriellen Produktionssystemen, eingebetteter Software, Autos und so-gar in medizinischen Implantaten verwendet. Daher benötigen Entwickler/-innen heutzutage umfassendesWissen im Bereich der angewandten Kryptographie.

Ziel dieses Moduls ist es, dem/den Leser/-innen ein solches Wissen zu vermitteln. Nach einer Einführungin das Thema der Kryptographie und Datensicherheit, werden die wichtigsten Techniken der modernensymmetrischen Kryptographie behandelt. Diese umfassen insbesondere Stromchiffren, den Data Encrypti-on Standard (DES), Advanced Encryption Standard (AES) sowie Message Authentication Codes (MACs).Nach erfolgreichem Abschluss dieses Moduls hat der Leser/ die Leserin grundlegende theoretische Kennt-nisse in obigen Bereichen erlangt. Darüber hinaus werden Probleme erörtert, die sich im Zusammenhangder praktischen Implementierung der Verfahren ergeben, etwa die Wahl der Sicherheitsparameter.

Das Modul ist physisch in zwei Teile geteilt: Der Inhalt des Moduls ist im Buch “Understanding Cryptogra-phy” von Paar und Pelzl nachzulesen, während Sie die Übungsaufgaben in diesen Studienbriefen finden. Esgibt sowohl theoretische als auch praktischeÜbungsaufgaben. Für die Bearbeitung vieler praktischer Aufga-ben empfiehlt sich die Verwendung der Lernsoftware CrypTool, die sie über http://www.cryptool-online.org/ kostenlos erhalten können.

Aufgaben, die mit CrypTool zu lösen sind, sind entsprechend gekennzeichnet. Wie sie in CrypTool die kryp-tologischen Verfahren finden, die zum Lösen der Aufgaben benötigt werden, wird in den entsprechendenAufgaben erläutert. Ist zumBeispiel die relativeHäufigkeitsverteilung von Buchstaben in einemText gefragt,so finden sie in CrypTool imReiter “Analyse” imUnterpunkt “symmetrischeVerfahren klassisch” denUnter-punkt “Ciphertext-Only” und hier wiederum das Feld Substitution. Hier angelangt finden sie ein Tool, dasden Text analysiert. In denAufgabenwird nur kurz (Analyse→ Symmetrisch (klassisch)→Ciphertext-Only→ Subsitution) stehen, um sie zum Tool zu führen.

http://www.cryptool-online.org/http://www.cryptool-online.org/

Studienbrief 1 Einführung und Stromchiffren Seite 7

Studienbrief 1 Einführung und Stromchiffren

Lesen Sie die Seiten 1 bis 51 (Kapitel 1 und 2) des Buchs “Understanding Crypto-graphy” von Paar und Pelzl. Videos in deutscher und englischer Sprache, in denender Inhalt zusätzlich erklärt wird, finden Sie auf http://www.crypto-textbook.com/ unter “online courses/videos”.

1.1 Lernziele

Nach demDurcharbeiten des Studienbriefs kennen Sie einige historische Chiffrenundverstehen,warumdiese heutzutage nichtmehr eingesetztwerden.Die hierfürnötige Arithmetik beherrschen Sie.

Sie können die Funktionsweise von Stromchiffren ist ihnen erklären. Speziell sindsiemit demOne-Time-Pad vertraut. Sie können begründen,warumdasOne-Time-Pad als uneingeschänkte sicher gilt.

1.2 Übungen

SGFP GTPHGQTP FT OGT ZTGQHNQXßCPGT GFTNGOGT GFTGX PNPDV DZX OGQYNOG IGJNYYGTGT DZXVDGZHGQX OGX SGXPVFßCGT XUFQDVDQYX OGQ IDVDMFXVGZßCPGP ZTRGDßCPGP GFTG JVGFTG IGVRG XNTTG. ZY XFG JQGFXP FT GFTGQGTPHGQTZTI ENT ZTIGHDGCQ DßCPZTOTGZTKFI YFVVFNTGT YGFVGT GFT DRXNVZPZTRGOGZPGTOGQ, RVDZIQZGTGQ UVDTGP, OGXXGT ENY DHHGT DRXPDYYGTOGTRFNHNQYGT XN GQXPDZTVFßC UQFYFPFE XFTO, ODA XFG OFIFPDVZCQGT TNßCFYYGQ HZGQ GFTG ZTSDCQXßCGFTVFßC PNVVG GQHFTOZTI CDVPGT.OFGXGQ UVDTGP CDP - NOGQ RGXXGQ IGXDIP, CDPPG - GFT UQNRVGY. OFGYGFXPGT XGFTGQ RGSNCTGQ SDQGT HDXP FYYGQ ZTIVZGßJVFßC. KZQ VNGXZTIOFGXGX UQNRVGYX SZQOGT EFGVG ENQXßCVDGIG IGYDßCP, DRGQ OFG OQGCPGTXFßC YGFXP ZY ODX CFT ZTO CGQ JVGFTGQ RGOQZßJPGQ UDUFGQXßCGFTßCGT,ZTO ODX FXP GFTHDßC OQNVVFI, SGFV GX FY IQNAGT ZTO IDTKGT BD TFßCPOFG JVGFTGT RGOQZßJPGT UDUFGQXßCGFTßCGT SDQGT, OFG XFßC ZTIVZGßJVFßCHZGCVPGT.ZTO XN RVFGR ODX UQNRVGY RGXPGCGT. EFGVGT VGZPGT IFTI GX XßCVGßCP, OGTYGFXPGT XNIDQ YFXGQDRGV, XGVRXP OGTGT YFP OFIFPDVZCQGT.EFGVG JDYGT DVVYDGCVFßC KZ OGQ ZGRGQKGZIZTI, GFTGT IQNAGT HGCVGQIGYDßCP KZ CDRGT, DVX XFG ENT OGT RDGZYGT CGQZTPGQIGJNYYGT SDQGT. ZTOGFTFIG XDIPGT, XßCNT OFG RDGZYG XGFGT GFT CNVKSGI IGSGXGT, OFG NKGDTGCDGPPG YDT TFGYDVX EGQVDXXGT OZGQHGT.ZTO GFTGX ONTGQXPDIX ODTT, HDXP KSGFPDZXGTO BDCQG, TDßCOGY GFT YDTTDT GFTGT RDZYXPDYY IGTDIGVP SNQOGT SDQ, SGFV GQ IGXDIP CDPPG, SFGUCDTPDXPFXßC GQ XFßC ODX ENQXPGVVG, SGTT OFG VGZPG KZQ DRSGßCXVZTIYDV TGPP KZGFTDTOGQ SDGQGT, JDY GFT YDGOßCGT, ODX IDTK DVVGFT FTGFTGY ßDHE FT QFßJYDTXSNQPC XDA, UVNGPKVFßC DZH OGT PQFßCPGQ, SDXOFG IDTKG KGFP XN XßCFGHIGVDZHGT SDQ, ZTO XFG SZAPG GTOVFßC, SFG OFGSGVP IZP ZTO IVZGßJVFßC SGQOGT JNGTTPG. OFGXYDV CDPPG XFG XFßC TFßCPIGPDGZXßCP, GX SZGQOG HZTJPFNTFGQGT, ZTO TFGYDTO SZGQOG ODHZGQ DTFQIGTOSDX IGTDIGVP SGQOGT.TZQ RQDßC PQDZQFIGQSGFXG, GCG XFG DTX PGVGHNT IGCGT ZTO BGYDTOGY ODENTGQKDGCVGT JNTTPG, GFTG HZQßCPRDQ OZYYG JDPDXPQNUCG CGQGFT, ZTO FCQGFOGG IFTI HZGQ FYYGQ EGQVNQGT...

Abb. 1.1: Mit Substitu-tionschiffre verschlüs-seltes Chiffrat

http://www.crypto-textbook.com/http://www.crypto-textbook.com/

Seite 8 Studienbrief 1 Einführung und Stromchiffren

ÜbungÜ

1.1: CrypTool: Substitutionschiffren

Der Text in Abbildung 1.1 ist mit einer Substitutionschiffre verschlüsselt wor-den. Ziel dieser Aufgabe ist es, den Klartext wiederzugewinnen, d.h., dasChiffrat zu entschlüsseln. Gehen Sie dabei wie folgt vor:

1. Geben Sie die relative Häufigkeit der Buchstaben A bis Z des Chiffratsan.

2. Entschlüsseln Sie den Text auf Grundlage der relativen Häufigkeitsver-teilungen (Analyse→ Symmetrisch (klassisch)→ Ciphertext-Only→Subsitution).

3. Geben Sie die verwendete (richtige!) Substitutionstabelle an.

4. Warum ist der Schlüssel, den CrypTool liefert, nicht korrekt? Betrach-ten Sie zur Beantwortung die nachfolgende Tabelle, die die Häufig-keitsverteilungen vonBuchstaben in deutschen Prosatexten angibt. DieHäufigkeitsverteilungen für andere Sprachen finden sie z.B. bei Wiki-pedia: http://de.wikipedia.org/wiki/Buchstabenhäufigkeit.

Buchstabe Häufigkeit Buchstabe Häufigkeit Buchstabe HäufigkeitA 6.51 J 0.27 S 7.27B 1.89 K 1.21 T 6.15C 3.06 L 3.44 U 4.35D 5.08 M 2.53 V 0.67E 17.40 N 9.78 W 1.89F 1.66 O 2.51 X 0.03G 3.01 P 0.79 Y 0.04H 4.76 Q 0.02 Z 1.13I 7.55 R 7.00 ß 0.31

5. AuswelchemBuch stammt der Text?Wie heißt der Autor? (Recherchie-ren Sie im Internet, wenn nötig.)

http://de.wikipedia.org/wiki/Buchstabenh%C3%A4ufigkeit

1.2 Übungen Seite 9

ÜbungÜ

1.2: Kongruenzen

1. Bestimmen Sie folgende Kongruenzen mit dem Modulus m = 29. DieErgebnisse müssen im Bereich 0, 1, . . . ,m− 1 liegen:

a) 13 · 24 mod 29

b) 17 · 1337 mod 29

c) 69 · 31 mod 29

d) (−36) · (−28) mod 29

e) 231 · (−51) mod 29

2. Beschreiben Sie kurz den Zusammenhang zwischen den einzelnen vor-herigen Rechnungen.

3. Bestimmen Sie:

a) 3−1 mod 29

b) 2 · 6−1 mod 23

c) 7 · 3−1 · 4 · 9−1 mod 13

ÜbungÜ

1.3: Reading Assignment

Lesen Sie den Artikel “Why cryptography is harder than it looks” von BruceSchneier (siehe Anhang). (Der Inhalt dieses Textes ist prüfungsrelevant!)Beantworten Sie stichpunktartig die folgenden Fragen:

1. Warum stehen die Wetten besser für den Angreifer als für den Sicher-heitsarchitekten?

2. Bis zu welchem Punkt können Sicherheitsziele durch Kryptographiegeschützt werden?

3. Wo liegt das Problem, wenn man feststellen möchte, ob ein System si-cher ist?

4. Warum reicht es nicht, ein sicheres kryptographisches System zu ent-wickeln? Was muss noch berücksichtigt werden, damit Dieses System,Daten und Ressourcen schützen kann?

5. Warum ist die Marketing-Politik, bei entdeckten Sicherheitslücken inkryptographischen Anwendungen nicht detailliert über diese zu infor-mieren, problematisch?

6. Was sollte laut Schneier getan werden, um kryptographische Anwen-dungen zukunftssicher zu machen ?

Seite 10 Studienbrief 1 Einführung und Stromchiffren

ÜbungÜ

1.4: CrypTool: Schiebeverschlüsselung

Ein alternativesVerfahren zur Substitionschiffre ist die Shift-Verschlüsselung(auch bekannt als Schiebechiffre). Hier wird allerdings anstatt einer belie-bigen Zuordnung für jeden Buchstaben (z.B. A 7→ T,B 7→ X,C 7→ F, . . .)lediglich eine Verschiebung des gesamten Alphabets um einen geheimenOffset (Verschiebungswert) vorgenommen. So wird z.B. für den Offsetk = 5 eine Verschiebung des Alphabets um 5 Zeichen durchgeführt, z.B.A 7→ F,B 7→ G,C 7→ H, . . . und mit dieser Abbildung der Klartext kodiert.

1. Gehen Sie davon aus, dass Ihnen das Alphabet Σ = {A,B,C, . . . , Z}für Klartext und Chiffrat zu Verfügung steht. Wenn Sie eine Shift-Verschlüsselung mit dem Offset k = 10 durchführen, wie müssen Siesinnvoll die Buchstaben Q, . . . , Z aus dem Klartext belegen?

2. Verschlüsseln Sie das Wort “Datensicherheit” mit der Shift-Ver-schlüsselung (Ver/Entschlüsselung→ symmetrisch (klassisch)→Cae-sar). Verwenden Sie die geheimen Offsets k1 = 10. Verschlüsseln Siedas erhaltene Chiffrat c1 erneut mit dem geheimen Offset k2 = 11. Sieerhalten das Chiffrat c2. Welchen Schlüssel liefert die Ciphertext-only-Analyse von c2 (Analyse → symmetrische (klassisch) → Ciphertext-Only→ Caesar)? Begründen Sie.

3. Wenn Sie die Sicherheit der Shift- und der Substitionschiffre bezüglichstatistischer Angriffe vergleichen, ist die Shift-Chiffre sicherer?

4. Wenn Sie den Offset für jedes Klartextzeichen von einem beliebigenStartpunkt an inkrementieren (jeweils um eins erhöhen), wird dadurchdie Sicherheit des Verfahrens gegen statistische Angriffe erhöht?Hinweis: Zum besseren Verständnis des Verfahrens sei folgendes Bei-spiel gegeben:

Klartext: i n t e r n e tOffset: 1 2 3 4 5 6 7 8Geheimtext: J P W I W T L B

1.2 Übungen Seite 11

ÜbungÜ

1.5: Mehrfache Verschlüsselung

Eine beliebte Methode, um die Sicherheit von symmetrischen Algorithmenzu vergrößern, beruht auf der Idee, denselben Algorithmus mehrfach anzu-wenden:

y = ek2(ek1(x))

Angenommen wir haben zwei affine Chiffren ek1 = a1x + b1 und ek2 =a2x + b2.

1. Zeigen Sie, dass es eine affine Chiffre ek3 = a3x + b3 gibt, die genaudieselbe Verschlüsselung (und Entschlüsselung) wie die Kombinationek2(ek1(x)) erzeugt.

2. Bestimmen Sie a3, b3 mit a1 = 7, b1 = 13 and a2 = 18, b2 = 9 mitModulus 23.

3. CrypTool: Verifizieren Sie ihr Ergebnismit CrypTool. Verschlüsseln Siedafür m = AB beliebigen Klartext mit k1 zu c1 (Ver-/Entschlüsselung→ symmetrisch (klassisch)→ Hill (1x1) Zahlwert a1, das Chiffrat mit-tels Caesar-Chiffre mit Schlüssel b1 verschlüsseln). Verschlüsseln Siedann c1 mit k2 zu c2. Können Sie c2 auch direkt aus m erhalten? Wielautet der Schlüssel hierfür? Begründen Sie.

4. Beschreiben Sie kurz was passiert, wenn Sie einen Brute-Force-Angriffgegen die Zweifach-Verschlüsselung der affinen Chiffre anwenden.Hat sich der effektive Schlüsselraum vergrößert? Kennen Sie einen ef-fektiveren Angriff auf die affine Chiffre als einen Brute-Force-Angriff?

Bemerkung: Die Verwendung vonMehrfach-Verschlüsselung ist von großerpraktischer Bedeutung. Bei DES erhöht sich z.B. die Sicherheit, wenn wirdieses mehrfach hintereinander anwenden; Mehr dazu später.

ÜbungÜ

1.6: CrypTool: Affine Chiffre

Dechiffrieren Sie den folgenden Text:

fhhp://5v8.qtje/twjo_f9c8ni_whglhneotxegn

unter Benutzung der affinen Chiffre mit den Schlüsselwerten a = 11, b = 6und dem Modulus 26. Hinweis: Ziffern und Satzzeichen wurde nicht ver-schlüsselt.

ÜbungÜ

1.7: One-Time-Pad-Sicherheit

Auf den ersten Blick scheint es, als ob eine Brute-Force-Attacke (vollständigeSchlüsselsuche) gegen das One-Time-Pad möglich ist. Das ist ein Paradoxon,dawirwissen, dass dasOTPuneingeschränkt sicher ist. Beschreiben Sie kurz(maximal 3 Sätze), warum die Brute-Force-Attacke nicht durchführbar ist.Anmerkung: Sie müssen das Paradoxon lösen, d.h. eine Antwort ”Der OTPist uneingeschränkt sicher und deshalb ist eine Brute-Force-Attacke nichtdurchführbar” ist nicht ausreichend!

Seite 12 Studienbrief 1 Einführung und Stromchiffren

ÜbungÜ

1.8: CrypTool: Rechenaufgabe zu One-Time-Pad

DasOne-Time-Pad (OTP)wird (u.a.) zur Verschlüsselung des binärenAlpha-bets (Σ ∈ {0, 1}) verwendet. Hiermit können Daten von beliebiger Längebitweise verschlüsselt werden.

Entschlüsseln Sie den folgenden Chiphertext18 03 07 1e 04 4c 28 1d 0c 01 54 09 49 27 0a 53 17 06 1b 19 5a,welcher mit dem OTP Schlüssel:48 6f 72 73 74 20 47 6f 65 72 74 7a 20 49 6e 73 74 69 74 75 74verschlüsselt worden ist.

Die Entschlüsselung ist von Hand durchzuführen (Klausurbedingungen).Verwenden Sie eine ASCII-Zeichensatz-Tabelle, um den Klartext und denSchlüssel wiederzugewinnen.

Verifizieren Sie ihr Ergebnis mit CrypTool.

ÜbungÜ

1.9: CrypTool: One-Time-Pad-Angriff bei sich wiederholendemSchlüsselSie haben bislang einigeVerschlüsselungsübungen bereits perHand erledigt.Im Ordner zur Veranstaltung befindet sich eine verschlüsselte JPG-Dateiboardingpass.jpg.hex.

Joe ist verschwunden. Sein letztes Lebenszeichen ist einOnline-Ticket auf sei-nem Rechner, das leider verschlüsselt abgelegt wurde. Anhand des Datein-amens konnten Sie erkennen, dass es sich bei demChiffrat umeine JPG-Dateihandelt. In diesem Format übermittelt nur eine Airline ihre Tickets. Von die-ser erfahren Sie, dass das Ticket zur Übertragung mit einem sich wiederho-lenden Schlüsselstring XOR verknüpft wurde. Dieser String ist allerdings beijeder Übertragung zufällig und nicht mehr bekannt.

1. Öffnen siewillkürlich einigeDateien im JPG-Formatmit demCrypToolund schauen sie sich jeweils den Anfang der Datei an. Beschreiben Sie,was alle Dateien gemeinsam haben.

2. Der Schlüssel zur Verschlüsselung der o.g. Datei hat eine Länge vonsechs Zeichen. Wie lautet er in HEX-Darstellung?

3. Nutzen Sie dieses Wissen, ummit Hilfe des CrypTools die Datei zu de-chiffrieren (entschl→ symmetrisch→ klassisch→ XOR). Wohin gingJoes letzte bekannte Reise? Wie lautet die Flugnummer? Mit welcherFluggesellschaft war er unterwegs?

Historische Bemerkung: Es wird berichtet, dass das Ehepaar Rosenberg inden 50er Jahren eine solche Verschlüsselung verwendete, um der UDSSRWissen über den Bau der Atombombe zukommen zu lassen. Da sie auf demelektrischen Stuhl endeten, könnenwir dieMehrfachverwendung einesOTP-Schlüssels nicht uneingeschränkt empfehlen.

Studienbrief 2 DES Seite 13

Studienbrief 2 DES

Lesen Sie die Seiten 55 bis 82 (Kapitel 3) des Buches “Understanding Cryptogra-phy” vonPaar undPelzl. Videos in deutscher und englischer Sprache, in denenderInhalt zusätzlich erklärt wird, finden Sie auf http://www.crypto-textbook.com/unter “online courses/videos”.

2.1 Lernziele

Wenn Sie diesen Studienbrief durchgearbeitet haben, erläutern sind Sie fähig dieFunktionsweise moderner Blockchiffren. Sie sind in der Lage die Begriffe Konfu-sion und Diffusion in den Kontext von Blockchiffren einzuordnen.

Speziell erklären Sie die Bestandteile von DES und deren Funktion während derVerschlüsselung. Sie verstehen die Bedeutung der S-Boxen.

Sie geben Schwachstellen von DES wieder.

2.2 Übungen

ÜbungÜ

2.1: Bit-Lawineneffekte im DES

Für eine gute Blockchiffre ist eswünschenswert, dass bei der Veränderung ei-nes Eingangsbits möglichst viele Ausgangsbits verändert werden (Diffusionoder Avalanche-Effekt). Im folgenden werden wir versuchen, die Diffusions-eigenschaft von DES zu überprüfen. Wir verwenden hierzu eine Eingangs-bitfolge, bei der das Bit an der Position 57 gleich Eins ist (x57 = 1) und alleanderen Bits gleich Null sind. Die 56 Schlüsselbits sind ebenfalls alle gleichNull. (Beachten Sie, daß die Eingangsbits als erstes die EingangspermutationIP durchlaufen!)

1. Auf welche S-Boxen wirkt sich dieses Bit in der ersten DES Runde aus, bzw.wie sehen die Eingangsbits aller S-Boxen aus?

Auswirkungen auf: (ankreuzen)S1 ~ S2 ~ S3 ~ S4 ~ S5 ~ S6 ~ S7 ~ S8 ~

Eingangsbits:S-Box 1 S-Box 2 S-Box 3 S-Box 4

S-Box 5 S-Box 6 S-Box 7 S-Box 8

2. Geben Sie das Ergebnis nach der ersten Runde an. (L1 und R1)

3. Ermitteln Sie das Ergebnis nach der ersten Runde für den Fall, daß alleEingangsbits gleich Null sind (d.h. auch x57). Wie viele Bits haben sich in

http://www.crypto-textbook.com/

Seite 14 Studienbrief 2 DES

L1

R1

L1 und R1 im Vergleich zu Aufgabenteil 2) verändert?

L1

R1

Anzahl geänderter Bits:

ÜbungÜ

2.2: Nichtlienarität der S-Boxen

Eine wichtige Eigenschaft des DES ist die Nichtlinearität der S-Boxen. In die-ser Übungsaufgabe wollen wir diese Eigenschaft verifizieren, indemwir dieAusgangsbits für verschiedene Eingangsbits in einer S-Box Si vergleichen.Zeigen Sie, daß für S5 das folgende Entwurfkriterium gilt:

Si(x1)⊕ Si(x2) 6= Si(x1 ⊕ x2).

Benutzen Sie die folgenden Eingangsbits:

1. x1 = 010100, x2 = 110001

2. x1 = 111111, x2 = 101000

3. x1 = 100001, x2 = 011110

ÜbungÜ

2.3: Permutationen im DES

Wir möchten überprüfen, ob IP−1 die inverse Operation von IP ist. Wir be-trachten den 64-Bit-Vektor x = (x1, x2, . . . , x64). Zeigen Sie für die Bits x8, x22und x58, dass IP−1(IP(xi)) = xi gilt.

2.2 Übungen Seite 15

ÜbungÜ

2.4: CrypTool: DES-Entschlüsselung

Ein Freund hat eine Nachricht für Sie mit dem DES verschlüsselt und hatIhnen den zugehörigen Schlüssel auf einem kleinen Stück Papier in der Vor-lesung zugesteckt. Da der Zettel von einer Ecke abgerissen wurde, ist leiderdie letzte Stelle des hexadezimalen 64-Bit-Schlüssels (=16 Hexzeichen) nichtvollständig lesbar. Erkennbar ist noch, dass das fehlende Symbol eine Zahlsein müsste.

1. Wie viele Möglichkeiten müssen Sie unter diesen Umständen imDurchschnitt und im schlimmsten Fall durchprobieren, um den kor-rekten Schlüssel durch Ausprobieren zu erraten? (Hinweis: DES ver-wendet 56-bit Schlüssel, aber es ist ein 64-bit Schlüssel angegeben.Die „überflüssigen“ Bit des 64-bit Schlüssels sind nicht willkürlich ge-wählt.)

2. ImÜbungsordner befindet sich dieNachricht E-Mail_ciphertext.hex.Gegeben sei der Schlüssel B3 3A 89 2B A5 2B CC FX, wobei X nurbedingt lesbar war (siehe Hinweis weiter oben). Verwenden Sie die imCrypTool vorhandene DES-Entschlüsselung, um

a) den korrekten Schlüsselkandidaten herauszufinden (Analyse →Symmetrische (modern) → DES (EBC) geben Sie die bekanntenSchlüsselzeichen ein) und

b) die Nachricht Ihres Freundes zu entschlüsseln.

3. Nehmen Sie an, sie hättenmehr Schlüsselzeichen verloren. Schauen Siesich mit CrypTool die erwartete Entschlüsselungsdauer in Abhängig-keit der Anzahl der bekannten Zeichen an.

Hinweis: Beachten Sie, dass Sie die Entschlüsselung im ECB-Modusverwenden. Was sich hinter diesem Entschlüsselungsmodus verbirgt,werden Sie im weiteren Verlauf der Veranstaltung kennenlernen.

4. Unterscheidet sich die erwartete Rechendauer desCBC-Modus vonderdes ECB-Modus?

Seite 16 Studienbrief 2 DES

ÜbungÜ

2.5: Brute-Force-Schlüsselsuche

Ein generischer Angriff auf Verschlüsselungsverfahren ist das systematischeDurchsuchen des Schlüsselraums, indem für einen bekannten Klartext jedermögliche Schlüssel ausprobiert und mit dem abgehörten Chiffretext vergli-chen wird. Dieser Angriff ist auch als Brute-Force-Angriff bekannt.Wie schnell der Angriff zumErfolg führt, hängt im Einzelfall vom gewähltenSchlüssel ab und an welcher Stelle er beim Durchsuchen probiert wird. Den-noch kannman allgemeineAussagen über die Erfolgswahrscheinlichkeit desAngriffs bei Verschlüsselungsverfahren machen.

1. Gegeben sei ein Verschlüsselungsverfahren mit 56 Bit Schlüssellänge(DES). Wie viele Verschlüsselungen benötigt man für einen erfolgrei-che Brute-Force-Angriff (I) im Durchschnitt und (II) im schlimmstenFall, wenn der Schlüssel als allerletzes gefunden wird?

2. Sie haben einen günstigen Computer für 350 EUR mit einem Core i7Prozessor und 4 · 3 GHz zur Verfügung. Dieser Rechner schafft 10 Mil-lionen DES-Verschlüsselungen bei 56 Bit Schlüssellänge pro Sekunde.Wie lange benötigt ein erfolgreicher Brute-Force-Angriff mit diesemRechner im Durchschnitt?

3. Nehmen Sie an, Sie haben insgesamt ein Budget von 17.500 EUR.WennSie für dieses Geld Computer zu je 350 EUR kaufen, wie lange dauertdann eine parallele DES-Schlüsselsuche im Schnitt?

4. Ein Spezialcluster mit 180 parallel arbeitenden Hardwarebausteinen(FPGAs) ist ebenfalls für 17.500 EUR zu realisieren. Ein einzelner Hard-warebaustein hat insgesamt 4 Rechenwerke, die jeweils 120 MillionenDES-Verschlüsselungen pro Sekunde schaffen. Wie lange dauert es imDurchschnitt, bis dieser Cluster einen DES-Schlüssel mit einem Brute-Force- Angriff erfolgreich knacken kann?

ÜbungÜ

2.6: DES-Entschlüsselung

Aus dem Buch zur Vorlesung wissen Sie, dass sich die Entschlüsselung nurgeringfügig von der Verschlüsselung unterscheidet. Dies liegt an der beson-deren Struktur, die nach dem Erfinder Horst Feistel benannt wurde.

1. Worin besteht der einzige Unterschied zwischen einer DES-Verschlüsselung und einer DES-Entschlüsselung?

2.2 Übungen Seite 17

ÜbungÜ

2.7: CrypTool: DES-Bitkomplement

Wir stellen das Komplement einer Zahl A (d.h. alle Bits dieser Zahl werdeninvertiert) mit A′ da. (Bsp.: Wenn A = 0110 ist, dann ist A′ = 1001.) “⊕“entspricht dem bitweisen XOR. Wir wollen folgendes zeigen:

Verschlüsseln Sie eine Zeichenkettenmder Länge 8 (ASCII Zeichen)mit DESunter einem gegebenen SchlüsselK. Lassen sie sich die Hex-Darstellung desKlar- und Geheimtextes anzeigen und ermitteln Sie daraus die Bitdarstel-lung. Verschlüsseln Sie anschließend das Komplement m′ von m mit DESunter demSchlüsselK ′ (Berechnen Sie dasKomplement bitweise. BerechnenSie daraus die Hex-Darstellung des Komplements. Konvertieren Sie diese inASCII-Zeichen.).

Betrachten Sie die Bitdarstellung der Verschlüsselung von m und m′. Wasfällt auf? Gilt dies immer?

Seite 18 Studienbrief 3 AES

Studienbrief 3 AES

Lesen Sie die Seiten 87 bis 117 (Kapitel 4) des Buches “Understanding Cryptogra-phy” vonPaar undPelzl. Videos in deutscher und englischer Sprache, in denenderInhalt zusätzlich erklärt wird, finden Sie auf http://www.crypto-textbook.com/unter “online courses/videos”.

3.1 Lernziele

Sie erklären die Komponenten von AES. Die zugrundeliegende Arithmetik be-herrschen Sie. Sie erläutern, wie bekannte Schwachstellen von DES behoben wer-den.

3.2 Übungen

ÜbungÜ

3.1: Polynome im endlichen Körper

Gegeben sei das irreduzible Polynom P (x) = x4 +x+ 1. Wieviele PolynomeA(x) mit Elementen aus

1. GF (2)

2. GF (n)

existieren, für die gilt grad(A(x)) < grad(P (x)).

ÜbungÜ

3.2: Addition in GF (24)

Berechnen Sie A(x) + B(x) mod P (x) in GF (24) mit dem irreduziblen Re-duktionspolynom P (x) = x4 + x3 + 1.

1. A(x) = x3 + x2 + 1, B(x) = x3 + x + 1

2. A(x) = x + 1, B(x) = x3 + x

3. A(x) = x3 + x2 + x + 1, B(x) = x3 + x

4. Welche Auswirkung hat dieWahl des Reduktionspolynoms auf die Be-rechnungsschritte?

http://www.crypto-textbook.com/

3.2 Übungen Seite 19

ÜbungÜ

3.3: Multiplikation in GF (24)

Berechnen SieA(x) ·B(x) mod P (x) inGF (24) mit dem irreduziblen Reduk-tionspolynom P (x) = x4 + x3 + 1.

1. A(x) = x3 + x2 + 1, B(x) = x3 + x

2. A(x) = x + 1, B(x) = x3 + 1

3. A(x) = x3 + x2 + x + 1, B(x) = x3 + x2

ÜbungÜ

3.4: Schlüsselableitung im AES

Jede Runde vom AES verwendet einen anderen Unterschlüssel, der vomHauptschlüssel abgeleitet wird. In dieser Aufgabe wollen wir die Schlüssela-bleitung im AES nachvollziehen. Oft werden die jeweiligen Teile des Schlüs-sels und Unterschlüssels in 32-Bit-Worten Ki angegeben.

1. Gegeben Sei ein Hauptschlüssel (K0,K1,K2,K3), der nur ausNullen besteht. Bestimmen Sie den entprechenden Unterschlüssel(K4,K5,K6,K7) nach der ersten Runde der Schlüsselableitung. (Abga-be nur als Hexwerte)

2. Gegeben Sei ein Hauptschlüssel (K0,K1,K2,K3) = (0x00000001,0x00000002, 0x00000003, 0x00000004). Bestimmen Sie erneut den Un-terschlüssel (K4,K5,K6,K7) nach der ersten Runde der Schlüsselablei-tung.

Seite 20 Studienbrief 3 AES

ÜbungÜ

3.5: Bit-Lawineneffekte im AES

Wie DES soll auch AES die Eigenschaft haben, dass die Veränderung einesBits am Eingang einer Runde eine Änderung möglichst vieler Ausgangsbitsder Runde zur Folge haben (Diffusion oder Avalanche-Effekt). Die Diffusi-onseigenschaft des AES nach einer Runde soll in dieser Aufgabe überprüftwerden.

Gegeben sei die folgende 128-Bit AES-Eingabe in je 32-Bit-Worten W =(w0, w1, w2, w3) = (0x00000000, 0x01000000, 0x00000000, 0x00000000). Derzur Berechnung der Ausgabe nach der ersten AES-Runde benötigte Unter-schlüssel k0 ist mit

k0 = (0xDEADBEEF)

(0xCAFEBABE)

(0xDEADBEEF)

(0xCAFEBABE)

gegeben. Sie können zur Lösung dieser Aufgabe auch Programme schreiben.

1. Geben Sie die entsprechende Ausgabe zur Eingabe W nach der erstenRunde des AES an! Verwenden Sie dabei den gegebenen Unterschlüs-sel k0!

Hinweise: Beachten Sie die Reihenfolge, in der die Bytes in den Algo-rithmus geschrieben werden (von oben nach unten und von links nachrechts).Rechnen Sie alle Zwischenergebnisse nach: Plaintext, KeyAddition,Substitution, ShiftRows, MixColumns und KeyAddition.

2. Ermitteln Sie die Ausgabebytes nach der ersten Runde für den Fall,dass diesmal alle Eingangsbytes gleich Null sind.

3. Wieviele Ausgangsbits haben sich im Vergleich der beiden Fälle verän-dert? Wir betrachten hier nur eine einzige Runde des AES. Nach jederweiteren Runde werden mehr und mehr Änderungen der Ausgangs-bits auftreten (Lawineneffekt).

ÜbungÜ

3.6: CrypTool: AES vs. DES

Sie haben DES bereits empirisch untersucht. Führen Sie ihre Untersuchun-gen auch für AES aus. Vergleichen Sie insbesondere:

• die Laufzeiten des Brute-Force-Angriffs bei nicht vollständig bekann-tem Schlüssel und

• Chiffretexte von komplementären Klartexten unter komplementärenSchlüsseln (s.o.).

Studienbrief 4 More about block ciphers Seite 21

Studienbrief 4 More about block ciphers

Lesen Sie die Seiten 123 bis 144 (Kapitel 5) des Buchs “Understanding Cryptogra-phy” vonPaar undPelzl. Videos in deutscher und englischer Sprache, in denenderInhalt zusätzlich erklärt wird, finden Sie auf http://www.crypto-textbook.com/unter “online courses/videos”.

4.1 Lernziele

Sie sind in der Lage die Notwendigkeit von Operationsmodi für Blockchiffren zuerklären und Sie erläutern die Funktionsweise der gängigsten Operationsmodi.Sie verstehen die Problematik der Fehlerfortpflanzung im Bezug auf Operations-modi.

4.2 Übungen

ÜbungÜ

4.1: CrypTool: CBC- vs. ECB-Modus

Verifizieren Sie mittels CrypTool die Konfusionseigenschaft des CBC-Betriebsmodus. Verschlüsseln Sie dazu einen sich periodisch wiederho-lenden String. Verschlüsseln Sie diesen sowohl im ECB-Modus als auch imCBC-Modus (mit DES). Vergleichen Sie die Chiffretexte.

Betrachten wir (stark vereinfacht) die Speicherung von Daten in verschüs-selter Form in einer großen Datenbank. Für die Verschlüsselung verwendenwir AES. Wir nehmen an, dass die zu speichernden Einträge eine Größe von1024 Bit haben, und dass zwischen den verschiedenen Einträgen kein Zu-sammenhang besteht. Beantworten Sie die beiden folgenden Fragen kurz inStichworten:

• Was sind die Vor- und Nachteile des ECB-Modes für dieser Anwen-dung?

• Was sind die Vor- und Nachteile des CBC-Modes?

http://www.crypto-textbook.com/

Seite 22 Studienbrief 4 More about block ciphers

ÜbungÜ

4.2: Fehlerfortpflanzung in Verschlüsselungsmodi

Ein wichtiges Entscheidungsmerkmal für die Auswahl des Verschlüsse-lungsmodus in der Praxis ist die Fehlerfortpflanzung.

• Nehmen wir an, dass während der Übermittlung ein Fehler in einemBlock des Geheimtextes yi auftritt. Welche Klartextblöcke sind auf derSeite von Bob betroffen, wenn wir ECB Mode verwenden?

• Nehmenwir wieder an, dass im Block yi ein Fehler während der Über-mittlung aufgetreten ist. Welche Klartextblöcke sind auf der Seite vonBob betroffen, wenn wir CBC Mode verwenden?

• Nehmenwir wieder an, dass im Block yi ein Fehler während der Über-mittlung aufgetreten ist. Welche Klartextblöcke sind auf der Seite vonBob betroffen, wenn wir OFB Mode verwenden?

• Stellenwir uns vor, wir haben einen Fehler imKlartextblock xi auf derSeite von Alice. Welche Klartextblöcke sind auf der Seite von Bob vondiesem Fehler betroffen, wenn wir CBC Mode verwenden?

• Was geschieht, wenn durch einen Übertragungsfehler ein Chiffretext-block im Netzwerk verloren geht, der zuvor mit dem CBC Mode ver-schlüsselt wurde?

• Was geschieht, wenn durch einen Übertragungsfehler ein Chiffretext-block im Netzwerk verloren geht, der zuvor mit dem OFB Mode ver-schlüsselt wurde?

4.2 Übungen Seite 23

ÜbungÜ

4.3: Doppelte DES-Verschlüsselung

Gegeben ist eine doppelte DES-Verschlüsselung (2DES)

2DES(x) = DESK2(DESK1(x))

In dieser Aufgabe wollen wir eine Kostenabschätzung für verschiedene An-griffe auf 2DES vornehmen.

• Zeichnen Sie ein Blockdiagramm von 2DES. Der DES-Algorithmussollte hierbei als einfache Box dargestellt werden (also keine DES-Interna!).

• Zunächst betrachten wir eine reine Schlüsselsuche ohne nennenswer-ten Speicheraufwand. Hierbei muss der gesamte Schlüsselraum, dergemeinsam von K1 und K2 gebildet wird, durchsucht werden. Wieteuerwird eine Suchmaschine, mit derwir 2DES im “worst case” nach1 Woche brechen können?Wir nehmen an, dass wir spezielle Hardware Chips (ASICs) zur Ver-fügung haben, die 107 Schlüssel pro Sekunde überprüfen können. EinChip kostet 5 Euro. Darüber hinaus nehmen wir einen Overhead von50% auf die Chipkosten für den Bau der Maschine an. Setzen Sie dieKosten der Suchmaschine insVerhältnis zumEtat der Bundesrepublik,der etwa bei 300 · 109 Euro beträgt.

• Alternativ betrachten wir jetzt eine meet-in-the-middle (auch time-memory trade-off) genannte Attacke, bei der wir viel Speicher einset-zen können. Beantworten Sie hierzu folgende Fragen:

– Wieviel Einträge müssen gespeichert werden?

– Wieviel Bytes (nicht Bits!) müssen pro Eintrag gespeichert wer-den?

– Wie teuer ist eine Schlüsselsuche, die nach maximal einer Wo-che zum Erfolg führt? Bitte beachten Sie, dass Sie zunächsteinen Schlüsselraum komplett durchlaufen müssen, um denSpeicher zu füllen. Erst danach kann der Raum des zweitenSchlüssels durchsucht werden. Für das nacheinander folgendeDurchlaufen der beiden Schlüsselräume kann die gleiche Hard-ware verwendet werden.

Für eineKostenabschätzungdes Speichers nehmen Sie einen Preis von100 Euro / 1 TB an, wobei der Einfachheit halber mit 1 TB = 1012 Bytegerechnet werden soll. Für die Kosten der Schlüsselsuche nehmen Siedie Kosten von oben an. Setzen Sie die Kosten für die meet-in-the-middle-Attacke wieder ins Verhältnis zum Bundeshaushalt.

Seite 24 Studienbrief 5 Message Authentication Codes

Studienbrief 5 Message Authentication Codes

5.1 Lernziele

Nach dem Durcharbeiten dieses Studienbriefs verstehen Sie die Notwendigkeitvon Message Authentication Codes (MACs) und erläutern, wie MACs berechnetwerden.

5.2 Übungen

Lesen Sie die Seiten 319 bis 328 (Kapitel 12) des Buches “Understanding Crypto-graphy” von Paar und Pelzl (Sie können den Abschnitt 12.2 auslassen). Videos indeutscher und englischer Sprache, in denen der Inhalt zusätzlich erklärt wird, fin-den Sie auf http://www.crypto-textbook.com/ unter “online courses/videos”.

ÜbungÜ

5.1: Adaptive Chosen Plaintext Angriff auf den CBC-MAC

Wir wollen in dieser Aufgabe zeigen, dass der CBC-MAC unter bestimmtenAnnahmen nicht sicher ist.

EinemAngreifer steht ein OrakelO zur Verfügung, das zu beliebig (endlich)vielen Nachrichten mit unterschiedlicher Länge einen MAC mit einem demAngreifer unbekannten Schlüssel k erzeugt. Der Angreifer darf jede erhal-tenen MAC für weitere Nachrichten verwenden (Adaptive Chosen PlaintextAttack).

1. Nehmen Sie an, dass im Rahmen des Angriffs als IV der Nullvektorverwendet wird. Zeigen Sie, wie Sie als Angreifer nach einer endli-chen Zahl anNachrichten xi, die SieO zur Authentifizierung geschickthaben, schließlich eine weitere, mit dem MAC von O authentifizierteNachricht selbst erzeugen können (die natürlich nicht dem O schon zu-vor übermittelt wurde, sonst macht der Angriff keinen Sinn).

2. Welche Annahme ist für den Angriff wichtig und wie kann er verhin-dert werden?

http://www.crypto-textbook.com/

WHY CRYPTOGRAPHYIS HARDER THAN IT LOOKSby Bruce Schneier

From e-mail to cellular communications, from secure Web access to digitalcash, cryptography is an essential part of today’s information systems.Cryptography helps provide accountability, fairness, accuracy, and confiden-tiality. It can prevent fraud in electronic commerce and assure the validity offinancial transactions. It can prove your identity or protect your anonymity. Itcan keep vandals from altering your Web page and prevent industrial com-petitors from reading your confidential documents. And in the future, as com-merce and communications continue to move to computer networks,cryptography will become more and more vital.

But the cryptography now on the market doesn’t provide the level of securityit advertises. Most systems are not designed and implemented in concert withcryptographers, but by engineers who thought of cryptography as just anoth-er component. It’s not. You can’t make systems secure by tacking on cryptog-raphy as an afterthought. You have to know what you are doing every step ofthe way, from conception through installation.

Billions of dollars are spent on computer security, and most of it is wasted oninsecure products. After all, weak cryptography looks the same on the shelf asstrong cryptography. Two e-mail encryption products may have almost thesame user interface, yet one is secure while the other permits eavesdropping. Acomparison chart may suggest that two programs have similar features,although one has gaping security holes that the other doesn’t. An experiencedcryptographer can tell the difference. So can a thief.

Present-day computer security is a house of cards; it may stand for now, but itcan’t last. Many insecure products have not yet been broken because they arestill in their infancy. But when these products are widely used, they willbecome tempting targets for criminals. The press will publicize the attacks,undermining public confidence in these systems. Ultimately, products will winor lose in the marketplace depending on the strength of their security.

With cryptography, what

you see isn’t what you get.

Subtle flaws can render

any security system

vulnerable to attack.

Counterpane Systems

has the expertise you need

to make sure your system

is as secure as it looks.

Copyright © 1997 Counterpane Systems. All rights reserved.

COUNTERPANE SYSTEMS

Counterpane Systemspage 2

Every form of commerce ever invented has been subject to fraud, from rigged scales in a farmers’ market to counterfeit currency to phony invoic-es. Electronic commerce schemes will also face fraud, through forgery, misrep-resentation, denial of service, and cheating. In fact, computerization makes therisks even greater, by allowing attacks that are impossible against non-auto-mated systems. A thief can make a living skimming a penny from every Visacardholder. You can’t walk the streets wearing a mask of someone else’s face,but in the digital world it is easy to impersonate others. Only strong cryptog-raphy can protect against these attacks.

Privacy violations are another threat. Some attacks on privacy are targeted: amember of the press tries to read a public figure’s e-mail, or a company tries tointercept a competitor’s communications. Others are broad data-harvestingattacks, searching a sea of data for interesting information: a list of rich wid-ows, AZT users, or people who view a particular Web page.

Criminal attacks are often opportunistic, and often all a system has to be ismore secure than the next system. But there are other threats. Some attackersare motivated by publicity. They usually have access to significant computingresources at their corporations or research institutions, and lots of time, butnot much money. Lawyers sometimes need a system attacked, in order toprove their client’s innocence. Lawyers can collect details on the systemthrough the discovery process, and then use considerable financial resources tohire experts and buy equipment. And they don’t have to defeat the security ofa system completely, just enough to convince a jury that the security is flawed.

Electronic vandalism is an increasingly serious problem. Computer vandalshave already graffitied the CIA’s web page, mail-bombed Internet providers,and canceled thousands of newsgroup messages. And of course, vandals andthieves routinely break into networked computer systems. When security safe-guards aren’t adequate, trespassers run little risk of getting caught.

Attackers don’t follow rules; they cheat. They can attack a system using tech-niques the designers never thought of. Art thieves have burgled homes by cut-ting through the walls with a chain saw. Home security systems, no matterhow expensive and sophisticated, won’t stand a chance against this attack.Computer thieves come through the walls too. They steal technical data, bribeinsiders, modify software, and collude. They take advantage of technologiesnewer than the system, and even invent new mathematics to attack the systemwith.

The odds favor the attacker. Bad guys have more to gain by examining a sys-tem than good guys. Defenders have to protect against every possible vulner-ability, but an attacker only has to find one security flaw to compromise thewhole system.

No one can guarantee 100% security. But we can work toward 100% riskacceptance. Fraud exists in current commerce systems: cash can be coun-terfeited, checks altered, credit card numbers stolen. Yet these systems are stillsuccessful, because the benefits and conveniences outweigh the losses. Privacysystems—wall safes, door locks, curtains—are not perfect, but they’re oftengood enough. A good cryptographic system strikes a balance between what ispossible and what is acceptable.

WHAT CRYPTOGRAPHYCAN AND CAN’T DO

THREATS TOCOMPUTER SYSTEMS

Strong cryptography can withstand targeted attacks up to a point—the pointat which it becomes easier to get the information some other way. A comput-er encryption program, no matter how good, will not prevent an attacker fromgoing through someone’s garbage. But it can prevent data-harvesting attacksabsolutely; no attacker can go through enough trash to find every AZT user inthe country. And it can protect communications against non-invasive attacks:it’s one thing to tap a phone line from the safety of the telephone central office,but quite another to break into someone’s house to install a bug.

The good news about cryptography is that we already have the algorithms andprotocols we need to secure our systems. The bad news is that that was the easypart; implementing the protocols successfully requires considerable expertise.The areas of security that interact with people—key management,human/computer interface security, access control—often defy analysis. Andthe disciplines of public-key infrastructure, software security, computer securi-ty, network security, and tamper-resistant hardware design are very poorlyunderstood.

Companies often get the easy part wrong, and implement insecure algorithmsand protocols. But even so, practical cryptography is rarely broken through themathematics; other parts of systems are much easier to break. The best proto-col ever invented can fall to an easy attack if no one pays attention to the morecomplex and subtle implementation issues. Netscape’s security fell to a bug inthe random-number generator. Flaws can be anywhere: the threat model, thedesign, the software or hardware implementation, the system management.Security is a chain, and a single weak link can break the entire system. Fatalbugs may be far removed from the security portion of the software; a designdecision that has nothing to do with security can nonetheless create a securityflaw.

Once you find a security flaw, you can fix it. But finding the flaws in a prod-uct can be incredibly difficult. Security is different from any other designrequirement, because functionality does not equal quality. If a word processorprints successfully, you know that the print function works. Security is differ-ent; just because a safe recognizes the correct combination does not mean thatits contents are secure from a safecracker. No amount of general beta testingwill reveal a security flaw, and there’s no test possible that can prove the absenceof flaws.

Agood design starts with a threat model: what the system is designed to protect, from whom, and for how long. The threat model must take theentire system into account—not just the data to be protected, but the peoplewho will use the system and how they will use it. What motivates the attack-ers? Must attacks be prevented, or can they just be detected? If the worst hap-pens and one of the fundamental security assumptions of a system is broken,what kind of disaster recovery is possible? The answers to these questions can’tbe standardized; they’re different for every system. Too often, designers don’ttake the time to build accurate threat models or analyze the real risks.

Threat models allow both product designers and consumers to determine whatsecurity measures they need. Does it makes sense to encrypt your hard drive ifyou don’t put your files in a safe? How can someone inside the company

Counterpane Systems page 3

THREAT MODELS

Counterpane Systemspage 4

defraud the commerce system? Are the audit logs good enough to convince acourt of law? You can’t design a secure system unless you understand what ithas to be secure against.

Design work is the mainstay of the science of cryptography, and it is very specialized. Cryptography blends several areas of mathematics: numbertheory, complexity theory, information theory, probability theory, abstractalgebra, and formal analysis, among others. Few can do the science properly,and a little knowledge is a dangerous thing: inexperienced cryptographersalmost always design flawed systems. Good cryptographers know that nothingsubstitutes for extensive peer review and years of analysis. Quality systems usepublished and well-understood algorithms and protocols; using unpublishedor unproven elements in a design is risky at best.

Cryptographic system design is also an art. A designer must strike a balancebetween security and accessibility, anonymity and accountability, privacy andavailability. Science alone cannot prove security; only experience, and the intu-ition born of experience, can help the cryptographer design secure systems andfind flaws in existing designs.

There is an enormous difference between a mathematical algorithm and itsconcrete implementation in hardware or software. Cryptographic systemdesigns are fragile. Just because a protocol is logically secure doesn’t mean itwill stay secure when a designer starts defining message structures and passingbits around. Close isn’t close enough; these systems must be implementedexactly, perfectly, or they will fail. A poorly-designed user interface can make ahard-drive encryption program completely insecure. A false reliance on tam-per-resistant hardware can render an electronic commerce system all but use-less. Since these mistakes aren’t apparent in testing, they end up in finishedproducts. Many flaws in implementation cannot be studied in the scientific lit-erature because they are not technically interesting. That’s why they crop up inproduct after product. Under pressure from budgets and deadlines, imple-menters use bad random-number generators, don’t check properly for errorconditions, and leave secret information in swap files. The only way to learnhow to prevent these flaws is to make and break systems, again and again.

In the end, many security systems are broken by the people who use them. Most fraud against commerce systems is perpetrated by insiders. Honestusers cause problems because they usually don’t care about security. They wantsimplicity, convenience, and compatibility with existing (insecure) systems.They choose bad passwords, write them down, give friends and relatives theirprivate keys, leave computers logged in, and so on. It’s hard to sell door locksto people who don’t want to be bothered with keys. A well-designed systemmust take people into account.

Often the hardest part of cryptography is getting people to use it. It’s hard toconvince consumers that their financial privacy is important when they arewilling to leave a detailed purchase record in exchange for one thousandth ofa free trip to Hawaii. It’s hard to build a system that provides strong authenti-cation on top of systems that can be penetrated by knowing someone’s moth-er’s maiden name. Security is routinely bypassed by store clerks, senior

CRYPTOGRAPHYFOR PEOPLE

IMPLEMENTATION

SYSTEM DESIGN

executives, and anyone else who just needs to get the job done. Only whencryptography is designed with careful consideration of users’ needs and thensmoothly integrated, can it protect their systems, resources, and data.

Right now, users have no good way of comparing secure systems. Computer magazines compare security products by listing their features, not byevaluating their security. Marketing literature makes claims that are just nottrue; a competing product that is more secure and more expensive will onlyfare worse in the market. People rely on the government to look out for theirsafety and security in areas where they lack the knowledge to make evalua-tions—food packaging, aviation, medicine. But for cryptography, the U.S.government is doing just the opposite.

When an airplane crashes, there are inquiries, analyses, and reports. Informa-tion is widely disseminated, and everyone learns from the failure. You can reada complete record of airline accidents from the beginning of commercial avia-tion. When a bank’s electronic commerce system is breached and defrauded,it’s usually covered up. If it does make the newspapers, details are omitted. Noone analyzes the attack; no one learns from the mistake. The bank tries topatch things in secret, hoping that the public won’t lose confidence in a systemthat deserves no confidence. In the long run, secrecy paves the way for moreserious breaches.

Laws are no substitute for engineering. The U.S. cellular phone industry haslobbied for protective laws, instead of spending the money to fix what shouldhave been designed corectly the first time. It’s no longer good enough to installsecurity patches in response to attacks. Computer systems move too quickly; asecurity flaw can be described on the Internet and exploited by thousands.Today’s systems must anticipate future attacks. Any comprehensive system—whether for authenticated communications, secure data storage, or electroniccommerce—is likely to remain in use for five years or more. It must be able towithstand the future: smarter attackers, more computational power, andgreater incentives to subvert a widespread system. There won’t be time toupgrade it in the field.

History has taught us: never underestimate the amount of money, time, andeffort someone will expend to thwart a security system. It’s always better toassume the worst. Assume your adversaries are better than they are. Assumescience and technology will soon be able to do things they cannot yet. Giveyourself a margin for error. Give yourself more security than you need today.When the unexpected happens, you’ll be glad you did.

❈ ❈ ❈ ❈ ❈

Counterpane Systems page 5

THE STATE OFSECURITY

Seite 30 Verzeichnisse

Verzeichnisse

I. AbbildungenAbb. 1.1: Mit Substitutionschiffre verschlüsseltes Chiffrat . . . . . . . . . . . . . . . . . . . . . . . . . . 7

II. Tabellen

Einleitung zu den StudienbriefenI. Abkürzungen der Randsymbole und FarbkodierungenII. Zu den AutorenIII. Modullehrziele

Studienbrief 1 Einführung und Stromchiffren1.1 Lernziele1.2 Übungen

Studienbrief 2 DES2.1 Lernziele2.2 Übungen

Studienbrief 3 AES3.1 Lernziele3.2 Übungen

Studienbrief 4 More about block ciphers4.1 Lernziele4.2 Übungen

Studienbrief 5 Message Authentication Codes5.1 Lernziele5.2 Übungen

VerzeichnisseI. AbbildungenII. Tabellen