Sign In

Communications of the ACM

Research highlights

Technical Perspective: Attacking a Problem from the Middle


View as: Print Mobile App ACM Digital Library Full Text (PDF) In the Digital Edition Share: Send by email Share on reddit Share on StumbleUpon Share on Hacker News Share on Tweeter Share on Facebook

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.

The authors of this paper ask a natural question: Would one get even better security with quadruple-DES? At first sight one would conclude that breaking quadruple DES requires 22k encryptions and 22k memory. But the rather surprising answer is the cost can be reduced to that of triple-DES by applying recursion, that is, guessing first the value in the middle and subsequently performing two meet-in-the-middle attacks. This idea was proposed by Zhu and Gong for the block cipher KATAN and the authors were inspired by the work of Isobe on the block cipher GOST; however, the authors push these ideas much further in their Crypto 2012 paper by optimizing and generalizing this algorithm for the case of n-fold encryption for any value of n. Moreover, they show that the dissection technique has many applications.


The authors of the following paper ask a natural question: Would one get even better security with quadruple-DES?


This paper describes dissection for two examples. The first is the solution of Rubik's cube. The dissection solution has the same complexity as an earlier algorithm, but without using group-theoretic properties. The second example is the combinatorial partition problem; a variant of this problem (the knapsack problem) has played a very important role in cryptography for the construction of public-key encryption and hash functions. For this example a more complex strategy is used that divides the problem into uneven parts.

The dissection technique is remarkable, as it starts from a very simple idea, the meet-in-the-middle attack. The authors show this idea can be generalized in an elegant way and that many clever optimizations can push the idea to its limits. A key contribution of this work is the realization that dissection is broadly applicable to combinatorial optimization problems. Finally, the proposed algorithms reduce memory requirements, which is essential to make the algorithms practical.

Back to Top

Author

Bart Preneel (bart.preneel@esat.kuleuven.be) is a professor in the COSIC research group of the Electrical Engineering Department at the Katholieke Universiteit Leuven, Belgium.

Back to Top

Footnotes

To view the accompanying paper, visit doi.acm.org/10.1145/2661434


Copyright held by author.

The Digital Library is published by the Association for Computing Machinery. Copyright © 2014 ACM, Inc.


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