Communications of the ACM
Technical Perspective: Attacking a Problem from the Middle
The following paper presents an elegant new algorithm for solving a broad class of combinatorial optimization problems. The idea of the dissection technique came up by studying strengthened versions of the DES algorithm. DES is a cryptographic algorithm proposed by the National Bureau of Standards (now known as the National Institute for Standards and Technology, or NIST) in 1977 for the protection of sensitive but unclassified U.S. government data. For almost three decades, DES has been a worldwide de facto standard for encryption. IBM may have designed DES, but the U.S. National Security Agency (NSA) decided the key length should be restricted to 56 bits. This was a controversial move, as it would allow the NSA (and no one else) to break the cipher by searching the key space.
A straightforward way to increase the key length seems to encrypt twice, known as double-DES or C = DESK1 (DESK2(P)), where P and C are the plaintext and ciphertext and K1 and K2 are two different k-bit keys. In 1977, Diffie and Hellman demonstrated this method does not help. Let us assume a few ciphertexts and corresponding plaintexts are known (this is a standard assumption in cryptography, one that is very often met in practice). The meet-in-the-middle attack works as follows: one tries all 2k values of the first key K1, computes the values in the middle A = DESK1(P) and stores the pairs (K1, A(K1)) in a table. In a second step, one computes for all keys K2 the value in the middle as 
and searches for the value A in the table. If a match is found, the candidate pair (K1, K2) is checked with an additional plaintext and ciphertext. This algorithm requires about 2k encryptions and 2k memory. This is the reason why the financial sector has upgraded single DES to triple-DES, with three encryptions. A meet-in-the-middle attack on triple-DES requires about 22k encryptions and 2k memory.
Comments
Thomas Jones
I found a mitigation to MitM attacks that I submitted to a conference in 1986 that was refereed by Ravi Sandhu. He rejected the paper because of a misunderstanding that I was susceptible to MitM rather than addressing it directly. The solution is particularly simple. If there is a place where an MitM attack is possible, just insert (pseudo) randomness at that point. In my paper I create an new version of triple-DES called CCC - or cypher/chain/cypher. In this the input is cyphered with the first 56 bits of the key (w/ or w/o chaining - irrelevant), an OFB version of the second key is x-or'd with the intermediate result, which is then cyphered with the third 56 bit key. This type of mitigation should address an MitM weakness.
Displaying 1 comment