Hellman Chains Analysis Base on Graph of Random Function

Despite several studies and attempts, in time-memory trade-off attacks on cryptographic algorithms, the coverage of Hellman tables and similar methods are practically much less than half and their probability of success is low. In fact, Hellman chains are paths with given starting and end vertices on a functional graph. In this paper, behavior of these chains is investigated with this approach. In the beginning of the paper, parameters of the functional graph for a random mapping are defined and based on these parameters, Hellman chains are analyzed. Our results show that the coverage of such tables can’t be high, for the following reasons: First, there exist some remarkable terminal vertices (37%) on the functional graph such that the possible occurrence of these vertices on chains (except in the starting vertices) is zero. Secondly, appropriate parameters for constructing chains exist in graph for about half of all hidden states of cipher function. Thirdly, for construction of noncyclic chains and collision of chains, we must pay attention to the obtained probabilities in this note.Practically, above reasons show that after some point the coverage of a Hellman table tends to zero quickly, and so construction of them will be ineffective. Our results are implemented on mAES algorithm where validate our theatrical results .