Meetinthemiddle attack
This article may be deleted soon.  

A meetinthe middle attack is a technique of cryptanalysis against a block cipher. It is a passive attack; it may allow the attacker to read messages without authorisation, but he or she would need more than just this attack to be able to alter or forge messages. The attacker must be able to calculate possible values of the same intermediate variable (the middle) in two independent ways, starting either from the input of the cipher (plaintext) or from the output (ciphertext). The attacker calculates some possible values each way and compares the results. It is a known plaintext attack; the attacker must get or guess one block of plaintext for which he has the matching ciphertext. Where it is applicable, this attack is devastating. The number of encryptions that must be tried is approximately the square root of the number required for a brute force attack. For example, against a 128bit key brute force takes 2^{127} steps, but meetinthemiddle needs only 2^{64} steps. However, the meetinthemiddle attack is rarely applicable; it only works if the two calculations of the middle variable are independent. In most ciphers, they are not; the first and second halves of a block cipher use closely related keys, two groups of round keys derived from the same basic key by the same key schedule. One case where the attack does apply is the construction where two block cipher encryptions are applied in succession with different keys in an attempt to gain greater security. It does not matter whether you use two different ciphers or apply the same cipher twice. The construction is vulnerable to a meetinthemiddle attack either way; having two independent keys makes the attack possible. The security gain from this construction is negligible in all cases; two ciphers combined this way are not significantly stronger than one used alone. This why triple DES rather than just double DES is used. Suppose you use DES twice expecting to obtain the security of a 112bit key by combining two 56bit DES keys. You do indeed obtain that if the attacker tries a brute force attack searching all possible combinations of keys. However, attackers cannot be expected to cooperate. Assuming the attacker can obtain or guess one block of plaintext for which he has the matching ciphertext, the meetinthemiddle attack is a much better strategy for him. He runs a number of decryptions of the known ciphertext with possible secondhalf keys, stores results in a table, then runs encryptions of the known plaintext using possible firsthalf keys and checking each output to see if it matches the table. On average, his total cost is 2^{57} encrypt/decrypt operations. Against triple DES, a similar attack is possible but not practical; the cost is 2^{112}. The attack does not depend at all on the properties of DES itself; the meetinthe middle strategy will work against any cipher doubled in this way, or even against two different ciphers used in succession with two independent keys. It fails if the keys are not independent, so any combining method that uses a single global key schedule is safe against this attack. For example, using two 16round instances of DES each with its own key and key schedule is vulnerable to this attack, but one might construct a 32round DES with a single larger key and a single overall key schedule that is not. Similarly, just applying, say, Twofish and AES in succession is vulnerable, but using both with a single global key schedule is not. Of course, to do these one would need to devise a suitable secure key schedule. The math for showing the cost of this attack is straightforward. Assume the attack is applicable; we want to break a cipher with two independent parts, C1 and C2 and we have one block of known plaintext and the matching ciphertext. We do N encryptions of the plaintext with C1 and store the results in a table, then do N decryptions of the ciphertext with C2 and check each of them to see if it matches a table entry. Total cost is 2N halfencryptions (C1 or C2), equivalent to N full encryptions (C1+C2). The number of key combinations tested, however, is N^{2} since each of the N test decryptions is compared to all the N table entries. The attacker gets to choose N, constrained by the available space for tables. With enough space, he just sets N equal to 2^{keysize} and breaks the cipher at a cost of 2*2^{keysize} halfencryptions, for example 2^{57} DES encryptions for double DES using 2^{53} bytes for a bitmap table. With less space, he can make tradeoffs between speed and space. The attack was first developed by Diffie and Hellman^{[1]}. It has been improved since then; see for example ^{[2]}. Variants have also been developed, for example unbalanced meetinthemiddle attacks.^{[3]}. References
