Sign In

Communications of the ACM

Research highlights

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 cacm5710_a.gif 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.


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

Log in to Read the Full Article

Sign In

Sign in using your ACM Web Account username and password to access premium content if you are an ACM member, Communications subscriber or Digital Library subscriber.

Need Access?

Please select one of the options below for access to premium content and features.

Create a Web Account

If you are already an ACM member, Communications subscriber, or Digital Library subscriber, please set up a web account to access premium content on this site.

Join the ACM

Become a member to take full advantage of ACM's outstanding computing information resources, networking opportunities, and other benefits.

Subscribe to Communications of the ACM Magazine

Get full access to 50+ years of CACM content and receive the print version of the magazine monthly.

Purchase the Article

Non-members can purchase this article or a copy of the magazine in which it appears.
Sign In for Full Access
» Forgot Password? » Create an ACM Web Account