Will double encryption increase the security of cipher vs bruteforce?

Question

Assume I have a function encrypt(mes,key) where mes is the message, and key is the key. The length of key is 64 bits. Last but not least: assume the only way to crack my cipher is a brute-force attack.

If I use double_encrypt(mes,key1,key2) = encrypt(encrypt(mes,key1),key2)), does definition of double_encrypt() mean that only way to crack double_encrypt() is to brute-force a 128 bit key?

I was told that it does not, but I can not come up with any attack with better performance than a simple 128 bit brute-force.

Answer 1

First point: there is a practical security increase only if both encryption algorithms, taken alone, would be independently vulnerable to exhaustive search, i.e. by using too small a key. That is the main issue, and it is better to fix that. Exhaustive search works only up to the key sizes such that the space of key can be enumerated with existing or foreseeable technology. There are good reasons why a 128-bit key would resist such attempts. Thus, if you use a decent encryption algorithm, there is no need to "double" it. There is no security level beyond "cannot break it": you cannot not-break an algorithm more than "not at all".

Doubling or tripling algorithms has been used in older days to reuse previous algorithms which were definitely too weak on their own; the prime example is Triple-DES (aka "3DES"), built over the previous DES. DES and its 56-bit key space is vulnerable to exhaustive search (it has been done). As @CodesInChaos points out in his comment, doubling and tripling don't give you your money worth: double-DES would use 112-but keys, but would not offer 112-bit security.

In a nutshell, for double-DES, the attacker would encrypt the known plaintext with the first DES and all possible keys k₁ (2⁵⁶ possibilities), and also decrypt the known ciphertext with all possible keys k₂ (2⁵⁶ possibilities again), and then look for a match in the two sets of 2⁵⁶ "intermediate values". Matching will have cost about 2·56·2⁵⁶, i.e. about 2⁶³ (that's the cost of sorting the two sets, so that matches are detected with a linear search). With a merge sort, the sorting-and-matching steps only require linear access, thus compatible with hard disks. We are talking here about 2⁵⁷ 128-bit values (two known plaintext blocks, so that there won't be ambiguity about the keys), aka 2⁶¹ bytes, aka 2 millions of terabytes. One million hard disks is expensive... but technologically doable, contrary to a 2¹¹² exhaustive key search.

Therefore, doubling algorithms does not bring that much of a benefit. Tripling increases security when beginning with weak algorithms (at least when the weakness is only about key size), but, there again, not as much as the invested effort (with 3DES, you have 168 bits of key, but resistance is "only" up to 2¹¹²). Of course, tripling also means dividing performance by three, which may or may not be tolerable in any given context. Tripling, quadrupling... does not fix other issues, such as blocks which are too small (3DES still uses the 64-bit blocks of DES, which means that serious issues arise when encrypting about 2³² blocks worth of data with a given key, i.e. about 32 gigabytes, which is not much by today's standards).

It is much better to start with an encryption algorithm (like AES) which does not have exhaustive search issues to begin with, making doubling or tripling useless. Doubling (or tripling) algorithms is like a pegleg: it helps you keep upright if you had the misfortune of losing a leg; but, if possible, it is better to keep your two biological legs.