Dieser Artikel beschäftigt sich mit der Vorlesung „Sicherheit“ am KIT. Er dient als Prüfungsvorbereitung. Ich habe die Vorlesungen bei Herrn Jun.-Prof. Hofheinz im Sommersemester 2013 gehört.
Falls hier etwas fehlt, könnt ihr mich gerne in den Kommentaren oder per Mail ([email protected]) darauf aufmerksam machen. Ich bin ja mal gespannt, ob ich das bis zum Ende aktuell halte.
Definitionen und Sätze
Eine über $k$ parametrisierte Funktion $H$ ist kollisionsresistent, wenn jeder PPT-Algorithmus nur mit höchstens vernachlässigbarer Wahrscheinlichkeit eine Kollision findet.
Für jeden PPT-Algorithmus $\mathcal{A}$ ist
$Adv^{cr}_{H,\mathcal{A}}(k) := Pr[(X,X') \leftarrow \mathcal{A}(1^k): X \neq X' \land H_k(X) = H_k(X')]$
vernachlässigbar.
Eine über $k$ parametrisierte Funktion $H$ ist eine Einwegfunktion bzgl. der Urbildverteilung $\mathcal{X}_k$, wenn jeder PPT-Algorithmus nur mit höchstens vernachlässigbarer Wahrscheinlichkeit ein Urbild eines gegebenen, aus $\mathcal{X}_k$ gezogenen Bildes findet.
Für jeden PPT-Algorithmus $\mathcal{A}$ ist
$Adv^{cr}_{H,\mathcal{A}}(k) := Pr[X' \leftarrow \mathcal{A}(1^k, H(X)): H(X) = H(X')]$
vernachlässigbar, wobei $X \leftarrow \mathcal{X}_k$ gewählt wurde.
Jede kollisionsresistente Hashfunktion $H:\{0,1\}^* \rightarrow \{0,1\}^k$ ist eine Einwegfunktion bzgl. der Gleichverteilung auf $\{0,1\}^{2k}$.
Ist $f$ eine kollisionsresistente Hashfunktion, so ist die Merkle–Damgård-Konstruktion mit $f$ kollisionsresistent.
Hash-Then-Sign-Paradigma: Sei (Sig, Ver) EUF-CMA-sicher und H eine kollisionsresistente Hashfunktion.
Dann ist der durch Sig'(K, M) = Sig(K, H(M)), Ver'(K, M, $\sigma$) = Ver(K, H(M), $\sigma$) erklärte MAC EUF-CMA-sicher.
Fragen
Wann ist ein Verschlüsselungsschema IND-CPA-sicher?
IND-CPA bedeutet „indistinguishability under chosen-plaintext attacks“. Ein Verschlüsselungsschema ist genau dann IND-CPA-sicher, wenn kein effizienter Angreifer $\mathcal{A}$ Chiffrate von selbstgewählten Klartexten unterscheiden kann.
Wann ist eine Signatur EUF-CMA-sicher?
EUF-CMA bedeutet „existentially unforgeable under chosen-message attacks“. Eine Signatur ist genau dann EUF-CMA-sicher, wenn alle PPT-Angreifer $\mathcal{A}$ folgendes Spiel nur vernachlässigbar oft gewinnen:
$\mathcal{A}$ hat Zugriff auf ein $Sig(K, \cdot)$-Orakel
$\mathcal{A}$ gibt als Ausgabe $(M^*, \sigma^*)$
$\mathcal{A}$ gewinnt, wenn $Ver(K, M^*, \sigma^*) = 1$ und $M^*$ „frisch“ ist
Was sind Replay-Angriffe?
Bei Replay-Angriffen fängt der Angreifer einen Teil der Kommunikation von Alice und Bob ab. Später schickt er diesen Teil ohne weitere Bearbeitung an einen der beiden.
Was versteht man unter der Merkle–Damgård-Konstruktion?
Die Merkle–Damgård-Konstruktion ist eine Methode zur Konstruktion von kryptographischen Hash-Funktionen. Sie funktioniert so:
Merkle-Damgard-Konstruktion Quelle: Wikipedia
Wie funktioniert RSA?
Generiere zwei (große, verschiedene) Primzahlen $p, q \in \mathbb{P}$
Berechne $n := p \cdot q$ und $\varphi(n) = (p-1) \cdot (q-1)$
Wähle $e$, sodass gilt: $\text{ggT}(e, \varphi(n)) = 1$ und $1 < e < \varphi(n)$
Verschlüsselung einer Nachricht $m$: $c = m^{e} \mod n$
Entschlüsselung eines Chiffrats $c$: $m = c^{d} \mod n$
Welches Problem birgt ein kleines $e$ beim RSA-Verfahren?
Folgender Angriff ist für $e=3$ möglich:
Nachricht $m$ wird an 3 Benutzer geschickt
Angreifer kennt Chiffrate für $N_1, N_2, N_3$.
Chinesischer Restsatz für $m^3 \mod N_1 N_2 N_3$.
Wurzelziehen über $\mathbb{Z}$ liefert $m$
Was ist damit gemeint, wenn man sagt „RSA ist homomorph“?
Homomorphie ist folgende (unerwünschte) Eigenschaft:
\begin{align}
Enc(pk, m_1) \cdot Enc(pk, m_2) &= m_1^e \cdot m_2^e\\
&= (m_1 \cdot m_2)^e \\
&= Enc(pk, m_1 \cdot m_2)
\end{align}
Diese Eigenschaft ist z.B. in folgendem Szenario problematisch:
Angenommen, bei einer Auktion werden die gebotenen Geldbeträge verschlüsselt. Dann kann ein Angreifer das Chiffrat (gültig) verändern. So kann er den Geldbetrag ohne Probleme verdoppeln.
Was sind HMACs?
Spezielle symmetrische Signaturen, die wie folgt aufgebaut sind:
$Sig(K, M) = H(K \oplus opad, H(K \oplus ipad, M))$
Wähle eine zyklische Gruppe $\mathbb{G} = \langle g \rangle$.
$pk = (\mathbb{G}, g, g^x)$, $sk=(\mathbb{G}, g, x)$, wobei $x$ zufällig gewählt wird.
Verschlüsselung einer Nachricht $m$: $Enc(pk, m) = (g^y, g^{xy} \cdot m)$ mit zufälligem $y$ → Verschlüsselung ist zufällig!
Entschlüsselung eines Chiffrats $(Y, Z)$: $Dec(sk, (Y, Z)) = \frac{Z}{Y^x} = \frac{g^{xy} \cdot m}{(g^{y})^x} = m$
Wie funktioniert das Kerberos-Schlüsselaustauschprotokoll?
Alice schreibt dem KC, dass Alice und Bob gerne einen Schlüsselaustausch vornehmen wollen.
Das KC wählt einen frischen Schlüssel $K$, einen Zeitstempel $T_{KC}$ und eine Gültigkeitsdauer $L$. Es schickt Alice $Enc(K_A, (T_{KC}, L, K, B))$ und das Ticket $Enc(K_B, (T_{KC}, L, K, A))$. Dabei ist $K_A$ bzw. $K_B$ der langfristige Schlüssel, den Alice bzw. Bob mit dem KC teilt.
Alice entschlüsselt den ersten Teil und erhält so $K$. Sie schickt Bob das Ticket sowie $Enc(K, (A, T_A))$ mit einem eigenen Zeitstempel $T_A$.
Bob entschlüsselt das Ticket, erhält so $K$ und prüft Zeitstempel und Gültigkeitsdauer. Zur Bestätigung schickt er $Enc(K, T_A + 1)$ an Alice.
Warum kann es schlecht für die Sicherheit sein, wenn man komprimiert?
Annahme: Ein Angreifer kann zu dem Geheimtext, der komprimiert wird, etwas vor der Kompression hinzufügen. Wenn der Ciphertext deutlich weniger wächst als er an Text hinzugefügt hat, kann er vermuten, dass er den Text erraten hat. (→ CRIME-Angriff)
Was ist damit gemeint, dass die One-Time-Pad-Chiffre verwundbar ist?
Ein Angreifer kann die Klartextnachricht ändern. Wenn er weiß (oder zumindest ahnt), was der Klartext ist, kann er dafür sorgen, dass ein Klartext gleicher Länge seiner Wahl bei der Entschlüsselung herauskommt.
Nennen Sie Verfahren, die IND-CPA-sicher sind.
Eine Blockchiffre im CBC-Modus (mit zufälligem IV)
Nennen Sie Verfahren, die EUF-CMA-sicher sind.
Sei PRF: $\{0,1\}^k \times \{0,1\}^k \rightarrow \{0,1\}^k$ eine PRF und $H:\{0,1\}^* \rightarrow \{0,1\}^k$ eine kollisionsresistente Hashfunktion. Dann ist der durch $Sig(K, M) = PRF(K, H(M))$ gegebene MAC EUF-CMA-sicher.
Es gibt Übungsblätter auf der Vorlesungswebsite, aber keinen Übungsschein, keine Abgaben und keine Bonuspunkte.
Termine und Klausurablauf
Datum: Freitag, den 26. Juli 2013 von 14:00 bis 15:00 Uhr (Klausur dauerte eine Stunde) Ort: seit 24.07.2013 auf der Vorlesungswebsite (ich bin im HSaF) Punkte: 60 Bestehensgrenze: 20 Übungsschein: Nein Bonuspunkte: Nein
