Crypto, hashing & passwords

Entry posted by EricBall September 17, 2012

716 views

Many years ago when I was a university student, I worked at Bell Northern Research (the R&D division of Nortel, RIP). One of the projects I worked on was a device which sat between an endpoint and an X.25 network and encrypted the data portions of the packets. A similar device at the destination handled the decryption. Although I didn't get down & dirty with the crypto, I learned enough to have a passing understanding of the field - including the wisdom to never roll your own crypto; use a proven standard instead.

But I'm thinking I might want to do just that.

The problem is passwords - we all have too many of them to ensure all of them are unique and sufficiently strong. Stories like http://arstechnica.com/security/2012/08/passwords-under-assault// have shown how easy it is for hackers to learn a site's passwords by brute-force testing (by using password dictionaries & heuristics developed based on other password files). And once your password from one site is exposed, they can use that same password at other sites. The obvious solution is to have unique passwords for each site, but how to keep track of each password - especially if you want the password to be uncrackable without a complete character by character search.

The standard answer is to use a key derivation function like PBKDF2 which takes a master password and a site-specific "salt" (random string which does not have to be secret) to create a site-specific password. PBKDF2 also makes cracking the master password more difficult by using a cryptographic hash function thousands of times over & over again.

I was going to use PBKDF2, but then I started looking deeper into how it works and realized that although it repeated the hashing function multiple times, each time it used the master password (which isn't random) and padding (zero bytes) - thus making the input less random. The second problem is even though it repeats the hashing function thousands of times, that doesn't prevent a brute force attack which can run over days and use GPUs to try multiple attempts in parallel.

The latter issue is why scrypt was created. It creates a large array of random data, then randomizes that data, then hashes it to provide the result. The theory is a PC can easily handle the large array while a doing the same for a GPU or custom hardware would be cost prohibitive. The problem I have with scrypt is twofold: first, it uses PBKDF to create the random data (as a very large key) and then uses it again to create the output - and as I've looked under the covers at how PBKDF2 works I'm not sure that's an optimal solution. And second is I don't like some of the details of the randomization portion. Plus, I think I can do better with a simpler function.

With all due respect and recognition to Colin Percival and scrypt, I would like to propose the following Sequential Memory-Hard Key Derivation Function based on SHA-256. The following is licensed under the Creative Commons Attribution License.

SHA-256 follows the Merkle–Damgård construction where a padded message is broken into N 512-bit message blocks M[1], M[2], ..., M[N] and the message digest H[N] is calculated via the following process:

H := hash( H[i-1], M )

hash is the 64 rounds of the SHA-256 compression function

H[0] is the first thirty-two bits of the fractional parts of the square roots of the first eight prime numbers

H[N] is the 256-bit message digest of M.

My proposal is to extend this construction as follows:

H[0] := Salt

H[1] := hash( IV, IK )

H := hash( H[i-1], H[(i-1) ** H[i-1]] || H[(i-1) ** ><H[i-1]] )

hash is the 64 rounds of the SHA-256 compression function

IV is the first thirty-two bits of the fractional parts of the square roots of the first eight prime numbers

IK is the 512-bit initial key

N is the number of iterations

Salt is a 256-bit random number

H[N] is the 256-bit derived key

><h is the bit reversal of h

m ** h is the integer portion of m multiplied by h as a binary fraction

|| is the concatenation function

The intent of this KDF is to make it infeasible, due to computation & memory requirements, to determine the initial key (by brute force or otherwise) given knowledge of the derived key and the Salt.

The purpose is to create hashes or passwords (via appropriate mapping) based on a master password and context and/or application specific information. In this context, 512 bits (64 8-bit characters) of input and 256 bits (43 base64 encoded characters) of output should be sufficient for most purposes. SHA-512 may be extended by the same method to double the initial and derived key lengths. Initial keys longer than 1024 bits may also be reduced by an initial hashing (preferably using SHA-512 to generate a 256 bit initial key). Derived passwords longer than 512 bits may be created using methods similar to those in RFC 2898 or RFC 5869.

The idea is you'd have a file containing the following information: site info (e.g. ericball@atariage.com), the salt, and the length of the output password and 64 characters used to translate the 256 bit derived key to the site password. When you wanted to access the site you'd select the site info, enter the master password and cut & paste (or transcribe) the output password.

My current challenge is twofold: first, getting some real cryptos to look at it and figure out if there's any problems with the idea (i.e. repeatedly using the hash will devolved the derived output to a small set of values), and second figuring out whether this will actually provide the desired result.

The hypothesis is using lots of RAM makes it more costly to brute force the master password. However, my KDF only outputs 256 bits (32 bytes) per hash iteration. So you need a ridiculous number of iterations to use up a sizable amount of RAM. The question is then at what point is enough RAM enough. Maybe use the PBDKF guidelines as a guide to the number of iterations and let the RAM usage fall where it may.