On the Incomparability of Entropy and Marginal Guesswork in Brute-Force Attacks
We discuss measures of statistical uncertainty relevant to determining random values in cryptology. It is shown that unbalanced and self-similar Huffman trees have extremal properties with respect to these measures. Their corresponding probability distributions exhibit an unbounded gap between (Shannon) entropy and the logarithm of the minimum search space size necessary to be guaranteed a certain chance of success (called marginal guesswork). Thus, there can be no general inequality between them. We discuss the implications of this result in terms of the security of weak secrets against brute-force searching attacks, and also in terms of Shannon's uncertainty axioms.
Record created on 2007-01-19, modified on 2016-08-08