Stream Ciphers
Table of Contents
1. Ψευδοτυχαίες Γεννήτριες Αριθμών (Pseudorandom Νumber Generators – PRG)
\(G : \mathcal{S} \longrightarrow \mathcal{R}\) (π.χ. \(\mathcal{S} = \{0,1\}^{\ell}\) και \(\mathcal{R} = \{0,1\}^L\))
2. Attack Games
2.1. Οι δύο κόσμοι
Game 0
\(\it{Challenger}\) \(\hspace{8cm}\) \(\mathcal{A}\)
\(s\stackrel{R}{\longleftarrow} \mathcal{S}\)
\(r \longleftarrow G(s)\)
\(\hspace{7cm}\) \(\stackrel{r}{\longrightarrow}\)
\(\hspace{7cm}\) \(\stackrel{\hat{b}}{\longleftarrow}\)
Game 1
\(\it{Challenger}\) \(\hspace{8cm}\) \(\mathcal{A}\)
\(r\stackrel{R}{\longleftarrow} \mathcal{R}\)
\(\hspace{7cm}\) \(\stackrel{r}{\longrightarrow}\)
\(\hspace{7cm}\) \(\stackrel{\hat{b}}{\longleftarrow}\)
- Ορίζουμε \(W_b\) να είναι το ενδεχόμενο \(\hat{b} = 1\) στο παιχνίδι \(b\).
Το πλεονέκτημα του επιτηθέμενου, \(\mathcal{A}\) είναι
\(\mathrm{Adv_{PRG}}[\mathcal{A}, \mathcal{E}] = \left|\Pr[W_0] - \Pr[W_1] \right| \)
2.2. Bit guessing game
\(\it{Challenger}\) \(\hspace{8cm}\) \(\mathcal{A}\)
\(b \stackrel{R}{\longleftarrow} \{0,1\}\)
Αν \(b = 0\) :
\(\hspace{1cm}\) \(s \stackrel{R}{\longleftarrow}\mathcal{S}\)
\(\hspace{1cm}\) \(r \longleftarrow G(s)\)
Αν \(b = 1\) :
\(\hspace{1cm}\) \(r\stackrel{R}{\longleftarrow}\mathcal{R}\)
\(\hspace{7cm}\) \(\stackrel{r}{\longrightarrow}\)
\(\hspace{7cm}\) \(\stackrel{\hat{b}}{\longleftarrow}\)
\(\mathrm{Adv_{PRG}^{*}}[\mathcal{A}, \mathcal{E}] = \left|\Pr[\hat{b} = b] - 1/2 \right| \)
Ισχύει \(\mathrm{Adv_{PRG}}[\mathcal{A}, \mathcal{E}] = 2\cdot \mathrm{Adv_{PRG}^{*}}[\mathcal{A}, \mathcal{E}]\)
3. Stream Cipher
\(\mathcal{E} = (E, D)\) με \(\mathcal{K} = \{0,1\}^{\ell}\), \(\mathcal{M} = \mathcal{C} = \{0,1\}^L\)
\(G : \{0,1\}^{\ell} \longrightarrow \{0,1\}^L\)
\(E(k, m) = G(k) \oplus m\)
\(D(k, c) = G(k) \oplus c\)
4. Ασφάλεια
Θεώρημα: Αν η \(G\) είναι ασφαλής PRG τότε το σύστημα \(\mathcal{E}\) είναι σημασιολογικά ασφαλές κρυπτοσύστημα.
Απόδειξη (ιδέα): Αν η \(G\) είναι ασφαλής PRG τότε κανένας αποτελεσματικός αντίπαλος δε μπορεί να ξεχωρίσει το \(G(k)\) από μία πραγματικά τυχαία τιμή του \(\mathcal{R}\). Οπότε δεν μπορεί να ξεχωρήσει το \(\mathcal{E}\) από το one-time-pad, το οποίο είναι σημασιολογικά ασφαλές.
5. Παραδείγματα
- Ad hoc κατασκευές
- RC4 (Ron Rivest, 1987) \(40\leq \ell \leq 2048\)
- Salsa20 (Daniel Bernstein, 2005) \(\ell \in \{128, 256\}\)
- ChaCha20 (Daniel Bernstein, 2008) \(\ell \in \{128, 256\}\)
- Κατασκευές που στηρίζονται σε υπολογιστικά δύσκολα προβλήματα
- Blum-Michali, 1984 (Discrete logarithm problem) Seed = \(x_0\), \(x_{n+1} = g^{x_n} \mod{p}\)
- Blum-Blum-Shub, 1986 (Quadratic residuosity problem, Integer factorization) Seed = \(x_0\), \(x_{n+1} = x_n^2 \mod{N},\ \ \ N = p q\)
6. Αντι-παραδείγματα
- Linear Congruencial Generator (LCG) Seed = \(x_0\), \(x_{n+1} = a x_n + b \mod{N}\)
- Linear-feedback Shift Register (LFSR) Seed = \(x_0,\ldots,x_{\ell-1}\), \(x_{n+\ell} = a_0 x_{n+\ell-1} + \cdots + a_{\ell-1} x_{n}\) Οι υπολογισμοί γίνονται σε κάποιο πεπερασμένο σώμα, συνήθως το \(\mathbb{F}_2\).
7. Περαιτέρω κατασκευές
Παράλληλη σύνθεση
\(G : \mathcal{S} \longrightarrow \mathcal{R}\)
\(G' : \mathcal{S}^k \longrightarrow \mathcal{R}^k\)
με \(G'(s_1,\ldots,s_k) = (G(s_1),\ldots, G(s_k))\).
Σειριακή σύνθεση
\(G : \mathcal{S} \longrightarrow \mathcal{S} \times \mathcal{R}\)
\(G'' : \mathcal{S} \longrightarrow \mathcal{S} \times \mathcal{R}^k\)
με \(G''(s) = (s_k, r_1, \ldots, r_k)\) όπου
\(s_0 = s\) και \((s_i, r_i) = G(s_{i-1})\).