Expected Coverage of Perfect Chains in the Hellman Time Memory Trade-Off

Abstract

Critical overlap situations in the classical Hellman's cryptanalytic time memory trade-off method can be avoided, provided that during the precomputation phase, we generate perfect chains which are merge-free and loop-free chains. In this paper, we present asymptotic behavior of perfect chains in terms of time memory trade-off attacks. More precisely, we obtained expected values and variances for the coverage of perfect chains. We have also confirmed our theoretic outcomes with test results.