How secure are passwords?

This is an adjunct to my other article "Choosing the right encryption for your needs".

Password types: Hashed and Encrypted

I'll make this initial intro to passwords and encryption brief: Password hashes are one-way mathematical operations that cannot be reversed. Plain-text goes in, and a hash comes out, to check against a hash, the same operation has to happen; Take the plain-text, hash it, and then compare against the stored hash to see if they match.

Some password hashes have another component, a salt. This salt is stored next to the hash, and when it's time to compare the hashed password, the salt get's added in, and then the hashes are finally compared. Salts are extra characters, unknown to the user, that are intended to slow down password guessing. If you and I have the same password, but different salts, then our hashes are not the same, even if the plain-text is.

Salts add time to an attackers efforts to hash the passwords, in that the salts have to be guessed as well as the passwords. If you dump Windows hashes off a domain you'd see a lot of duplicate hashes, but if you dump a bunch of Linux machines you will be hard pressed to find any hashes that are the same, even if the plain-text passwords are not unique. Windows uses no salts when it hashes logon passwords, Linux/Unix/Macintosh/BSD and others do use salts, they have for past few decades.

Symmetric encryption is different than hashing, because encryption is a reversible process. The same plain-text that you used to encrypt is used to decrypt. You are probably used to using symmetric encryption when you use a password protected Zip or Rar archive. Even Microsoft Office and Open/Libre Office documents use symmetric encryption for protection. Asymmetric encryption is a little trickier. One "key" is used to encrypt, and the other to decrypt. You can freely share one key, the other you have to keep private. Someone can use the key you share to encrypt something for your eyes only, send it to you, and you can use your private key to decrypt it. Typically both parties share their public keys with one another. So to reply to the person, you use their public key, and they can read the reply using the private key they have. Technically you can use your either key to encrypt something, and the the other key to decrypt it; For example: You can send a message encrypted with your private key to someone, and they use your public key to decrypt it. This type of encryption is used in SSL aka Https connections, as well as in products like PGP or GPG.

Websites that use SSL/TLS, they send you an encrypted message using their private keys, and your computer and browsers come bundled with the public keys so you can decrypt the data. There are other mechanisms in play, and the above isn't the default behaviour of all Https, but it is possible and recommend to use the asymmetric for the session keys. Read a better intro here: Microsoft.

Password Policies: The good, the bad, and the undermining.

Password policies are a good way to enforce users to create strong passwords, and to not repeat passwords over time. Some policies are able to be very vigorous and enforce users to not increment a password by adding a number or changing one letter only. Others are far more generic. From a mathematical stand point, requiring passwords to contain at least one of this or at least one of that, reduces the number of possibilities an attacker has to guess. But it's not a dramatic reduction unless you go overboard.

If you require all four possible generic polices, at least one digit,  one upper, one lower and one special, and the minimum length is eight, you've reduced the guessing by over half. Instead of 6,704,780,954,517,120 possible it's reduced to 3,025,989,069,143,040 , which is a 55% reduction when the password is only 8 characters long. The attacker will get your passwords that are 8 characters in half the time, if all things were equal.

If you only required three of the four for the length of eight, then it's only a 7% possible reduction. You can see more statistics and get code to test with on the Opewall Wiki Policy page.

Real world passwords: How hard are passwords to crack?

Not hard, typically. Windows passwords for the OS and some of the Microsoft products are notoriously easy and fast, some aren't even really encryption! However beginning with Microsoft Office 2007, their encryption finally got on track. As I briefly explained in my previous article, MS Office started using thousands of iterations of a hash and then encrypting the document using that hash as the encryption key. You basically hash the plain-text password, and hash that hash, and that one and so on until you've done it  10,000 (or more)times. Then you use AES-128 to encrypt the document based on the last hash you generated. All of that takes time, when you have the right password, it's maybe a second or two, but if you don't and you have to guess over and over, it's very very slow.

Linux and other *nix flavours (like Android and Macintosh/Apple) use salted and or slow to compute passwords. This is ok when a user is authorized, even if the hash is "slow", to the user it should take no time if the password is right. To the attacker its going to take much longer when compared to Microsoft. Overall there are many fast hashes and even encryption products out there, most are still fast to attack. You can see some basic benchmarks on JtR's wiki or Hashcat's benchmark page.

How to make passwords harder to find.

There are two distinct ways, make them unlikely to be guessed, by making them long but not necessarily complicated. Or use slow hashing methods. Naturally combining the two is even better. You can create a long password that is strong and doesn't contain anything special, despite most people feeling otherwise about that.

The password "iamaverylongpasswordnoonecouldbreak" is all lower, no digits or specials. I as an auditor would never in a lifetime find this password without some other clue to help. It's too long to bruteforce even for the fastest hash, and no dictionary or permutation script would find it. It's also ok to use written passwords, just keep them safe and away from prying eyes.

Your passwords don't have to be changed as often if they are good passwords. The above 34 character password doesn't *seem* hard to guess, but it is. The longer a password is the better in 99.9% of the cases. Some hashes have limitations about the input, but many support 127 or more characters with ease. These days, from my perspective as a long time password auditor, you need 10 or more characters at a minimum, no matter what hash or encryption you're using.

You should audit your users passwords, you should see if they are choosing good ones by not finding them. The ones you do find are weak, and possibly hurting your security.
Active password guessing goes on all the time, and not all authenticators reject attempts after so many failures, more often than not bruteforce guessing is effective as seen by the Conficker and Morto worms. There are even databases that keep track of default passwords for thousands of networked items. Make sure you reset all default passwords to something unlikely to be found easily.

What does an unlikely or strong password look like?

That's the best part, I don't know :) I know I've found some crazy ones, passwords I never thought I'd find, even when they were long. I can give a few examples of passwords that are strong from an auditing perspective.

A personal favourite "wnstlyktrasdi", uses the first letter for each word in the first two lines of  the song "I'm never gonna give you up" Again not the best if you look at it through a policy perspective, but long, and unlikely to be found nonetheless.

How passwords are found: Bruteforce, Dictionaries, Mangling, Trigraphs and More!

Bruteforce consists of iterating through every possible combination of characters until you find the matches. That is the slowest, but the one of the most thorough ways of doing brute force. (aaaa, aaab, aaac, aaad, aaae ... zaaa, zaab, zaac, zaad, zaae etc)

Dictionaries and wordlists are also used. You can manipulate the dictionaries and wordlists using mangling rules, rules that add, subtract or change the input to something else. Mangling "password" to "p@ssw0rd" or to "p@55w()rd" for example.

Mangling rules can duplicate, repeat, do CamELCAsE, add years to the front or back of the input, or all of those things. You don't want your passwords to be based on one single item, they should be based on multiple items.

Trigraphs are statistical probabilities of three characters will be next to one another. "and" is more likely to be guess before "dna" for example. Same thing when more letters are added "sand" will be guessed before "qand". There is far more to go into but it's the likelihood of 3 characters appearing together in certain positions. This is like educated bruteforce guessing.

Markov model guessing is sometimes faster than Trigraph's, and is highly adjustable to the complexities you're expecting to find in your passwords. There is other work being done along these same lines that are making short passwords lengths a thing of the past.

Other methods are keyboard attacks, looking for passwords like "1qaz2wsx3edc" which looks pretty secure until you realize it's the first character on the first 3 rows of the US keyboard. Sifting or xieve attacks try to gather words and characters from other places like in your log files, word documents or emails, and add them to the word lists.

Rainbow Tables: Rainbow tables are effectively precomputed hashes and plain-texts, but done so in a more efficient manner than hash_x = pass_y. Rainbow Tables (aka RT) are a sorted database of hash and plain-text "parts" or chains. If you were to write all possible 8 character plain-texts to a file it would take up 7,258 Gigabytes of space. That's all 95 printable US-ASCII characters and 8 characters long, and that's the plain-text's only... if you add in the hashes it doubles and then some because most hashes are 16 or more characters long themselves. So RT's are far more efficient than writing hashes and plain-texts to a file.

RT's have their draw backs, they can't find lots of passwords that quickly, say over 100 at once, it's going to be a very slow search. They also can't store 100% of all possible hashes. Searching for a few or single hashes is very fast, but when auditing a large group of hashes at once it's not fast, RT's should be used at the end rather than the beginning of an audit. RT's don't work against salted hashes or challenge-response hashes, unless you have pregenerated a table with the salt or challenge. RT's a perfect for small or fixed key-size attacks, old Microsoft Office for instance uses a 40-bit RC4 encryption key (not a hash btw). It's actually faster to attack the key-space of the document than to try to guess the password used. 40-bit is very small, and a RT for old MS Office is under 4 Gigabytes and takes 30 seconds to 15 minutes to find the key to old MS Office or older PDF protection.

Ultimate takeaway:

Speed of the encryption and or hash are the main factors for recovering weak passwords. If the hash mechanism is slow, it can make a weak password take much longer than it would if it was a fast algorithm. Weak is still weak. Keeping the hashes out of the wrong hands is also key, but that's what the audit is for, making sure that the users are using strong passwords even if the worst should happen. Passwords that are good, can be written down, and probably don't have to be changed as often. Well protected passwords I would argue don't have to ever be changed, but there is something to be said for changing just in case. You never know if the most complex password might still be stored on your machine in plain-text somewhere :)