A Really Good Article on How Easy it Is to Crack Passwords

Ars Technica gave three experts a 16,000-entry encrypted password file, and asked them to break them. The winner got 90% of them, the loser 62% -- in a few hours.

The list of "plains," as many crackers refer to deciphered hashes, contains the usual list of commonly used passcodes that are found in virtually every breach involving consumer websites. "123456," "1234567," and "password" are there, as is "letmein," "Destiny21," and "pizzapizza." Passwords of this ilk are hopelessly weak. Despite the additional tweaking, "p@$$word," "123456789j," "letmein1!," and "LETMEin3" are equally awful....

As big as the word lists that all three crackers in this article wielded -- close to 1 billion strong in the case of Gosney and Steube -- none of them contained "Coneyisland9/," "momof3g8kids," or the more than 10,000 other plains that were revealed with just a few hours of effort. So how did they do it? The short answer boils down to two variables: the website's unfortunate and irresponsible use of MD5 and the use of non-randomized passwords by the account holders.

The article goes on to explain how dictionary attacks work, how well they do, and the sorts of passwords they find.

Steube was able to crack "momof3g8kids" because he had "momof3g" in his 111 million dict and "8kids" in a smaller dict.

"The combinator attack got it! It's cool," he said. Then referring to the oft-cited xkcd comic, he added: "This is an answer to the batteryhorsestaple thing."

What was remarkable about all three cracking sessions were the types of plains that got revealed. They included passcodes such as "k1araj0hns0n," "Sh1a-labe0uf," "Apr!l221973," "Qbesancon321," "DG091101%," "@Yourmom69," "ilovetofunot," "windermere2313," "tmdmmj17," and "BandGeek2014." Also included in the list: "all of the lights" (yes, spaces are allowed on many sites), "i hate hackers," "allineedislove," "ilovemySister31," "iloveyousomuch," "Philippians4:13," "Philippians4:6-7," and "qeadzcwrsfxv1331." "gonefishing1125" was another password Steube saw appear on his computer screen. Seconds after it was cracked, he noted, "You won't ever find it using brute force."

Great reading, but nothing theoretically new. Ars Technica wrote about this last year, and Joe Bonneau wrote an excellent commentary.

Password cracking can be evaluated on two nearly independent axes: power (the ability to check a large number of guesses quickly and cheaply using optimized software, GPUs, FPGAs, and so on) and efficiency (the ability to generate large lists of candidate passwords accurately ranked by real-world likelihood using sophisticated models).

I wrote about this same thing back in 2007. The news in 2013, such as it is, is that this kind of thing is getting easier faster than people think. Pretty much anything that can be remembered can be cracked.

If you need to memorize a password, I still stand by the Schneier scheme from 2008:

So if you want your password to be hard to guess, you should choose something that this process will miss. My advice is to take a sentence and turn it into a password. Something like "This little piggy went to market" might become "tlpWENT2m". That nine-character password won't be in anyone's dictionary. Of course, don't use this one, because I've written about it. Choose your own sentence -- something personal.

Until this very moment, these passwords were still secure:

  • WIw7,mstmsritt... = When I was seven, my sister threw my stuffed rabbit in the toilet.
  • Wow...doestcst::amazon.cccooommm = Wow, does that couch smell terrible.
  • Ltime@go-inag~faaa! = Long time ago in a galaxy not far away at all.
  • uTVM,TPw55:utvm,tpwstillsecure = Until this very moment, these passwords were still secure.

You get the idea. Combine a personally memorable sentence, some personal memorable tricks to modify that sentence into a password, and create a long-length password.

Better, though, is to use random unmemorable alphanumeric passwords (with symbols, if the site will allow them), and a password manager like Password Safe to store them. (If anyone wants to port it to the Mac, iPhone, iPad, or Android, please contact me.) This article does a good job of explaining the same thing. David Pogue likes Dashlane, but doesn't know if it's secure.

In related news, Password Safe is a candidate for July's project-of-the-month on SourceForge. Please vote for it.

EDITED TO ADD (6/7): As a commenter noted, none of this is useful advice if the site puts artificial limits on your password.

EDITED TO ADD (6/14): Various ports of Password Safe. I know nothing about them, nor can I vouch for their security.

Analysis of the xkcd scheme.

Posted on June 7, 2013 at 6:41 AM • 127 Comments

Comments

JurgenJune 7, 2013 6:55 AM

Or just use a password/passphrase from a little-used language (Klingon is out, Old West Stellingwerfs as still spoken by literally only a handful old people, is in); will probably not be in any rainbow table...

Geordie StewartJune 7, 2013 7:01 AM

However...as we move to online services which can control the rate of password guessing attempts then complexity becomes less of a factor. Instead, predictability becomes the issue. 'Password1' is a somewhat complex password since it has uppercase, lowercase & numerals. The problem isn't a lack of complexity, it's the predictability of the combination.

Somewhere along the way, some seem to have confused complexity and predictability but they're not the same thing.

As a side note, why is it that we build systems that allow common complex passwords such as 'Password1' and then spend our time attempting to train every last user not to use those common combinations?

Kiyoshi AmanJune 7, 2013 7:07 AM

Actually, any software that purports to generate passwords for you and then stores them isn't much better than manually generating a derivative of any particular sentence (unless it stores them in a TPM). What you really want is a password hasher: something that takes a password, some site-specific salt (e.g. 'arstechnica.com'), and password-shaping parameters (e.g. alphanumeric, no special characters, 20 characters in length), and spits out a string for you to copy/paste. (PawHash for Chrome and Password Hasher for Firefox are good examples of this.)

The benefit here is that the user only needs to remember the master password and, if they switch browsers, the site-specific salt if it's not the default for the site they're logging into.

Victor EngmarkJune 7, 2013 7:11 AM

Password Safe looks interesting. How does it compare to for example the cross-platform KeePass/KeePassX?

Dr. I. Needtob AtheJune 7, 2013 7:29 AM

A smartphone version of Password Safe would be great, but if someone implements it, please make its .dat file compatible with the current PC version.

SimonJune 7, 2013 7:34 AM

Yeah, and then you need a different one for umpteen other sites along with the office network and banking UI's that demand a new password every 3 months. And if you own a business, double or triple the demands. One slip up and they'll hammer you on blogs like this for being stupid and not choosing a stronger password. How many freakin' "memorable" expressions can people cough up for crying out loud. And don't forget the providers who get hacked, like banks and social networking... 'oops, sorry, someone hacked our site and you should change your password right away. But don't complain because we're so big and couldn't care less whether you live or die.'

Carlo GrazianiJune 7, 2013 7:38 AM

If you are the sort of person who finds equations memorable, they are a good way to bring together small, non-word atoms with entropy from the top line of the keyboard. For example

du=Tds+(P/rho^2)drho

U+2ClF3->UF6+Cl2

and so on. There are tons from physics, math, chemistry, etc. The variable names can be nonstandard. Inequalities are just as memorable as equations. One can use an expression, rather than a full equation.

Of course it's still true that using the same one over and over is asking for trouble, so a password keeper is essential. I like keypass, which has clients for android and linux.

And, no, I don't use anything like the two examples above. You shouldn't either, now.

phred14June 7, 2013 7:41 AM

@Victor Engmark - There used to be a Linux port of Password Safe, but it has withered. There is an actively maintained version of KeePassX. But I too would be interested in hearing of the relative security of the two. I know I've seen reports of relatively subtle bugs in this kind of program in the past, so I know it's nothing simple to make secure.

LesJune 7, 2013 7:58 AM

The real threat here is that hackers will get access to the encrypted password file (or table, if the site is really a database).

Any site with info that's worth protecting should have multiple layers of security in front of that file. It's really not that hard to do: encrypted tablespaces, virtual private databases, split master keys to be entered by different employees, no external access to the database outside of specific applications.

The fundamental rules still apply: use different complex passwords for what matters (banks/financial institutions, email), and use throwaway passwords for everything else.

JJune 7, 2013 8:00 AM

@Kiyoshi Aman: I think you'll need to elaborate on why you think a password hasher is more secure than a password vault.

I noticed that PawHash claims:

This avoids having to use a password manager which stores all your passwords, meaning there is nothing for an attacker to steal,

but this honestly seems like a bit of a distraction, because having a copy of someone's encrypted password vault (without knowing the master password to open it) is just as secure as someone knowing that you use a particular password hasher without knowing the master password you use to generate your site-specific passwords.

A password vault also has the nice property that you can change the password on an individual site without having to change your master password or remember to not use the default parameters every time you log in to that site.

Clive RobinsonJune 7, 2013 8:07 AM

As Bruce notes with,

    The moral: pretty much anything getting easier faster than people think.

The problem with passwords is that seven pound lump of (omega rich) fats people have aproximately between their ears.

Humans are very very good at aproximate pattern recognition (such as knowing what's a cat and whats a dog) but realy very bad at precise remembering of charecter strings. Computers however are almost exactly opposit, and passwords were designed for computers not humans.

It is not suprising that the likes of Markov Chains and similar are making massive inroads into password attacking because they can be fairly easily used to mimic generalised human thinking, giving the computer a much better advantage than in previous times.

You often hear recomendations for the XCD Method but the reality is it's little better than using one word with upper/lower and punc marks.

To see why most humans actually have a very limited vocabulary and for a sentance to make sense and thus be memorable a lot of very very common connectives are used.

If you made up a frequency table of usage of English words you would see that,

    The Cat sat on the mat

Realy has a very low entropy. The first word "The " is such a common single sentance opener it falls in a list of about ten reasonable guesses. Which means that although effectivly four charecters long it has about the same entropy as the single charecters 'E' and 'T'...

That is most "words" in common sentance types have less entropy than single charecters in a random password.

Also unlike a random letter password where the individual charecters retain their entropy irrespective of where they appear in a password, the entropy of words in sentance decreases quite rapidly to just a couple or so bits after just a few words. For instance the number of object nouns that appear at the end of "The cat..." is a very small fraction of the hundred or so common object nouns in most peoples vocabulary. But changing the near certainty of "mat" to say "tap" makes the sentance a good deal less memorable (unless you happen to be a cat owner that has a favourate place such as on top of the DAT drive you use for backup).

Which is why Bruce emphersizes "personaly memorable".

Due to the memorable/entropy issue even long lines from common 'poems' songs, sayings, chants, prayers and even sentances from common books are fairly easily Brut-forceable, certainly more so than true random letter passwords even a fraction of the sentance length.

Thus my advice would be to use "Personaly Memorable" Passphrases for the likes of good quality "password safes" and use long random letter passwords for services. Where "random" means generated by either a True Random Number Generator (TRNG) or Crypto Secure Psudo Random Number Generator (CSPRNG) and "long" means 15 or more charecters long.

Because like it or not one thing we can say that is passwords have been with us for over half a century and they are unlikely to disappear in even half that time, if ever...

Eric RileyJune 7, 2013 8:24 AM

At work I have to change my password every three months, but fortunately for me I am actually reasonably able to memorize a random string of 10 characters after having to use it a dozen or so times (changing all of my passwords at the same time). So - I take my old password, advance each character by one place, shift left, and shift the upper case letter to the next letter to the right (everything wrapping around the edges).

I'm not *sure* that I would escape these attacks, but I really can't think of anything better to do (I did increase the length from 8 to 10, but I don't think I can make it much longer...

FPJune 7, 2013 8:26 AM

Password Gorilla (https://github.com/zdia/gorilla/wiki) uses the same database format as Password Safe and works cross-platform.

AlexJune 7, 2013 8:37 AM

I don't understand. I already use Password Safe on Windows, Mac (Password Gorilla) and Android (don't remember the name, will have to look it up again as it was deleted when I got upgraded to ICS).

Thomas StoneJune 7, 2013 8:43 AM

I use a modified xkcd idea. I go to a site such as passphra.se to get 4 random words. I then make up a sentence that contains all four words in the same order that they were given to me by the website.

As an example, I just went to passphra.se and it gave me "pile being kitchen remarkable". I then create a sentence that I can remember, such as "A pile of manure being in the kitchen is remarkable". I then use this sentence as my passphrase for passwordsafe.

I wish websites allowed for long passphrases such as the above. I've complained until I'm blue in the face about WellsFargo.com max 14, BankOfAmerica.com max 20, 401K.com (fidelity) 12. Unless you are using randomly generated strings, it is not possible to create passwords with reasonable entropy (> 2^^40), especially since many of these site prohibit the use of special characters. They claim that special characters aren't compatible with their phone apps.

Brian WintersJune 7, 2013 8:56 AM

I use pwSafe on Mac and iOS. It uses the same file format as Password Safe, and on iOS it supports storing on iCloud (syncs to Mac version) and Dropbox. I use Password Gorilla on Linux. (Which tells you which of iCloud or Dropbox I'm using most of the time.)

Obviously I'm putting A LOT of faith in my master password. Clearly the NSA can access all of my passwords, but since all of the services I use have a US presence, it isn't like the NSA would need to bother cracking my passwords.

And where I can (Google, Dropbox, PAM) I add in OATH-based two-factor authentication. (Not to be confused with OAuth.) Google Authenticator (the smartphone app) works for more services than just Google.

So my password file is at the mercy of (Dropbox security + my master password) or (my Dropbox password + OATH from my iPhone + my master password). I have multiple safes, so I can match the sensitivity of the password to the level of convenience in trying to type the relevant master password on a smartphone.

Personally, I think there comes a point where you have to say "good enough". Relatively speaking, how much effort would it be to hack into my always-on-the-internet desktop, and subvert it? Or break in to my house and install a keystroke-logger? Or…

Darryl DaughertyJune 7, 2013 9:01 AM

Append the website name to a memorable phrase:
"This is a memorable phrase schneier.com".

MD5 hash it and use the first 12 characters:
f214514e5b96

Looks random to the wider world, tough to brute, easily rebuilt if you need to, and never reused on multiple websites. And relatively immune to combo dictionary attacks unless you luck out with abadcafeabacabcd or something as equally improbable.

FionaJune 7, 2013 9:03 AM

I've been using KeePass for years and I'm very happy with it. For any important accounts, I can generate long, highly entropic strings of characters - I like to get up past 200 bits. It's really never been an inconvenience, even when I decide to change all my passwords every two months or so.

It really seems like the only viable way to maintain security into the near future.

jonJune 7, 2013 9:03 AM

foreign language passwords seem a good way to avoid dictionary attacks.

When I was seven, my sister threw my stuffed rabbit in the toilet.

into french and nobody will guess.

RogerJune 7, 2013 9:09 AM

I'm a little puzzled at the criticisms of the xkcd method.

The idea is simply that at any given level of entropy, a chain of several randomly chosen words is easier for a human to memorise than is a string of random characters. This is manifestly true.

It could be argued that Randall's example of 4 words is too short -- and indeed, for some applications, it is. However for a typical dictionary size, and genuinely random selection, it is massively stronger than "typical" passwords and in fact easily adequte to defeat the above-mentioned attacks.

In this case, by use of GPU cards to attack an unfortunately fast, unsalted, unstretched hashing algorithm, they are getting around 10 million trials per second. But a really well organised group might manage far more, let's say 1 billion trials per second. One dictionary file that I use contains 74,550 "common words": just over 16 bits per word. At 1 billion trials per second, a totally random selection of 4 words from that list would take around 500 years to crack, on average.

The issue with passphrases like "momof3g8kids" is not that they are chains of simple elements; it is that they have low overall entropy because the elements are not random (unrelated.)

DaveJune 7, 2013 9:14 AM

Bruce,

It's all very well coming up with these schemes and preaching to use a long password, but when your online service (and I'm looking at you, National Savings & Investments), limits your account password to 8 characters, it's all rather academic, isn't it.

bcsJune 7, 2013 9:25 AM

Password safe for Android:

https://play-next-dogfood.corp.google.com/store/apps/details?id=com.jefftharris.passwdsafe

I maintain there are 3 classes of passwords:

1: very well used passwords that you don't remember, but your fingers do
2: passwords you use rarely but need to remember
3: passwords you use rarely and don't need to remember

Type 1 should be totally random but easy to type and it's length measured by key presses (including shift).

Type 2 should be follow the advice in the above post, or XKCD's list of random works suggestion (with the length adjusted to the attempt rate of the threat environment; 8k word dictionary, 5 truly random words, 1G/sec ~> 1k year).

Type 3 should be totally random (dd if=/dev/random bs=256 count=1 2>/dev/null | base64) and saved in a password keeper secured by a type 1 or 2 password.

AndrewJune 7, 2013 9:30 AM

Is there any reason to not use Mac OS X's built in Keychain app? It will generate random passwords of any length, uses a single master password to encrypt everything else and is integrated with the OS so that any app that needs a password can let the user store it in the Keychain.

Sounds like it does everything you could want but I may have missed some big security flaw it has.

jay cJune 7, 2013 9:31 AM

Another type of secure password uses multiple languages, preferably words from less common languages. A password containing Numbers + Spaces + Symbols + Korean + Urdu is unlikely to appear in anyone's dictionary.

AlanTJune 7, 2013 9:55 AM

I suggest a browser Add-on that will take any password that you type, "process it", and then substitute the result of the process. The process could include XORing the password with a random number, and then hashing it to create as long a random password as the site will accept. When logging in at a later time, the same Add-on repeats the process. Very secure as long as the attacker cannot get at the Add-on directly.

CraigJune 7, 2013 10:14 AM

Darn, now I have to change my password! How did you know my sister threw my stuffed rabbit in the toilet when I was seven?

(just kidding)

NobodySpecialJune 7, 2013 10:16 AM

I just use "password" everywhere, nobody would guess anyone would be stupid enough to use that.

Scott RaunJune 7, 2013 10:19 AM

There's a PasswordSafe compatible app for IOS that stores the database in either iCloud or Dropbox. It costs $2.99.

The SourceForge project is also working a Linux version - as of 5/11, it's in beta, up to version 0.91.

I'm using the Windows version and an Android fork currently.

ChristopherJune 7, 2013 10:20 AM

1) I've been using PWSafe for years now. It has a basic Java implementation that I keep as a "break in case of emergency" tool but I am using it on Linux, Win32, and Android and have been for at least three years now. I have the database synchronized across all platforms, and it's a key tool for me.

2) The battery-horse-correct-staple proposal by xkcd always bothered me because it felt like a dictionary attack with combos would work. However, a two-word combo is much, much less secure than a four-word combo, even with a 20k vocabulary. I think four random words is still going to work, if and only if the number of letters also exceeded practical brute-force, i.e. a-tiny-word-list is 13 characters, not gonna cut it.

JonathanJune 7, 2013 10:37 AM

I have always used keyboard patters for passwords that are easy to remember and hard for a computer to guess. (eg. start at F, go up three, four to the left, etc...) I believe this provides sufficient entropy and I am unaware of any algorithms that target this type of password; does anyone here have any reason why this would not be sufficient?

Mrs. SJune 7, 2013 10:38 AM

I think the article made a point that initial caps are one of the common password schemes. Are passwords that don't use this set-up (as 3 of 4 of your examples do) a bit more secure, all else being equal?

Jordan BrownJune 7, 2013 10:44 AM

Some random thoughts...

Switching languages only adds bits; it doesn't do anything magical. ISO 639 is language codes, which seems like a reasonable source of a list of the world's languages. According to Wikipedia, ISO 639-1 (2-letter codes) has 184 entries; 639-2 (3-letter codes) has something like 450. That means that if you're *completely randomly* choosing between such common languages as Korean and Urdu, you're only adding about 7.5 bits per switch. If you start bringing in obscure languages like Votic, Tinglit, and Phoenician, you can take it up to 8.8 bits (but how big are the dictionaries you can get in those languages?). By way of comparison, adding two digits adds 6.6 bits, a lower-case letter and a digit adds 8, and two lower-case letters adds 9.5.

Web sites keep demanding "strong" passwords, measured by whether you use mixed case, digits, and punctuation. The improvement from moving a random 8-character password from lower-case letters (4.7 bits each, 37 bits total) to the full set of printable ASCII (6.5 each, 53 total) is less than the improvement from adding four lower-case letters (56 total). But which one do they consider "stronger"? Sigh.

Interesting question: which is safer, an encrypted "password safe" that malware will know to scoop up and attempt to crack, or a Microsoft Word document called "Proposal 57" containing a human-readable list of sites, usernames, and passwords?

bcsJune 7, 2013 10:59 AM

@Mrs. S: the title of the article include "qeadzcwrsfxv1331" which is a pattern.

Stephen CarpenterJune 7, 2013 11:08 AM

In a previous job, we employed the mnemonic method for root passwords. We made everyone submit a pgp public key, and then would encrypt a file to everyone with the password + mnemonic. I have not worked there in almost a decade now, and I can still remember a few fragments.

...and of the chuckles when a co-worker rather innocently used "420" as the substitution for "four score and 20" (we had to explain it to her)

I still use that for passwords that I need to remember, that or my own riff on the xkcd method.... but that is mainly for remembering the passphrase to the password vault.

dimitrisJune 7, 2013 11:17 AM

I'm converging to having all my (random, long, absolutely non-memorable) passwords managed by a couple of "password safe" types of apps: Firefox master password and Gnome wallet/KWallet. These are soon going to be consolidated down to just KWallet.

These wallet-unlocking passphrases plus a full-disk-encryption passphrase are generated using diceware. They contain sufficient entropy and can be easily remembered (I think of them as bad surrealistic poetry).

TreeJune 7, 2013 11:48 AM

@ Jonathan

The number of passwords that can generate is bounded by keys * 6^(length), which isn't particularly large, and that assumes you include up-left and up-right (and the equivalent for down). It's much smaller if you only have up, down, left, right.

VladanJune 7, 2013 11:55 AM

The best idea of choosing a password is to take some foreign language world(s). For example I currently speak 3 languages, so for me is not a problem.

For people who don't speak several languages, they can still leverage google translate... -:)


Andrew YeomansJune 7, 2013 12:00 PM

As Les says, the real threat is that the hash database is captured.

So why doesn't the IT industry use dedicated HSM devices for password hash storage and verification?

Within a reasonably-guarded data centre, there arguably would not even be the need for a full HSM, just a well-designed and hardened system designed just for this function, with no way to extract passwords (or hashes) except physical attack.

ChrisJune 7, 2013 12:55 PM

I too find the criticism of "correct battery horse staple" misplaced. Firstly he's only squaring the search space of his dictionary, using four words instead of two is the square of that difficulty. But more importantly, this was a stolen hash attack on a braindead storage method. Randall states up front that he's not trying to protect against matching on a stolen hash. If you really need to be protected against attacks on a stolen hash on a website with unknown storage methods I would recommend you use a unique totally random password and pray they didn't store it in plaintext or reversible. The best password in the world could be recovered from a reversible storage method, but he couldn't have cracked that password if they had used md5crypt instead of md5.

Nick PJune 7, 2013 12:59 PM

@ Andrew Yeomans

HSM's are expensive, inflexible and hard to scale. I've told people to use them in certain high risk intranet type settings. As for dedicated device for authentication, that has been a good idea as far back as people using Kerberos and putting it on its own server. (I used a hardened OpenBSD for security-centric server, for instance.)

I think one complication is that many are web systems. If it was just client server (messages over TCP/UDP), that would be one thing. However, the "web" way seems to add a bazillion lines of code and plenty complexity to the TCB of such solutions. In past designs, I put the authentication system on a hardened system with every execution safeguard possible and a web front end translated the messages to/from simple formats. So, the authentication machine was very simple and had less risk of compromise.

Good luck getting companies using typical web stacks to do that sort of thing. The developers and management will gripe too much.

SMJune 7, 2013 1:32 PM

Clive, I think that you are criticizing something other than the "horse battery staple"/"n random words" system. Under that system, one picks words by flipping through a dictionary and poking blind, then -invents a story- to make those random words meaningful. This combines true randomness and the ability of human brains to invent meaning for random noise. Using a grammatical phrase for the password is a different system.

hairlesshackerJune 7, 2013 1:38 PM

Seems like another attempt to scare the public...
I understand that users need strong passwords. But the use of MD5 is the real issue here, not the use of weak passwords.
Let's try SHA-1 with a changing salt.. Or pbkdf2.

And this also assumes that an entire list of hashed credentials is compromised. They try to make it sound like they can break into your bank, which hopefully only allows a limited amount of guesses before locking them out.

MeJune 7, 2013 1:39 PM

@Andrew

The only reason I can think of is that it is not open source, and thus you would be ignorant of any security flaw it may have.

If that is not important to you, go ahead, as for me an my family, we will use KeyPass 2.

boogJune 7, 2013 1:40 PM

Here's my method of devising passwords:

1. Generate a bunch of random uppercase/lowercase letters, numbers, and symbols.

2. Commit them to muscle memory.

Hasn't steered me wrong yet. Except when I lock myself out after mistyping it 3 times. Damn the 3 strikes rule!

NoxonomusJune 7, 2013 2:02 PM

Here like so many other places I see people suggesting the use of foreign languages, which bothers me for several reasons. Partly because its no more difficult to use multiple language dictionaries than multiple password dictionaries in an attack. Further there is no reason to think the password dictionaries aren't global so unless you think your Hindi word choice is better than that of an Indian users and your English alternative what's the point.
I also find it particularly ironic given how often foreign hackers are in the news.

anonJune 7, 2013 2:21 PM

pwSafe on the mac and apple mobile devices is -- eh, -- okay... but I was surprised the author was able to charge for something that is available for free in the windows platform. Also, it lacks the ability to merge safes. The icloud safes are not a bad idea, except if the safe is deleted from any device, it's no longer available to the other devices.... I'd prefer the idea of a master safe with slave synchronization to a single safe accessible from other devices.

PWSafe on mac/mobile also lacks the ability to auto-type the values from the safe into an application or browser form. That makes it a wee bit harder to use than the windows counterpart.

Nosey ParkerJune 7, 2013 2:23 PM

grc.com has a password generator, and also claims that strings such as ten commas, nine periods, four question marks, and on and on, as long as you like but can remember, can make for good passwords, virtually impossible to crack.

How likely is this kind of password creation tool likely to be cracked (the string of letters or odd characters) compared to other tools. I can easily remember 9 parentheses, fourteen @ signs, and on and on, in various combinations. Does duplicating a character make it easier to crack the password?

KWHJune 7, 2013 2:26 PM

The combinator attack got a password made of two pieces in its dictionary, but is that really a solution to the "CorrectHorseBatteryStapler" type password with four words?

For words of [4567] letters, /usr/share/dict/web2 has 5110, 9987, 17477, 23734 words listed. Choosing one of each in order by length would give over 1e20 possibilities, and if you didn't know what order the words were placed in that would give 2e21 possibilities. I wouldn't think that was a tractable search space; are computers really powerful enough that 2e21 possibilities can be reasonably tested?

AlexJune 7, 2013 2:32 PM

I don't know that complexity/entropy of the individual password itself is the real issue here.

First, let's look at the "attack" -- the password file was obtained. Priority #1) Keep the bad guys from getting near the password file. I've often pondered a system where the hashes were stored on a separate system. Without direct access to a password file, life becomes much more difficult for an intruder.

Similarly, most password databases store the username & pw hash in the same record. Why not two DBs/files? One containing a list of usernames and record of the line# (preferably random-ish) of where the matching hash should be found in the password db? Even if someone got ahold of one or the other (but not both), they'd have a fun time trying to figure out how to match up the entries. Hopefully it'd give enough time for a proper intrusion detection system to trigger.

Also, why not do some sequential encryption? CPU cycles are cheap. Most of my company's network runs over a WWAN. All of those links have multiple sequential encryption w/different ciphers running on them. I figure if someone manages to get past the outer encryption cipher, they'll look at the stream and realize there's more work to do. My goal is to put enough barriers in place to deter most hacker types, and at least give our IDS time to recognize and block and alert. For fun we also run a stream of useless traffic with only 1 layer of encryption running, hoping that'll keep someone busy for awhile. This traffic also helps us keep track of the networks' performance.

What is indeed scary about this article is the relatively cheap rig they were using. Single off-the-shelf computer w/graphics card. Not a supercomputer, not a cluster, not a grid. Just a single workstation.

Dr. I. Needtob AtheJune 7, 2013 3:15 PM

I found two Android applications named "Password Safe" in the Google Play Store. One is free and the other costs $2.99. Neither appears to be related in any way to the original Password Safe program that Bruce Schneier mentions above.

What I'd like to see is the real Password Safe made available for Android, not a program from some amateur who didn't even know enough about computer security or cryptography to know that the name was already taken!

SomebodyJune 7, 2013 4:07 PM

Why do people discuss passwords without mentioning entropy?

The following passwords were all generated using the same random number but different transformation rules and are therefore equally strong (or weak). Arguments that one is stronger or weaker than the others are garbage. The user should be able to pick which one is easier to remember and/or type. People who do not understand this have no business designing systems.

1907131024473210 -- decimal integer
77FC408B8C6 -- Hex integer
wkX6qHD9 -- base 96
mario buss foyer inn -- diceware

Hugh NoJune 7, 2013 4:39 PM

As has been mentioned a couple of times here, in general passwords don't need to be complex, just unguessable in a few guesses.

Usually if someone can get to the password file then they can get to the user accounts as well. Having a complicated password is no help against that. Not using that password elsewhere is what's important in that scenario.

The attack you would then worry about is someone guessing your password through the standard interface, which should limit the number of attempts to a small number. So you just need a password that can't be guessed in a small number of attempts. This is much easier to create and remember.

Of course, this does not apply to administrator, and similar, accounts which often don't have limits on password attempts (to avoid being locked out). Stronger controls which include stronger passwords are needed for these accounts.

Steve FriedlJune 7, 2013 5:08 PM

This is the first time I've heard of MD5 and SHA1 being "irresponsible" for use in hashing passwords; how long has this been the norm?

Patrick TJune 7, 2013 6:15 PM

Here is an interesting look at Randall's cartoon.

And this article offers a good look at entropy.

Also, another password manager I'm surprised hasn't yet been mentioned is LastPass. It's actually quite convenient for online account credentials. Obviously the main concern is in confirming it's client-side encryption and making sure it's doing what it claims it's doing.

One suggestion is to use the Non-binary Chrome, Firefox, Opera, or Safari extension, which is 100% JavaScript, and use network sniffing with a proxy to see that the sensitive data is encrypted before being sent.


@Victor Engmark
Password Safe was obviously the inspiration for KeePass. The latter has gotten quite popular, and added a few more bells and whistles, although it does a have a few limitations as well. You don't get the option of a nested tree view as with Password Safe, and the latest versions require .NET, and they attempt to auto update.

If you're really interested, I would download both and see which you like better.


@Brian Winters
"Clearly the NSA can access all of my passwords"...

Are you suggesting the agency has cracked Bruce's algorithm?


@Roger
"..they are getting around 10 million trials per second. But a really well organised group might manage far more, let's say 1 billion trials per second."

Try 350 Billion/second.


@everyone looking for ports of Password Safe

The official site lists several fork projects:

http://pwsafe.org/relatedprojects.shtml

JasonJune 7, 2013 7:14 PM

Would sure be nice if people/places would get beyond MD5 already. SHA2-256 should be the min imo. And since it seems an awful lot skipped that, there should be a push to go to SHA3 now.

RogerJune 7, 2013 8:26 PM

@Steve Friedl:
The necessity of "salting" has been understood since the 1970s at least -- yet we still see systems with unsalted hashes.

The concept of "stretching" also occurred in the 1970s era Unix crypt, but it wasn't widely recognised as a general principle until the 1997 paper by Kelsey, Hall, Wagner and our own dear Schneier.

The specific fact that unadorned MD5 was thoroughly unsuitable, and should be avoided in new systems and phased out in old ones, has been widely advertised since around 1999.

GodelJune 7, 2013 9:19 PM

Those using Keepass with Firefox should also look at the Keefox add-on. It provides an additional autofill capability -- works about 80% of the time.

I tried Dashlane briefly and didn't like it. At one stage Zemana anti-logger reported something was trying to take a snapshot of my desktop, and I suspected Dashlane was responsible. It also left behind an incredible amount of junk when I uninstalled it, as reported by Revo Uninstaller Pro.

The requirement for web sites to use proper password hashing is the missing factor. If the web site in the Ars Technica article had used a properly salted bCrypt sCrypt or PBKDF2, there probably wouldn't have been an article.

RogerJune 7, 2013 9:20 PM

@Patrick T:
Try 3501 Billion/second.

Of course I realise that you can go much faster if the opponent pours money at the problem, e.g. if you attract the focussed attention of a national intelliugence agency. However, the machine to which you linked looks like it could be built for under $3k. Very interesting, price / performance has certainly come down lately more than I realised. Thanks for the pointer.

Still, even that machine is not practical2 for attacking a 4 word xkcd3 style password -- and I only use 4 word ones for medium-grade accounts.

___
1. Strictly, 350 billion was the super-weak NTLM hash. Plain MD5 it was doing at 180 billion/s. Of course in "guesstimating" password security, a factor of 2 is much less than your margin of error. I note with a smirk that bcrypt choked it back to a mere 71,000/s.
2. With all the usual caveats about dictionary size, proper randomness and so on, I calculate about 2.7 years mean cracking time, if this $3k machine was dedicated 24 hours a day to attacking not just me personally, but just one of my accounts. Not quite a sufficient margin of safety for my 3 most valuable accounts -- but those all use much stronger passwords.
3. Strictly speaking, of course, Randall didn't invent this, not by a long shot. But he seems to be associated in common discourse.

Joseph ArpaiaJune 7, 2013 10:27 PM

A problem is that the process going from the password to the hash is standard. So the hacker can try numerous passwords from a dictionary knowing that each password will have a unique hash associated with it.

A solution in addition to salting the hash is to have a random number of encryption cycles associated with each password. This number can be stored in the database. The program can use a function of that number to determine the number of encryption cycles. Then the hacker would need access to the site code to determine how many encryption cycles were being used to create the hash.

Nick PJune 7, 2013 11:50 PM

@ Roger and Patrick T

Just goes to show that the inherently slow algorithms I've espoused are (and were) the best bet. Scrypt is the best one I've heard of. I think an even better one is possible for situations where speed of authentication is less important than security. I vaguely imagine a randomly generated chain of ciphers with many individual ciphers to choose from. The number, possibilities and loops from input (password, key, nonces, etc) to output (auth code) makes the use of these ultra high performance fixed type designs impossible.

Will this be realized or even needed? We shall see.

SueJune 8, 2013 7:43 AM

And as soon as a pwd manager (as Password Safe) is used, there's another full slew of attacks possible (especially on net connected devices like iphones or android phones)

AlonJune 8, 2013 11:36 AM

I wonder if any of the password managers has tried to collect a list of website-specific password limits, in order to generate passwords that will fit the sites' password policies?


(Even better would be if the sites could somehow publish their password policies... Probably a pipe dream for now)

TomJune 8, 2013 2:05 PM

If someone has your password file, there's no need to crack it. They already have access to your system and your data. It's like worrying if someone will find your house keys after they've already broken into your house.

If they're trying to crack passwords through a web login form, there should be a try limit per IP address. If you can't guess it in 3-5 tries, you're blocked. Almost insanely weak passwords will be pretty safe if you only get a handful of guesses, even with a distributed attack.

Using the xkcd word string method is made a lot better through the addition of random capiTalizAtion and s¥mB01 replacement. These aren't too hard for humans to remember, but would require a massive database to include such variations in a dictionary.

BillJune 8, 2013 2:15 PM

Would running the windows version of password safe under wine on linux be secure. (Let's just say, I really hope so.)

Patrick TJune 8, 2013 4:20 PM

@roger
Good points. Ironically, the Ars article profiling that GPU cluster was actually linked on the second page of the article in the OP (I just hadn't gotten to that page yet ;)) (And on another side note, in that article they actually give a shoutout/recommendation of Password Safe.)

I would be interested to know how such a cluster would fare against PBKDF2, as that seems to be the more popular of the "secure" functions, being incorporated by both Password Safe and LastPass, as well as several encryption programs including TrueCrypt and LUKS, and even everyday use areas such as WPA, OS X, and iOS.

Pertaining to your recent comments about salting, something else the OP article mentions is how (a) salting "only slows down cracking only by a multiple of the number of unique salts in a given list. That means the benefit of salting diminishes with each cracked hash"...and

(b) what's more, "salting does nothing to slow down the cracking of a single hash and does little to slow down attacks on small numbers of hashes."


@Tom
What sort of nonsense is that?...

1) What if I want to keep a backup list of all my login credentials offsite somewhere in case my hard drive fails? An encrypted password database stored in cloud backup is perfect for this. There are plenty of scenarios in which an attacker might gain access to cloud storage, and therefore "have my password file" and NOT access to my system and data.

2) Even supposing someone has physical access to my machine...that doesn't necessarily mean they have access to all my online accounts. The vast majority of attackers aren't going to be of the sophisticated ilk installing keyloggers and such. Having your passwords stored in an encrypted database is much more secure than a plaintext Excel document, and here again "having access to my password file" does NOT automatically mean access to my data that is protected by those passwords (i.e. online accounts, which account for the vast majority of the passwords any given person uses.)


@alon
"I wonder if any of the password managers has tried to collect a list of website-specific password limits, in order to generate passwords that will fit the sites' password policies?

(Even better would be if the sites could somehow publish their password policies... Probably a pipe dream for now)"

Umm...a pipe dream for crackers maybe. Did you not read the article? That's one of the first things they'd do is go try to determine what the password policy of a site is so they can set their rules to that and not waste time with guess outside of it. Learning the policy cuts a cracker's work time down considerably (especially if it's a lax policy).

And password managers do tend to allow you to set parameters for password generation (they just don't do it for you, obviously.) Password Safe gives this option, LastPass gives this option...heck, LastPass even has web app generator...

https://lastpass.com/generate

BenJune 8, 2013 8:59 PM

A question that has always bugged me: why can't websites help us keep our passwords secure by putting limits on the number of times you can guess a wrong password? It doesn't have to be a "three strikes you're out" thing, but maybe a "ten strikes, you need to wait 2 hours before trying again." Wouldn't that greatly inhibit the ability of these crackers to run through the millions of wrong guesses before they find the right one?

Nick PJune 8, 2013 9:37 PM

@ Ben

" It doesn't have to be a "three strikes you're out" thing, but maybe a "ten strikes, you need to wait 2 hours before trying again." "

I'm lacking the link to it right now but I remember a scheme similar to that. The first try or two had no wait. After that, the mandatory wait time after each try got longer and longer. Maybe a second at first. Then 3-5 on next try. And so on. It would barely be a noticeable wait to most legitimate users yet it would vastly slow down automated attacks was the idea.

AlanTJune 8, 2013 10:42 PM

What if you ask for a zip code with the password? The site then hashes both values together. Would that work?

FigureitoutJune 9, 2013 12:41 AM

AlanT
--A random zip code aka random 5-9 digit number? Or the one you live in? If so, that's not a secure piece of info (how many places have you written your zip code next to your name); but gas stations use that for authentication for credit cards...

JardaJune 9, 2013 3:10 AM

Better than Password Safe is KeePassX. Password Safe runs only on Windoze if I recall correctly. KeePassX runs on Linux too and I think even on Mac.

WaelJune 9, 2013 11:46 AM

For password choices, I have previously used a password that contained pieR^3! which was derived from the area of a circle; 𝜋r2. I changed the 2 to a 3 for camouflage, and put an exclamation mark at the end to denote the error. So I was subconsciously aware of recurring pattern weaknesses of having special characters appended or prepended to the passphrase, as the article mentions. This formula was unfortunately so ingrained in my mind, that as a consequence, during an exam, I calculated the area of a circle to be 𝜋r3, and I subsequently changed my password...
Nothing new as Bruce has mentioned. However, I do have some remarks to share about the conducted experiment:

  • passwd file was made available to the attacker -- obtaining a passwd file is not necessarily an easy task on some well protected systems
  • Experiment slightly ignored common defense mechanisms (don't apply for offline attacks):
    • Anti-thrashing, or anti dictionary attack mechanisms, such as progressive delays with each failed password attempt
    • Account lockout after reaching a preset failure threshold count
The experiment also shows that it's essential to protect the passwd file. There are (is) more than one way to do that. I would bind the passwd file to the platform it resides on as a first line of defense. The passwd file itself would be encrypted with a HW protected key. This way, even if the attacker were able to gain access and copy the passwd file for an offline attack, s/he would have to decrypt it first. A second enhancement would utilize a TPM (yup, TPM again) for trusted boot -- something that was discussed on this forum briefly. I am also aware of other efforts to utilize GPUs for protection (mainly encryption and hashing) of information -- Fight fire with fire, eh? GPU's have many cores compared to General Purpose CPUs, although the "core concept" is different -- so we are not comparing apple to apple. But GPU's excel at running hundreds of threads, preferably tens of thousands of threads... Which can be utilized for parallel computing to accomplish tasks that would take General Purpose CPU's a significantly longer time.

Worth mentioning that utilizing parallel processing, of a GPU for implementing encryption algorithms has been going on for a while, for example nvidia Developer Zone. Most of crypto algorithm implementations, however, are serial in nature. Algorithms will have to change to allow parallel processing and OpenCL to utilize -- more research needs to be done in this area... As far as I know, currently, some portions of encryption algorithms can be parallelized, and others can not benefit from parallization of processing.

Bruce SchneierJune 9, 2013 5:27 PM

"As I mentioned earlier, there are already ports of Password Safe for other OSs..."

I know nothing about those ports, nor can I vouch for their security.

Patrick TJune 9, 2013 7:32 PM

Important point, Bruce. I'm glad you came in to personally voice that, because the fact that they are listed on the official Password Safe site does offer the possibility of a misunderstanding.

(I notice the page does state "I have not tested these personally", but it could be quite easily for someone to miss that, or to assume it simply means "not tested for stability".)

MariusJune 10, 2013 1:05 AM

So the ports of Password Safe are possibly not safe to use? How do we know they are not safe? Just becase Bruce haven't verified their source code?

I think we at some point just have to trust someone else with our personal data. The alternative is using a notebook and keep it in my back pocket at all times...

FigureitoutJune 10, 2013 2:46 AM

Marius
--Duh, everything is possibly not safe; we make jokes how Bruce can carry out impossible feats, but if you've read his books or his blog even he makes errors like everyone else.

Trust is tricky, and I actually prefer keeping my PW's spread out; remember wipe impressionable surfaces (I've made that mistake) and stay the hell away from Apollo Robbins.

RyanJune 10, 2013 5:58 AM

It's clear that 'something you know' isn't good enough for this type of authentication. ANY scheme you come up with is not going to be perfect.

We have to rely on 'something you have'. In this discussion the thing you 'have' is a password database. It could also be cell phone with google authenticator (time based password).

ToolburnJune 10, 2013 6:42 AM

Take a look at Lastpass. I have a 100 plus sites saved. Have no idea what the password is for them, never have to look. I also take advantage of the YubiKey integration for 2 factor access.

Phill Hallam-BakerJune 10, 2013 7:20 AM

I wish Bruce had given more than a throw-away comment on MD5 being a bad choice. The problem isn't the algorithm, its the architecture.

World readable password files are bad. People had a long argument about that in 1990 and the result was that we now use shadow password files. Until crack appeared people would argue at great length that setting the password file to world readable increased security.

This is a brute force attack without the use of rainbow tables or other precomputed data. So salting the password file has absolutely no effect because a salt is made public by definition. Changing to SHA-1 would have almost no effect as the only impact on the process is speed of execution. Some of the new algorithms might actually be worse being more efficient. If folk have a way to use the new graphics hardware that comes with ~3000 processors per card they can improve processing speed by 3 orders of magnitude which is equivalent to 11.5 bits. Which kills half the leverage of Randall's scheme.

So really the only way to improve the password file security is to encrypt the password file entries under a strong key. Then you have to work out how to store the key on the machine which is actually pretty hard. That is the sort of application that trustworthy computing would be good for.

SomebodyJune 10, 2013 11:47 AM

"Randall's scheme" is not a way of providing entropy. It is way of making it easy for humans to remember entropy. If you need 51 bits then four words will do, if you need a 100 bits you'll need an 8 word list. But in any case the contention is that the words are easier to remember than the same entropy expressed as random bytes.

A lot of people who don't understand this seem dead set on passing a reverse Turing test (I.e. proving they are not human.)

FigureitoutJune 10, 2013 12:27 PM

Somebody
--Lol, yeah I only want to know numbers like 3.14159, 2.71828, 6.626E-34, 6.02E23 if they have meaning and practical use. Passphrases make it easier, plus make a rhyme to it (in your head of course!), but "word glue" may be a hole. Hopefully it never gets so stupid we have to recall a whole story as a password.

Hugh NoJune 10, 2013 4:11 PM

@Patrick T said "There are plenty of scenarios in which an attacker might ..."have my password file" and NOT access to my system and data."

Tom and I are referring to a password file on a server, not a personal file. If someone can get to the password file on a server, then they probably have some kind of administrative access to that file (through whatever method) which implies admin access to the accounts on that server.

If someone has admin access to your account on a particular system, then it doesn't matter how strong your password is. So make sure it's not easily guessed but in general you don't have to make it super strong. And don't use that password on any other system in case it does get cracked.

Patrick TJune 10, 2013 8:41 PM

@Marius
So the ports of Password Safe are possibly not safe to use? How do we know they are not safe? Just becase Bruce haven't verified their source code?

Seriously? Who said they weren't safe? Please show me where anyone said that.


@Phill Hallam-Baker
"the only way to improve the password file security is to encrypt the password file entries under a strong key"

It depends on what you mean by "strong key." The way you talk about MD5 it sounds like you're saying all encryption schemes are created equal...that any cipher is just as good as another, and that any key derivation function is just as good as any other...but obviously that's not the case.

MD5 is a bad choice for security implementations because it's not collision resistant. Carnegie Mellon SEI said it "should be considered cryptographically broken and unsuitable for further use".


@Hugh No
If there's no need to crack password files, why does anyone bother encrypting them? And why do so many people spend time and computing power trying to crack them? And why do so many people expend effort writing software and compiling dictionaries and devising methods of cracking them?

You're saying the whole world of IT is so dumb that they don't see something that is so obvious to you and Tom?

JonadabJune 11, 2013 8:05 AM

Darryl Daugherty says:
> MD5 hash it and use the first
> 12 characters: f214514e5b96

I just want to point out that the entropy here is only log(16^12), or about 33 (using e as the base; which base you use for these calculations is largely immaterial, as long as you're consistent). By comparison, a traditional random mixed-alphanumeric password reaches a comparable entropy at only eight characters long: log(62^8). We've known for a while that, computing power being what it is these days, an 8-character mixed alphanumeric password is weak (except in rate-limited scenarios, which are clearly not what we're talking about here).

These attacks are compromising passwords like ilovetofunot, which would have an entropy of 39 if cracked via brute force and about the same entropy using a single dictionary that includes the word "tofu" but contains only twenty thousand words (which is rather unlikely; I suspect any dictionary with "tofu" in it that's not specifically limited to food or Japanese culture will have significantly more than twenty thousand entries). I suspect the technique actually used involved one large dictionary, from which only one word was selected, and a much smaller dictionary (Bauman's General Service List, with only 2000 entries, would be adequate) from which multiple additional words were selected. That would yield an entropy number of somewhere around log(dictsize * 2000^3). If tofu came from a dictionary the same size as my system's spelling dictionary (/usr/share/dict/words on squeeze), that comes to 34 -- more entropy than your twelve hex characters.

If you take the same MD5 hash and instead of hexadecimal notation express it in base64 and use the first 12 characters of that, it raises your entropy from 33 to almost 50. That's somewhat better.

But what you really want is to use more than 12 characters.

Incidentally, can anyone explain "qeadzcwrsfxv1331."? I'm seeing log(26^12*10^4*p), where p is some small number of common punctuation characters. Even ignoring p altogether, that comes to at least 48 by my reckoning. Is "qeadzcwrsfxv" some kind of cultural reference I'm missing that would cause it to show up on more password element lists than other strings of twelve letters? Or are they really cracking things with that much entropy (48+, using e as the base) already?

RogerJune 11, 2013 8:10 AM

@Patrick T:
What they say about salting is quite true: most of those benefits are minor (but cheap, so still worthwhile.) However the main purpose of salting is to stop precomputation attacks (e.g. rainbow tables), and for that purpose even a modest amount of salt pretty much stops the attack dead.

@Hugh No, Tom and others:
Historically there have been many attacks in which a supposedly hidden password file was obtained, without completely rooting the server. It is a particularly common problem for web applications -- which in practice, today, are at least as important as host security. Typically these run an unprivileged account with an authentication system that is completely independent of the host OS. (Quite commonly, the web application is owned and operated by a completely different company to the server, and its administrators are not allowed root access even if they want it.)

In this scenario it is distressingly common to find application security flaws that enable a clever attacker to get a dump of the (hopefully hashed) password table even whilst operating as an unprivileged guest. The most common method for this is SQL injection but it is by no means the only method.

You may well say "Oh, my web application will not have such flaws, so it is irrelevant to me"; if so, then you are exactly the sort of bloody fool that causes these problems in the first place, and I would kindly ask you to either wise up or seek another career.

The rest of us say "do not underestimate the power of the dark side", then use shadowed password files, lock down the server, educate the users about password security, and hash the passwords with bcrypt, scrypt or their ilk. (And firewalls, and IDS, and a disaster recovery policy, and ...)

RogerJune 11, 2013 8:15 AM

@Jonadab:

`Incidentally, can anyone explain "qeadzcwrsfxv1331."?'

It's a finger pattern. Slightly more complicated than "qwertyuiopas", but not by much. Try typing it out with two fingers, alternating letters between left and right hands.

Certainly a lot less than 48 bits.

JonathanJune 11, 2013 10:18 AM

@Tree

Thank you, when you express it mathamatically like that you can really see how the keyspace is limited.

@Sam

These are great articles, thanks!

JonadabJune 12, 2013 7:21 AM

> It could be argued that [correct horse
> battery staple] is too short... However
> for a typical dictionary size, and genuinely
> random selection, it is massively stronger
> than "typical" passwords and in fact easily
> adequte to defeat the above-mentioned
> attacks.

Well, clearly, correct-horse-battery-staple has more entropy than any of the ones on the list of "plains" in the article. On the one hand, none of the words in it are unusual, so a dictionary on the small side of medium sized would contain all of them. On the other hand, zero of the four words would be in the sort of really small secondary dictionary that presumably enabled them to crack things like ilovetofunot in reasonable time. In fact, the four words in the xkcd example are of roughly equal frequency. As I think about it, this is instructive. Attackers clearly have caught onto the fact that many people are throwing *one* complex element into an otherwise bland password and expecting that to protect them by increasing the complexity of the whole thing. So the attackers are now using an approach that combines large and small dictionaries (plus automated variations). Consequently, adding a short truly random segment to a long but computationally simple password ("UwillnotguessY3Hx") is no longer secure. You may as well make your whole password equally complex.

That's a meaningful take-home point, because I've been using the combination method myself.

My passwords have been more complex than the sample broken ones, because my simple elements were medium-frequency dictionary words, and my complex elements were things you won't find in any normal-size dictionary, yielding passwords along the lines of priolaptic-indigenous-marquee, frenetic-preauriculoid-grunge, or concussive-virlomi-ace-lymphocite. (These specific examples, of course, are not ones I have used; they are merely constructed in the same way.)

Nonetheless, this article has caused me to revise downward my estimation of how difficult my passwords are to crack, and I am considering altering my policy to increase their complexity somewhat going forward. Perhaps none of the elements should be anything you could find in a medium-sized dictionary. Also, perhaps I should stop using three-element passwords and always use at least four elements -- five for passwords that need to be especially secure.

I'm currently still ahead of where these particular crackers are, but I'd like to *stay* ahead of them, and I'm not as far ahead of them as I thought I was. They'll be continuing to make further progress. When they do, I don't want them to catch me out. Also, there may already be other crackers who are doing better than the ones in the article. As a properly paranoid system administrator, I have to assume there are crackers out there who can compromise passwords like valid-zebra-collection-affix, and I have to make sure my passwords are more secure than that -- preferably without being impossible-to-remember line noise.

JonadabJune 12, 2013 7:36 AM

> which is safer, an encrypted "password
> safe" that malware will know to ... crack,
> or a Microsoft Word document called
> "Proposal 57" containing a human-readable

I'd say that depends on the encryption (and on the key used for it).

Personally, I use physical paper and avoid storing important passwords on any computer. This has downsides as well, but the upshot is that a remote computer security breach won't compromise other systems unless they install a keylogger. In my particular case (living in a small city), I judge my physical environment to be much more secure than any computer connected to the internet. YMMV.

I do email myself copies of unimportant passwords, e.g., ones I use to leave comments on various blogs and whatnot. I also use significantly less secure passwords in those cases, compared to anything that actually matters.

SomebodyJune 12, 2013 9:10 AM

Jonedad:

You may want to look up "diceware". It formalises many of the issues you raise. By specifying a way of selecting entropy (by rolling dice) and mapping the entropy into passwords (by using a particular 7776 word dictionary) it allows exact calculations. Like good cryptography, diceware assumes the opponent knows your algorithm (dictionary) and keeps you secure anyway.

http://world.std.com/~reinhold/dicewarefaq.html#howlong

NooneJune 13, 2013 3:51 AM

I tend to use a PGP key encrypted plaintext file for my password storage. And most of my strong passwords tend to be above 20 chars but still easy to remember.

JamesJune 13, 2013 5:16 AM

Someone pls. explain me in layman's terms if the standard Diceware method is still safe now or for the coming 10-20 years - if yes; why? I am not that much of a technical person. Thanks.

crypto-ninjaJune 13, 2013 8:15 AM

diceware can be used, I suggest using it with at least 8 words, then it is safe for the next 200 years from all cracking-attempts from planet earth. But it is not safe if the alien-mothership comes along and cracks your password in one second with his quantumcomputer (which gets its energy from a black hole and antimatter) LOL

crypto-ninjaJune 13, 2013 10:56 AM

I recalculated it, you need at least 10 diceware-words to be on the really secure side for the next 50 years or so. I used diceware before, but since 3 years I use Keepass, which I can recommend.

Clive RobinsonJune 13, 2013 1:08 PM

@ Crypto-Ninja

I'm not sure what your security margin is but I tend to favour 2^128 equivalent,

Which if I remember correctly 50 throws of the perfect dice is just over 128 bit equivalent.

SomebodyJune 13, 2013 4:23 PM

Keepass and diceware are not mutually exclusive. Password managers need a master password, which you have to remember. I use Diceware for my master password.

If I tried to remember a couple of dozen rarely used Diceware passwords they would start to get muddled and I'd have to write a program to try various combinations of the 100 or so words involved.

crypto-ninjaJune 13, 2013 7:32 PM

I have written that you need 10 diceware-words, makes 5 throws per word, so 5x10=50 throws, yes. In my calculation, you have 12,9 bit per word of entropy and with 10 words, thats 129 bits entropy. Only the alien mothership can crack that :-)
That is a good idea, to use at least an easy-to-remember diceware-master-password for keepass or passwordsafe. There you can save your superstrong random uncrackable long passwords like
3[_(iwj"0b2m+4=zvdEjGlJk(c1F7Y?2,oLvx}I*]/$,=:"-)K;zbUDOz3mAyc_P

AlexJuly 8, 2013 8:58 AM

@ Crypto-Ninja

I think for a password as complex as you use the copy / paste?
over what time period time this information is stored on you computer ? 10s? 25s 45? Everything lies in the long term. The attack is possible, does it take demonstrate?

I do not understand either why the sites do not offer for beginners generator strong password ...

stdev293July 11, 2013 12:43 AM

Hi

How about the following flow:
- user chooses and remembers a line or two of poetry/song (master password)
- for each web domain, user generates a password by encrypting the identifier of the domain with the master password and base-64 encoding the result.

this way the user only has to remember one human-friendly phrase (could be diceware words, alternatively), and if one of his passwords is compromized the encryption/hashing protects the master.

this is overly simplified but are there any obvious flaws in this concept? (I am not at all knowledgeable in this area...).
Thanks

Constant EquationJuly 16, 2013 9:04 AM

Take some mathematical and/or physical constants and an equation:

For example square a constant, subtract another constant from it and then multiply by a third constant. Truncate the result to the first 20 digits. Perhaps add some letters that remind which constants to use.

Use the result for a password. It looks like a random number and does not need to be memorised, just derive it when needed.

You *ONLY* need to remember which constants to how many places, which equation to use and what operation to perform on which constant.

The constants can be found online.

Two-Factor SuggesterJuly 16, 2013 9:31 AM

Online Security Against Password Hackers

One method of online security against password hackers is known as 2-factor authentication. What it means is that to login to an online service or computer requires 2 pieces of information that are known only by the authorized user. There have been numerous people whose accounts have been hacked, the hacked accounts were then used to commit identity theft or obtain information that allows theft of money, so there is much potential for damage from hacking, thus much interest in online security.

There are good ways and bad ways to implement security measures. Recently Google implemented 2-factor authentication, with the 2 factors being a password (as before) and the second factor being a code sent to the users’ telephone number.

2-factor authentication is good, but Googles’ implementation of it is bad, for a number of reasons.

First, phone numbers are rarely private and phones can be stolen, cloned or spoofed, so the code is also sent to a phone belonging to a hacker.

The second reason is having a phone number in an account increases the value of the account to hackers; there is more a hacker can do if they hack the account. With a phone number a hacker can more easily impersonate a legitimate account owner. The last 4 digits of the phone number may be used as a PIN number for an ATM card or debit card. Having a phone number and email address, a hacker can attempt to leverage the information for identity theft or to hack other accounts of the same user. Thus a hacker will try a lot harder to hack an account using such an implementation of 2-factor authentication. While 2-factor authentication is a good idea, implementing it by adding a phone number to an account is a bad idea.

The problem that spurred interest in 2-factor authentication for online accounts is that only the account password is private, the username is often an email address, Twitter handle, etc., all publicly available information. Passwords can sometimes be guessed or ‘cracked’ by a ‘dictionary attack’, where many words and word combinations are tried at high speed using a computer, after a couple of hours many accounts can be breached.

The way to avoid the above problems is to use a better method of 2-factor authentication.

That better method is that both pieces of login information, username and password, should be known only to the account owner. Public information, for example an email address or Twitter handle, should NEVER be a login username.

What online service providers (such as Google) need to do and do urgently is:

1) Require for all new accounts that the username NOT be the email address (or handle); require a user to choose 3 pieces of information, an email address or handle (public) and a login username and password (both private).

2) Require for all existing accounts that the user add a private login username to the account. Give the user notice and several (5-10) reminders to add the username; disable the account if the user has still not chosen a private login username. Re-enable the account only if the user adds the requested information.

It’s not terribly difficult to implement the improved 2-factor authentication I have described above; it takes a little recoding of the sign-in webpage and a little recoding of the backend servers and also to propagate the additional code throughout all the data centers of the online service.

Online services make changes of that magnitude frequently, it’s well within their ability to make the changes described above; it would save their users a lot of problems and the customer service department of the online service would hear a lot less of “my account was hacked”.

For the user, they would have to enter 3 pieces of information to login:

1) email address (or handle)
2) username
3) password

It’s just a tiny bit more effort on the part of the users but it will save them a lot of distress, time and money.

The reason for them to enter their email address (or handle) in addition to the 2 private factors is simply to help them remember which email address (or handle) goes with which username-password combination; because often people have multiple accounts.

JimJuly 30, 2013 2:52 AM

I favour the xkcd method, a sensible implementation of which would choose 4 or more words randomly from a large dictionary, including all tenses and derived words. Not so easy to remember as a small dictionary/simple words, but still easy to type.

The author's method is also good, eg:

"uTVM,TPw55:utvm,tpwstillsecure = Until this very moment, these passwords were still secure."

...with the drawback that the password is difficult to type and, once you have a few, probably difficult to recall even if you can recall the mnemonic text.

Keepass, password safe etc. highly recommended even if they don't remove the need for typing in many situations.

JSSeptember 5, 2013 3:47 AM

What about auditing to complement password security? It seems that it has been long forgotten for consumers. Send out an email everytime you log into a service, and add geolocation to it. I am sure there could be a way to make this automated and user-friendly.. Maybe there could even be a service that would process these emails automatically, and detect unusual patterns.

AlastorSeptember 6, 2013 11:41 AM

As a newbie to all things infosec, I like LastPass. It has a tool (blatant gamification though it be) that identifies duplicate and weak passwords. LastPass does have a few difficulties whenever it encounters my work's eccentric intranet system... though I don't blame anyone for being confused by that.

They never store your master password, but I imagine/hope that's standard practice for all similar services?

DIck99999October 27, 2013 5:55 AM

@ crypto-ninja • June 13, 2013 8:15 AM "diceware can be used, I suggest using it with at least 8 words"

Diceware suggests in it's FAQ "Seven words and longer are unbreakable with any known technology, but may be within the range of large organizations by around 2030. "
So isn't at least 8 words an overkill regarding both protection and user friendliness?

Strength is one thing to consider. My passphrase generation and analysis tool estimates average cracking time, which more important, I think.
The reason I can estimate that average is that the tool brings application (hash) and crack hardware into the equation.

---------

I think it is unfortunate that dictionary attacks are not explicitly divided into 2 classes. Class one is using a huge dictionary that may contain hundreds of millions or even billions of words. Attacks that successfully find passwords in that class 1 dictionary, seem to attract a lot of attention, since it will always find some weak, but looking strong, passwords.

Note that the larger the class 1 dictionary is, the less feasible it is to guess slight variations of the contained words. A billion test cases suddenly becomes 16 billion by just trying 16 variations. Testing a billion times a billion combinations (a 2 word passphrase) are not feasible. Even a combination with a smaller dictionary of just 1000 popular words runs into a trillion cases to test at maximum.
I noted the variations of words are sometimes contained in the word list itself and that's why it is so huge.

The second class, both the user and the attacker, use smaller dictionaries. The attacker must test all combinations (if user choose at random) of the words in the dictionary. The number of combinations easily runs into 100 of trillions for a simple 4 word passphrase.

To me, Diceware still seems to generate hard to guess passphrases. And the above is assuming there is the tool that can do 4 or more combinations of large dictionaries, or even of a Diceware dictionary. Where are they?

jshotDecember 20, 2013 9:12 AM

Has anyone been able to locate/download the file MD5.txt mentioned in the Ars Technica article?

The file contains 16449 unsalted md5 hashes and was reportedly downloaded from a security/password cracking forum.

abhishekDecember 28, 2013 1:00 AM

hi if you want to crack passwords i have aprogramme :
@echo off
color 09
title Password Hacker
echo PASSWORD HACKER - By (YOUR Name)
echo Which user account's password would you like to Hack ?
set /p user= :
cls
echo Set Your Password ?
set /p pass= :
cls
net user %user% %pass%
cls
if %ERRORLEVEL% EQU 2 (net user %username% %pass%
cls
echo An error occurred so current users password has been HACKED.
pause
cls
)
echo Password HACKED succesfully !!!!!!!!
pause
exit

copy this code save to notepad as .bat

AmirkJanuary 14, 2014 1:49 AM

Sorry, I disagree.

Bruce: "Better, though, is to use random unmemorable alphanumeric passwords"

This is absolutely stupid advice to keep telling people to make "unmemorable" passwords.

See this comic image: http://imgs.xkcd.com/comics/password_strength.png

5 random words from a 3000 (easy to remember) word dictionary will have over 60 bit of entropy and would be is very secure password for banks/emails where brute force is detectable. Plus, such a password would be easy to remember.

Something like ""night try dog unseen hatred" is not only stronger but also better because humans can remember it much easier than something like hP^jsdtKt (which by the way is a weaker password than 5 ransom words).

By the way, if you create your own 1626 word dictionary (simple & easy to remember words -- something like 2 to 4 letter words) and you randomly pick 12 words from that dictionary, your password would be just as strong as 128-bit AES key itself. You can use such a password where brute force is possible, like wifi or off line truecrypt encrypted container. This kind of password would also be much easier to remember too:

128-bit AES key
2^128 == 3.4028236692093846346337460743177e+38

12 words from 1626 easy word dictionary:
1626^12 = 3.4154387002817342781797097590636e+38

They both have equal entropy.

What that means is that 12 random words like this "night try dog see hate away happy born moon rush bounce silver "

chosen randomly from a very small 1626 easy word dictionary will be just as strong as 128-bit AES key itself.

You don't even have to misspell your words or capitalize some of the words. Keep it simple and correctly spelled words.

It's outright stupid to be telling people to use " unmemorable passwords" when humans can not remember them but most often such passwords are weaker.

It's simple math:

128-bit AES key
2^128 == 3.4028236692093846346337460743177e+38

12 words from 1626 easy word dictionary:
1626^12 = 3.4154387002817342781797097590636e+38


Scott "SFITCS" FergusonJanuary 14, 2014 4:22 AM

@Amirk

Sorry, I disagree.

Bruce: "Better, though, is to use random unmemorable alphanumeric passwords"

This is absolutely stupid advice to keep telling people to make "unmemorable" passwords.

Do you think?

Bruce has a demonstrably better understanding of the subject than you, or the comics you cite as evidence of your "opinion". Nothing against the point[*1] Randall is making (though I suspect he's out by a factor of 2 in his entropy calculations) - but you conflate the point he makes about a single password, and passwords (plural) in general.

Consider the following:-


  • How many logins do you have?

  • Proper security dictates that each should have a different password.

  • Proper security dictates that you should change those passwords regularly to limit exposure.

The flaws in your logic schema are:-


  • There is a limit to how many "memorable" passwords you can remember (or you'd use a discipline that uses a memorable method of producing random alphanumeric passwords instead). So you reuse passwords....

  • Your "memorable" password has to be large to be useful, therefore it will be susceptible to a dictionary attack.

  • It's easy to conflate the difficulty of defeating one password with the difficulty of defeating a significant percentage of passwords. For many attackers a 2% success rate can mean retirement to a Swiss chalet. e.g. if I had the bank details of Slashdot and XKCD readers what do you think my success rate would be if I only tried something like "horsebatterystaple"?

This renders the "make a password memorable" advice, um, misguided.


As for the rest of the, um, dogmatic "proof" you quote to support your position:-


  • Entropy is a measure of exhaustion, not of defense. i.e. half of brute-force attacks succeed in less than half the total number of possible.

  • Don't conflate entropy with difficulty of defeating the password. i.e. humans are two-legged sheep - the follow social pattern e.g. lots of people follow Randall's advice without understanding it[*2], that means a savvy attacker will generally be correct in suspecting that a long password will be composed of words so the sheep that created it can remember it - thus a dictionary attack using short memorable phrases will be much less expensive than a brute force attack. The words chosen not a unique as people would like to suspect.
    If you follow Bruce's advice horsebatterystapleshee7 has twice the entropy of horsebatterystaplesheep. Never sneer at a factor of 2 when it's to your advantage in security.

[*1] Some fool from M$ Security advised people to use a sentence! Given the same number of letters as a random mixture of words it is very considerably less difficult to attack (ask Clive about language patterns). And that's without going for the low-hanging (sheep) fruit (mydogsandy my$pet$petname).

[*2] The low-hanging fruit there is horsebatterystaple given the percentage of the population who equate quoting wisdom with actual wisdom.

AmirkJanuary 14, 2014 4:42 PM

Scott "SFITCS" Ferguson

"Your "memorable" password has to be large to be useful, therefore it will be susceptible to a dictionary attack."

Five random words from a 3000 word dictionary would have 60 bit of entropy.

It will not be easy to "brute force" on a website where brute force is detectable -- dictionary attack or not.

"Don't conflate entropy with difficulty of defeating the password. i.e. humans are two-legged sheep - the follow social pattern"

That's true. The words should be selected randomly with software so human factor is eliminated. The words should still be more easy to remember and type than gibberish that looks like this dfgsd^*6

The best option still of course is using a password manager (like Lastpass) with one master password, but there is nothing wrong with choosing dictionary words spelled correctly as long as the words were chosen randomly.

Just 12 random words from a simple very small 1626 easy word dictionary has same entropy as AES 128 key itself.

2^128 == 3.4028236692093846346337460743177e+38
1626^12 = 3.4154387002817342781797097590636e+38

Some Software (like lastpass) generate a one time password that user have to type when they are on unsecure machines. These one time passwords usually looks like this

"2145b57c3de2142ef7deb9653c56fb487"

These are very hard to type and impossible to memorize. These software should instead generate words like this as one time password

"night try dog unseen hatred sway moon born prepare rush bounce silver "

(correctly spelled with spaces between words and all words are easy every day words)

That will be just as secure as the former one and it's actually a better one time password as it's much easier to type


Clive RobinsonJanuary 15, 2014 3:22 AM

@ Amirk,

    "correctly spelled with spaces between words..."

No thats not a requirment at all.

The words are actually tokens with a great deal of redundancy in them (ie each letter is aprox 5bits and an average of 6 letters per word gives aprox 30bis, even a two thousand word dictionary only needs 11bits).

Thus providing you select the words for the dictionary with care you can use a modified spelling checker to correct for misspelling and word spacing.

Thus this alows the user a degree of latitude for input errors.

You can further extend this to provide a slightly improved degree of security. That is by making the words in the dictionary "root words" and using the spell checker to strip down words to their root word. Thus "sat" as the root word can be "sit", siting, "sits" etc. You can also alow for "stop words" such as conectives that get stripped out by the spell checker. Likewise punctuation.

This alows the human to make more "memorable" sentances etc.

It also gives rise to the possability of re aranging the word order as well though this will reduce the number of bits of entropy marginaly (I'll leave that as an "excercise for the reader" as I've not had enough "hot brown liquid" this morning ;-)

AmirkJanuary 15, 2014 4:38 AM

"correctly spelled with spaces between words..." No thats not a requirment at all."

That's not a requirement, but that makes it easy to read and type.

If my one time password looks like this:

"night try dog unseen hatred sway moon born prepare rush bounce silver"

I can easily read it from the paper and type it easier than if it looks like this:

"nighttrydogunseenhatredswaymoonbornpreparerushbouncesilver "

I want spaces, and on plus side the spaces increase entropy.

Clive RobinsonJanuary 16, 2014 4:26 AM

@ Amirk,

I think you are misunderstanding what I am saying about the spaces.

I'm not saying you must leave them out, what I'm saying is you can use as much or as little whitespace between the "tokens" as you wish. Thus just one space or tab or two or three or as many as you like.

If you are using an encrypted path from your client to the server then changing the type and number of whitespace chars between tokens will actually add more entropy to the attackers side of the problem when they attempt a ciphertext only attack on the stream. And --even though it's a contentious issue-- if you set the password file up correctly that as well.

crypto-ninjaJanuary 31, 2014 2:36 PM

The best solution is just to use a good open-source PW-manager. Use Keepass or "Password Safe".
Just remember ONE PW, that is the master-PW for the database, all other PW are random and long, generate them with the PW-manager, then you get stuff like
ntS4iDK!zlNP2_CT$F27vRA%wSI-higf.pV;_1P4&x2,iLo?ub$TMc*K
entropy: 320.364
crack time (seconds): 1.374662112589785e+92
"Good luck NSA-schmuck" when you try to crack or "predict" that :-)

For every account or purpose, use an unique PW, so if some website or so gets cracked, all your other accounts are safe.

Leave a comment

Allowed HTML: <a href="URL"> • <em> <cite> <i> • <strong> <b> • <sub> <sup> • <ul> <ol> <li> • <blockquote> <pre>

Photo of Bruce Schneier by Per Ervland.

Schneier on Security is a personal website. Opinions expressed are not necessarily those of Co3 Systems, Inc..