4 ms·

Texas nitrogen snail purple penut. Every word from a different domain, complete with a word I often misspell, and at least one word not in the top 10,000 most

Texas nitrogen snail purple penut. Every word from a different domain, complete with a word I often misspell, and at least one word not in the top 10,000 most common words. I think you're going to need a bigger Markov Chain.

atemerev 11y ago
No, unless you obtained these words using a crypto-rated PRNG. Otherwise your passphrase is vulnerable to semantic network analysis (somewhat more complicated than Markov chains, but still trivial). Sorry, humans can't generate secure passwords and passphrases anymore. (You still can memorize secure passwords, but it becomes increasingly harder).
- chronial 11y ago
  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 :).
- merpnderp 11y ago
  True, I really don't know the exact entropy and perhaps an attacker will have access to large amounts of my previous writing, which might help them guess how I would connect different domains. We know the relationship between horses and batteries, but what's the weight of the relationship between snails and purple? But 30 billion hashes a second is quite a hashing rig, and even if they could reduce the entropy by a 2 orders of magnitude, they're still looking at nearly a hundred years. With a hard algorithm, like bcrypt, or without access to my writings, that password is impregnable.
- merpnderp 11y ago
  Could you expand on this. If someone is using words not in the top 10,000 words along with words in the top 10,000, and they pick 4-5 words, how is semantic network analysis going to help? You're saying this analysis can reduce the ~10,000 possibilities to something much smaller? And you're reasoning being that people don't actually pick from the top 10,000? How does that work?

atemerev 11y ago

No, unless you obtained these words using a crypto-rated PRNG. Otherwise your passphrase is vulnerable to semantic network analysis (somewhat more complicated than Markov chains, but still trivial). Sorry, humans can't generate secure passwords and passphrases anymore. (You still can memorize secure passwords, but it becomes increasingly harder).

chronial 11y ago
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 :).
merpnderp 11y ago
True, I really don't know the exact entropy and perhaps an attacker will have access to large amounts of my previous writing, which might help them guess how I would connect different domains. We know the relationship between horses and batteries, but what's the weight of the relationship between snails and purple? But 30 billion hashes a second is quite a hashing rig, and even if they could reduce the entropy by a 2 orders of magnitude, they're still looking at nearly a hundred years. With a hard algorithm, like bcrypt, or without access to my writings, that password is impregnable.
merpnderp 11y ago
Could you expand on this. If someone is using words not in the top 10,000 words along with words in the top 10,000, and they pick 4-5 words, how is semantic network analysis going to help? You're saying this analysis can reduce the ~10,000 possibilities to something much smaller? And you're reasoning being that people don't actually pick from the top 10,000? How does that work?