Scrypt Kdf

[Kenneth]

Incryptography, scrypt (pronounced "ess crypt"[1]) is a password-based key derivation function created by Colin Percival in March 2009, originally for the Tarsnap online backup service.[2][3] The algorithm was specifically designed to make it costly to perform large-scale custom hardware attacks by requiring large amounts of memory. In 2016, the scrypt algorithm was published by IETF as RFC 7914.[4] A simplified version of scrypt is used as a proof-of-work scheme by a number of cryptocurrencies, first implemented by an anonymous programmer called ArtForz in Tenebrix and followed by Fairbrix and Litecoin soon after.[5]

A password-based key derivation function (password-based KDF) is generally designed to be computationally intensive, so that it takes a relatively long time to compute (say on the order of several hundred milliseconds). Legitimate users only need to perform the function once per operation (e.g., authentication), and so the time required is negligible. However, a brute-force attack would likely need to perform the operation billions of times, at which point the time requirements become significant and, ideally, prohibitive.

Previous password-based KDFs (such as the popular PBKDF2 from RSA Laboratories) have relatively low resource demands, meaning they do not require elaborate hardware or very much memory to perform. They are therefore easily and cheaply implemented in hardware (for instance on an ASIC or even an FPGA). This allows an attacker with sufficient resources to launch a large-scale parallel attack by building hundreds or even thousands of implementations of the algorithm in hardware and having each search a different subset of the key space. This divides the amount of time needed to complete a brute-force attack by the number of implementations available, very possibly bringing it down to a reasonable time frame.

The scrypt function is designed to hinder such attempts by raising the resource demands of the algorithm. Specifically, the algorithm is designed to use a large amount of memory compared to other password-based KDFs,[6] making the size and the cost of a hardware implementation much more expensive, and therefore limiting the amount of parallelism an attacker can use, for a given amount of financial resources.

The large memory requirements of scrypt come from a large vector of pseudorandom bit strings that are generated as part of the algorithm. Once the vector is generated, the elements of it are accessed in a pseudo-random order and combined to produce the derived key. A straightforward implementation would need to keep the entire vector in RAM so that it can be accessed as needed.

Because the elements of the vector are generated algorithmically, each element could be generated on the fly as needed, only storing one element in memory at a time and therefore cutting the memory requirements significantly. However, the generation of each element is intended to be computationally expensive, and the elements are expected to be accessed many times throughout the execution of the function. Thus there is a significant trade-off in speed to get rid of the large memory requirements.

Scrypt is used in many cryptocurrencies as a proof-of-work algorithm (more precisely, as the hash function in the Hashcash proof-of-work algorithm). It was first implemented for Tenebrix (released in September 2011) and served as the basis for Litecoin and Dogecoin, which also adopted its scrypt algorithm.[7][8] Mining of cryptocurrencies that use scrypt is often performed on graphics processing units (GPUs) since GPUs tend to have significantly more processing power (for some algorithms) compared to the CPU.[9] This led to shortages of high end GPUs due to the rising price of these currencies in the months of November and December 2013.[10]

The scrypt key derivation function was originally developedfor use in theTarsnap online backup systemand is designed to be far more secure againsthardware brute-force attacks than alternative functions such asPBKDF2orbcrypt.

We estimate that on modern (2009) hardware, if 5 seconds are spentcomputing a derived key, the cost of a hardware brute-force attackagainst scrypt is roughly 4000 times greater than the costof a similar attack against bcrypt (to find the same password), and20000 times greater than a similar attack against PBKDF2.

A simple password-based encryption utility is available as ademonstration of the scrypt key derivation function. Onmodern hardware and with default parameters, the cost of cracking thepassword on a file encrypted by scrypt enc is approximately100 billion times more than the cost of cracking the same password ona file encrypted by openssl enc; this means that afive-character password using scrypt is stronger than aten-character password using openssl.

The scrypt utility can be invoked as scrypt enc infile[outfile] to encrypt data (if outfile is notspecified, the encrypted data is written to the standard output), oras scrypt dec infile [outfile] to decrypt data (ifoutfile is not specified, the decrypted data is written tothe standard output). scrypt also supports threecommand-line options:

If the encrypted data is corrupt, scrypt dec will exit witha non-zero status. However, scrypt dec may produceoutput before it determines that the encrypted data was corrupt,so for applications which require data to be authenticated, you muststore the output of scrypt dec in a temporary location andcheck scrypt's exit code before using the decrypted data.

Functions for working with the scrypt key derivation functions originally described by Colin Percival and in Percival and Josefsson (2016) . Scrypt is a password-based key derivation function created by Colin Percival. The algorithm was specifically designed to make it costly to perform large-scale custom hardware attacks by requiring large amounts of memory.

As should be the case with any security tool, this library should be scrutinizedby anyone using it. If you find or suspect an issue with the code- please bringit to my attention and I'll spend some time trying to make sure that this tool isas secure as possible.

Version 5 is not backward compatible, but it should still be easy to migrate.Please read the api section to see what's changed. One big change that isworth noting is a name change: What used to be called hash has now beenchanged to kdf and conversely, what was kdf is now called hash.

Produces a key derivation function that uses the scrypt hash function. Thisshould be used for hashing and checking passwords as it incorporates salt as wellas HMAC intoits format. It is based on a design by Colin Percival, the author of scrypt. The formatcan be seen here.

Passwords hashed with scrypt with sufficiently-high strength values (there are 3 tweakableinput numbers) are fundamentally impervious to being cracked. I use the word "fundamental"in the literal sense, here; even if you had the resources of a large country, you would notbe able to design any hardware (whether it be GPU hardware, custom-designed hardware, orotherwise) which could crack these hashes. Ever. (For sufficiently-small definitions of"ever". At the very least "within your lifetime"; probably far longer.)

We estimate that on modern (2009) hardware, if 5 seconds are spent computing a derived key,the cost of a hardware brute-force attack against scrypt is roughly 4000 times greater than thecost of a similar attack against bcrypt (to find the same password), and 20000 times greaterthan a similar attack against PBKDF2.

There is just one con I can think of: It is a relatively new library (only been around since 2009).Cryptographers don't really like new libraries for production deployment as it has not been battletested. That being said, it is being actively used in Tarsnap(as mentioned above) and the author is very active.

As an example of how storing passwords can be done badly, take LinkedIn.In 2012, they came under firefor using unsalted hashes to store their passwords. As most commentators atthe time were focusing no salt being present, the big picture was missed.In fact, their biggest problem was that they used sha1,a very fast hash function.

The kdf has a specific format:The word "scrypt" is added as a prefix. The reason for this is becauseI am sticking to Colin Percival's (the creator of scrypt) reference implementation,whereby he prefixes scrypt in this way. The base64 encoding of the ascii "scrypt"is c2NyeXB0. The scrypt parameters are then appended. Users of scrypt normally donot change this information once it is settled upon (hence this will also look thebe identical).

As one can see from the above example, both hashes start off by looking similar (they both startwith c2NyeXB0AAwAAAAIAAAAA - as explained above), but after this, things change very rapidly.In fact, I hashed the password password1 again:

Compare this hash to the one above. Even though they start off looking similar, their outputsare vastly different (even though it is the same password being hashed). This is because ofthe random salt that has been added, ensuring that no two hashes will ever be identical,even if the password that is being hashed is the same.

Scrypt was created by Colin Percival and is licensed as 2-clause BSD.Since scrypt does not normally build as a shared library, I have includedthe source for the currently latest version of the library in thisrepository. When a new version arrives, I will update these sources.

Kelvin Wong on Bitbucket provided changes to make the libraryavailable on Mac OS X 10.6 and earlier, as well as changes to make thelibrary work more like the command-line version of scrypt bydefault. Kelvin also contributed with the unit tests, lots of crossplatform testing and work on the hash function.

It's an enjoyable and witty read, even if mathy at times, with lots of future predictions and reality modeling. Really drives across how scrypt is a fine piece of engineering. Also, it's single column with numbered pages, which earns it 100 points in my book.

3a8082e126