Reduce Database Load by Using a Redundancy Check Character for Password Validation

Introduction

The tip is related to the website authentication process in which login and password strings submitted by the user are compared against information stored in the database.

Background

Normally, new users are allowed to create custom logins, but more and more often some restrictions are placed on password strings in order to eliminate those which can be easily broken. Therefore, passwords are required to be of a certain length and must include a mix of lower case and upper case letters, numbers and special characters. Typically, only password hashes are stored in the database and during the authentication process the script creates the password hash and checks it against the information in the database.

An alternative solution

Implementing a redundancy check as the first step in validating user credentials might be a good idea. The fact is that users have a limited choice when creating their passwords, anyway. That is why, it wouldn't be much of a burden if they are required to remember an additional character appended to their password string. This extra character might be used as a check character (like a check digit in the IBAN) in order to perform an initial user validation without the need query the database. That would considerably reduce the database load especially in cases of attempted brute-force attacks (and, potentially, denial or service attacks). One must bear in mind that database systems often impose a limit on the maximum number of concurrent connections, which makes it easier for an attacker to paralyse a website. Validating a check character during the authorisation process results in much fewer useless database queries.

An example

Let's say that a new user chooses the "hillybilly" word as his login. In order to comply with the password creation rules, he comes up with the "N0t_e@Sy" string as his password. Then, he submits the login/password pair to the server. The server side script calculates a check digit (and its corresponding check character) on the basis of the two strings. The developer can employ any algorithm to to obtain check digits. This might be md5 with some extra salt added to each login/password pair. Let's say that the salt is the same in each case and it is the ")r3*..D+q }mW/~5iX-0" string.

In this example, the server side script joins the three strings, obtains their hash and then calculates the check digit value using just the last two characters of the checksum. In practice, however, the developer may use any other means to obtain a check digit on the basis of user credentials. In PHP this might be the following code:

$salt = ")r3*..D+q }mW/~5iX-0";
$hash = md5(
	$_POST[ 'login' ] // "hillybilly"
	. $_POST[ 'password' ] // "N0t_e@Sy"
	. $salt
	); 
// $hash value is now "c7759cb828b41f91fa6daeb9ba5f7cf0"

$checkDigitValue = hexdec( substr( $hash , -2 ) ); // 240
// the last two characters of the hash ("f0") have been converted to a decimal value (240)

Finally, the check digit value is used to obtain the check character. Here, everything depends on the size of a character set we want to allow within password strings:

• lower case latin letters (26)
• upper case latin letters (26)
• numbers (10)
• special characters including a space (33)

The above sums up to 95 characters. However, the ~ (tilde) character might be difficult for some users to type in so our set might be reduced to 94 characters. The rest of the code could be like this:

// convert the $checkDigitValue so that it falls within the range of 94 values (0 to 93)
$checkDigitCharacterValue = $checkDigitValue % 94; // 52

// obtain the check character using the ASCII table:
$checkCharacter = chr( 32 + $checkDigitCharacterValue ); // "T"

The server sends back the user password which now is "N0t_e@SyT". The user needs to remember just one more character.

The authentication process is analogous. The user submits his login ("hillybilly") and password ("N0t_e@SyT"). The server side script extracts the original check character from the password, calculates the check digit again and compares the result against the check character supplied by the user. If the two characters do not match there is no need to query the database. The redundancy check is fast so it might be a good idea to use some random delay mechanism and respond after a couple of seconds so that a potential attacker should not be able to figure out whether or not the check character has been correct. If the check character happens to be valid the database query needs to be performed to do the login/password hash check. However, during a potential brute-force attack only some 1 in 94 login/password pairs will require employing the database. If the developer decides to use two check characters in each password this number decreases to 1 in 8836.

History

2013.04.29

• initial version