# Is there a security proof for the Triple-DES construction in the ideal cipher model?

Suppose one has an ideal block cipher

$E \: : \: \{0,\hspace{-0.04 in}1\hspace{-0.03 in}\}^k \times \{0,\hspace{-0.04 in}1\hspace{-0.03 in}\}^w \: \to \: \{0,\hspace{-0.04 in}1\hspace{-0.03 in}\}^w \;\;\;$ and $\;\;\; D \: : \: \{0,\hspace{-0.04 in}1\hspace{-0.03 in}\}^k \times \{0,\hspace{-0.04 in}1\hspace{-0.03 in}\}^w \: \to \: \{0,\hspace{-0.04 in}1\hspace{-0.03 in}\}^w$.

One can obviously follow the Triple-DES construction with that block cipher and keying option $n$, to get the block ciphers

$\operatorname{enc}_n \: : \: \{0,\hspace{-0.04 in}1\hspace{-0.03 in}\}^{(4-n)\cdot k} \times \{0,\hspace{-0.04 in}1\hspace{-0.03 in}\}^w \: \to \: \{0,\hspace{-0.04 in}1\hspace{-0.03 in}\}^w \;\;\;$ and $\;\;\; \operatorname{dec}_n \: : \: \{0,\hspace{-0.04 in}1\hspace{-0.03 in}\}^{(4-n)\cdot k} \times \{0,\hspace{-0.04 in}1\hspace{-0.03 in}\}^w \: \to \: \{0,\hspace{-0.04 in}1\hspace{-0.03 in}\}^w$.

One can easily show that is takes $\:$$\Theta$$\left(2^k\right)\:$ queries to $E$ and $D$ to break the security of $E\hspace{.02 in}$.

Regardless of which keying option is used, $\:\operatorname{enc}_n\:$ will be at least that secure.

For $\:n\in \{\hspace{-0.02 in}1,\hspace{-0.02 in}2\hspace{-0.02 in}\}$, is it known that $\:\operatorname{enc}_n\:$ will be a PRP family against adversaries that can make significantly more than $2^k$ queries to $E$ and $D\hspace{.03 in}$?

-

Yes. The following papers should be exactly what you are looking for.

The following paper shows that the answer is "Yes" and provides evidence that 3-key Triple DES is more secure than single DES:

They show that, in the ideal cipher model, the adversary must make more than about $2^{78}$ chosen-plaintext/ciphertext queries to have a reasonable chance at distinguishing 3-key Triple DES from a random permutation. This not too far off from the best known attack on 3-key Triple DES (which requires about $2^{90}$ queries), and shows that 3-key Triple DES is significantly more secure than single DES (again, in the ideal cipher model).

There is prior work by Aiello et al. that analyzes 2-key Triple DES in the ideal cipher; see the related work section of the Bellare et al. paper for a citation and discussion.

There is also subsequent work that re-proves the result on 3-key Triple DES in a simpler form, and analyzes 5DES and longer cascades as well:

-
The Aiello paper only obtains the same bound for 2-key 3DES as it obtains for "double DES". $\hspace{.98 in}$ – Ricky Demer Aug 19 '13 at 8:09
@RickyDemer, I thought you were curious about whether 2-key 3DES is more secure than single DES (rather than whether it's more secure than double DES), and I believe the Aiello paper does demonstrate one sense in which it is. Anyway, it's not important -- if the Aiello paper isn't what you were looking for, I'm fine with that! The other papers should still be useful. – D.W. Aug 19 '13 at 19:51