Are you struggling for passwords for wallet encryption ?

[dogisland]

You might want to take a look at this first.

https://www.grc.com/haystack.htm

[1714028461]

1714028461

[1714028461]

1714028461

[1714028461]

1714028461

[BubbleBoy]

The idea of padding for increased security is laughable. Another GRC classic.

[lettucebee]

I went through an unpleasant experience where, after MtGox, I changed my wallet password.  To get real tricky I inserted ascii characters in a few places in my passphrase.  Made perfect sense at the time, to embellish the old with a little new.

Then a couple months later I couldn't remember it!

I ended up having to bruteforce my own password!  Had I not known most of it already this would have been impossible as it was almost 20 characters.

[JohnnyCashout]

The idea of padding for increased security is laughable. Another GRC classic.

forgive my ignorance but it seems like you are saying a password like this :

p@$$w0rd


is more secure than this :

p@$$w0rd+8%($1)5B,1


can you explain how that is even possible?

[defxor]

http://lastpass.com

[Lumpy]

Keep it in your own hands.

http://keepass.info

[defxor]

Keep it in your own hands.

http://keepass.info

LastPass neither have nor can they retrieve your passwords. They're "in your hands".

[DeathAndTaxes]

Meh.  Pick a password that is hard for computers to solve and easy for you to remember.



http://xkcd.com/936/

I tend to use a longer passphrase but one not completely random.

For example:
"To be or not to be a toaster"  (I will remember the famous quote combined with toaster = Battlestar)
"This is my password for Google Universal Life" (A play on the whole password as a password combined with inside joke that someday google will own everything)
"In cryptography we trust, in quantum computing we fail" (an unofficial bitcoin motto and fear of a future SHA-256 killer)

The long password length maxes a large bruteforce attack space.   A smarter attacker would use dictionary to search for word combinations however using more than 4 words makes that prohibitive even with a hashing network.  Even if the attacker used a dictionary of 100K words the bottom password would require 100,000^9 (equivalent to 2^150) for an exaustive search.

There is a danger is using a passphrase that is well known as it could be subject to a precomputation attack which is why we conduct word substitution.

The nice thing is the weirder you are the less likely any phrase you use come up with be in precomputation database:
"A salt a day keeps both snails and rainbow tables away"

Less entropy than random words (of equal length) but still stronger than most cryptic short passwords and easier to remember than just random words which allow a longer passphrase.  

Be sure to modify a quote to make it psuedo unique (and don't use any I used here).

[Grinder]

Meh.  Pick a password that is hard for computers to solve and easy for you to remember.
For example:
"To be or not to be a toaster"  (I will remember the famous quote combined with toaster = Battlestar)

The MtGox incident showed that people writing password crackers are much more clever than most people think, so these kinds of passwords are likely to be cracked. 8-9 bytes of random chars is better than fairly long strings of words, even if they are obfuscated.

[DeathAndTaxes]

The MtGox incident showed that people writing password crackers are much more clever than most people think, so these kinds of passwords are likely to be cracked. 8-9 bytes of random chars is better than fairly long strings of words, even if they are obfuscated.

No it didn't.  Show me one example of someone with a 20+ char password that was brute forced.  It is computationally infeasible with current technology.

There exists databases of know COMMON passwords taken from prior online hacks (hotmail was one of the largest).  The most popular one contains roughly 14.1 million known passwords and substitutions of known passwords.  So one can hash every password in the database and compare it against stolen password hash file looking for matches.

Remember in an attack like Mt Gox, 90%+ of accounts WEREN'T hacked.  If an attacker gets hash file they don't need to hack every account.  Just the 1% that are the weakest.  Mt Gox was a combination of rookie mistakes by Mt. Gox combined with weak passwords combined with people who didn't update their password.

Still password databases don't contain long complex pass-phrases because as password length increases the likelihood the password is used decreases and it isn't cost effective to selectively attempt those less likely pass-phrases.  Brute forcing 20+ characters is beyond our computational ability even IF you told the attacker it is all lowercase assuming some key-strengthening was done.

That remind me I should check if bitcoin client does any key-strengthening to reduce the number of attacks per second (i.e. PBKDF2) http://en.wikipedia.org/wiki/PBKDF2

On edit:  Looks like bitcoin wallet does some dynamic key strenghening.  Nice feature.  Now if they just used OpenCL to generate key it would vastly reduce the ability to execute a brute force attack.

Technical details of wallet encryption
--------------------------------------
Wallet encryption uses AES-256-CBC to encrypt only the private keys
that are held in a wallet.  The keys are encrypted with a master key
which is entirely random.  This master key is then encrypted with
AES-256-CBC with a key derived from the passphrase using SHA512 and
OpenSSL's EVP_BytesToKey and a dynamic number of rounds determined by
the speed of the machine which does the initial encryption (and is
updated based on the speed of a computer which does a subsequent
passphrase change). Although the underlying code supports multiple
encrypted copies of the same master key (and thus multiple passphrases)
the client does not yet have a method to add additional passphrases.

At runtime, the client loads the wallet as it normally would, however
the keystore stores the keys in encrypted form.  When the passphrase
is required (to top up keypool or send coins) it will either be queried
by a GUI prompt, or must first be entered with the walletpassphrase
RPC command.  This will change the wallet to "unlocked" state where the
unencrypted master key is stored in memory (in the case of GUI, only for
long enough to complete the requested operation, in RPC, for as long as
is specified by the second parameter to walletpassphrase).  The wallet is
then locked (or can be manually locked using the walletlock RPC command)
and the unencrypted master key is removed from memory.

8-9 bytes of random chars is better than fairly long strings of words

This is true.  Nobody said otherwise.  However most people tend to forget 9 random characters (and it must be purely random to have more entropy AND never be used on any other site/application.   As a result most people don't use purely random single use passwords and figure an easier substitution password (as indicated in the cartoon) is good enough.  The reality is despite it being harder to remember they lack any useful entropy and can be brute forced relatively easily.  

So yes if you:
a) use 9 random digit (containing upper, lower, number & punctuation).
b) always generate them randomly.
c) never re-use them (password re-use kills any security you have).
d) never store a backup copy digitally.

then nothing is safer.  It is impossible to brute force or use a lookup table assuming the implementation is secure.  You still need to worry about social engineering attacks, fraud, trojans, keyloggers, etc.

Most people don't do that.  Hell I would wager that you likely don't do that.

[defxor]

if you use 9 digit purely random password (containing upper, lower, number & punctuation), always generate them randomly, never re-use them (password re-use kills any security you have), and never store a backup copy online then nothing is safer and it is impossible to brute force with current hardware. I doubt you do that though.

I'll just keep repeating "LastPass", since it's by far the easiest way to get non-security trained consumers to use proper passwords. Always generated randomly, contains the full charset incl. numbers and special characters, never re-used and with no plaintext backups stored neither locally nor online.

Doubt away.

[BubbleBoy]

The idea of padding for increased security is laughable. Another GRC classic.

forgive my ignorance but it seems like you are saying a password like this :

p@$$w0rd


is more secure than this :

p@$$w0rd+8%($1)5B,1


can you explain how that is even possible?

GRC claims that "p@$$w0rd[[[[[[[[[[[[[[[" is much more secure than "p@$$w0rd". Simply extending the password length with bogus and easy to remember characters is said to be a much stronger password. In fact, taking all possible padding characters (2^6.5), all lengths between 0 and 31 padding chars (5 bits) and all positions  of the padding block within a 16 char password (2^4) you only gain 15 bits of entropy. But you can get 13 extra bits that by simply adding 2 random characters to your password, without bothering to count bogus padding chars.

He goes as far as claiming that "D0g....................." is stronger than "PrXyc.N(n4k77#L!eVdAfp9" based simply on the length. That's preposterous ! The first password has 36 bits of entropy while the second has 150 bits, assuming a cracker aware of the "technique". Presuming that you are smarter than the attacker is the road to security hell.

a) use 9 random digit (containing upper, lower, number & punctuation).
...
It is impossible to brute force or use a lookup table assuming the implementation is secure.

It's quite possible, depending on the algorithm used and the size of the attacker. The key-space for 9 characters is 6.37 x 10^17 so assuming it's a SHA256 salted hash then the current bitcoin mining network at 15THash/sec will exhaust the keyspace in 12 hours. The US government can probably do it in minutes. You could rent the current mining network for a small multiple of t 6*50BTC*5$ = 1500$/hour, assuming a market for cracking SHA256 hashes would exist.
To escape even the US government use a 16 character random password not generated by a human (no inter-character memory, characters are statistically independent). That is indeed hard to remember.

"To be or not to be a toaster"

With the exception of "toaster" all words are in the top 100 by frequency. "toaster" is maybe in the core 10K vocabulary. There's no need to use 100K words dictionaries if most users don't use words like "Lymphocytopenia" or "Synecdoche". So 7*7+10 = 59 bits, hard but crackable see above. A non naive lexical cracker will not throw words randomly in a sentence and the rules of the English language would allow it to massively prune the search space.

[Grinder]

No it didn't.  Show me one example of someone with a 20+ char password that was brute forced.  It is computationally infeasible with current technology.

I don't have the list of cracked passwords anymore, but it's not necessarily hard to crack sentences. If you use only dictionary words the entropy is "number of words in dictionary" ^ "number of words in string", and if you use a grammatically valid sentence and/or mostly common words it's much lower.

[DeathAndTaxes]

It's quite possible, depending on the algorithm used and the size of the attacker. The key-space for 9 characters is 6.37 x 10^17 so assuming it's a SHA256 salted hash then the current bitcoin mining network at 15THash/sec will exhaust the keyspace in 12 hours. The US government can probably do it in minutes. You could rent the current mining network for a small multiple of t 6*50BTC*5$ = 1500$/hour, assuming a market for cracking SHA256 hashes would exist.
To escape even the US government use a 16 character random password not generated by a human (no inter-character memory, characters are statistically independent). That is indeed hard to remember.

You obviously haven't heard of key strengthening.  Nobody (including the bitcoin client) simple takes password -> SHA1 -> key.  That would allow the average GPU to attempt 100 million to 1 billion passwords per second.  An obvious an huge security flaw.

Instead you take password -> SHA1 -> output -> SHA1 -> output .... 10K iterations -> key.  Now the number of permutations is limited by how fast you want the client to respond.  An excel file for example does 17,500 permutations.  The bitcoin client picks a permutation count that is dynamic depending on how fast the owners computer is.   The goal is to increase the length of time to hash one password.  The user isn't hindered.  Do you really care if it takes bitcoin client 1.2 seconds to open instead of 0.00000000000000000000000000000000000000001 seconds?  However by increasing the computation load to try one password you vastly reduces the effectiveness of attacker's hardware.


So your hypothetical example of 15TH/s exhausting the keyspace in 12 hours.  that is for 1 hash = 1 key.  If it is 10K hashes = 1 key then it isn't 12 hours it is 120,000 hours = 14 years.  If it is 100K hashes per key it is now 140 years.    Even if the govt had 100 TH of computing power it would take them over a year to crack.  Here is the great thing .... adding a single digit would increase size of keyspace by a factor of 94x.  So now 100TH would take almost a century.  Even 1 PH would take a decade.

The bitcoin implementation goes a step even further by using dynamic key strengthening.  Every time you set or change the password it sets the permutations of key strengthening based on current hardware.  So as computer hardware gets faster your passphrase gets more difficult.  Everytime you change your passphrase it changes the permutation count based on how powerful your hardware is.

If someday a bitcoin client uses GPU to hash the password well then the permutation count could be in the millions.  In that scenario even a 15 TH network could only try 1.5 million passwords per second.  Sounds like a lot but to exhaust a 9 random digit password would require over 12,000 years.

More info on key derivation functions:
http://en.wikipedia.org/wiki/Key_derivation_function
http://en.wikipedia.org/wiki/PBKDF2

[joulesbeef]

Prediction:


a crap load of people lose their coins before people get used to encrypting their wallets.

most people might have experience with passwords online, where when they lose it they answer some stupid questions like what is their dogs name and get a reset link mailed to them.. with this you are SOL.
I suggest you write it down and keep it in your wallet or safety deposit box, you my want to obfuscate it a bit.
"This girl that looked like a horse and wasnt Sarah Jessica Parker gave me a staple hooked up to a battery and thought it might be worth something but I corrected her"

The alternative coins have already added encryption as it was in the beta of bitcoin... they have already seen a ton of people lose their coins.
DONT BE ONE OF THESE PEOPLE.

[Gavin Andresen]

He goes as far as claiming that "D0g....................." is stronger than "PrXyc.N(n4k77#L!eVdAfp9" based simply on the length. That's preposterous ! The first password has 36 bits of entropy while the second has 150 bits, assuming a cracker aware of the "technique". Presuming that you are smarter than the attacker is the road to security hell.

I've been wondering about that-- is it possible to write a password cracker that generates all the lower-entropy passwords first?

That's the kind of theoretical computer science problem that it seems like should have an answer, or have a proof that it is equivalent to the halting problem.

[ctoon6]

i think a password like this is more than adequate.

"ighghghlikeghghghbooksghghgh"

all you need to remember is "gh" 3 times after every word, and the phrase i like books.

i have no idea how secure that password is, but id imagine its far more secure than a password like ilikebooks. and if you were paranoid you could use diceware with custom words and pad each word with 3 or more random characters that repeat. after all, a computer does not know if the password is half right, only that the password is right or wrong. and really, if your password is good enough for at least 7 days, its served its purpose long enough for you to change it, but it will not work like that all the time, for example files encrypted in a lost flash drive.

but if i could recommend an awesome way to log in, it would be with pgp/gpg/similar. you give the server a public key which matches a private key in an offline only system. it could be a random 4 char code that you sign, and send the signed results back to the server that can be verified. every time you wish to log in, you need to resign a new random phrase. we could come up with a standard where you use the current time and date to the minute, the server only accepts signed data within the last 10 minutes. for example

sign "2011-09-23-15-05"

year, month, day, hour, minute

this way you can ensure that no company will ever send out the same sign requests. and really, you would not even need to send out the requests anyway, as long as the time on the device and the server are accurate ~±2 or so, your good to go, a server could easily check it 10 times in under a few seconds for every possible time in the last few minutes.

return the signed data, server verify the data, accept login to the session.

BTW, feel free to steal the idea, id love this. just send me a pm or something if you use it so i can try it out myself

[DeathAndTaxes]

He goes as far as claiming that "D0g....................." is stronger than "PrXyc.N(n4k77#L!eVdAfp9" based simply on the length. That's preposterous ! The first password has 36 bits of entropy while the second has 150 bits, assuming a cracker aware of the "technique". Presuming that you are smarter than the attacker is the road to security hell.

I've been wondering about that-- is it possible to write a password cracker that generates all the lower-entropy passwords first?

That's the kind of theoretical computer science problem that it seems like should have an answer, or have a proof that it is equivalent to the halting problem.

There are engines that work that way but they don't handle the example provided well.

One well known example is Jack the Ripper an open source powerful cracking engine.  It starts with a root word dictionary of common root words used in passwords (pull from prior password compromises, the largest being an hotmail password hash file which didn't use a per user salt.  This allowed pools of hackers to brute force that list to determine common password root words with a very large sample.

Essentially the engine takes a root word and "mangles it".  
Applies permutations of
1) capitalization changes
2) simple substitutions d0g for dog
3) apply suffix of symbols & numbers

so words with small amount of deviation from a root password have a reasonable chance of being compromised. However quickly the number of pemutations start adding up and it is better to just try brute force of all permutations.

In the example above both the high and low entropy passwords would be tough to brute force.  While the more complex one is indeed stronger they are both beyond limits of current algorithms and an attacker would need to resort to brute force.  The only exception would be if the attacker knew you were using a single repeated symbol  Even if they did one would greatly increase the effective entropy by using a second symbol.

d0g.....................................................!

In most password breaches it simply isn't worth it for an attacker to search exhaustively.  In Mt Gox attack the attackers obtained the password hash file and compromised accounts until further cracking didn't warrant the risk of delaying the attack.  Since the attack space grows geometrically at some point it isn't worth it to try and compromise more accounts.  Simply put the accounts breaches were the ones that were so easily cracked it was worth delaying the attack. Once the had got all the low hanging fruit they attacked.

The unique challenge with bitcoin is that an attacker could keep brute forcing a wallet for a very long time.  The counter solution would be to periodicaly move funds to a new address.  Maybe some future version of bitcoin client (or a high security variant) could do something like that.  One address (or group of adresses) would be designated the "savings account" and keep the large balance of coins. 

Now say wallet.dat is stolen and attacker begins to brute force it.  The bitcoin client would periodically (period set by user say once per month) create a new address transfer funds to that address and then stop using old saving account addresses.  This now limits the attacker attack horizon to < 15 days on average.  IF the compromise the wallet.dat they stole AFTER the funds are moved it is worthless.

[DeathAndTaxes]

if i could recommend an awesome way to log in, it would be with pgp/gpg/similar. you give the server a public key which matches a private key in an offline only system. it could be a random 4 char code that you sign, and send the signed results back to the server that can be verified. every time you wish to log in, you need to resign a new random phrase. we could come up with a standard where you use the current time and date to the minute, the server only accepts signed data within the last 10 minutes. for example

sign "2011-09-23-15-05"

year, month, day, hour, minute

this way you can ensure that no company will ever send out the same sign requests. and really, you would not even need to send out the requests anyway, as long as the time on the device and the server are accurate ~±2 or so, your good to go, a server could easily check it 10 times in under a few seconds for every possible time in the last few minutes.

return the signed data, server verify the data, accept login to the session.

That is how secure tokens (RSA, yubikey, etc) work.

Still one should also have a password.  The token/cert/key could be stolen.  It should only be used as a second factor in multi-factor authentication.

The premise being authentication should involve
a) something you know (password, pass-phrase, personal knowledge, combination, etc)
b) something you have (RSA token, cert private key, etc)
c) something you are (biometrics, language exploitation - using challenge words with L in WWII to catch Japanese, etc)

Good security involves more than one independent factor
Mt Grox login uses password (something you know) and yubikey (something you have).
Access to my department at work requires pin code (something I know) and security badge (something I have).

Compromising the system requires defeating two independent factors.

[ctoon6]

if i could recommend an awesome way to log in, it would be with pgp/gpg/similar. you give the server a public key which matches a private key in an offline only system. it could be a random 4 char code that you sign, and send the signed results back to the server that can be verified. every time you wish to log in, you need to resign a new random phrase. we could come up with a standard where you use the current time and date to the minute, the server only accepts signed data within the last 10 minutes. for example

sign "2011-09-23-15-05"

year, month, day, hour, minute

this way you can ensure that no company will ever send out the same sign requests. and really, you would not even need to send out the requests anyway, as long as the time on the device and the server are accurate ~±2 or so, your good to go, a server could easily check it 10 times in under a few seconds for every possible time in the last few minutes.

return the signed data, server verify the data, accept login to the session.

That is how secure tokens (RSA, yubikey, etc) work.

Still one should also have a password.  The token/cert/key could be stolen.  It should only be used as a second factor in multi-factor authentication.

The premise being authentication should involve
a) something you know (password, pass-phrase, personal knowledge, combination, etc)
b) something you have (RSA token, cert private key, etc)
c) something you are (biometrics, language exploitation - using challenge words with L in WWII to catch Japanese, etc)

Good security involves more than one independent factor
Mt Grox login uses password (something you know) and yubikey (something you have).
Access to my department at work requires pin code (something I know) and security badge (something I have).

Compromising the system requires defeating two independent factors.

the reason i suggest it is because

1. security tokens, physical ones can break or run out of battery, what i propose is something very similar to it, but can be used by people who do not own said token or have a cellular device.
2. tokens are in a way, somtimes worthless, how do you "recover" an account to which you "lost" or broke the token or something. this can make or break the system.
3. you can mail or use the internet or give the key in person at a real establishment.
4. it is 1 way, you do not need the other persons key, unless you want to do something else as well.
5. the system with the key is always offline, and can be used for bitcoin as well, export signed transactions. hell, ill go on ahead and suggest and entire new system, call it "cryptographic tools". make and verify and encrypt/decrypt files and such, just like gpg, except not suck on windows. and do bitcoin as well. it could be module based, where you have the main system, but then have separate files that define the rules and genesis block and checkpoint blocks too. it could support import/export private keys, transactions, blocks and my password idea as well. the whole thing could be stream lined where all you do is move the flash drive from one system to another. or you could use a usb cable or if your computer has 2 Ethernet ports, hook one directly to the other computer and communicate that way.