Take the 2-minute tour ×
Information Security Stack Exchange is a question and answer site for Information security professionals. It's 100% free, no registration required.

Lets say, I have a function

encrypt(mes,key)

where :

mes = message

key = key

Length of key is 64bits. Lets say, that only way to crack my cipher is 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 128bit key? I was told that it does not, but I can not come up with any attack with better performance then simple 128bit brute-force.

share|improve this question
    
Security gain is rather small. Meet-in-the middle. That's the reason 3DES is used instead of 2DES. –  CodesInChaos Mar 8 '13 at 8:07
    
    
Exactly what I was searching for, thanks! –  Tomáš Šíma Mar 8 '13 at 8:26
add comment

1 Answer

up vote 11 down vote accepted

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 k1 (256 possibilities), and also decrypt the known ciphertext with all possible keys k2 (256 possibilities again), and then look for a match in the two sets of 256 "intermediate values". Matching will have cost about 2·56·256, i.e. about 263 (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 257 128-bit values (two known plaintext blocks, so that there won't be ambiguity about the keys), aka 261 bytes, aka 2 millions of terabytes. One million hard disks is expensive... but technologically doable, contrary to a 2112 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 2112). 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 232 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.

share|improve this answer
    
Thank you for explaining how the "meet-in-the-middle" approach works! I quickly read the Wikipedia article, but didn't understand it until I read your excellent explanation. –  HeatfanJohn Mar 9 '13 at 16:41
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.