We now analyze the security of DES double encryption (2DES) by doing a cost-estimate:

2DES(x) = DESK₂ (DESK₁ (x))

1. First, let us assume a pure key search without any memory usage. For this purpose, the whole key space spanned by K1 and K2 has to be searched. How much does a key-search machine for breaking 2DES (worst case) in 1 week cost? In this case, assume ASICs which can perform 107 keys per second at a cost of $5 per IC. Furthermore, assume an overhead of 50% for building the key search machine.

2. Let us now consider the meet-in-the-middle (or time-memory tradeoff) attack, in which we can use memory. Answer the following questions:

a. How many entries have to be stored?

b. How many bytes (not bits!) have to be stored for each entry?

c. How costly is a key search in one week? Please note that the key space has to be searched before filling up the memory completely. Then we can begin to search the key space of the second key. Assume the same hardware for both key spaces.

For a rough cost estimate, assume the following costs for hard disk space: $8/10 GByte, where 1 GByte = 109 Byte.

3. Assuming Moores Law, when do the costs move below $1 million?