Ideal ciphers
A block cipher is a function E:\mathcal K \times \mathcal M \rightarrow \mathcal C. Here we shall let |\mathcal K| = n and |\mathcal M| = |\mathcal C| = poly(n), where n is called the security parameter. A block cipher E is called an ideal cipher if for any m\in \mathcal M, Adv(E(k,m),r) is negligible for r \in_r \{0,1\}^{poly(n)} and k \in_r \mathcal K. Another characterization of an ideal block cipher E is \{E(k,m)\} \approx_p \{f_k(m)\} for any m\in \mathcal M, where {f_k} are a random subset of the family of all invertible functions from \mathcal M to \mathcal C. The second characterization is especially helpful, because it allows us to approximate an ideal cipher by a random invertible functions.
Fact. Let E:\mathcal K\times\mathcal M\rightarrow \mathcal C be an ideal cipher. For all c,m, the probability that a cipher-text can only be decrypted by the encryption key is P\{k'\neq k, E(k',m)=c\} \le \sum_{k'\in\mathcal K,k'\neq k} P\{E(k',m)=c\} \le \frac{|\mathcal K|}{|\mathcal M|}. Assuming that DES is ideal, the probability that one can recover a unique key from N input-output pairs is larger than 1-N2^{56-64N}. When n=1, the probability is roughly 99.5% --- already high enough for an exhaustive search attack to be reasonable.
Fact. Let E:\mathcal K\times\mathcal M\rightarrow \mathcal C be an ideal cipher. For all c,m, the probability that a cipher-text can only be decrypted by the encryption key is P\{k'\neq k, E(k',m)=c\} \le \sum_{k'\in\mathcal K,k'\neq k} P\{E(k',m)=c\} \le \frac{|\mathcal K|}{|\mathcal M|}. Assuming that DES is ideal, the probability that one can recover a unique key from N input-output pairs is larger than 1-N2^{56-64N}. When n=1, the probability is roughly 99.5% --- already high enough for an exhaustive search attack to be reasonable.
Attacks on block ciphers
To attack a block cipher (E,D), we are given a few input-output pairs (m_i, c_i=E(k,m_i)), i=1,...,n to find the key k. The ciphers we are interested here are DES and some of its strengthened versions
DES: E(k,m) for k\in \{0,1\}^{56}, m\in \{0,1\}^{64}
2DES: E^2((k_1,k_2),m) = E(k_2,E(k_1,m))
3DES: E^3((k_1,k_2,k_3),m) = E(k_3,D(k_2,E(k_1,m)))
DX: E^x((k_1,k_2,k_3),m) = k_3\oplus E(k_2, k_1\oplus m)
DES Challenge: Broken by exhaustive search attack since 1997.
2DES Challenge: Given c,m, find k_1,k_2 such that E(k_2,E(k_1,m))=c.
3DES Challenge: Given c,m, find k_1,k_2,k_3 such that E(k_3,D(k_2,E(k_1,m)))=c.
DES: E(k,m) for k\in \{0,1\}^{56}, m\in \{0,1\}^{64}
2DES: E^2((k_1,k_2),m) = E(k_2,E(k_1,m))
3DES: E^3((k_1,k_2,k_3),m) = E(k_3,D(k_2,E(k_1,m)))
DX: E^x((k_1,k_2,k_3),m) = k_3\oplus E(k_2, k_1\oplus m)
DES Challenge: Broken by exhaustive search attack since 1997.
2DES Challenge: Given c,m, find k_1,k_2 such that E(k_2,E(k_1,m))=c.
- Build a sorted table T such that for each k_1, T[k_1]=E(k_1,m).
- For each k_1, check whether D(k_2,c) is in the table.
3DES Challenge: Given c,m, find k_1,k_2,k_3 such that E(k_3,D(k_2,E(k_1,m)))=c.
- Build a sorted table T such that for each k_1, T[k_1]=E(k_1,m).
- For each k_1,k_2, check whether E(k_2,D(k_3,c)) is in the table.
No comments:
Post a Comment