3 ms·
> which effect the "pick one of ten" method exactly has on the entropy Probably impossible to say exactly without knowing what your brain is doing when it pick
by gjm11 11y ago
> which effect the "pick one of ten" method exactly has on the entropy
Probably impossible to say exactly without knowing what your brain is doing when it picks one. But let's be pessimistic and suppose it picks the "nicest" in some global sense and that "nicest" is the same for everyone (or, at least, that an attacker knows what you consider "nicest".
Then the question is this. Generate m samples uniformly from {1,...,N} (with replacement? without? That depends on exactly what you do if you happen to get two passphrases the same, but the probability of this is small enough that it likely doesn't matter) and take the smallest; what's the entropy of the resulting probability distribution?
That seems like a difficult combinatorial question, so let's consider a continuous approximation. If we pick numbers uniformly on [0,1] and take the min of m of them, the CDF is 1-(1-t)^m because the probability the min is >= t equals the probability all m numbers are >= t, so the pdf is m(1-t)^(m-1). We can compute the continuous entropy of this distribution (if both Wolfram Alpha and I have done our parts right, the answer is - log m + 1 - 1/m) and of the uniform distribution (zero). Continuous entropies are kinda meaningless but in the limit their differences equal those of the corresponding discrete distributions -- and for large N we are close to that limit.
So I think what this means is that by picking the "nicest" of m choices, you lose log(m) - 1 + 1/m nats of entropy. (Divide by log 2 for the number of bits.)
Crappy simple approximation to those: you lose log(m) nats of entropy (log2(m) bits), which is just the same as if you divided the number of possible passphrases by m. In reality the amount you lose is a little less.
So, e.g., if m=10 you lose about 1.4 nats or 2 bits. (The crappy approximation says 2.3 bits.)
- chronial 11y agoThanks a lot for this clear analysis. I had gotten till the “difficult combinatorial question” and was stuck. Didn't think of just going into continuous space. The “crappy approximation” is actually what I used up until now and it's good to see that I wasn't wrong in assuming it would overestimate the loss. You made one small mistake at the end: The approximation says you loose 2.3 nats = 3.32 bits, so they actually differ by over a bit. Btw: What did you ask wolfram alpha to get the -log m + 1 - 1/m? It was out of computation time when I asked :) http://www.wolframalpha.com/input/?i=-+int_0^1+%28m*%281-x%29^%28m-1%29%29+*+log%28%28m*%281-x%29^%28m-1%29%29%29++dx http://www.wolframalpha.com/input/?i=-+int_0^1+%28m*%281-x%2... Or do you have a subscription?
- gjm11 11y ago> You made one small mistake at the end Oh yes, so I did. Sorry about that. > What did you ask wolfram alpha to get the -log m + 1 - 1/m? This, I think: http://www.wolframalpha.com/input/?i=Integrate[m+t^%28m-1%29+Log[m+t^%28m-1%29],{t,0,1} http://www.wolframalpha.com/input/?i=Integrate[m+t^%28m-1%29...] I get a message about computation time exceeded, but I also get the answer (both the indefinite integral and the definite). I don't have a subscription.
- chronial 11y agoFascinating ^^. Removing the minus before the integral and changing 1-x to x is the difference that matters. I would have though that wa is so quick with those transformations that it doesn’t make a difference. Well, I was wrong :).