The Problem With Passwords…
The Problem With Passwords…
A couple of comments I received recently have stuck out a bit. The first was someone asking me why I didn’t include time to crack a 24 and a 64 character password. This left me scratching my head, as the number of possible passwords for a random 64 character password — with just lower case letters — is:
3616548304479297085365330736464680499909051895704748593486634912486670341490423472351870976
and there is not enough computing power in the world to crack that. The other comment I received was when I was told that it was okay if a hash database was accessed, as salt was being used, and so a rainbow table couldn’t be used. Again, there’s a worry that there’s some misunderstandings about the hashing process, as the salt is stored against the hashed value, and GPU and hashcat is then able to perform Terahashes per second, and where even a password such as “7&4K1pxZm” can be broken in minutes.
The strength of a password relates to four major elements:
- The number of characters in the password. The more characters that are in the password the stronger the password will be.
- The range of characters in the password. The wider the range of characters in a password will increase its strength, especially to use non-alphabet ones (such as “!”, “@”, and so on).
- The cracking speed of a brute force generator. This relates to the speed of the cracker, such as 1,000,000 tries per second.
- Whether the company who stores your password uses salt to hash it, and the hashing method they use.
Password Strength Calculator
For example if we have lowercase letters [a-z] we have 26 characters, and add uppercase letters [A-Z], we get 52 characters. If we then have 5 characters in the password, the number of password combinations will be:
aaaaa to ZZZZZ
which will be 52 to the power of 5 = 380,204,032
If we crack these passwords at a rate of one million per second then it will take 380 seconds to try all of them (6.23 mins). In order to try all the combinations I’ve created a password strength checker [here]:
Here is the calculation for [a-zA-Z] with one million password attempts per second. We can see that for seven digit password it takes 11.9 days, and for a 10-digit one it takes over 4,000 years:
But if we now use 1 billion passwords per second, we can see that a seven character password only takes 17.13 mins to crack:
The following outlines the different password requirements for a 5-character one:
Salting
It was recently released that LinkedIn failed to salt its passwords in the 2012 hack, and while salting would have increased the time it takes to crack a salted hash, it is merely a bump in the road if users use passwords such as “123456”.
Why? Because the salt is typically stored with the hashed password, so if the user selects “123456”, the cracker just selects a dictionary with this password and then adds the salt, and compares it. Every one of these passwords, from the LinkedIn password breach in 2012, would have been cracked almost instantly on standard GPU hardware (such as with an NVIDIA graphic card or from an AWS GPU instance).
You don’t have to be Eve The Magician to realise that if I tell you that my password is “qwerty”, and you take a hash signature of it to get: “B1B3773A05C0ED 0176787A4F1574FF00 75F7521E” [here], and then I tell you I’ve used a salt value of “64gfc*w”, and you quickly take a hash of “64gfc*wqwerty” and get: “DAA903ACDA75 D0FEDDEFED1FE 39825EDB42D9991” [here]. If the salt is stored with the hashed value, it is of little use with easily guessed passwords.
The $5 million class action, in 2012, against LinkedIn outlined:
In particular, LinkedIn failed to adequately protect user data because it stored passwords in unsalted SHA1 hashed format.
While this is true, the shocking truth that the passwords themselves would have been cracked even with salting. If the salt is kept with the hashed password, as most systems do, the weak passwords which come from dictionaries would have been easily cracked.
A recent data breach of 150 million users for the MyFittness app created front-page headlines. But when we look into it the data exposed wasn’t quite a bad as it looked. On the data breach only related email address, usernames and passwords, and other important data, such as credit card numbers and date of birth had been segmented away from the username data. The company responsible — Under Armour — even reported within one week of the discovery (which vastly improves on companies such as Equifax, who took many months to report, or Uber who took over a year).
The company reported they had hashed passwords with BCrypt, and which puts up a considerable barrier to cracking the passwords. BCrypt uses salting and then defines a number of rounds, and where an extra round doubles the time taken to compute a hash.
Armour, though, did admit that some of their passwords had been hashed with the 160-bit SHA-1 method, and which are not recommended for password hashing. It is likely that, like Ashley Maddison, that users who had not changed their password were still using SHA-1, and that only new passwords used BCrypt. Auditors thus need to get more tech-savvy, in order to spot weaknesses such as this.
Recently hacks also show the hybrid approach, with Yahoo reporting:
"We have confirmed, based on a recent investigation, that a copy of
certain user account information was stolen from our networks in late 2014 by what we believe is a state-sponsored actor," Lord wrote.
"The account information may have included names, e-mail addresses,
telephone numbers, dates of birth, hashed passwords (the vast majority with bcrypt), and, in some cases, encrypted or unencrypted security questions and answers."
where it quotes that Bcrypt was used in the majority of the accounts, but there is a vagueness about the actual scope of the data breach.
Background
In 2012 Linkedin was hacked, and there was a leak of 6.5 million usernames and passwords, but this has risen to 117 million. Now, a dark web market dealer — The Real Deal — has been offering these account details for 5 Bitcoins ($2,200). The passwords themselves are hashed version, but these are fairly easily to crack with rainbow tables, especially as users tend to pick weak passwords.
Many organisations think they are safe as they use salted passwords, but they are not if they use weak passwords. With Bcrypt we get a number of rounds for the hashing, so if I increase the number of rounds from 6 to 16 … it is over 1,000 times more difficult to crack. In fact, if I increase to 31 it is over 33 million times more difficult (2²⁵). The penalty is that it is slower to hash, so there a sweet spot, but with computing power vastly increasing in the cloud, every crypto method needs a bit of slack!
In cryptography we like things to be fast in order that we can process things in real-time. Generally we have moved from running cryptography on hardware to software implementations. With hashing methods we often want to slow things down, as we want to stop an intruder from brute forcing the hash (where they try a wide range of passwords). We can add salt, but if the intruder gets the salt, they can try popular passwords.
Computing power, too, is increasing massively, especially around parallel processing in the Cloud, and with GPU Graphics cards (which can have over 4,000 cores, each capable of try a range of hash values).
A Few Basics
There are four related core concepts in cryptography: public key encryption (asymmetric encryption); private key encryption (symmetric encryption); one-way hash; and encoding.
All of the methods above allow for the easy reverse of the encryption or encoding process if the key is known, apart from one-way hashing where it should be almost impossible to reverse back the hashed value to the original data. Unfortunately technology has moved on since the creation of hashing methods, and they can often be easily cracked using brute force (where an intruder keeps hashing values until the output matches the hash) using a dictionary of common passwords, or use a rainbow table (which has a pre-compiled list of hash values).
These days MD5 and SHA-1 are seen as weak for many reasons, so we often start with SHA-256 (which produces a 256-bit hashed value) [Link]:
Hash = sha256(password)
Unfortunately this is weak from both a dictionary attack and brute force, so we add some salt:
Hash = salt + sha256(salt + password)
Now this becomes more difficult as the same password is likely to produce a different output. Before, with simple hashing, if one hashed password was cracked, all the other passwords with the same value will also be cracked. The weakness is that the salt requires to be stored with the password, so the intruder just uses a fast computer — such as using NVIDIA graphics cards on the Amazon Cloud — and tries all the main passwords, and is able to determine the original password. The reason this happens is become SHA256 has been designed to be fast, so the intruder uses this for their advantage, and can quickly try lots passwords. If the password is weak and in a dictionary it is relatively easy for the intruder.
So the walls of crypto are falling, especially due to high performance computers, but one solution is to use a hashing method which slows down the process of hashing, adds a bit of salt, and then iterates. This makes it extremely difficult to compile the list of hashes, as it is computationally expensive to compute them — on the Cloud time is money, so a computationally difficult challenge many take years to complete and thus be costly.
PBKDF2
One of the best around for hashing passwords is PBKDF2 (Password-Based Key Derivation Function 2) and is defined in RFC 2898 [here]. It is used in TrueCrypt to generate the key required to read the header information of the encrypted drive, and which stores the encryption keys, and also in WPA-2 [here] to protect the wi-fi password for the pre-shared key. If you’re interested, here’s an overview:
And a calculator is here.
Scrypt
Scrypt is a password-based key derivation function which produces a hash with a salt and iterations. The iteration count slows down the cracking and the salt makes pre-computation difficult. The main parameters are: passphrase (P); salt (S); Blocksize (r) and CPU/Memory cost parameter (N — a power of 2). A demo is here.
Bcrypt
MD5 and SHA-1 produce a hash signature, but this can be attacked by rainbow tables. Bcrypt is a more powerful hash generator for passwords and uses salt to create a non-recurrent hash. It was designed by Niels Provos and David Mazières, and is based on the Blowfish cipher. It is used as the default password hashing method for BSD and other systems.
Overall it uses a 128-bit salt value, which requires 22 Base-64 characters. It can use a number of iterations, which will slow down any brute-force cracking of the hashed value.
For example, “Hello” with a salt value of “$2a$06$NkYh0RCM8pNWPaYvRLgN9.” gives:
$2a$06$NkYh0RCM8pNWPaYvRLgN9.LbJw4gcnWCOQYIom0P08UEZRQQjbfpy
As illustrated below, the first part is “$2a$” (or “$2b$”), and then followed by the number of rounds used. In this case is it 6 rounds which is ²⁶ iterations (where each additional round doubles the hash time). The 128-bit (22 character) salt values comes after this, and then finally there is a 184-bit hash code (which is 31 characters).
The following provides an example of Bcrypt [here]:
The slowness of Bcrypt is highlighted with a recent AWS EC2 server benchmark using hashcat [here]:
- Hash type: MD5 Speed/sec: 380.02M words
- Hash type: SHA1 Speed/sec: 218.86M words
- Hash type: SHA256 Speed/sec: 110.37M words
- Hash type: bcrypt, Blowfish(OpenBSD) Speed/sec: 25.86k words
- Hash type: NTLM. Speed/sec: 370.22M words
You can see that Bcrypt is almost 15,000 times slower than MD5 (380,000,000 words/sec down to only 25,860 words/sec). With John The Ripper:
- md5crypt [MD5 32/64 X2] 318237 c/s real, 8881 c/s virtual
- bcrypt (“$2a$05”, 32 iterations) 25488 c/s real, 708 c/s virtual
- LM [DES 128/128 SSE2–16] 88090K c/s real, 2462K c/s virtual
where you can see that Bcrypt over 3,000 times slower than LM hashes. So, although the main hashing methods are fast and efficient, this speed has a down-side, in that they can be cracked easier. With Bcrypt the speed of cracking is considerably slowed down, with each iteration doubling the amount of time it takes to crack the hash with brute force.
Here is the Python implementation:
from pbkdf2 import PBKDF2
import hashlib;
import passlib.hash;
salt=”ZDzPE45C”
string=”password”
salt2=”1111111111111111111111"
print “General Hashes”
print “MD5:”+hashlib.md5(string).hexdigest()
print “SHA1:”+hashlib.sha1(string).hexdigest()
print “SHA256:”+hashlib.sha256(string).hexdigest()
print “SHA512:”+hashlib.sha512(string).hexdigest()
print “UNIX hashes (with salt)”
print “DES:”+passlib.hash.des_crypt.encrypt(string, salt=salt[:2])
print “MD5:”+passlib.hash.md5_crypt.encrypt(string, salt=salt)
print “Bcrypt:”+passlib.hash.bcrypt.encrypt(string, salt=salt2[:22])
print “Sun MD5:”+passlib.hash.sun_md5_crypt.encrypt(string, salt=salt)
print “SHA1:”+passlib.hash.sha1_crypt.encrypt(string, salt=salt)
print “SHA256:”+passlib.hash.sha256_crypt.encrypt(string, salt=salt)
print “SHA512:”+passlib.hash.sha512_crypt.encrypt(string, salt=salt)
and which gives:
MD5:5f4dcc3b5aa765d61d8327deb882cf99
SHA1:5baa61e4c9b93f3f0682250b6cf8331b7ee68fd8
SHA256:5e884898da28047151d0e56f8dc6292773603d0d6aabbdd62a11ef721d1542d8
SHA512:b109f3bbbc244eb82441917ed06d618b9008dd09b3befd1b5e07394c706a8bb980b1d7785e5976ec049b46df5f1326af5a2ea6d103fd07c95385ffab0cacbc86
UNIX hashes (with salt)
DES:ZD3yxA4N/XZVg
MD5:$1$ZDzPE45C$EEQHJaCXI6yInV3FnskmF1
Bcrypt:$2a$12$111111111111111111111uAQxS9vJNRtBb6zeFDV6k7tyB0DZJF0a
Sun MD5:$md5,rounds=34000$ZDzPE45C$$RGKsbBUBhidHsaNDUMEEX0
SHA1:$sha1$480000$ZDzPE45C$gfgoLWRrJHj/ZiXsV101NCX1GfUH
In this case we see we are using 12 iterations and a pre-prepared salt of “1111111111111111111111” (22 characters to give a 128-bit salt value):
Bcrypt:$2a$12$111111111111111111111uAQxS9vJNRtBb6zeFDV6k7tyB0DZJF0a
We can increase the rounds to 20 with:
print “Bcrypt:”+passlib.hash.bcrypt.encrypt(string, salt=salt2[:22],rounds=14)
to give:
Bcrypt:$2a$14$NkYh0RCM8pNWPaYvRLgN9.OcinBT2h.8NWt/KfmHQ5eIr/50zCt8q
and which considerably slows down the hashing. In fact it will show by a factor of 4. It is thus going to cost four times as much to crack a single hashed value. Here is a demo of Hashcat on an AWS GPU instance:
Conclusion
So, in the days of massively parallel systems, swimming in molasses is a good thing for protecting passwords. The more iterations we have for each round is good too, as it makes it more difficult to crack. PBKDF2 is doing very well just now, with its adoption in WPA, along with TrueCrypt, and a number of password vaults. Bcrypt is still a strong contender, though.
So remember … if your crackers have managed to get a million passwords from your system … with Bcrypt you just have to change a single parameter … and they will only get one in the same time. I reckon the value goes from 6 to 26 … and it is one million times more difficult to crack (2²⁰)!
Finally, you can test password strength here.
And the hashing calculator here.
import timeit
from time import time
import sys
from hashlib import md5
import passlib.hash;
import mmh3
import smhasher
import sha3
import hashlib
num = 20
repeat_n=1
salt="ZDzPE45C"
string="the boy stood on the burning deck"
salt2="1111111111111111111111"
print "Hashes"
print "SHA-1\t",hashlib.sha1(string).hexdigest()
print "SHA-256\t",hashlib.sha256(string).hexdigest()
print "SHA-512\t",hashlib.sha512(string).hexdigest()
print "MD-5:\t\t\t", md5(string).hexdigest()
print "DES:\t\t\t", passlib.hash.des_crypt.encrypt(string, salt=salt[:2])
print "Bcrypt:\t\t\t", passlib.hash.bcrypt.encrypt(string,rounds=5)
print "APR1:\t\t\t", passlib.hash.apr_md5_crypt.encrypt(string, salt=salt)
print "PBKDF2 (SHA1):\t\t", passlib.hash.pbkdf2_sha1.encrypt(string,rounds=5, salt=salt)
print "PBKDF2 (SHA-256):\t", passlib.hash.pbkdf2_sha256.encrypt(string,rounds=5, salt=salt)
print "LM Hash:\t\t", passlib.hash.lmhash.encrypt(string)
print "NT Hash:\t\t", passlib.hash.nthash.encrypt(string)
print "MS DCC:\t\t\t", passlib.hash.msdcc.encrypt(string, salt)
print "LDAP (MD5):\t\t", passlib.hash.ldap_hex_md5.encrypt(string)
print "LDAP (SHA1):\t\t", passlib.hash.ldap_hex_sha1.encrypt(string)
print "MS SQL 2000:\t\t", passlib.hash.mssql2000.encrypt(string)
print "MySQL:\t\t\t", passlib.hash.mysql41.encrypt(string)
print "Oracle 10:\t\t", passlib.hash.oracle10.encrypt(string, user=salt)
print "Postgres (MD5):\t\t", passlib.hash.postgres_md5.encrypt(string, user=salt)
print "Cisco PIX:\t\t", passlib.hash.cisco_pix.encrypt(string, user=salt)
print "Cisco Type 7:\t\t", passlib.hash.cisco_type7.encrypt(string)