I am trying to understand the basic TMTO by Diffie Hellman as described here. I am having trouble understanding this passage here:

Hellman had the idea of storing the dictionary in the form of long chains. A randomly chosen key, with which a specific message is encrypted, stands at the beginning of such a chain. The result of the first pass is used as a key for encrypting the original message during the next pass. The result of this pass provides the key for the next one, and so on, until the chain has reached a predefined length. In order to save space, Hellman stored only the first and last values in the chain. The dictionary thus compressed is a two-column table sorted by end value.

enter image description here

What does the author mean by first and by last value? If I use a key a (from a set A of keys) on a certain cipher, it should give me a result b (from a set B of possible results). Now what exactly are the middle values in this process?

Also, do I get it right: in order to save memory the sets A and B are conjuncted? So when a 64-bit key a1 produces a 64-bit b1, in the next step we have b1=a2 (so in the image above, it should be 77CF=22CB)? But how does that work in ciphers where key and output length are not the same length? Also why does the author speak of a table, if the data structure here would obviously is a list? it would especially be no lookup-table, as the keys/values would be in a random order, so you could not look up a certain key/value by its bit-order (00001 00010 00011 ...) and would have to go through the entire database to find the entry you are looking for.

  • $\begingroup$ TMTO is due only to Hellman, has nothing to do with your tag. I'd suggest cryptanalysis as a top level tag. $\endgroup$ – kodlu Mar 9 '16 at 21:47

This is a complex topic. Hence my suggestion:

There is a reasonable tutorial here. Forget the example table above and whatever you are reading and read the tutorial first. The example above is full of vague words and undefined terms. There is a lot going on in the TMTO and things have to be fully defined.

Even Hellman's paper while very technical is more enlightening than what you have given above, but the tutorial is more gentle.

In the case keylength is not equal to blocklength, a projection map is used from 64 bits (say) to 56 bits (say) by taking the first 56 bits of the output, since the only goal of the update function along the trails is to give you a pseudorandom walk among possible key values.

Table vs list, these are valid programming and data management distinctions and the author was sloppy. While they have impact on the exact complexity, they have small impact on the overall big-oh complexity of the attack.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.