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 Detailed Cryptographic Design
Complete SQRL Crypto Design
The complete SQRL authenticator architecture.

Let's begin by examining SQRL's cryptographic design at the interconnected functional block level. Later, we'll examine the critical and non-obvious functions—“Crypto Signature” & “Make Public Key.”

When beautiful theory collides with grubby reality . . .
The schematic above provides for every feature discussed in the previous two pages.

If you look again at the simplified schematic shown near the top of the first intro page, you'll see the essence of the design, which was where we initially began. This original pure solution delivers perfect remote security, but it lacks any provision for local abuse protection. If smartphones perfectly protected their applications from use by non-owners, and if it could be safe to export non-encrypted master identity keys, then that first diagram would be the finished solution. And it would be extremely secure. But we know that smartphones in the real (grubby) world are treated casually. People allow others to use and play with their phones, and there's probably no other application needing abuse prevention security safeguards more than a user's universal identity authenticator.

Consequently, it was necessary to add some additional functions to the conceptually pure design to make it practical and safe for use in the real world.

Allowing for a changeable password
The “Crypto Signature” and “Make Public Key” functions both take long 256-bit values as their “Private Key” input. We obtain this value from an HMAC-SHA256 (Hashed Message Authentication Code using a 256-bit Secure Hash Algorithm) where the HMAC is keyed with the user's master key and the authenticating domain name is the message to be hashed. For this system to work, the master key input to the HMAC function must never change even as the user's password is changed. The HMAC key is the user's ultimate root identification. But in a real-world implementation, we want to allow (almost require) the user to provide a password every time the system is used to prove that they are the person holding the phone and authenticating. We implement this password function by processing the user's password through a password-based key definition function (PBKDF — the well-known Scrypt sequential memory-hard function) which generates a 256-bit result. This value is then exclusive or'd (XOR) with the user's current master identity key to produce the never-changing value which keys the HMAC private key generating function. An XOR function is used because, as the user's chosen password is changed, the user's master key can be updated to produce a consistent 256-bit value from the XOR output.

ONLY IF the user enters the correct password will the output of the PBKDF function correctly XOR with the current value of the identity master key to produce the correct original master key value which keys the private key generating HMAC function.

Every time the user changes their identity authentication password—including the first time when it is changed from a null password—the identity master key's value is updated to preserve the post-XOR value which keys the private key generating HMAC function.

Verifying the user's password
Because present-day smartphones do not provide spoof-proof “who's holding me now” authentication, the SQRL application must provide its own access control. Therefore, many aspects of the user interface require the user to prove their identity by re-entering their password. But the XOR solution described thus far only allows us to apply a password. It provides no means for verifying it. For that, we add the “Password Verify” function. See the diagram above. The Password Verifier stores a 128-bit “verification” piece of the entire 256-bit output of the PBKDF function. Here's how it works:

When a brand new identity is first created, local device's cryptographically secure pseudo random number generator (CSPRNG), augmented by entropy streamed in from the device's camera(s) for five seconds (because SQRL is not going to rely solely upon any platform's CSPRNG), generates the user's identity master key. The system's secure PBKDF Scrypt function should be used for this.

The user will be prompted to enter and re-enter a master SQRL password which will be used to prove their identity to the application whenever they wish to adjust settings, import or export a backup master key, or identify and authenticate themselves to a remote website. Whenever a new password is being set, 64-bits of random “salt” will be created for input to Script's PBKFD2 functions. Then, driven by the user's supplied and confirmed new password, the Scrypt PBKDF function will generate a 256-bit value which will be XOR'd with the user's master key and that result used to key the private key generating HMAC function.

To verify future password reentry, that final 256-bit password output value is then hashed once more to produce a derived 256-bit value. The lower 128 bits of that value will be saved as the password verifier so that future password entries can be quickly verified. The single additional hashing yields a verification value that gives away nothing of the hash's previous 256-bit output

Thwarting brute-force key-guessing attacks
The trouble is, if the SQRL system has the free-standing offline capability to verify its user's password, as it must to deliver practical ease-of-use, this inherently renders the system vulnerable to hardware-based brute-force password guessing attacks. Remember though, thanks to the fundamental architecture of the SQRL system, we are not talking about any form of remote attack. Here, we are specifically addressing the situation where an extremely determined adversary is able to obtain a decrypted memory snapshot of the user's smartphone, and wishes to crack the user's access password after obtaining the password verifier. The system's design makes even doing that difficult and extremely time consuming.

As mentioned above, the SQRL system employs the “Scrypt” function as its PBKDF. Scrypt is a so-called “sequential memory hard” function which was deliberately designed to require much more memory for its execution than traditional cryptographic hashing functions. This means that it actively resists acceleration by GPU's and FPGA's which inherently lack the “per-function” memory resources which Scrypt requires. Therefore, the first prong of defense is our use of a memory hard PBKDF for password processing.

The SQRL application uses Scrypt for password processing in two different “strengths”: a half-second strength used for on-the-fly user authentication, and the much longer 60-second strength used to protect the user's exported identity master key. These varying strengths balance cracking difficulty with convenience and relative threat level. Half a second is completely acceptable for interactive user-interface password verification, yet it still renders brute-force attacks inefficient enough as to be impractical. This time-targeted strengthening allows the entire password verification system to dynamically adapt to whatever platform it is installed upon, and to maintain a fixed half-second password verification time even as the speed and power of smartphones increases over time.

As discussed on the user experience page, since an exported identity master key potentially exposes its user to a password guessing attack, exported keys are encrypted under an Scrypt strength which requires a full 60 seconds of extremely acceleration resistant processing by the smartphone. Since importing and exporting master keys is performed infrequently, a 60-second wait is a useful and non-burdensome precaution for allowing the user's master key to exist outside of the phone.

Now that we have examined all aspects of the overall SQRL cryptographic architecture, let's look at how this structure supports the various user interactions described on the previous user experience page:

Initial identity creation
The exact sequence of events would be up to the SQRL application author. But for the sake of discussion, let's assume that the user begins with an empty SQRL app and the first thing they do, prompted by the app since it's the only thing available to do in an empty app, is to create a new user identity. It would be possible at this point to import an existing user's identity using their identity master key QR code, but we'll discuss that separately, below.

The user should probably first be asked to enter and re-enter a secure password to protect their identity. A built-in password strength meter should encourage them to use a longish password with a variety of character element types, etc. And it might also discourage their use of their “standard” password, which would help to improve their security. (“Oh, I know the password my mom always uses.”) They should also be instructed and encouraged to write this down and store it for safe keeping. We discuss this system's password recovery facility below, but there is no third-party to take responsibility.

Once the user has verified their ability to reenter their password, the app should ask them to wave the smartphone around until it chimes. The application would send the platform's random number generator, and five seconds of the smartphone's streaming video, through a secure SHA256 PBKDF2 function to generate the user's initial encrypted master key. This would be saved as shown above as their 256-bit identity master key.

Master identity key import and export
We consider the master identity key to be encrypted under the user's password since the “effective master key” which is applied to the HMAC-SHA256 private key hash never changes. It is the result of Scrypt PBKDF processing the password and XORing the result with the encrypted master key. The encrypted master key changes as necessary to balance any changes made to the password so that the XOR's product remains constant. Therefore, the user's exported master key is simply the currently saved 256-bit identity master key . . . with its associated password implied. Since the system's chosen Scrypt strength also directly affects the final output, those parameters must always be exported and imported along with the current master key.

Since the same password that was in place during the master key's export must be used after that key has been imported into the same or another device, the exported master key QR code also contains the 64-bit nonce salt, the 128-bit password verifier and the Scrypt strength parameter to allow for password verification after the master key has been imported. The system recognizes that the addition of password verification information enables an offline brute-force attack using only the information contained in the exported QR code. So the computational burden of verifying every password is increased to 60-seconds. During the exportation process, the system uses an Scrypt strength that yields 60 seconds of processing on the exporting smartphone. During this time a percentage complete indication is displayed.

Therefore, exportation of the user's master key converts the currently saved 256-bit master key into a QR code graphic for display, copying, eMailing, etc. The user would be instructed that it is “encrypted” by their current password, so it should be stored somewhere securely and the matching password at the time of its export should also be written down and saved alongside the QR code. (The user might change their working password after the export, but the exported key would be encrypted by their previous password.)

Importation of a master identity key would occur either to add a new user identity to the application or to overwrite an existing identity. In either case, the password which was associated with that key at the time it was exported MUST be provided to catch entry errors. (This, of course, protects the user from theft of their identity master key.)

Forgotten or locked-out password recovery
The procedure for recovering a forgotten password, or restoring operation after a password-guessing lockout, is identical to master key import. An existing account is overwritten by importing a previously exported master key QR code image, and the password that was in use at the time of the previous key export must be provided to obtain the information required for the password verification procedure.

What about the mysterious “Make Public Key”
and “Crypto Signature” functions?

SQRL's underlying crypto technology

The primary enabling feature of the SQRL system's underlying crypto technology is its ability to use the randomly distributed arbitrary output of the 256-bit SHA256 hash function as its private key. It is that singular feature which enables everything else. To achieve that, we employ elliptic curve public key cryptography as opposed to older “products of primes” RSA-style cryptography which inherently lacks the required keying flexibility.

The other necessary feature offered by elliptic curves over RSA prime factorization cryptography is the performance of key generation, digest signing and signature verification. For this system to be feasible on the authenticating server's end, signature verification must be extremely fast and efficient . . . and we do have that.

The SQRL system uses the so-called “25519” (as in 2255-19) elliptic curve, which was developed by and has been extensively studied by University of Illinois mathematician, cryptographer, programmer, and research professor of computer science, Daniel Julius Bernstein, who is well know by his initials DJB or more often just “djb.” He maintains the website at the double-take worthy domain name of: “cr.yp.to”.

What is Curve25519's security target?

As Dan discusses in the papers above, his security target was at least or better than 2128 or roughly equivalent to a traditional RSA key length of 3,000 bits. Web sites have long been using RSA at 1,024 bits (never known to be broken) and are just beginning to switch up to 2,048, mostly for the sake of prudence and marketing. (In mid-2013 Google was making a lot of noise about their move to 2,048 bit RSA keys by the end of 2013.) So at an equivalent strength of approximately 3,000 RSA bits, Dan's “25519” elliptic curve-based system appears to provide very good long term protection, even for very short lived signatures.

Since the SQRL system uses a unique public/private key pair for every website, even if it were possible to somehow crack an instance of authentication security (and no one knows how to do that in any reasonable length of time) only that one website's authentication would be compromised. Every other site authenticates with its own unique keys.

And finally, Dan states that the best known attacks appear to require a minimum of 2140 operations, so he exceeded even his original security target by a factor of 4,096.

Having established an understanding of the complete SQRL architecture, let's now turn to the topic of: Attacks, weaknesses and vulnerabilities.

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) 2014 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 (31.30 days ago)Viewed 15 times per day