OT: that reminds me of something I've wondered about. I've always assumed that a serious password cracker trying a dictionary attack or trying a list of known common passwords would also try assorted simple transformations on them that people who think they are clever might try, like using sha on the memorized password and using the output of that as the password the site sees.
But how about more complicated transforms? For example, suppose someone did this in their shell to get the password (or private key, or whatever):
X=common_word.four_digit_number
S=$(echo -n $X | shasum)
for i in {1..501}
do
X=$(echo -n $X.$S | shasum)
done
echo $X
How do you estimate the entropy of something like that? At first it might seem it is just the entropy from the choice of common_word and four_digit_number, which is presumably fairly low. But that code is simple enough and short enough that I can delete it as soon as I recover the final $X, and retype it from memory the next time I need it.
In effect, isn't the secret that has to be guessed here both common_work.four_digit_number AND the code? And so doesn't the choice of code contribute to the entropy?
If so, what's the entropy of the program above? Let's say the bad guy knows that I've got some kind of memorized program that can take text input and transform it to text output, and it's small enough that I'm willing to type it in whenever I need it. That still leaves a huge number of possible algorithms.
Back in the days before password managers were common, I played around with something like this. I had a PGP encrypted file containing my password list. My PGP password was a long random string that I had memorized, and did not have written down anywhere. I wanted to have some kind of recovery procedure in case I forgot that password.
An encrypted file with my PGP password, encrypted with some other password, is the obvious approach, but then we are right back where we started with having to deal with that other password. It occurred to me that I'm less likely to forget an algorithm than a long random string, so if the second password was the result of an algorithm, I could memorize the algorithm and generate the password as needed.
Here's the algorithm I used:
1. Make a 100 x 100 array of all zeros.
2. Imagining this array represents a bitmapped 100x100 pixel display black and white display, draw in the lower left corner the string "tzs!" using a specific bitmapped font.
3. Run 108 generations of Conways's Life cellular automaton on the 100 x 100 array, with left to right and top to bottom wrapping.
3. Form a string of 10000 characters by scanning the array row by row, adding a "0" or "1" to the string depending on the state of the current array cell.
4. MD5 (this was a long time ago) that string, and print the result in hex. That hex string is the password for the PGP encrypted file containing my PGP password for my encrypted password list.
I never actually put that into production, but every few months I would sit down and implement that algorithm in C and run it, see that I got the right password, and then delete the code again. I had no trouble remembering it, even with only such sparse usage.
If you're using Kolmogorov complexity as your measure of entropy, then the entropy is given by the shortest program required to produce the output. So yes, in your example, you would need to include the code in the entropy measure.
This is still kinda subtle though, because computing SHA obviously requires a fairly complex program -- and yet, if your program had consisted of a single SHA and nothing else, it would be far less secure. Why?
I think it's because the security of a password doesn't depend purely on its Kolmogorov complexity, but rather something like its...distance from a Shelling point? SHA is complicated, but it's also so common that you can invoke it in your shell with six letters. So a single application of SHA is not far from a Shelling point. If you had used a modified SHA, say tweaking one of the constants involved, then your password would immediately become much harder to guess. And yet your modified SHA could have the exact same Kolmogorov complexity as the unmodified version.
(Obviously, random or secure pseudorandom passwords fit this definition as well, since a random string is not close to any Shelling point.)
They are close enough that the relationship between them is graspable to the human mind, if the numbers themselves are not. Take the unimaginable 10^77, put it in a box. Now imagine a thousand boxes. That's 10^80. Of course a thousand times an unimaginable number is astronomically bigger on a linear scale, but if you just look at the relationship between the two numbers it's imaginable.
Is it cheaper yet to random walk the entire private key address space to look for wallets with value, than it is to generate Bitcoins, in terms of "dollars earned per hour/month/year"?
>Randomly generating an existing key is essentially impossible. If all 7 billion people on the planet generated a million keys per second for a century, a year later they would have on the order of 1025 new keys - the probability of any of those matching a previously-used key is far less than the probability of winning a lottery jackpot every day for three years. In other words, it’s impossible to “get lucky” and generate a duplicate key even if you have all the computational power on Earth and try for more than the average human lifespan.
13 comments
[ 3.8 ms ] story [ 18.0 ms ] threadEveryone else was just messing about with fractions of a cent and didn't care about security.
But how about more complicated transforms? For example, suppose someone did this in their shell to get the password (or private key, or whatever):
How do you estimate the entropy of something like that? At first it might seem it is just the entropy from the choice of common_word and four_digit_number, which is presumably fairly low. But that code is simple enough and short enough that I can delete it as soon as I recover the final $X, and retype it from memory the next time I need it.In effect, isn't the secret that has to be guessed here both common_work.four_digit_number AND the code? And so doesn't the choice of code contribute to the entropy?
If so, what's the entropy of the program above? Let's say the bad guy knows that I've got some kind of memorized program that can take text input and transform it to text output, and it's small enough that I'm willing to type it in whenever I need it. That still leaves a huge number of possible algorithms.
Back in the days before password managers were common, I played around with something like this. I had a PGP encrypted file containing my password list. My PGP password was a long random string that I had memorized, and did not have written down anywhere. I wanted to have some kind of recovery procedure in case I forgot that password.
An encrypted file with my PGP password, encrypted with some other password, is the obvious approach, but then we are right back where we started with having to deal with that other password. It occurred to me that I'm less likely to forget an algorithm than a long random string, so if the second password was the result of an algorithm, I could memorize the algorithm and generate the password as needed.
Here's the algorithm I used:
1. Make a 100 x 100 array of all zeros.
2. Imagining this array represents a bitmapped 100x100 pixel display black and white display, draw in the lower left corner the string "tzs!" using a specific bitmapped font.
3. Run 108 generations of Conways's Life cellular automaton on the 100 x 100 array, with left to right and top to bottom wrapping.
3. Form a string of 10000 characters by scanning the array row by row, adding a "0" or "1" to the string depending on the state of the current array cell.
4. MD5 (this was a long time ago) that string, and print the result in hex. That hex string is the password for the PGP encrypted file containing my PGP password for my encrypted password list.
I never actually put that into production, but every few months I would sit down and implement that algorithm in C and run it, see that I got the right password, and then delete the code again. I had no trouble remembering it, even with only such sparse usage.
This is still kinda subtle though, because computing SHA obviously requires a fairly complex program -- and yet, if your program had consisted of a single SHA and nothing else, it would be far less secure. Why?
I think it's because the security of a password doesn't depend purely on its Kolmogorov complexity, but rather something like its...distance from a Shelling point? SHA is complicated, but it's also so common that you can invoke it in your shell with six letters. So a single application of SHA is not far from a Shelling point. If you had used a modified SHA, say tweaking one of the constants involved, then your password would immediately become much harder to guess. And yet your modified SHA could have the exact same Kolmogorov complexity as the unmodified version.
(Obviously, random or secure pseudorandom passwords fit this definition as well, since a random string is not close to any Shelling point.)
Ugh. My pedant-bone is itching... That's not "pretty close" at all. There's a universe of distance between 10^77 and 10^80.
But still; Between 10^3 and 10^77, that 77 OWNS
>Randomly generating an existing key is essentially impossible. If all 7 billion people on the planet generated a million keys per second for a century, a year later they would have on the order of 1025 new keys - the probability of any of those matching a previously-used key is far less than the probability of winning a lottery jackpot every day for three years. In other words, it’s impossible to “get lucky” and generate a duplicate key even if you have all the computational power on Earth and try for more than the average human lifespan.