An analysis of chain characteristics in the cryptanalytic TMTO method

The classical Hellmanʼs cryptanalytic time–memory trade-off method and its later enhancements notoriously suffer from false alarm phenomena, which are the consequence of multiple occurrences of keys in Hellman chains. These detrimental situations can be avoided if the record of the keys already included into chains is kept during the generation of chains in the precomputation phase which guarantees perfect chains without key repetitions. The paper presents the theoretical and practical analysis that determines relevant characteristics of the perfect chains such as the probabilities that a chain will be of a certain length, the number of chains, their average lengths, as well as the coverage of the key space. In order to obtain these indicators, a detailed probabilistic analytical model is developed which treats the chain generation as a random process. The close matching of the model outputs to the numerical results obtained by the simulation experiments for different sizes of the key space proved the validity of the model. The numerical results are discussed in detail and the conclusions are finally drawn.