Cryptographic Authentication

In computer applications, basic authentication is typically done using a username and a secret "password" known only to a specific user and a server (often also the system administrator).

You have used this username/password authentication scheme countless times, logging in to email servers, web servers, your computer, your network operating system, etc. Users are notoriously bad at choosing good (difficult to crack) passwords. Various schemes can be employed to force users to choose a new password periodically (to prevent one being used too long, which increases chance of compromise), or require minimum length or password complexity (e.g. at least one from each of lower case, upper case, numeric and/or special characters).


Password Strength

Unfortunately increased password complexity does not increase password strength very much (esp. using "hacker spelling", like 3 for E, 4 for A, 0 for O - that is the first thing they check). The main increase in password strength comes from increased password length (ideally over 12 characters). Assuming no common mistakes are made (like using common English words, names, etc), password strength depends on the number of possible passwords must be checked. This is n raised to the mth power, where n = number of possible characters in each position (character set size), and m = password length. For only one case alpha (or case-insensitive alpha), m = 26. Using both upper and lower case increases m to 52, using numeric characters (0..9) increases m by another 10, and using special characters increases m about another 10.

Typical character sets for choosing passwords are:

26    a..z   or   A..Z

52    a..z  and  A..Z

62    a..z, A..Z and 0..9

72    a..z, A..Z, 0..9 plus "special characters" !@#$%^&*()

Here is a table that shows the relative strength of passwords with various values of m (character set size, across the top) and n (password length, down the left side). The table values are in "scientific notation", e.g. 1.19E+07 means 1.19 x 107 or in conventional notation, 11,900,000.

pw strength

As you can see, you must go from a character set size of 26 characters (e.g. a-z) to one of 52 characters (increase of 26) to get the same increase as going from 9 character long passwords to 11 character long passwords (increase of 2). Using all 4 characters sets compared to just upper and lower alpha gives even less marginal benefit. 11 character passwords with only upper and lower alpha characters are about as strong as 10 character using all four character sets.

Increasing the character set size makes it FAR harder for users to remember the password (think you can remember "6t4&yyH2" without writing it down?). Strength goes up RAPIDLY with increasing length, but only slowly with increasing character set size. The password "Purple&daizy" has a strength of 3.23E+21, while "6t4&yyH2" has a strength of 7.22E+14. The long (but easy to remember) password is 4.4 million times stronger than the short (but difficult to remember) one. Use longer passwords (at least 12 characters if allowed), with only limited character sets, including English-like words (ideally with some minor misspellings). Most randomly generated passwords are almost impossible for users to remember. Some systems rate user chosen passwords as weak, medium or strong. Most of these are not very accurate, unless the developers understand the above analysis. Most would rate "6t4&yyH2" as very strong.


Attacks on Password Lists on Servers

With most username/password system, the server must contain a list of passwords for all users. This is the source of most massive security breaches against websites. If the passwords are kept in plaintext, it is not difficult for a hacker to get access to your server, and steal ALL user passwords. To combat this, server designers hash the stored passwords, e.g. store the password hashed by SHA1 on the server, instead of the password itself. When the user logs in, their client software hashes the entered password and sends the hash. The server compares the received hash against the stored hash of that user's password. If they match, then the user knew the correct password. Because hash algorithms are "one way" (irreversible) hackers cannot figure out the user's actual password given the hash. But a hacker can try a large number of passwords (computing a hash of each one) and compare the computed hashes against the hashed password stored for that user, to discover that user's original password. Even with today's computers, and working with a stolen hashed password list on the hacker's own computer, this can take a while. It can take even longer if the hashing is done correctly with "salt" and "slow algorithms". For details, see this writeup. Not many servers have their password list protected this well. Where Sixscape keeps password lists on servers (e.g. for use until the user obtains a client certificate), we use this scheme. It is very difficult for a hacker to obtain even one user's password, let alone the passwords of all users. It is still possible to create hashes of common passwords and look for those hashes on the server's hashed password list, so a good system should not allow any passwords from these well known lists (see Dictionary Attacks).

With strong client authentication using client digital certs, there is no need to have that dangerous list of passwords (even ones hashed with salt) on the server at all. There is no need for the user to enter a username or password, or for those to be sent from client to server. The cryptographic challenge is millions of times stronger than any password scheme, and the username is included in (or can be derived from) the supplied client digital certificate. For example, you can use the supplied email address as the UserID or you can map the supplied email address to the user's UserID via a database. Email addresses of necessity are globally unique for a given user. Since there is no password list on the server, hackers cannot do a massive security breach on secure servers that use cryptographic authentication, even if they obtain root access to the server.


Dictionary Attacks

There are easy to obtain dictionaries of the most commonly used 10,000 or so passwords. It is possible for a hacker to try all of these very quickly against a stored hashed password from the server. Some 90% of the passwords commonly used can be found among the top 1000 on this list. Some organizations check user's passwords against such lists periodically (or even brute force test for short passwords), and any users whose password is discovered during such scans gets a stern warning to create a stronger password with information on how to do it. In some cases, their account might be locked, and the user must obtain a new password from the administrator before they can log in again.


Packet Sniffer Attacks

If the connection between client and server is in plaintext (unencrypted), the hacker need only sniff the network traffic anywhere along the path that they have access. Very powerful network sniffing tools are available free today, e.g. WireShark. The username and password will be easily found among the sniffed traffic. This is quite easy, depending on where the hacker might have access (e.g. via a compromised server in a subnet).

Adding SSL/TLS helps a lot here. Any network sniffer between the client and server will see only encrypted information (assuming the SSL/TLS wasn't compromised, e.g. by getting the server to use a compromised certificate). It is common practice today to send plaintext username and password authentication inside an SSL/TLS encrypted connection.

I once wrote a hacking tool that took the output of a packet sniffer and captured all traffic on port 110 (POP3) and 143 (IMAP), looking for email logins. After a few hours running on the , everyone's email retrievals (including their username and password) were easily captured to a file. This is why you should use POP3S (995) or IMAPS (993). Similarly, SMTP should use SMTPS (465) or SMTP/TLS (25) for transmissions from your email client to your email server. This requires a server cert on your email server, and client and server software that support the secure versions of the email protocols (most do today).


The really bad news for passwords

Today it is easy to infect a target computer with a keyboard sniffer that can capture everything typed. If someone has done this to your computer, even 20 character long passwords are easy for the hacker to obtain. It doesn't matter if the password is echoed as "*" characters when you log in - they are watching and capturing what keys you press on your keyboard. The "*" characters echoed during password entry only prevent someone from looking over your shoulder as you enter your password.

The only defense against a keyboard sniffer is to not enter any password via your keyboard. In theory "One Time Passwords" are a defense against this (even if the hacker captures a One Time Password, they can't use it), but they have their own problems. The only real defense is to use cryptographic authentication.


Synchronized Time Tokens

RSA (and other companies) produce small tokens (e.g. "SecureID") that continually display time synchronized OTPs (One Time Passwords). The token and the server stay in synchronization (and continually resynchronize as the system is used). This can be used as the password, or in addition to a password (for two factor authentication - something you have and something you know).

Hackers have figured out how to duplicate the algorithms that generate the "random" numbers  (they are not really random, they are psuedo-random). Such schemes are mostly broken now, and should not be depended on for security.


Other "One Time Password" (OTP) Schemes

There are numerous other ways to provide users with a list of one-time passwords (each time one password is used, it is discarded, and the next one in the list is valid). Each of these schemes has weaknesses, vulnerabilities, or serious inconveniences (like getting out of sync). Unless the OTPs are truly random, it has proven possible for hackers to figure out how they were generated by an algorithm. If they are truly random (e.g. generated from rolling dice, or sampling white noise), it is really difficult to supply these to users in a secure manner.

This is really the same problem encountered with "One Time Pad" encryption schemes. They are essentially uncrackable (unless the bad guy can steal a copy of the One Time Pad), but it is very difficult to securely distribute One Time Pads to all participants. Each message should use a unique page from the One Time Pad, so there is the issue of synchronization between participants (which page from the pad do I use for this message?).  Also, if any copy of the One Time Pad is compromised, all have been compromised, since they are all the same. The military used to employ tons of clerks to generate random strings of characters for One Time Pads from throwing dice, etc.

For some reason, people keep inventing One Time Password authentication schemes (and even One Time Pad encryption schemes), in spite of the almost intractable problems of deployment and use.


Cryptographic Authentication

There are a number of schemes to use cryptography to replace username/password authentication. The best schemes depend on public/private key (asymmetric key) cryptography, digital certificates and PKI.

One approach that works over a single link (like client to server) is to use cryptographic algorithms in conjunction with public key digital certificates to do a "cryptographic challenge". An object's "identity" resides in their private key (not in the public key digital certificate). The challenge is to prove the object's ownership of that private key, without revealing it (without sending it over the Internet). This is done by using the public key certificate corresponding to the object's private key (after establishing that the presented public key is the correct one for the object being authenticated). One end does a cryptographic challenge to the other, which can only be answered correctly if that end has the relevant private key. For server to client authentication, the client creates a random character string and encrypts it with the public key of the server (obtained from a validated public key digital certificate). The encrypted string is sent to the server, which decrypts it with its private key and returns it to the client. If the returned string matches the original string, that is proof of ownership of the private key corresponding to the public key used, which is considered proof of identity. At no point is the private key sent over the Internet.

For an example of how this works in a real world system, see the writeup on SSL/TLS.

Note that SSL/TLS works only over a single network link (e.g. between a client and a server). Another scheme that works end to end (over any number of insecure nodes) is S/MIME, commonly used to secure e-mail. Here a digital signature can provide sender to recipient authentication. With basic S/MIME, there is no recipient to sender authentication, but the recipient can always provide sender-to-recipient authentication to the original sender by replying to the message with another, digitally signed message. There is an optional automatically sent digitally signed receipt possible with S/MIME that can provide recipient to sender authentication, but it is not widely used.


Very Strong Cryptographic Authentication

If someone can steal your private key, they can assume your identity. They may also need to know some passphrase that unlocks access to your private key, but that is usually not difficult to obtain. By default, public/private keys are generated in, and used in, your main computer's CPU and memory. They typically are kept on a disk file (possibly encrypted, but again, this can be overcome).

The solution is to create and use private keys in a cryptographic security token. These look like USB flash drives, but have much less memory (maybe only 64Kbytes or so), but also include a tiny CPU able to do cryptographic algorithms, including RSA. They are protected according to the FIPS 140-2 standard, which makes it very difficult to extract the private key. To use the private key, you send the thing to be encrypted or decrypted with the private key into the security token (via USB or wireless). The token does the encryption or decryption and returns the result (via USB or wireless). The private key is created in, and never leaves, the security token. If you remove the security token from the computer, your identity goes with the token. If you plug it into another computer, your public key certificate and private key are available on that computer (this makes your key material portable).

The problem is key backup and recovery is much more difficult, if you generate the keypair inside the token. For digital signatures this is not a problem, since you can always generate a new keypair. For encrypted files, losing the private key is a major disaster, since any files encrypted with it can no longer be decrypted. The solution is to generate the public/private keypair as a soft token (in the main CPU and memory), then load that key material into one or more cryptographic tokens (with PKCS #11 compliant tokens, you can load a private key into a token, you just cannot extract it once there). The original keypair can be securely backed up (e.g. in a physical safe) and then the soft token is carefully destroyed. This is best done on a computer that is not connected to the Internet (e.g. a virtual machine with no network connection, or an isolated notebook computer).

For use with mobile devices, conventional USB tokens are difficult or impossible to use. Tokens that connect via WiFi or Bluetooth will work with both mobile devices and PCs. Hopefully phone vendors will soon include the circuitry found in a cryptographic token in the mobile device itself, and then your mobile device can become your security token. This is one of the most useful developments possible with mobile devices.

Why Doesn't Everyone Use Cryptographic Authentication?

Virtually all SSL/TLS client and server software (web, email, etc) supports this optional strong client authentication. So why doesn't everyone use it today, given the problems with username/password authentication (even with SSL/TLS)? Securely issuing, distributing and managing a separate client certificate for each user has typically been a very difficult and/or expensive proposition. This is the problem Sixscape Communications has solved with its Identity Registration Protocol (IRP) and infrastructure.