Grundlagen der IT-Sicherheit PDF

Grundlagen der IT-Sicherheit Kapitel 2 – Kryptographie Lehrstuhl: Data Privacy and Security, Center for Scalable Data Analytics and Artificial Intelligence Kontakt: [email protected] Gliederung der Vorlesung ▪ Grundlagen der IT-Sicherheit − Zugriffskont...

Grundlagen der IT-Sicherheit Kapitel 2 – Kryptographie Lehrstuhl: Data Privacy and Security, Center for Scalable Data Analytics and Artificial Intelligence Kontakt: [email protected] Gliederung der Vorlesung ▪ Grundlagen der IT-Sicherheit − Zugriffskontrolle, Verschlüsselung ▪ Anwendungsschicht − Krypto-Protokolle, Tracking, Browser-Sicherheit, sichere Programmierung ▪ Übertragungsschicht − Firewalls, Angriffe auf die Infrastruktur, Netzwerkarchitekturen ▪ Management-Ebene − Basis-Absicherung und Security Engineering − Mobile Security Prof. Buchmann - Kryptographie 2 Inhalte und Lernziele dieses Kapitels ▪ Inhalt – Einführung in die Kryptographie – Symmetrische Verschlüsselung – Asymmetrische Verschlüsselung – Post-Quantum-Cryptographie und andere Herausforderungen ▪ Lernziele – Sie können die verschiedenen Verschlüsselungsverfahren anwenden, und kennen ihre Stärken und Schwächen. − Sie können die Ziele der Kryptographie erklären, sowie passende Sicherheitskriterien und Verschlüsselungsverfahren erläutern. Prof. Buchmann - Kryptographie 3 Einführung in die Kryptographie Wer etwas zu verbergen hat......versucht es zu verstecken. ▪ Unsichtbare Tinte (Zitronensaft trocken unsichtbar, bei Erhitzen braun) ▪ Codebücher ▪ Steganographie (rechts: Morsecode in Grashalm-Länge codiert) ▪ Geheimschrift (unten: nach Arthur C. Doyle) Prof. Buchmann - Kryptographie 5 Kryptographie und IT-Sicherheit ▪ Vertraulichkeit − Nur Berechtigte sollen Nachricht lesen, − Absender/Empfänger in Erfahrung bringen, − Existenz einer Nachricht erfahren ▪ Integrität − Daten nachweislich unverfälscht vom Sender zum Empfänger ▪ Authentizität − Urheber einer Nachricht eindeutig nachprüfbar ▪ Verbindlichkeit − Absender einer Nachricht soll Urheberschaft nicht abstreiten können ▪ Verfahren müssen nicht unbedingt jedes Ziel erfüllen Prof. Buchmann - Kryptographie 6 Kryptographie und Datenschutz ▪ Allgemein − Vertraulichkeit, Integrität, Verfügbarkeit bzgl. Zweckbindung ▪ Neue Ziele − Plausible Deniability (Glaubhafte Abstreitbarkeit) ▪ Gegenkonzept zur Verbindlichkeit ▪ Urheberschaft einer Nachricht plausibel leugnen können − Separation of Duties (Funktionstrennung bei Nichtverknüpfbarkeit) ▪ Abstrakter als Anonymisierung; hier geht es um Daten allgemein ▪ Neuartige Anwendungen − Homomorphe Verschlüsselung: Berechnung von Operationen auf verschlüsselten Daten − Secure Multiparty Computation: Verteilte Berechnung, ohne Datenquelle, Rohdaten oder Zwischenergebnisse öffentlich zu machen Prof. Buchmann - Kryptographie 7 Anfänge der Verschlüsselung ▪ Motivation: ein Angreifer soll eine Nachricht nicht lesen können, obwohl er die Methode der Übertragung kennt ▪ Skytale − Mittelmeerraum (Griechische Kleinstaaten, Persien) − Um 500 v. Chr. ▪ Caesar-Chiffre − Nach Julius Caesar, um 100 v. Chr. − Verschiebechiffre X → X + 3 mod 26 (wer kennt noch ROT-13?) Bilder: Wikimedia Prof. Buchmann - Kryptographie 8 Klassische Vorgehensweise ▪ Security through obscurity − Mache das Verfahren möglichst kompliziert und halte es geheim ▪ break-it fix-it break-it fix-it... − Alice entwickelt Verschlüsselung − Carol versucht Verfahren zu knacken − Nach einiger Zeit kein Angriff: → Verfahren gilt als „sicher“ Bei erfolgreichem Angriff: → Alice entwickelt nächstes Verfahren ▪ Beispiel von so entstandenen Verfahren − Enigma, 2. WK (drehbare Rotoren mit unregelmäßiger Verzahnung) Prof. Buchmann - Kryptographie 9 Stand der Technik ▪ Kerckhoff's Maxime (1883): "The security of a cryptosystem must not depend on the secrecy of the algorithm. The security is based only on the secrecy of the key. " ▪ Etabliertes Prinzip in der modernen Kryptographie, denn − Sicherheit von Geheimhaltung des Algorithmus abhängig: Algorithmus wird öffentlich → alle Nutzer des Algorithmus betroffen − Sicherheit von Geheimhaltung des Schlüssels abhängig: Schlüssel wird öffentlich → nur Nutzer des Schlüssels betroffen ▪ Ein veröffentlichter Algorithmus kann von Experten geprüft werden Prof. Buchmann - Kryptographie 10 Stand der Technik (cont'd.) ▪ Sicherheit bestimmbar durch – Ressourcen des Angreifers ▪ Polynomial beschränkter Angreifer – Ziele des Angreifers ▪ den Schlüssel K herausfinden ▪ min. ein Klartext-Bit p є P vom cipher C → encK(P) herausfinden ▪ Metainformationen von C herausfinden, z.B. die Länge von K, die Länge des Texts P, die Sprache des Texts P, den Absender etc. – Angreifermodell (nächste Folie) Prof. Buchmann - Kryptographie 11 Angreifermodelle ▪ Angreifermodelle unterscheiden nach Wissen des Angreifers ▪ Ciphertext-Only − Angreifer hat nur Ciphertext zur Verfügung ▪ Known-Plaintext − Angreifer kennt Ciphertext-Klartext-Paare ▪ Chosen-Plaintext − Angreifer kann aus Klartext selbst Ciphertext erzeugen (typisch für Public-Key-Verfahren, öffentlicher Schüssel bekannt) ▪ Chosen-Ciphertext − Angreifer kann aus gewählten Ciphertexten Klartext erzeugen Prof. Buchmann - Kryptographie 12  7 Beispiel: Brechen des 6 Caesar-Chiffres 5 4 ▪ Verschiebechiffre ROT13: 3 X → X + 13 mod 26 2 1 ▪ K: „This should be a very secret message!“ 0 a b c d e f g h i j k l mn o p q r s t u vwy z C: „Guvf fubhyq or n irel frperg zrffntr!“ Häufigkeitsverteilung der Buchstaben im Ciphertext ▪ Ciphertext-Only-Angriff: 0.14 − „e“ ist häufigster Buchstabe, 0.12 wurde „e“ zu „r“? 0.1 0.08 − Bei bekanntem Verfahren ist 0.06 Verschüsselung gebrochen, „r“→„e“=13 0.04 0.02 0 a b c d e f g h i j k l m n o p q r s t u v w x y z Häufigkeitsverteilung der Buchstaben in eng. Texten Prof. Buchmann - Kryptographie 13 One-time Pad ▪ One-time Pad ist das einzige Verfahren, das absolute Sicherheit garantiert, wenn der Schlüssel folgende Eigenschaften hat: − Echt zufälliger Schlüssel − Genauso lang wie Nachricht − Bits haben Gleichverteilung − Schlüssel bleibt geheim − Schlüssel wird nur 1x verwendet ▪ Encryption: Xi → Xi XOR Pi Key: 1010 1001 0000 1000 …. XOR Ciphertext: 1010 0000 1111 1001... Plaintext: 0000 1001 1111 0001 …. Prof. Buchmann - Kryptographie 14 One-time Pad & Quantenphysik ▪ Beitrag der Quantenkryptographie – Laser sendet polarisierte Photonen, die sich in Superposition befinden, zum Schlüsselaustausch zum Empfänger − Sicherer Kanal: Messung der Photonen führt dank Quanteneigenschaften zur Veränderung der Photonenverteilung ▪ Problem: teure Hardware und komplizierte physikalische Prozesse, komplizierte Handhabung Prof. Buchmann - Kryptographie 15 ESA baut gerade einen Satelliten für Quantum Key Distribution... ▪...die Chinesen sind damit schon fertig ;-) Prof. Buchmann - Kryptographie 16 Symmetrische Verschlüsselung Symmetrische Verschlüsselung ▪ Alice und Bob haben den gleichen Schlüssel − Der selbe Schlüssel zur Ver- und Entschlüsselung − Schlüssel ist geheim, über gesicherten Kanal übertragen S Sicherer Kanal S K encS(K) C decS(C) K Alice Bob ▪ Alice → Bob und Bob → Alice kann mit gleichem Schlüssel erfolgen Carol Prof. Buchmann - Kryptographie 18 Blockchiffrierung ▪ Ziel: Klartexte beliebiger Länge mit kurzem Schlüssel verschlüsseln ▪ Designprinzip: Substitutions-Permutations-Netzwerke − Aus Schlüssel Rundenschlüssel generieren − Mehrere Verschlüsselungsrunden ▪ Rundenschlüssel auf Eingabe addieren ▪ Ergebnis in Blöcke aufteilen ▪ Substitutionsbox (S1...S4): Einen Block durch einen anderen substituieren ▪ Permutationsbox (P): Entstehende Blöcke durchmischen − In der letzten Verschlüsselungsrunde nochmals Rundenschlüssel addieren − Entschlüsselung erfolgt genauso wie Verschlüsselung, nur rückwärts Bilder:Wikimedia Prof. Buchmann - Kryptographie 19  Advanced Encryption Standard (AES) K ▪ Symmetrische Verschlüsselung ▪ Schlüssel 128, 192 oder 256 Bit S AddRoundkey ▪ Anwendungen in IPSec, WLAN (9 Runden) (WPA2), SSH, HTTPS, etc. SubBytes ShiftRows ▪ AES ist ein Blockchiffre MixColumns S0...9 − Ein Block ist AddRoundKey ▪ Tabelle mit 4 Zeilen, 4 Spalten ▪ 1 Byte pro Zelle SubBytes ▪ 128 Bit insgesamt ShiftRows S10 − S-Boxen: SubBytes AddRoundKey − P-Boxen: ShiftRows, MixColumns Frage: Warum ist die letzte Operation AddRoundKey? C Prof. Buchmann - Kryptographie 20  Erzeugung der Rundenschlüssel in AES ▪ Schlüssel ebenfalls 4x4-Tabelle, Start Wort: eine Spalte der Tabelle ▪ 10 Runden- Ist Wort # schlüssel durch vier Nein Ja werden ge- Teilbar? braucht Das so bearbeitete Das oberste Byte des Wort wird nun mittels Worts wird nach unten XOR mit dem Wort XOR RotWord gebracht, die anderen vier weiter links Bytes rutschen nach ▪ Rekursive verknüpft oben. Berechnung Nein Alle Mit der Substitutionsbox (S-Box) werden die der Runden- Schlüssel SubBytes einzelnen Bytes erzeugt? ausgetauscht. schlüssel Ja Das so bearbeitete Wort wird nun mittels XOR mit dem Wort vier weiter links Ende XOR und mit der Rundenkonstante verknüpft Bilder:Wikimedia Prof. Buchmann - Kryptographie 21 Addition des Rundenschlüssels in AES a0,0 a0,1 a0,2 a0,3 b0,0 b0,1 b0,2 b0,3 ▪ Methode AddRoundKey AddRoundKey a1,0 a 1,1 a1,2 a1,3 b1,0 b1,1 b1,2 b1,3 ▪ Bitweise XOR-Verknüpfung a2,0 a2,1 a2,2 a2,3 b2,0 b2,1 b2,2 b2,3 von einem Block und a3,0 a3,1 a3,2 a3,3 b3,0 b3,1 b3,2 b3,3 dem Rundenschlüssel ▪ Rundenschlüssel k0,0 k0,1 k 0,2 k0,3 ebenfalls 4x4-Tabelle k 1,0 k 1,1 k1,2 k1,3 k2,0 k2,1 k2,2 k2,3 A B A XOR B ▪ Anmerkung: Schlüssel k3,0 k 3,1 k3,2 k3,3 0 0 0 wird nur hier angewendet, 0 1 1 alle anderen Operationen 1 0 1 sind von den Eingabedaten 1 1 0 abhängig Bilder:Wikimedia Prof. Buchmann - Kryptographie 22 S-Boxen in AES ▪ Methode SubBytes ▪ Jedes Byte der Tabelle wird durch ein anderes in der S-Box ersetzt → Monoalphabetische Kodierung 0 1 2 3 4 5 6 7 8 9 a b c d e f ▪ S-Box entsteht als Kehrwert 0 10 63 ca 7c 82 77 c9 7b 7d f2 fa 6b 59 6f 47 c5 f0 30 ad 1 d4 67 a2 2b af fe 9c d7 a4 ab 72 76 c0 einer Matrize, die auch in der 20 30 b7 4 fd c7 93 23 26 c3 36 18 3f 96 f7 5 cc 9a 34 7 a5 12 e5 80 f1 e2 71 eb d8 27 31 b2 15 75 P-Box genutzt wird 40 50 9 53 83 d1 2c 0 1a ed 1b 20 6e fc 5a b1 a0 5b 52 6a 3b cb d6 be b3 39 29 4a e3 4c 2f 58 84 cf 60 d0 ef aa fb 43 4d 33 85 45 f9 2 7f 50 3c 9f a8 − Galois-Körper GF, 70 51 a3 40 8f 92 9d 38 f5 bc b6 da 21 10 ff f3 d2 80 cd 0c 13 ec 5f 97 44 17 c4 a7 7e 3d 64 5d 19 73 → fragen Sie einen 90 60 81 4f dc 22 2a 90 88 46 ee b8 14 de 5e 0b db Mathematiker ;-) a0 b0 e0 e7 32 c8 3a 37 0a 6d 49 8d 6 d5 24 4e 5c a9 c2 6c d3 56 ac f4 62 ea 91 65 95 7a e4 ae 79 8 c0 ba 78 25 2e 1c a6 b4 c6 e8 dd 74 1f 4b bd 8b 8a d0 70 3e b5 66 48 3 f6 0e 61 35 57 b9 86 c1 1d 9e − Tabelle in Hex-Code e0 f0 e1 8c f8 a1 98 89 11 0d 69 bf d9 e6 8e 42 94 68 9b 41 1e 99 87 2d e9 0f ce b0 55 54 28 bb df 16 − Bsp.: aus 12 wird c9 Prof. Buchmann - Kryptographie 23 P-Boxen in AES No a0,0 a0,1 a0,2 a0,3 a0,0 a0,1 a0,2 a0,3 ▪ Methode ShiftRows change ShiftRows Shift 1 a1,0 a1,1 a1,2 a1,3 a1,1 a1,2 a1,3 a1,0 − Jede Zelle um Nummer seiner Shift 2 a2,0 a2,1 a2,2 a2,3 a2,2 a2,3 a2,0 a2,1 Zeile nach Links schieben Shift 3 a3,0 a3,1 a3,2 a3,3 a3,3 a3,0 a 3,1 a3,2 − Links herausfallende Zellen rechts einfügen ▪ Methode MixColumns a0,1 b0,1 a0,0 a0,2 a0,3 b0,0 b0,2 b0,3 − Matritzenmultiplikation a1,0 a 1,1 a1,2 a1,3 MixColumns b1,0 b1,1 b1,2 b1,3 a2,0 a2,1 a2,2 a2,3 b2,0 b2,1 b2,2 b2,3 a3,0 a3,2 a3,3 b3,0 b3,2 b3,3 a3,1 b3,1 Bsp.: b01=2*a01+3*a11+1*a21+1*a31 − alle 4 Eingabebytes beeinflussen jedes Ausgabebyte Bilder:Wikimedia Prof. Buchmann - Kryptographie 24 Wie sicher ist das, was Sie bisher gesehen haben? ▪ Bis hierher: Electronic Codebook Mode − Jeder Block einzeln für sich verschlüsselt ▪ Was passiert, wenn − ein Bit in einem Cipher-Block verändert wird? − ein Cipher-Block aus dem verschlüsselten Dokument gelöscht wird? − identische Klartextabschnitte existieren? − nur einen bestimmten Block entschlüsseln möchten? Dokument A Dokument B ***** *** ******** ****** ***** *** **** *** *** ***** ******* ** ********* *** ***** ******* *** **** ***** ****** *********** ************ *** ****** ******* * ********** *** *** ********* ** **** *** *** ***** ******* ** ******** ** ******** ******** ** ******** ***** *** ******** ****** ***** **** ***** ****** *********** ********* *** ***** ******* *** ********** *** *** ********* ******* ***** *** ************* ******** ** ******** *** ****** ******* ****** ****** Prof. Buchmann - Kryptographie 25 Cipher Block Chaining Mode (CBC) ▪ Erster Block XOR Initialisierungsvektor mit Zufallszahlen − Initialisierungsvektor zufällig/einzigartig, aber nicht geheim ▪ Ergebnis wird verschlüsselt und ergibt Cipher-Block ▪ Jeder Cipher-Block per XOR mit dem nächsten Klartext-Block verkettet − identische Klartextblöcke → unterschiedliche Cipher-Texte − Bitfehler zerstört diesen Block und das selbe Bit im nächsten Block − sequenzielle Verarbeitung der Blöcke (Image: Wikimedia) Prof. Buchmann - Kryptographie 26 Cipher Feedback Mode (CFB) ▪ Initialisierungsvektor wird verschlüsselt − Initialisierungsvektor zufällig/einzigartig, aber nicht geheim ▪ Jeder Klartext-Block per XOR mit dem Cipher-Block verkettet − sequenzielle Verarbeitung der Blöcke ▪ Ergebnis wird verschlüsselt − Bitfehler zerstört das Bit dieses Blocks und den ganzen nächsten Block − Jeder Block ist der Initialisierungsvektor des Folgeblocks (Image: Wikimedia) Prof. Buchmann - Kryptographie 27 Output Feedback Mode (OFB) ▪ Initialisierungsvektor wird verschlüsselt − Initialisierungsvektor zufällig/einzigartig, aber nicht geheim ▪ Verschlüsselter Initialisierungsvektor wird an andere Blöcke weitergereicht − Schlüsselstrom kann vorausberechnet werden, dann paralellisierbar ▪ Jeder Klartext-Block per XOR mit dem Ciphertext-Block verkettet − Bitfehler zerstört nur das betreffende Bit im Klartext-Block − Bitfolge für XOR kann ohne Klartext vorausberechnet werden (Image: Wikimedia) Prof. Buchmann - Kryptographie 28 Counter Mode (CTR) ▪ Vereinfachung des Output Feedback Mode ▪ Counter wird auf Initialisierungsvektor aufaddiert, anstelle verschlüsselten Initialisierungsvektor an den nächsten Block weiterzureichen − Initialisierungsvektor zufällig/einzigartig, aber nicht geheim − Counter mit zufälligem Startwert, ebenfalls nicht geheim − Bitfehler zerstört nur das betreffende Bit im Klartext-Block − Vollständig parallelisierbar, auch Schlüsselstrom (Image: Wikimedia) Prof. Buchmann - Kryptographie 29 Diskussion AES ▪ AES ist performant − Nur „billige“ Operationen − 128 Bit Blockgröße passt sehr gut in CPU- oder GPU-Register − Hardware-Implementierung möglich, z.B. auf FPGA ▪ AES ist sicher − Bester Angriff (2011) nur um Faktor 4 schneller als Brute Force → kein ernsthafter Angriff, vollst. Suche 2128 – 2256 Möglichkeiten, nun Suchraum reduziert auf 2126 - 2254 Möglichkeiten − Erfolgreichere Angriffe bisher auf Implementierung, nicht auf AES selbst ▪ Nachteile − Sicherer Kanal für die Schlüsselübertragung − Viele Kommunikationspartner = viele Schlüssel (s. nächste Folie) − Verarbeitet nur ganze Datenblöcke (s. übernächste Folie) Prof. Buchmann - Kryptographie 30 Anzahl der Schlüsselpaare bei N Teilnehmern ▪ N Nutzer wollen miteinander privat kommunizieren – Jeder der N Nutzer benötigt N-1 Schlüssel um mit den anderen zu kommunizieren – Gesamtanzahl Schlüssel im System: N ( N ( N −1)) ( )= 2 2 Beispiel für 5 Nutzer: B C 10 Schlüssel Beispiel für 500 Nutzer: D A 124.750 Schlüssel E Prof. Buchmann - Kryptographie 31 Stromverschlüsselung Stromverschlüsselung vs. Blockverschlüsselung ▪ Blockverschlüsselung – Eingabedaten werden Block für Block verschlüsselt – Für die Verschlüsselung von im Ganzen vorliegenden Daten z.B. Dateien, Bilder, aber auch größere Datenströme – Ansätze: DES, AES, RC2, Blowfish, Twofish ▪ Stromverschlüsselung – Eingabedaten werden sequenziell Bit für Bit verschlüsselt – Für die Verschlüsselung von Echtzeitdaten z.B. Voice over IP, Video, Audio – Üblicherweise weniger sicher als Blockverschlüsselung – Ansätze: RC4, E0 (Bluetooth-Standard), WEP, WPA2, WPA3 Prof. Buchmann - Kryptographie 33 RC4 ▪ 1987 von Ron Rivest (das R in RSA) entwickelt ▪ In HTTPS, SSH, WEP/WPA (wegen Sicherheitslücken werden heute Nachfolger mit etwas anderer S-Box verwendet,) ▪ Funktionsweise: − Eine rekursive S-Box ähnlich derjenigen in AES erzeugt einen endlosen Bitstrom Xi=0...∞ aus dem Schlüssel K − Verschlüsselung: Xi → Xi XOR Pi Key: 1101 0010 S-Box 1010 1001 0000 1000 …. XOR Cipher: 1010 0000 1111 1001... Plaintext: 0000 1001 1111 0001 …. Prof. Buchmann - Kryptographie 34 Diskussion RC4 ▪ Keine Garantie der Integrität (wie bei jedem Stromcipher) – Wenn ein Bit im Cipher-Strom verändert wird, verändert sich dasselbe Bit im Klartext (vgl. Output Feedback Mode, Counter Mode von AES) ▪ Eine Chosen-Plaintext-Attacke enthüllt den Schlüssel – Genau genommen, den Schlüsselstrom aus der S-Box – Nie, nie niemals nicht denselben Schlüssel mehrmals verwenden (in AES auch ein Problem, wenn Initialisierungsvektor oder Klartext einiger Blöcke erraten werden kann) Prof. Buchmann - Kryptographie 35 Asymmetrische Verschlüsselung Asymmetrische Verschlüsselung ▪ auch: Public-Key-Verschlüsselung ▪ Öffentlicher Schlüssel P zur Verschlüsselung, Übertragung ungesichert ▪ Privater Schlüssel Q zur Entschlüsselung, wird vom Empfänger geheimgehalten K encP(K) C decQ(C) K Alice Q Bob P ▪ Alice → Bob und Carol Bob → Alice erfordern unterschliedliche Schlüssel Prof. Buchmann - Kryptographie 37 RSA-Chiffre ▪ 1977 von Ron Rivest, Adi Shamir, Leonard Adleman am MIT entwickelt ▪ Erstes veröffentlichtes Public-Key-Verschlüsselungsverfahren ▪ Trapdoor-Funktion: Multiplikation von zwei Primzahlen ist „billiger“ als Primfaktorzerlegung ▪ Public Key − Für die Verschlüsselung, kann veröffentlicht werden − Schlüssel: {RSA-Modul, Verschlüsselungskomponente} (Produkt zweier Primzahlen, Hilfswert) ▪ Private Key − Für die Entschlüsselung, muss geheim bleiben − Schlüssel: {RSA-Modul, Entschlüsselungsexponent} (Produkt zweier Primzahlen, anderer Hilfswert) Prof. Buchmann - Kryptographie 38  Be isp iel Schlüsselerzeugung für RSA ▪ Wähle zwei große Primzahlen p,q ▪ Berechne den RSA-Modul N = p*q ▪ Berechne die Eulersche φ-Funktion des RSA-Moduls φ(p,q) = ( p-1 ) * ( q-1 ) ▪ Wähle zufällig eine zu φ(p,q) teilerfremde Zahl e mit 1 < e < φ(p,q) ▪ Bestimme einen Entschlüsselungsexponenten d, so dass gilt d * e ≡ 1 MOD φ(p,q) ▪ Die Parameter p,q und φ(p,q) können nun gelöscht werden ▪ Public Key: {N,e} ▪ Private Key: {N,d} Prof. Buchmann - Kryptographie 39  Be isp iel Verschlüsselung mit RSA Hilfsvariablen: N = p*q φ(p,q) = (p-1)*(q-1) ▪ Public Key: {N,e} e = zu φ(p,q) teilerfremde Zahl d * e ≡ 1 MOD φ(p,q) ▪ Private Key: {N,d} ▪ Verschüsselung: C = Ke MOD N ▪ Entschlüssselung: K = Cd MOD N ▪ Beispiel: Verschlüssele den Wert 7 festgelegt berechnet p = 11, q = 13 N = 11*13 = 143 ← Public/Private Key φ(p,q) = (11-1)*(13-1) = 120 Klartext 1< e < 120 e = 23 ← Public Key K=7 d * 23 ≡ 1 MOD 120 d = 47 ← Private Key enc(7) = (7^23) MOD (11*13) = 2 Prof. Buchmann - Kryptographie 40  Be isp iel Entschlüsselung mit RSA Hilfsvariablen: N = p*q φ(p,q) = (p-1)*(q-1) ▪ Public Key: {N,e} e = zu φ(p,q) teilerfremde Zahl d * e ≡ 1 MOD φ(p,q) ▪ Private Key: {N,d} ▪ Verschüsselung: C = Ke MOD N ▪ Entschlüssselung: K = Cd MOD N ▪ Beispiel: Entschlüssele den Ciphertext 2 Private Key Ciphertext N = 143 C=2 d = 47 dec(2) = (2^47) MOD (143) = 7 Prof. Buchmann - Kryptographie 41 Diskussion Public-Key-Verfahren ▪ Asymmetrische Verschlüsselung ist langsam − Viele Modulo-Divisionen − Sehr große Primzahlen mit wenigstens 1024 Bit → in der Praxis mit symmetrischer Verschlüsselung kombiniert ▪ Zwei verschiedene Schlüssel für Ver- und Entschlüsselung − Öffentlichen Schlüssel wie authentifizieren / zurückziehen? → komplexe Lösungen zum Schlüsselmanagement erforderlich − Es sind immer Chosen-Plaintext-Angriffe möglich → Angreifer kennt öffentlichen Schlüssel, kann beliebig chiffrieren ▪ Asymmetrische Verschlüsselung ist sicher − Aber: hängt davon ab, dass es keine Möglichkeit gibt, bestimmte Rechnungen effizient durchzuführen (RSA: Primzahlzerlegung) − Aber: hängt auch wieder von der Implementierung ab (Padding mit Zufallswerten muss Chosen Plaintext-Angriffe verhindern) Prof. Buchmann - Kryptographie 42 Probabilistische Verschlüsselung Zuordnungsangriffe ▪ Bisher vorgestellte Verschlüsselungsverfahren sind deterministisch − Bei jeder Verschlüsselung: Identischer Klartext → identischer Ciphertext − Public-Key-Verfahren erlauben Chosen-Plaintext-Angriffe, d.h., man kann ausprobieren, ob man den Klartext erraten kann ▪ Beispiel: Befindet sich „Alice“ in einer verschlüsselten DB? − Angreifer kennt Public Key: „Alice“ → „H71A00EF91“ Person Krankheit Alter AA73F9E001 Magersucht 24 H71A00EF91 Diabetes 31 3429A9F64E Schnupfen 26 Prof. Buchmann - Kryptographie 44 Frequenzangriffe ▪ Bisher vorgestellte Verschlüsselungsverfahren sind deterministisch − Bei jeder Verschlüsselung: Identischer Klartext → identischer Ciphertext − Aus der Verteilung von identischen Ciphertexten kann auf Inhalte geschlossen werden ▪ Beispiel: Was ist das Gehalt von Person Gehalt „Alice“ in verschlüsselter Datenbank? Alice A7 − Angreifer weiß, dass ca. die Hälfte der Kollegen durch Tarifbindung Bob EF 60.000 € verdienen Carol A7 Dave A7 Eve 21 Frank FF Prof. Buchmann - Kryptographie 45 Probabilistische Verschlüsselung ▪ Bei jeder Verschlüsselung desselben Klartexts anderer Ciphertext ▪ Strategie: Zufall einbauen − z.B.: tausche die deterministische Trapdoor-Funktion in RSA gegen eine probabilistsche Trapdoor-Funktion (Trapdoor-Funktion: lässt sich nur in einer Richtung effizient berechnen) ▪ Beispiel: Goldwasser-Micali-Kryptosystem − Public-Key-Verschlüsselung Prof. Buchmann - Kryptographie 46  Be isp iel Goldwasser-Micali-Kryptosystem ▪ Schlüsselerzeugung − Wähle zwei Primzahlen p, q so dass (p, q) ≡ 3 MOD 4 − Berechne n = p * q und x = n – 1 − Public Key: {x, n} Private Key: {p, q} ▪ Ein Bit m verschlüsseln − Wähle Zufallszahl z mit 1 < z < n − C = xm *z2 MOD n ▪ Ein Bit entschlüsseln − Wenn C(p-1)/2 ≡ 1 MOD p und C(q-1)/2 ≡ 1 MOD q, dann m = 1, sonst 0 Prof. Buchmann - Kryptographie 47 Sicherheitsbeweis: IND-CPA ▪ Indistinguishability under Chosen-Plaintext Attack (IND-CPA) − Nachweis, dass Angreifer nicht zwischen der Verschlüsselung zweier beliebiger Klartexte gleicher Länge unterscheiden kann − Sicherheit asymm. Verschlüsselung gegen Chosen-Plaintext Angriff ▪ Input: − Verschlüsselungsfunktion C = enc(K) ▪ Angriff: Für eine große Zahl von Runden − Challenger erzeugt Private/Public Key, sendet Public Key an Adversary − Adversary sendet 2 beliebige, gleich lange Klartexte K0, K1 an Challenger − Challenger wählt Zufallsbit M, sendet CM = enc(KM) an Adversary − Angriff ist erfolgreich, wenn Adversary mit Wahrscheinlichkeit > 50% + ε das Bit M bestimmen kann (ε ist „Sicherheitsmarge“ für polynomiale Beschränktheit des Angreifers. Ein ratender Angreifer erzielt eine Trefferwahrscheinlichkeit von 50%) Prof. Buchmann - Kryptographie 48 Secure Multiparty Computation Secure Multiparty Computation ▪ Verteiltes Protokoll privat − mehrere Parteien − jede Partei speichert geheime Daten Daten − es soll ein öffentliches Anfrageergebnis berechnet werden − Parteien vertrauen sich nicht, Verteiltes arbeiten nur im Protokoll zusammen, Protokoll ohne Rohdaten auszutauschen Daten Daten ▪ Schutzziele − Rohdaten bleiben geheim privat privat und/oder − Herkunft der Rohdaten bleibt geheim Ergebnis Prof. Buchmann - Kryptographie 50 Ziele der Secure Multiparty Computation ▪ Gegeben: − Parteien P0, P1,... Pn speichern Daten D0, D1, … Dn ▪ Correctness − Ergebnis der Berechnungen e = f(D0, D1, … Dn) ist prüfbar korrekt ▪ Privacy − Eingabedaten bleiben geheim, und/oder − Es bleibt geheim, von wem welche Daten kommen ▪ Output Delivery − Protokoll endet erst, wenn alle Parteien Ergebnis bekommen haben ▪ Fairness − Entweder alle Parteien bekommen das gültige Endergebnis oder keine (Anm.: Nicht jedes Ziel muss immer erfüllt/erfüllbar sein) Prof. Buchmann - Kryptographie 51 Anwendungsbeispiele ▪ Private Auktion − Öffentlich werden das Gewinner-Gebot und der Gewinner der Auktion, alle anderen Daten bleiben geheim ▪ Privates Machine Learning − Ein Data-Mining-Modell oder künstliches Neuronales Netz anlernen auf geheimen Trainingsdaten, nur das fertige Modell wird öffentlich ▪ Private Datenaggregation − Verteilte Berechnungen auf sensiblen Daten, z.B. zur Frühwarnung vor Infektionskrankheiten aus medizinischen Datensätzen, die nicht weitergegeben werden dürfen Prof. Buchmann - Kryptographie 52 Angreifermodell Secure Multiparty Computation ▪ Korrumpierte Knoten tauschen Informationen aus P0 − Zwischenergebnisse, Protokollschritte D0 ▪ Ressourcen des Angreifers − Threshold Adversaries Schwellwert t, Angreifer kann Set von Verteiltes {Pi,...Pj} ⊆ {P0, … Pn} Knoten mit P2 P1 Protokoll |{Pi,...Pj}| ≤ t übernehmen D2 D1 ▪ typische Beispiele − t