pbhogan/scrypt — pull request #8 by nomoon (2012-05-05 22:55:45+00:00)
Title: Security concerns, cleanups/fixes, and user-tunable salt and keysize.

Looking over the code, I noticed a few things about the key generation process that seem a bit out of sorts. I've worked on some fixes and improvements in my own fork that mean generating non-backwards-compatible strings, but don't impair the system's ability to easily compare passwords made with older versions. Also, they should help this ruby Scrypt implementation play nice with other potential Scrypt implementations.

Here's a summary of each issue and my proposed fix/change:

**1. SCrypt function key-length hardcoded to 256 bytes.**

While the underlying function allows for a user-selectable keylength, the `scrypt_ext.c` C code enforces a 256 byte length on every generated key. This isn't inherently undesirable, though we aren't attempting to generate 2048-bit keys, so it doesn't seem like we'd have any need for 7 extra blocks from the PBKDF2 function (Since SCrypt uses PBKDF2-SHA256 in it's final step, which means it generates 256-bit blocks) on every call.

Overall, it seems like it may be desirable to be able to tell the C function exactly how long we want our key to be, whether small or enormous.

**2. Potentially-excessive (and non-tunable) salts.**

Each salt generated is 32 bytes. This means that hypothetically we wouldn't expect to reach the birthday paradox (50% chance of two users having the same salt) until we had 3.40282367 × 10^38 users. A length of 8-10 bytes (64-80 bits) would almost-certainly be sufficient to prevent non-unique salts in most systems. A 64-bit salt would become questionable around the 4.2 billion users mark, while an 80-bit salt around the 1 trillion users mark.

In fact, it would probably be best if people could tune their salt-length, and have it processable either way. Since two different random users having the same salt is a relatively minor concern overall, I chose 64 bits as default/minimum for the moment, but 80 or even a more could be acceptable.

As an addendum to the salt issues, it appears that the system currently feeds a string consisting of the cost parameters and salt hexstring into the scrypt function. It would be more portable and friendly to people implementing this elsewhere to send only the generated salt, packed from hex back into its native bytes, into the function.

**3. SHA1 on Salts and Keys (Security issue)**

This is an actual potential security issue. All salts and keys are currently hashed with SHA1 before being placed into the hash string. Since SHA1 is a 160-bit hash, this means that the 256-bit salt and 2048-bit key are necessarily weakened down to a maximum of 160 bits of entropy each. Furthermore, since SHA1 is an older hash function which is no longer recommended for us, it is unlikely that it really offers even a full 160 bits of security.

Since we are generating cryptographically-secure random bytes for the salt, and have a key provided directly by the SCrypt function (which passes through PBKDF2-SHA256 at the end), why don't we simply encode these values in hex and store them in the string? This goes along with the first issue discussed here -- we can simply ask the SCrypt function for a key of the length we desire. Again, this is friendlier to people writing compatible implementations -- the key in the hashstring is the result of the function directly.

**New Strings and Maintaining compatibility**

I've changed the key generation process to :
* Generate a salt (of 8-32 bytes / 64-256 bits, 8/64 default) and unpack it to hex directly, padding to a minimum of 16-characters (in case of the occasional leading 0s in the value, which `unpack()` will drop). Since an old-style salt will always have 40 characters of output from `OpenSSL::Digest::SHA1.hexdigest()`), any newly-generated salt string that ends up being exactly 40 characters long will be padded with a leading '0' to 41 characters, keeping the same hex value but ensuring that old-style hashes can be detected and processed compatibly.
* The key is generated from the secret string and salt string (not including the cost params, and unpacked from its hexstring to its raw bytes) with the desired key-size in bytes specified to the C function. The results are unpacked directly to hex, and padded with leading '0's (upto `key_len * 2`) in order to ensure that the keysize of any hash can be trivially detected upon loading it.
* The default result for the new-style string is thus **exactly the same size** as the old-style one (16 characters of hex-salt plus 32 characters of hex-key), except that the key is much stronger (by inherently 96 bits) and neither the salt nor key is encumbered by the SHA1 algorithm.

I've added some specs (including the published SCrypt test vectors), docs, and comments to the code where appropriate, and I look forward to discussing these with you.

I hope this helps improve your already great Rubygem.