6

Given two 56-bit keys, $k_1$ and $k_2$, why does $E_{k_1}(E_{k_2}(M))$ only give 57 bits of security?

So basically I'm unsure why it only gives 57 bits of security; I understand that one key will provide 56 bits. Only thing I can think of is that when adding another 56 bit it will cycle through all the bits and realize they are the same so it just adds 1 extra bit, for the second keyblock instead of another 56 bits?

If I'm wrong, could someone please explain it simply and step-by-step?

fgrieu
  • 131,696
  • 12
  • 284
  • 553
user3411002
  • 171
  • 3
  • This basic question is **NOT** a duplicate of [these](http://crypto.stackexchange.com/q/16073/555) [questions](http://crypto.stackexchange.com/q/6345/555). In fact I do not find it either asked or answered anywhere on CSE. We have a closely related but more complex question, with good answers: [Attacking 2DES efficiently](http://crypto.stackexchange.com/q/11392/555). – fgrieu Apr 19 '15 at 09:27
  • 1
    I looked closer, and indeed we have a close match for that question, though asked in more precise and quantitative terms: [Meet-in-the-middle with checking complexity](http://crypto.stackexchange.com/q/10068/555), with a [good answer](http://crypto.stackexchange.com/a/10077/555). – fgrieu Apr 19 '15 at 09:57
  • I ask in [meta](http://meta.crypto.stackexchange.com/q/526/555) if we should have closed this question, or should reopen it so as not to loose its simple and useful [answer](http://crypto.stackexchange.com/a/25078/555). – fgrieu Apr 19 '15 at 14:41

1 Answers1

14

Decrypt the ciphertext with every possible key and store the result: $2^{56}$ decryptions. Now encrypt the (known) plaintext of the ciphertext with every possible key: $2^{56}$ encryptions. Now you have to check every entry, which is in both lists and try it with another plaintext-ciphertext pair. If you can successfully decrypt that, you are very likely to have found the correct key. All in all $2^{56} + 2^{56} = 2^{57}$ DES operations (encryptions and decryptions), much less than $2^{112}$. You need some work to search inside the list and check every possible key, but for DES this is not really much work.

All this is called Meet-in-the-middle attack.

Nova
  • 3,860
  • 1
  • 15
  • 23
  • 3
    Note that an actual attacker wouldn't create a table with $2^{56}$. They'd use distinguished points/cycle finding to reduce the memory use. – CodesInChaos Apr 18 '15 at 18:49
  • @CodesInChaos: I would be surprised that distinguished points/cycle finding can work with known plaintext (which seems to be the context of the question, since it is said that DES has 56-bit security, when it has only 55-bit security under chosen-plaintext attack due to DES's complementation property, with $\operatorname{DES}_{k_1}(\operatorname{DES}_{k_2}(M))$ only about 56-bit security, not 57-bit). $\;$ More generally, I'm not sure that I understand what you are thinking about. – fgrieu Apr 19 '15 at 09:16
  • 1
    @fgrieu I guess we could build the table with only one block of plaintext-ciphertext, and for each of the $2^{48}$ found matches check the second block. This would have work of $2^{57} + 2^{49}$, which I would still consider as 57-bit security. – Paŭlo Ebermann Apr 19 '15 at 09:44
  • 1
    @fgrieu: We can just fix the answer and everyone is / should be happy. It's not like the answer was fundamentally wrong. Please take a look now and mention other problems, if you find some. – Nova Apr 19 '15 at 11:39
  • @Nova: some user, like [Paŭlo Ebermann](http://crypto.stackexchange.com/users/58/pa%c5%adlo-ebermann), consider fine that others edit their post, and explicitly give license to that effect in their profile. In that case (only) I feel comfortable to edit (rather than constructively criticize) their answer when I see something wrong but fixable. – fgrieu Apr 19 '15 at 14:32
  • @fgrieu: i understand that both. Thank you for your contribution. – Nova Apr 19 '15 at 16:16
  • @CodesInChaos: As is, this attack is _not really much work_ only on an hypothetical computer with at least $2^{59}$ bytes of memory (like 500 times the total RAM on the 80,000 CPUs in the [current top supercomputer](http://en.wikipedia.org/wiki/Tianhe-2) of the [TOP500](http://en.wikipedia.org/wiki/TOP500)). Otherwise said, as is, it is purely theoretical. $\;$ That why I'd like to understand what you have in mind. – fgrieu Apr 26 '15 at 12:03
  • @fgrieu I originally planned to verify the technique experimentally with small keys before posting about it, but since I don't have the time for that at the moment, I've asked it as a question: [Can cycle findinding techniques reduce the memory usage of the MitM attack against 2DES and 3DES?](http://crypto.stackexchange.com/questions/25258/can-cycle-findinding-techniques-reduce-the-memory-usage-of-the-mitm-attack-again) – CodesInChaos Apr 26 '15 at 12:36
  • @CodesInChaos: After studying (and tentatively answering) your question: indeed, distinguished points/cycle finding can help reduce memory requirement, including with known plaintext, more than obvious partitioning of the work does, even if that's still at the expense of more DES operations. I now have some better understanding of how. $\;$ Somewhat the context of the question had me totally stuck to things with cost near $2^{57}$, hence my overlook of what you had in mind. Thanks ! – fgrieu Apr 26 '15 at 17:25