100x100 SQRL Logo   Secure Quick Reliable Login
A highly secure, comprehensive, easy-to-use replacement
for usernames, passwords, reminders, one-time-code
authenticators . . . and everything else.
SQRL's use of the ‘SCrypt’ Password
Based Key Definition Function
The path that brought us here
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.

That's all good. But SQRL needs a bit more.

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.

SQRL needed a solution that was not only strongly
acceleration resistant... but also vastly slower.
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.

How many rounds?
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.

The SCRYPT function parameters
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:

Multilingual password handling via null-terminated UTF-8
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.
GRC's “EnScrypt” Scrypt-based password hashing implementation

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.

“EnScrypt” verification vectors
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

Secure QR Login (SQRL) Documentation:

Jump to top of page
Gibson Research Corporation is owned and operated by Steve Gibson.  The contents
of this page are Copyright (c) 2016 Gibson Research Corporation. SpinRite, ShieldsUP,
NanoProbe, and any other indicated trademarks are registered trademarks of Gibson
Research Corporation, Laguna Hills, CA, USA. GRC's web and customer privacy policy.
Jump to top of page

Last Edit: Aug 02, 2015 at 14:17 (696.06 days ago)Viewed 7 times per day