Password strength of random words and brainflayer

Question

I have read from multiple sources that it might be better to have a password composed of several random words since this is easier to remember than a random sequence of characters. For example this article from Thomas Baekdal. I even see this xkcd comic quite often.

Now, I read this article about a new tool called brainflayer, currently target Bitcoin wallets, that can guess 130000 passwords a second. This makes Bitcoin brainwallets useless. I wonder if a similar tool could be used against all passwords and are passwords such as "this is fun" really as safe as Thomas Baekdal claims?

Answer 1

I wrote brainflayer and gave a talk about it at DEFCON. Neither Thomas Baekdal's article nor XKCD's comic apply well to modern offline attacks. I read Thomas's article and his FAQ about it, and it may have been marginally reasonable when he wrote it, it no longer is. A key point is that password cracking attacks have gotten much better since then.

Q: If I cannot write "this is fun" because of the spaces, can I not just write "thisisfun"?

A: Absolutely not! The reason why "this is fun" is 10 times more secure, is simply because it is much longer (11 characters). By removing the spaces, you reduce the length and the complexity substantially. The spaces are effectively special characters, which in itself makes the password much more secure.

Use "this-is-fun" instead.

Password crackers don't try long brute force attacks much - it's all about cracking ROI. A smart cracker will try word combinations with various delimiters, so using spaces, hyphens, underscores or nothing all ends up providing about the same security. Today's cracking methods use wordlists - which can include phrases - and large corpuses of previously compromised passwords along with popularity. This is combined with rule-based permutation and statistical models. Ars Technica posted a great article detailing modern techniques mid-2013, and attacks only get better.

I am also of the (possibly controversial) opinion that it is pointless to talk about guesses per second for offline attacks. A much better way of thinking about it is guesses per dollar. If you want to be pedantic you could add a one-time guesses per second per dollar cost, but the operational cost will tend to dominate. Brainflayer's upper bound on operational cost is 560M guesses per dollar, based on EC2 spot instance benchmarks - with zero one-time cost. It's possible to make these costs many orders of magnitude higher with a "harder" hash function like bcrypt, scrypt, PBKDF2 or, once it is finalized, Argon2.

Answer 2

The specific attack your talking about had, per the defcon talk, certain specific characteristics that mean that the same attack doesn't really apply to all passwords.

First and most importantly, brainwallets effectively put the password hash in a public location. Usually the first defence against cracking of password hashes is to try and secure the hash itself.

Second up, brainwallet didn't use any of the common password storage algorithms (e.g. PBKDF2 or bcrypt) to protect the hashes. In cases where the attacker gets access to the hash, it's important to try and slow down their attack as much as possible. Password storage algorithms do this by making it "Computationally difficult" for the password hash to be created from the password, slowing down the attack. There's loads more details on these here

Answer 3

Interesting question. @RoryMcCune nicely addressed the question about brainflyer, so I'd like to address your more open-ended question:

are passwords such as "this is fun" really as safe as Thomas Baekdal claims?

No, no it is not.

My first thoughts are 1) that Thomas Baekdal doesn't explain how he's calculating his time estimates, which makes my inner scientist skeptical, and 2) that his article doesn't take into account Moore's Law - the idea that our computing power is increasing at an alarming rate. The article was written in 2007 and since then both our brunt computing power per $, and ability to effectively use parallel processors (esp. GPGPU's) have gone up leaps and bounds.

I take issue with his statement: "100 years - this is really the limit for most people. Who cares about their password being hacked after they have died?". This is a fallacy; this number is based on the speed of today's computers and assumes that technology will not increase during those 100 years.

In my opinion, passwords are a dying technology since they do not scale with CPU speed (ie, our ability to crack them is increasing exponentially, but our ability to remember longer ones is not). Unfortunately, no single technology has risen yet to replace them. Two good attempts to solve the scaling problem come to mind:

1. Private key-based authentication. This scales since we can keep increasing the key size as CPU speed increases.

2. Proof-of-work schemes. This idea is to require the login process to involve something which takes a very large amount of computation. Password stretching / hashing functions like PBKDF2 or bcrypt are examples, as well as challenge-response authentication schemes which include asking the client to do a very long computation which the server can easily verify (like factoring: "here is a very large number n, send me back p, q such that p*q = n"). As processors get faster, you simply increase the amount of work that you're asking for.

Both of these have nice theoretical properties, but are inconvenient for end-users, which is stopping them from getting widespread adoption.

Answer 4

Offline attacks are slightly different than online attacks.

In an online attack, rate limiting and the overhead of network transmission means that extremely fast password attempts are not practical.

In an offline attack, when you have a hashed password, you can get much much faster attack rates typically. And you can scale it up (by using cloud computing) in a broad way (which is difficult to do online, without bot-armies).

Still, a speed of 130,000 attempts/second, or 560 million guesses per dollar, is not that hard to defeat. Thomas assumed 100 attempts/second: hitting 100,000/second just makes passwords 1000x less secure. The 5 uncommon word password had a crack time of half a trillion years: after a 1000x speed, this becomes half a billion years.

The XKCD method's makes it easier to analyze the cost of your password. Suppose your attacker can try 1 billion passwords per dollar spent ("30 bits" of password entropy per dollar) (twice as efficient as brainflayer).

Then picking 4 random words from the most common 1000 English words (a 4*1k XKCD password) has 40 bits of entropy, so it takes 40-30 = 10 bits of dollars, or about 1000 dollars, to crack your password "offline".

Up it to 4 random words from the most common 4k English words (a 4*4k XKCD password), and it takes 48-30=18 bits of dollars, or 250,000 dollars to crack your password.

6 random words from the most common 8k English words (6*8k) is 78 bits. It costs 48 bits of dollars to defeat it today, or 250,000,000,000,000$, or 2-4x the annual GDP of the entire world.

Now, if we presume Moore's law will continue to hold with regard to password cracking (every 2 years, the cost of cracking a password halves), and we want to know "how long will our password be 1 million dollars secure), we can do this:

30 (current bits/dollar) + 20 (1 million dollars) = 50.

Take the number of password entropy bits, and subtract 50.

Moore's law states that computation gets half as expensive every 2 years. So double the number of bits remaining, and that is how many years your password should be secure against a 1 million dollar attack.

4*1k is 40 bits, which is less than 50, so it is not secure today against an offline attack.

5*4k is 60 bits, so it is safe for ~20 years against an offline attack.

6*8k is 78 bits, so it is safe for ~56 years against an offline attack.

All of this assumes you let a good quality, secure system do the password pick for you (if you try to pick a password this way, you'll almost certainly get way less entropy).

Answer 5

SHA-256 and ECDSA are considered very strong currently, but they might be broken in the far future. If that happens, Bitcoin can shift to a stronger algorithm.

(Block hashing algorithm)

So the hashing algorithms used are not an issue. Adding to this, the computational capacities (Block hashing algorithm) required for cracking are not that easy; even if this is questionable already (ASIC mining). The strength of Bitcoin is not your question but take this as a comment to the other answer you have, and actually Knowledge of passphrase == Control of money (Cracking Cryptocurrency Brainwallets)

Coming back to your question properly said, theoretically speaking, the set of human behaviors is more enormous than the universe itself. However, in practice we tend to all share the same practices as others (Mind, society and behavior). As a matter of proof, even with 4 digits PINs, lot of combination are rarely used whereas others are so widely used:

I mentioned this PIN code survey of 4 digits length to make a parallel with a password or a phrase as a password (passphrase): it is not a matter of what is the best password schema to use, (Edward Snowden Explains Why You Should Use Passphrases, Not Passwords) but rather how many people are ready to follow the advice in practice . So what you ask about is really plausible (above table is a good proof). These last days, researchers here in France succeeded to develop a software based on a set of algorithms to identify users following the way they type on a keyboard (an example of how we can model even complicated activities such as typing on a keyboard, so modeling -cracking- passphrases could not be that complicated either).

I think this a race of mouse and cat.