1
$\begingroup$

Is there some algorithm that, given the Shannon entropy of a string, compute an estimation of the time that an average home computer will take to crack the password? Thank you.

$\endgroup$
  • 1
    $\begingroup$ What's the "string"? Is it the password, the plain or cipher text? $\endgroup$ – Paul Uszak Oct 15 '19 at 11:40
  • $\begingroup$ @PaulUszak the string is the password. $\endgroup$ – Yamar69 Oct 15 '19 at 11:56
1
$\begingroup$

Assuming knowing the entropy in the generation process is meaningful, the relationship between difficulty of brute force guessing an unknown random variable 𝑋 and entropy (or entropies) is quite a delicate one, and depends on the assumptions about the attack scenario.

In particular, the direct use of Shannon entropy can give misleading results, and the best case brute force number of guesses can be much lower than that implied by shannon entropy (say $H_0$ bits, should imply roughly $2^{H_0}$ guesses in the worst case.

One result on the expectation is that the expected number of guesses to determine a random variable 𝑋 (for the optimal guessing sequence) is upperbounded by

$$2^{𝐻_{1/2}(𝑋)−1}$$ and lowerbounded by $$\frac{2^{𝐻_{1/2}}(𝑋)−1}{\log |X|}$$ where $H_{1/2}(X)$ is the Renyi entropy. In general Renyi entropy can be much lower than Shannon entropy, hence Shannon gives a misleading result for this problem. See the answers to this question for details and references.

$\endgroup$
  • $\begingroup$ One little sticky thing in the bag of feathers is that the question revolves around time rather than guesses. And is further complicated as at home it's feasible to operate a key derivation function with 8GB/5s parameters. This somewhat decouples the password's entropy from the brute force time requirement. Plus there's that little issue of how can you even determine H(password)? That's an old chestnut. $\endgroup$ – Paul Uszak Oct 15 '19 at 23:23

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.