3 ms·

Yes, this. If you want a password that is secure against a bruteforce attack, I would strongly advice against making it up yourself. You will never know the ent

Yes, this. If you want a password that is secure against a bruteforce attack, I would strongly advice against making it up yourself. You will never know the entropy of your password and it could be anything. I personally just generate 10 passphrases from a wordlist and take the one the I like the most. This way you get both – predictable entropy and good chances of getting something you can remember. Even though I could never quite figure out which effect the "pick one of ten" method exactly has on the entropy :). If anybody has any good input on that, I would be very happy to hear it. If you have a wordlist that contains information on the type of word, you can generate grammatically valid sentences without loosing too much entropy. I wrote a tool to this in my native language (german) and I get sentences like "schleimendes Hervorbringen transportiert krampflösend". This (very) roughly translates to "slimy production transports anticonvulsantly". The german sentence has an entropy of 52 bit.

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 ago
  Thanks 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 ago
      Fascinating ^^. 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 :).

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 ago
Thanks 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 ago
    Fascinating ^^. 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 :).