Simple Authentication using a Variable Length Random Challenge

This is a rough draft of an authentication / identification protocol I wrote back in February 2005.  I assume their are a few technical mistakes in this summary, though know of one or two.

REV. 3

Simple Authentication using a Variable Length Random Challenge

Andy Wright

This is an example of a simple PHP script to do, again, simple authentication using a variable byte length random challenge. I will briefly go over some of the functions included in the authentication process.

The first two variables in the script define the string used to authenticate the client server relationship. The first variable, username represents the alphanumerical string stored on the server side. The second variable, username2, also represents an alphanumerical string used for authentication on the client side. In addition to the user name, this process uses a common authority string and a password for final authentication.

The following will be presented in the order of the code execution.

The first portion of the salt string takes the MD5 hash of random integers using the mt_rand function (which is several times faster than standard rand()) and converts them in to a string of hexadecimal bits with the help of the pack function. It then uses the substr() function to truncate the hexadicimal stream starting position 0, and ending positon 8 for a total of 8 bits. You can use any size MD5 hash for the salt. For the scope of this script, it is unnecessary. However, if there was a need to do follow up authentications, this would be required to make the challenge, and peer authenticator challenge unique. Otherwise, it is possible to use a man in the middle attack to obtain two identical challenge / response negotiations, and possibly discover the random challenge. You could use SHA1 for this, but the salt is completely random and does not carry any significant data for comparison. It is simply for the initial challenge. From what I understand, this is sufficient to produce a unique random challenge for each authentication attempt.

The next step makes a random challenge stored in the variable random_challenge. The code that creates this block uses the makerand function. This function can create a string of Unicode characters including upper case letter, special characters, numbers, all variable length. The variable passed to this function is the length of the return variable key. Next, the function myhash_keyge_s2k is used to make a variable length key with the supplied salt and random characters. The third variable passed to this function defines the total number of bytes that the function should return. This is the Salted S2K algorithm as specified in the OpenPGP document (RFC 2440). Generally a MD5 hash is 128 bits long, for a total of 16 bytes. Instead, this function returns a hacked variable length MD5 hash of the random data, and the unique salt, which is 32 bytes. Not only does this make it hard to guess what type of payload is being exchanged, but it also adds a small complication when trying to extract the random challenge.

The random challenge is used by the client to make a 32 byte hash using the common authority string known by both the server and client. The salt is used to make this hash unique for multiple authentication attempts. This hash, called a peer authenticator challenge, is then transferred to the authentication server.

The server creates a comparison hash with the same data, only this time it uses the common authority string known to the server only. If the server created hash matches the peer authenticator challenge, then there is a common authority and the authentication can continue. If the common authority string does not match, the process DIES with no further communication.

Now we are back to the client. What I wanted to do was verify the user name and password at the same time. I took a variable byte hash of the peer authenticator challenge concatenated with the user name, and then encrypted this hash using the password stored on the client side. This is called 'signing the hash', and I will call this the encrypted peer credentials. The encryption method is a MD5 based block cypher (MDC – like) written by Alexander Valyalkin. The encrypted hash should generally be equal to, or twice the length of the key used to encrypt the hash. So in this example, the length of the encrypted hash is equal to the string length of the password. The password being the key used for this cypher text.

The server uses the password stored on the server to decrypt the MD5 encrypted data. The server then compares the unencrypted peer credentials and ensures that a MD5 hash of the peer authenticator challenge and the user name match the unencrypted hash. This is not possible if the password was incorrect, as it would then be unable to decrypt the hash with the credentials. If the common authority, user name, and password all match, then the client is successfully authenticated.

The implication of this is very broad. This is the basic of basic authentication example. To make it more secure, we could add an authenticator response, for example, or a message authentication code. It might be fun to use DES after a successful authentication, and then use a secondary system, such as an authenticator response to make it a little more secure.

I give no guarantee that the information provided in this summary is correct, or suitable for any type of application, both private, or commercial. In fact, if you were going to use any of this code to generate an authentication system of any sort, you are a dumb ass.

http://us2.php.net/md5

Kevin L
01-Dec-2004 10:58
Correction regarding MD5's security:

A method of producing collisions in MD5 and related algorithms has been discovered that is more efficient than brute-force. What this means is that an attacker can produce two strings that hash to the same result in a "reasonable" amount of time.

This does NOT mean that an attacker can a) decrypt an MD5 hash or b) find another string that will MD5 to the same value. So MD5 protected passwords cannot be attacked by this method.

Note that all hashes have collisions in them-- reducing an infinite set of inputs to a finite set of outputs must have duplicates.

February 18, 2005

When thinking over the methods I use to do client server authentication, I ask myself this particular question: Why does the server not also authenticate to the client when all the credentials are known to both the client and server?

The second negotiation for authentication uses a peer authentication string. Would a fourth variable that is unique to each party be sufficient to do a secondary, or second level authentication of the peer authentication string? For instance, could this fourth variable use a unique salt for the MD5 hashes, the salt data being based on the fourth unique variable? And if so, could this salt for both the client and server be transferred somehow by the use of the peer authenticator challenge, or the initial challenge? Maybe a concatenation of the random challenge on the server side, or the peer authenticator challenge on the client side?

[Reply]

Humm... interesting,

This is a great authentication,

Really helpful,

Keep up the good work,

Thanks

Add Comment
Topic
Your spew (Required)
Your name (Required)
E-Mail address (Required)
Have a web page?
Verification (Required)

Your comment will appear once approved by the post author.

Your e-mail address will NOT be shared.

Main Entry: spew Pronunciation: \ˈspyü\
Function: verb
Etymology: Middle English, from Old English spīwan; akin to Old High German spIwan to spit, Latin spuere, Greek ptyein intransitive verb
Date: before 12th century

1. VOMIT
2. to come forth in a flood or gush
3. to ooze out as if under pressure : EXUDE

transitive verb

1. VOMIT
2. to send or cast forth with vigor or violence or in great quantity <a volcano spewing out ash> —often used with out —spew·er noun

- [edited source] Merriam-Webster