WhyNotEncryptedPasswords

From FOAF

When the topic of using FoaF for authentication comes up, one of the most obvious potential solutions springs immediately to mind, "encrypted passwords in the FoaF instance." This page describes current-art implementations and risk in that approach.

See FoafAuthentication for other solutions and discussion of authentication using FoaF in general.

[edit] What is an encrypted password?

A "password" or "passphrase" is a small sequence of letters or words that a user provides a system, usually along with an identifier for that user, that "proves", or authenticates, to the system that this user is who they really say they are (sidestepping the issue of users sharing passwords or password theft).

A side note, the purpose of providing a user identifier along with the password is to disambiguate two people who coincidentally have chosen the same password.  In some other authentication schemes, the scheme can both identify and authenticate the user with one action or piece of information.

In some systems, particularly simpler or early database systems, passwords are stored "in the clear" or "clear text" which means without encryption. Anyone with privileged or physical access to those systems, intentional or otherwise, can simply read the passwords. Some systems, notably common usage of HTTP Basic Authentication and CVS .cvspass files, "encode" the password so that a casual glance does not reveal the password to those who don't want to know, but are still considered "in the clear".

Two common functions or algorithms for encrypting passwords are found in Unix and Unix-like systems. The 'crypt' function dates back to the original Unix systems, newer systems' crypt function also support using the MD5 message-digest algorithm as part of the encryption. Although the same function is used, the orginal encryption is called "crypt" while the new encryption is commonly referred to as "MD5 password" or just "MD5" in context.

'crypt' is "based on the Data Encryption Standard algorithm with variations intended (among other things) to discourage use of hardware implementations of a key search." It uses a password of up to eight characters plus two "salt" characters.

The "MD5 message-digest algorithm", defined in RFC1321, "takes as input a message of arbitrary length and produces as output a 128-bit "fingerprint" or "message digest" of the input. It is conjectured that it is computationally infeasible to produce two messages having the same message digest, or to produce any message having a given prespecified target message digest." Newer implementations of the 'crypt' function support encryption using the MD5 message-digest algorithm. The function takes a password of any length, plus up to eight characters of salt, to produce the encrypted password.

Both of these algorithms are "one way", they cannot (by means known today) be "decrypted" to get the original clear text password. Instead, they are used by taking the password provided by the user plus the "salt" that is stored with the encrypted password to re-encrypt the user-provided password, where the two encrypted passwords are matched as strings. The "salt" characters are used to "mix up" the encrypted password so that when two people happen to share the same password, the resulting encrypted password isn't the same.

[edit] "Breaking" encrypted passwords.

One might ask, "if you can't decrypt a password, how can you break it?" The answer lies not in "breaking" the encrypted password but instead trying every combination of password until you find a match. If you start with common dictionary words, combinations of small words, common "joining" characters, common letter substitutions ('0' for 'O', '1' for 'l'), or words relevant to the user, it is more likely a match will be found "sooner" than "later". This is called a "dictionary attack."

Salt adds a tiny factor in, that you can't use the same dictionary list to test every password, you must encrypt the dictionary list for each salt used. This increases the time to attack a list of passwords linearly.

The original crypt function uses only eight characters of password. In the 1990's, the common password guessing program, 'crack', would typically produce many matches from a Unix "passwd" file in a matter of days or weeks. Today, that's down to hours.

Note, the crack library was created for and is used extensively by systems administrators to catch "bad" passwords and to check new passwords against current rulesets to make sure they are "good" passwords.

Unix "passwd" files used to be world-readable, and still are on many Unix systems and by tools using the same functions, based on the assumption that one couldn't quickly match the encrypted passwords. Today, most Unix systems store the encrypted passwords in a "shadow password" file that is not world-readable.

Modern password systems have moved to using the MD5 password. MD5 uses a password of potentially unlimited length, and the system or the administrator can add information to the encryption input to increase the strength of all passwords within that system. Since most users still only use a few characters in their passwords, the additional strength of the MD5 password is based primarily in the larger computation (more bits of input) and the ability to "strengthen" individual passwords unilaterally.

A key strength of both functions in modern systems, in the context of system login authentication, is that the encrypted passwords are not available (world-readable) for someone to run a dictionary attack on them.

See The Ambitious Amateur vs. crypt(3) for more in-depth evaluation of crypt and the dictionary attack.

[edit] Encrypted Passwords and FoaF

Most proposals for using encrypted passwords in FoaF instances do recommend the computationally longer MD5 password, but by providing the encrypted copy of the password and needing to standardize any additional input to the encryption algorithm to allow for third parties to authenticate a password leaves the password open for a dictionary attack. It is entirely a matter of how "good" the password is and how many matches per second can be made (which increases every day).

Alternatives to encrypted passwords use techniques that do not require matching the piece of information the user "knows" (the password) to a copy of that information stored elsewhere.

One such system is PublicKeyCryptography. In PublicKeyCryptography, two keys are created that can encrypt and decrypt data encrypted by the other key. One key is made public and the other key is kept private. While the user typically encodes the private key using a passphrase that acts like a password, it is the larger private key that acts as the signature for the user to the rest of the world.

Users can "sign" digital items using their private key, and others can "authenticate" that the information is signed by the user by 1) using the known public key for that user, and 2) by having others vouch that the public key does in fact belong to that user.

But signing an item, like a FoaF instance, is not enough to provide access to a system. Anyone can offer someone else's signed FoaF instance. What has to happen is that the system has to make sure that the person offering the signed item is the person who signed the item. One such solution is described in FoafIdentityAssurance.