Hashes and Password Storage

Password Storage

The user's password is NEVER saved.  Rather, at a minimum, a hash of that password is kept.  The idea is that only the user knows the password and any footprint on the server is a complex representation of that password.  That representation should be 

• Different for each different password (and ultimately, each combo of username and password)

• Be difficult (i.e. impossible) to determine the password from the server-kept representation (i.e. reverse determination)

• Difficult (i.e. impossible) to input a multitude of passwords and then match to the server-kept representation

This discussion will walk through various aspects of attempts to achieve these goals.

Note Regarding Examples

To keep things simple and reproducible, all the examples and discussion below will use the Python 2.7 implementation of the various hashing and encryption methods.  Lots of arguments can be made whether this is good, bad, details, etc. but this gives a pretty simple and consistent baseline for this discussion.  It’s what I’ve chosen to use as a demo baseline…live with it or don’t read this article.

Key Derivation Function (KDF)

Passwords are usually of variable length and character sets.  For example, a password of 10 printable/type-able characters (i.e. a-z, A-Z, 0-9, and all the other keyboard characters) would be described by 

8*10 = 80 bits using an 8-bit byte for each character.  

The number of characters available is 

26 (upper case) + 26 (lower case) + 9 (numbers) + 30 (~ symbols) = 91 printable characters.  

But 28 = 256 meaning that a single byte of 8 bits can represent 256 different combinations.  Consider a 10 printable character password…..9110 = 3.9*1010 possible combinations.  With today’s computing power, that is not really that astronomical a number. But using all 8 bits and not limiting to simply printable/type-able characters…i.e. 256 combinations….would give 25610 = 1.2*1024.  This is significantly larger number of possible combinations using the same 10 byte password size.  

A KDF takes an input and expands (or contracts) that password input into a fixed-size set of bytes…the key.  An input password of 10 characters or 5 characters or 50 characters would then become a 32 byte key (i.e. using the terminology that a password becomes a key when it is transformed).  That password would be thus bit-centric key and thus be one of 25632 = 1077 possibilities….which is about as many atoms as there are in the entire universe…earth, sun, planets, galaxies….  That should be just fine.

Therefore the desirable KDF will take any input password of any length and uniquely map into a all-bits-used 32-byte key.  Add in the requirement that the KDF do this uniquely -- one input password results in one and only one fixed-length (i.e. a 32-bit key).  The hard part is to make it so that the KDF be able to withstand various methods of guessing/transforming an inverse (given a key, what was the initial password).

The simplest KDF is the basic hash function.

Hash function

A hash function takes an input of nearly any length and maps to a fixed-length output.  What makes a hash strong is (1) the one-way nature of the function (i.e. there is no known mathematical function that will “un-hash” an output into the input data, (2) the minimization of likelihood that two input data sets will produce the same hashed output (a.k.a. a “collision”), and (3) a set of input data/bits maps only into one output hash.  The hash produces a unique “fingerprint” for the larger individual (i.e. input data set).

Expanding on (2).  A typical hash results in 256 bits (i.e. SHA-2, SHA256).  An input could (often) contain thousands of bits.  It is thus necessary that there are multiple bit combinations that result in the same hashed result.  A good hash function, however, will map the thousands of bits into the 256 bit in such a way as to have overlaps that evenly, randomly distributed.  For example, a thousand-bit input whose last bit changes from 0 to 1 will have a very different output hash.  Likewise, changing one (or multiple) bit anywhere in the hash would result in different and uncorrelated resultant hashes.

A 256 bit hash = 32 characters = 32 bytes = 32 octets.  A 256 bit hash has 1077 possible results. A 512 bit hash (64 octet characters) has 10154 possible results.  There is obviously a lot of room for an input dataset to one-way map into a hash!

A typical hash of a password, such as with the SHA-2 hash, renders it "invisible."  A one-way hash, such as SHA-2, takes a group of input characters (bits) and performs shifting and/or math functions on it to produce a second group of characters (bits).  The hash function maps a set of input bits to a set of output bits -- always the same and (desirably) highly unique.  In essence, the hash functions produces a unique fingerprint of the input.

The input can be one or many, many characters (i.e. a file or even a book).  What is most appealing is that for any two input set of bits, it is very rare (nearly never, ever happens) to have as hash output the same set of bits (a.k.a. a collision).  For example only changing initial capitalization from "Now is the time for all good men." (Example 1) to "now is the time for all good men" (Example 2) produces these two SHA256 has results (64 hex characters representing 32 byte = 256 bit hash):

Example 1 (hex):  bcdab49c382384fd4c2a65acc72ca2030a5010ed23641087c27a7f1c078e118f

Example 2 (hex):  6fef37aed78e2622f887318044025f828b85b84db1e70353bb99c002c99af46c

A hash function is a one-way street. A strong hash function, such as SHA-2 (i.e. SHA256), makes it essentially impossible to calculate the initial set of characters from the final output set of characters.  There is no inverse function for a hash function.

[Python note: example used hashlib.sha256(‘text to hash’).hexdigest() from hashlib library https://docs.python.org/2.7/library/hashlib.html ]

Password Hashes

However, a hashed password may be readily hacked or guessed via a Rainbow Table...a pre-computed table consisting of the hash of common passwords.  Computing a hash is very quick – a double-edged sword.  Easy to compute and easy to make precomputed Rainbow Tables.  

For example, a password of "pass123" could be kept as a SHA256 (32 bytes hash).  The hex representation (64 hex characters) of SAH256("pass123") is

   (hex) 9b8769a4a742959a2d0298c36fb70623f2dfacda8436237df08d8dfd5b37374c

But just as there are catalogs of common passwords, there are catalogs of these common passwords as hashes...MD5, SHA128, SHA256, etc

Salt:

To kill the use of these pre-computed hashed password Rainbow Tables, one should simply add random characters to the password being hashed, a.k.a. a salt.  For example, use the random initial addition an 8-character salt of "7yttu38h" to "pass123" (i.e. "7yttu38hpass123").  This hash then becomes:

  (hex) 270b85816c7a4b6ce73b12083a9b74db6e9b9776e5ed45aa9b1aede53107244c

This could then be stored as:

  $7yttu38h$270b85816c7a4b6ce73b12083a9b74db6e9b9776e5ed45aa9b1aede53107244c

This storage method contains the salt at the beginning and braced by “$” characters and the resulting hash follows at the end.  To recompute the hash – to check if the current input matches the input that produced this hash – extract the salt from the old hash and recompute.

For a hacker, a new rainbow table would have to be generated for each new salt.  Changing the salt for every stored hashed password increases the work needed to try to find the password each time.  Pre-computing rainbow tables for an 8 character salt increases the table size by (using characters of just UC and LC and numbers... 26+26+9 = 61 characters) of 61^8 = 191707312997281 ~ 1014.

Note: this salt example which gives 61 characters is analogous to a 61 bit salt.  Using binary salts created via a random bit generator could easily increase this to 64 bits...but this is just fine for this discussion example!).

Speed

The SHA256/512 hashes are built for speed and ease of computation -- their prime objective is to give a unique fingerprint for the input.  For a typical i7 CPU laptop running Python implementations of the hash, one million sequential hashes of “Now is the time for all good men.” (i.e. a very long password) takes less than 2 seconds.  (A sequential hash hashes the input, then hashes that output, then hashes that output, etc.)

Time to run one million hashes for various hash functions (using Python SHA C++ implementation routines):

SHA512 (512 bits, 64 bytes)   dt seconds = 1.83

SHA256 (256 bits, 32 bytes)   dt seconds = 1.6

SHA224 (224 bits, 28 bytes)   dt seconds = 1.2

MD5 (128 bits, 16 bytes)   dt seconds = 0.97

(8 bits = 1 byte = 1 octet = 1 character = 2 hex characters)

Using Python's SHA256 routine, one million hashes can be run in 1.6 seconds.  Using the example above, that means that the 1014 permutations can be computed in (1014/106)*1.6sec ~ 1850 days.  Not bad.

However, and it is a big however, the i7 laptop is not the hacker’s tool of choice.  Many serious hackers have determined ways to use either a GPU (graphical processing unit) or a FPGA (field programmable gate array) that greatly increase the speed of computing a hash function.  In reality, this method of protecting passwords is not really very strong.  There are also various other attacks (timing, etc.) that can speed the calculation by reducing the set of possible matches.  However, there are readily available methods that provide much better protection.

Hardened KDFs:  PBKDF2, bcrypt and Argon2:

As of 2016, three password hashing and protecting functions are considered strong and acceptable for use.  Argon2 – built, tested and accepted in 2015 – is crowned the preferred protection method for the new systems.

Compare the time to run various hashes:

Python notes:  

BCRYPT function bcrypt.hashpw() ref: https://pypi.python.org/pypi/bcrypt/2.0.0 .  

PBKDF2 function hashlib.pbkdf2_hmac() ref: https://docs.python.org/2.7/library/hashlib.html .

ARGON2 fuction low_level.hash_secret() ref:  https://pypi.python.org/pypi/argon2_cffi .

PBKDF2:

Typical output of PBKDF2 using SHA256 hash produces a 64 hex character string:

(hex)059c470eb7d0d042c2ff04e486edf85cebf9f0d52b001360dc58815383e22332

Typical output of PBKDF2 using SHA512: 128 hex character string

(hex) 67482520fffb01e3665485d51c0a39a9ba13a67712ac3b9f62401fcb047e3881aa37c79d8078a7b06f1b1e3a6d14319c75452e9f68430d342ad3c801e9ef9593

BCRYPT:

“BCRYPT” is even better than PBKDF2:

BCRYPT happens to heavily rely on accesses to a table which is constantly altered throughout the algorithm execution. This is very fast on a PC, much less so on a GPU, where memory is shared and all cores compete for control of the internal memory bus. Thus, the boost that an attacker can get from using GPU is quite reduced, compared to what the attacker gets with PBKDF2 or similar designs…. The BCRYPT authors were working in 1999. At that time, the threat was custom ASIC with very low gate counts. Times have changed; now, the sophisticated attacker will use big FPGA, and the newer models (e.g. the Virtex from Xilinx) have embedded RAM blocks, which allow them to implement Blowfish and BCRYPT very efficiently. BCRYPT needs only 4 kB of fast RAM. While BCRYPT does a decent job at making life difficult for a GPU-enhanced attacker, it does little against a FPGA-wielding attacker. 

http://security.stackexchange.com/questions/4781/do-any-security-experts-recommend-bcrypt-for-password-storage)

If one assumes that BCRYPT is “better,” the parameter to adjust is the number of rounds.  Using the same i7 laptop and the Python implementation, variation of the rounds parameter gives the data in the table.

The typical BCRYPT output is 

  $2b$04$3Svu4cxG8o7OjcNYHPqmT.keC69OYxBRzPWsFr0vepHh/E63d.FiK

Note that the 60 character output provides three pieces of info between the “$”:

• Version of the algorithm or program info (i.e. “2b”)

• Number of rounds/work function (example = 4)

• The hashed output (example = 3Svu….)

The first two outputs (version and rounds) are necessary to properly reproduce the hash when checking the trial password versus the original password.  The second, longer input contains both the hash of the password and info about the salt that was used.  In the two examples using the default/suggested work value of 12 that the same password was used but that the result is different because of two different salts having been used.

The work function is non-linear (seems exponential?).  From 12 to 16 is a roughly 15x timing difference.

ARGON2

ARGON2 is the winner of a recent, seemingly rigorous hash/KDF completion.  It contains the various looping and iterative complexities of previous hashes.  It also has timing and memory size countermeasures against the use of FPGA and GPU attacks.  

Example ARGON2 hash...with a 32byte salt and 32byte result (base64 representation output):

  $argon2i$v=19$m=8,t=1,p=1$2eZ2LdHI6vbWGzxhkvxAjU1tXxF20MKRabwk5xw/J0o$9xOq1jxtcOAPEmjOneX086L7dlkeH9IJe0+cRXsQVfs

['', 'argon2i', 'v=19', 'm=8,t=1,p=1', '2eZ2LdHI6vbWGzxhkvxAjU1tXxF20MKRabwk5xw/J0o', 

'9xOq1jxtcOAPEmjOneX086L7dlkeH9IJe0+cRXsQVfs']

The first elements are the basic description of the particular ARGON parameters used.  The last two elements are the input salt and the final resulting hash.

Discussion:

A fast hash – such as SHA – can take any input (of nearly any various length) and quickly produce a unique fingerprint of that input.  Because it is one-way, the actual input cannot (realistically) be determined from the fingerprint.  But, because it is fast, it is easy to build pre-computed tables that could be used to invert the hash.  To avoid this inversion method, other hashes have been developed which address potential issues with speed and custom hardware attacks.  The three most widely used – BCRYPT, BKDF2, and ARGON2 – all address the timing issue via slow calculation and loops.  Hardening against side-channel and GPU/hardware attacks, ARGON2 is the currently (2016) the hardest hash/KDE to attack.

What to use?

Personal opinion follows.

Encryption:  

When building an AES encryption routine, a (16, 24 or) 32 byte key is required.  To assure a good bit-centric key (rather than simply a 32 character key using only printable characters), use SHA256 on any input key and use that bit-centric key for the AES encryption.  One might also consider prefixing an obfuscating “salt” to the input key to assure that the hashed key is somewhat unique.  

One way to achieve this is to build the actual AES key:

AES-key-used = SHA256( SHA256(“salt1234*&%^*“) || SHA256(“AES-input-key”) )  

where  || means concatenate.  In words, hash a salt and hash the input key.  Concatenate these two hashes and then hash the result into a 32-byte  (256 bit) key.  The salt should be unique to the particular encryption and might be stored as a prefix to the encrypted data (or stored elsewhere other than with the input key depending upon the situation).  Even if someone has the salt, rainbow tables are not easily useable and it should make getting the key a little bit harder.  While I’ve seen many other similar ways of producing a 32-byte key, I’ve never seen an analysis that would justify why or how one method is superior to another.  Your mileage may vary!

Note that I prefer to make the KDF work – slow building of an AES-input-key – be done as a separate step rather than lumped in with the AES encryption setup routine.

AES Input Key:

The AES-input-key can be derived from a password using a slow and hardened KDF.  Using ARGON2, there is a sub-function which will use the ARGON2 method to build a key and out just the hashed output.  If ARGON is not available, use one of the other password functions (i.e. PBKDF2) to take the input key and treat it like a password.  Use the output hash as the key passed to an AES encryption.

Password storage:

Use ARGON2.  Most hosted services do not have ARGON available but usually PBKDF2 is included in the main packages.  If one does not want to manually include or have access to ARGON, use PBKDF2 with 100,000 rounds to make keys and store passwords.  For password storage, examine the pre-built functions as there is likely a pre-built function available for this common task.

Note also that some implementations of ARGON2 and the other KDFs provide a simplified output and verification API that takes care of salting and other helpful bookkeeping (Python implementation https://argon2-cffi.readthedocs.io/en/stable/api.html ).

Additional References:

https://www.owasp.org/index.php/Password_Storage_Cheat_Sheet 

http://eli.thegreenplace.net/2010/06/25/aes-encryption-of-files-in-python-with-pycrypto