Password-Based Key Derivation Functions (PBKDF) attempt to convert a user-supplied password into a cryptographically useful binary key in such a fashion that attackers who might later obtain the key cannot determine the original password. The struggle to achieve this has an interesting history . . .

The value of one-way functions
The first PBKDFs were simple hash functions. The reasoning was that it was better to store the hash of user's password than the password itself. That way, if a website were to leak its users' stored account information, only the hashes of its users' passwords would be revealed, not the passwords themselves. The powerful feature of any cryptographically strong hash function is that it cannot be “reversed.” It's a one-way function. So, to verify a user's login and the correctness of their password, the site merely had to re-hash the candidate password to verify that its hash matched what was previously stored. But attackers soon realized that if they could not go “backwards” with a hash function, they could go forwards a great many times very quickly. This saw the development of “rainbow tables” and other means to defeat the well known one-way hash functions.

Let's add some salt
Keyed hashing functions were then introduced to add “salt” to password hashing to thwart these hash pre-computation attacks. “Salt” effectively created a custom hash function for every translation of a password into a key. A new “salt” value would be chosen randomly whenever a password was being hashed. The salt would be used to “key the hash” and the salt which was used as the key would be stored alongside the salted and hashed password for use when it was necessary to rehash a user's password for verification. This solution prevented pre-computation attacks. But the trouble was that the keyed hashing operations (such as HMAC) were based upon cryptographic hashing functions that were originally chosen to be, among other things, very fast. So now an attacker who had obtained a leaked password database (including the password's corresponding salt value) would run the keyed hash function through a large password dictionary to search for the input password that delivered the proper hashed result. If it could be found, the attacker would have discovered the user's password through a brute force search and could logon as the user.

Let's do it a bunch of times
The next step in PBKDF evolution was “iteration”: If performing one keyed hash operation was too fast and easy because attackers could still use brute force guessing, we'd perform one hundred, or one thousand, or ten thousand! The idea was to chain the output of the first iteration of the function into the input of the second iteration, and so on. Since each iteration performing a cryptographically complex conversion of its input to its output, there was no way to short-circuit the process. The only way to correctly determine the final result was to “iterate” through every intermediate result. Thus the official PBKDF(2) function was born.

GPUs, FPGAs and ASICs are faster than CPUs
It didn't take attackers long to realize that the specialized computational architecture of the graphics processing units (GPUs) built into high-end graphics cards was perfectly suited to dramatically accelerating common hashing functions. This was the same realization that allowed virtual currency “mining” ‑ which is also based upon cryptographic hash functions ‑ to be first accelerated by GPUs, then field-programmable gate arrays (FPGAs) and finally by fully custom application specific integrated circuits (ASICs).

Where GPUs, FPGAs and ASICs cannot follow
When Colin Percival wanted a “stronger‑than‑PBKDF2” password encryptor for his TARSNAP online cloud backup system, he invented one. Colin realized that while GPUs, FPGAs and ASICs were extremely good at crunching numbers within a somewhat confined space ‑ they had excellent computational resources ‑ he noted that they didn't have much local memory resource. And there's a very good reason for this: memory occupies space. And lots of memory occupies lots of space. High-performance cache memory is “static memory” which occupies even more space than the “dynamic memory” which is what we're referring to when we refer to our computer's main memory. Colin conceived of an algorithm that would be “memory hard,” or more specifically “sequentially memory hard”, and Scrypt was born.

Colin's innovation uses Scrypt's input password and salt to fill a very large region of memory with deterministic pseudo-random data. (“Deterministic” simply means that every time the same password and salt are given, the large memory region is filled with exactly the same data.) Once the large memory region is filled, its pseudo-random contents is used to direct a series of operations that alter its contents and simultaneously determines the eventual outcome of the process. The process is cleverly designed so that it is extremely difficult to determine in advance which regions of memory will be referenced, and when. So either all of the memory needs to be present at once, or excessively time-consuming computations must be used to “fake it”. Colin's algorithm has proven to be extremely hostile to “hardware acceleration.” Although GPUs, FPGAs and ASICs may have access to fast “on-chip” memory of up to 128k, none have access to multiple megabytes of memory. The only way for them to access Scrypt's deliberately large memory array is to go “off chip.” And off-chip memory reads and writes, which Scrypt can be easily made to require, are excruciatingly slow by comparison. Consequently, no substantial current or foreseeable hardware acceleration appears to be feasible.

SQRL's identity authentication needs to be EXTRA-well protected from abuse
When a user backs up and exports their identity master key for long-term safe keeping, its export password must be extremely well encrypted to make brute force guessing completely infeasible. Hopefully, the exported password will never fall into an attacker's hands. But if it should, requiring a full minute to process and then test every single password guess, in a way that cannot be shortened using any known hardware acceleration tricks, will quickly discourage even the most determined attacker. Yet, for the legitimate owner of the backed up master key, waiting a full minute, or perhaps even more ‑ only in the rare event that the master key backup must be decrypted and used ‑ doesn't impose any sort of operational barrier.

PBKDF2 with Scrypt as its PRF
The formal definition of the standard PBDKF2 function allows for a “plug-in” pseudo-random function (PRF). We provide for SQRL's requirement of a very-long-executing, highly-acceleration-resistant, non-short-circuitable, cryptographically secure, password based key derivation function by using Colin's Scrypt function in a PBKDF2-style iterative construction:

As shown in the schematic diagram above, the first iteration of Scrypt takes the user's password and a pseudo-random salt, and processes it in its normal fashion. The result of that first round becomes the salt for the second round, and the output also participates in the collective XORing of every round's output to form the final result 32-byte, 256-bit password based key. Successive rounds proceed in this fashion, using the user's password in every case and with each round taking the preceding round's output as its salt input.

A significant advantage to the “deliberately time-consuming” iterative design of this algorithm, is that its successive rounds can be terminated either after some prescribed amount of time has been consumed or after a prescribed total iteration count. SQRL uses BOTH of these modes:

Setting a password for device lock or key export
When SQRL sets or reset a password, either for a device or SQRL client's authentication, or before exporting a key for external backup, the user may specify the length of time the device should spend working to encrypt the password. The user should keep in mind that the same device will require the same amount of time to later decrypt the password on the same device, and that the longer the password-setting time is, the more encryption iterations the device will complete in the allotted time, and the longer any attacker will need to wait between guesses. The final iteration count, whatever it is, is stored alongside the encrypted password and the per-encryption pseudo-random salt for later use in decrypting the password.

Verifying the password to unlock a device or import a saved key
Whenever SQRL needs to reverse the encryption process to verify a user's encrypted password, it uses (and must use) the exact iteration count that was used and saved along with the password when the password was set. If the verification is being done on the device that originally set the password, the verification will require the same amount of time to process. If the verification is being performed on a faster device ‑ for example, a desktop computer instead of a mobile smartphone ‑ the verification will likely consume less time than was required to set the password on the slower device.

In addition to the user's password and a pseudo-random salt, Colin's Scrypt algorithm accepts two parameters (N & r) to govern its memory usage, one parameter (p) to allow parallel processing to improve the algorithm's performance, and a final parameter to specify the algorithm's output size in bytes.

Starting at the end and working backward:

• Output length = 32 bytes: SQRL uses 256 bits (32 bytes) for nearly all of its internal keys, ciphers, and data paths. Although the length of the user's password will inherently be variable, the pseudo-random salt used to seed the first Scrypt iteration will be 32 bytes, as will every output from each Scrypt function iteration.
• ‘p = 1’ to disable parallelism: Colin designed Scrypt to optionally allow multiple processors to chew on the separate subsets of the overall problem at the same time, in parallel. Since this is expressly not what we want for our application, SQRL always sets Scrypt's ‘p’ parameter equal to 1 (so that only 1 processor can be used at a time).
• ‘N = 512’ and ‘r = 256’ to set memory requirements: Scrypt's ‘r’ parameter controls how much data is processed within its shortest time window. We need this to be large enough to thoroughly “bust the fast local cache” of whatever platform Scrypt is running on. The amount of memory used is 256r, so SQRL sets r = 256 to use 64 Kbytes within Scrypt's shortest time window.
  
  Scrypt's total (large) memory-occupying footprint requirement is set by ‘N’ which is ‘N’ times half the memory specified by the ‘r’ parameter ‑ so 32,768 bytes times ‘N’. Therefore, with r = 256 and N = 512, Scrypt's large memory consumption footprint is 16 megabytes. This RAM requirement was chosen to be far beyond the amount of fast local cache RAM available to any current or probable near-term GPU, FPGA or ASIC chip (typically on the order of 128 Kbytes), while also being small enough to be readily available to SQRL client applications running on mobile smartphone platforms.
  
  Note that since ‘N’ will always be a power of 2, it is represented within SQRL clients and in SQRL's secure storage format as log₂(N). This allows it to be stored in a single byte while providing a huge dynamic range to address future needs. The byte-size representation (n) can be converted into its actual value (N) by shifting the binary value 1 left ‘n’ times, represented in the C language as (1<<n). Therefore, the value for N of 512 would be a value of 9 for n.

In order to properly hash multilingual passwords in a client-transparent fashion, we need to agree upon a byte-level encoding. Fortunately, and largely thanks to the international success of the Internet's World Wide Web, the world has solved this problem with the UTF-8 variable-length encoding of the UCS (universal character set). Although “NUL” is technically a character, we will herewith specify that NUL is invalid for SQRL passwords and may thereby be used as the string terminator.
Windows and WINE users may download and experiment with the results of this password hashing development: GRC's EnScrypt (71Kb). It may be used to experiment with this iterative Scrypt hashing solution, and developers can use it to verify the cross-platform interoperability of their independent implementations of this function. EnScrypt's console output when it is started without parameters:

As documented by the program's usage information, passwords, salt, iteration counts and execution duration may be specified in order to experiment with the operation of this function. Note that an iteration count of 1 (parameter ‘1i’) will produce the same result as calling the Scrypt by itself.

Independent implementations of this function may be verified by their production of these correct results. At the time of this page's first publication, three independently written EnScrypt functions have produced identical results. (Note that the measured elapsed time will vary with the system's performance):

enscrypt 1i
  Password: <null>
      Salt: <null>
Iterations: 1

Output Key: a8ea62a6e1bfd20e4275011595307aa302645c1801600ef5cd79bf9d884d911c
Iterations: 1
   Elapsed: 0.053 seconds

enscrypt 100i
  Password: <null>
      Salt: <null>
Iterations: 100

Output Key: 45a42a01709a0012a37b7b6874cf16623543409d19e7740ed96741d2e99aab67
Iterations: 100
   Elapsed: 5.671 seconds

enscrypt 1000i
  Password: <null>
      Salt: <null>
Iterations: 1,000

Output Key: 3f671adf47d2b1744b1bf9b50248cc71f2a58e8d2b43c76edb1d2a2c200907f5
Iterations: 1,000
   Elapsed: 57.199 seconds

enscrypt password 123i
  Password: password
      Salt: <null>
Iterations: 123

Output Key: 129d96d1e735618517259416a605be7094c2856a53c14ef7d4e4ba8e4ea36aeb
Iterations: 123
   Elapsed: 7.023 seconds

enscrypt password 0000000000000000000000000000000000000000000000000000000000000000 123i
  Password: password
      Salt: 0000000000000000000000000000000000000000000000000000000000000000
Iterations: 123

Output Key: 2f30b9d4e5c48056177ff90a6cc9da04b648a7e8451dfa60da56c148187f6a7d
Iterations: 123
   Elapsed: 6.996 seconds