Saturday, March 17, 2007
History-based authentication
Well, after reading Saul Griffith's column “Who wants to be an Inventor” in the latest Make magazine, I got inspired. Here's an idea that has been echoing around in my head for quite some time. Enjoy, critique, criticize – it's all good.
Digital authentication schemes are currently based on four things: what the user knows, what the user has, what the user does, or what the user is. Yet there is something else we can use: the user's history (I couldn't think up a catchy “what the user ...” saying for this one). We use our interpersonal histories to recognize each other in our day-to-day relationships. Imagine talking to someone who looked and acted exactly like a good friend, but had no knowledge of any of your previously-shared experiences. Authentication based on history has become a Hollywood staple – usually when some malevolent lifeform has taken over someone else's body. How does the hero find out if someone is friend or foe? By asking about their history.
Enough theatrics. Here's how it works:
When the user's account is set up, the server generates a block of strings. Each string is a series of random characters sufficiently large enough to be difficult to guess, and the block is long enough to protect a suitable number of the user's sessions. The server stores this block, and the user receives a copy as well.
The first time the user attempts to authenticate, the server randomly selects one position out of that user's block and requests that position from the applicant. The applicant's client looks in the user's block and sends the string residing in that position to the server. If the string supplied by the applicant matches the string held by the server, the applicant is let in. The server then generates another string and sends it to the user. The user's client replaces the previously requested string with the newly-generated one, and acknowledges. The server then performs the same replacement, and notes the position that was used.
The next time the user attempts to authenticate, the server requests two strings from the applicant: the one at the position used in that user's previous session and another one chosen at random that has not been used before. Upon successful authentication, the strings in both positions, in both the user's block and the server's block, are changed to random ones generated by the server.
From then on, when a user attempts to authenticate, the server requests two strings from the applicant: one that was used in the user's previous session (this will actually be the string generated during the user's last session) and another string that has not been used yet. Each position is changed upon successful authentication.
If the strings supplied by the applicant do not match the strings stored by the server, access is denied. The account should then be locked and steps should be taken to authenticate the user through manual means (telephone call, ID check ...)
When each position has been used, the server can either:
Forget which positions have been used and start the process over again, using the same block of strings. (least secure, but easiest)
Re-start the process by using the same block of strings in the same order. This would require the server to remember the order in which the strings are used.
Re-initialize by creating another block of strings and sending the block to the client.
The chief advantage of this scheme is that it gets stronger the more often it is used and the more places it is used in. Regular password-based authentication gets weaker with more use and more locations because every login represents an opportunity for the user's password to slip into someone else's hands. For example, suppose a user's home computer had become compromised with a keylogging trojan. Once that user logs into a password-protected web site, that account is compromised. Both the legitimate user and the intruder are then able to access that account. Then we can only hope that the intruder moves on before doing too much damage, the user changes the password, or the server detects simultaneous logins and acts on it.
However, if this scheme was in place the damage would be prevented, or at least mitigated. Suppose that some nefarious individual managed to obtain a user's login credentials, including a complete copy of the user's string block. One of two scenarios would occur: if the user logs in before the intruder does, the legitimate string block is updated, rendering the intruder's copy obsolete and useless (remember that the server will ask for the string given out in the user's previous session). If the intruder logs in before the user does, he will be able to access that account until the legitimate user comes back. At that time the account will be frozen, and the user's login credentials will have to be re-established (after manual authentication checks are done, of course)
This scheme actually performs two tasks – authentication based on information previously exchanged, and it detects compromised accounts. It would be best used as an extra layer of security, run in the background after a regular password check, to create a two-factor authentication scheme.
The primary disadvantage of this scheme is that it gives the user another security credential to manage. The user's block of strings would have to be stored somewhere (encrypted, of course) and would have to move around with the user. A USB key would be the natural choice, but that comes with a host of it's own problems (lost, stolen, file corruption). However, when compared to other two-factor authentication schemes out there, this one is nearly as secure as a SecureID token, but without the hardware expenses, and better than fingerprint or facial recognition, which are unreliable.
Labels: Ideas
