idea for OTP system, comments desired

[John Bethencourt]

I've come up with an idea for a one-time-password based authentication
protocol, and I would like any comments on it. It doesn't use
sequences of passwords that need to be periodically reinitialized, so
it is more convenient than systems like S/Key.

In the following explanation, `h' is a cryptographic hash function and
`x.y' denotes the concatenation of strings x and y. The `server' is
taken to be a system which users need to authenticate to, e.g., to use
some service. The `client' is software run by the user to assist them
in authentication.

To begin, the administrator of the server adds a user to the
system. The server stores the username and an initial password set by
the administrator. A flag is set for that user to indicate that that
user has never been authenticated. The administrator tells the initial
password to the user.

To authenticate for the first time, the client connects to the server
and sends the username. The server requests the initial password. The
client prompts the user for it, and sends it to the server. The server
then generates a random string, r_0, and sends it to the client. The
client now prompts the user for the password, s, which they would like
to use from now on. The client computes h(h(s.r_0)) and sends it to
the server. The server stores the username, r_0, and h(h(s.r_0)).

To authenticate for the second time, the client connects to the server
and sends the username. The server sends r_0 to the client. The client
prompts the user for s, then computes h(s.r_0) and sends it to the
server. The server computes h(h(s.r_0)) and checks that it matches
what it has stored for that user. The server then makes a new random
string r_1 and sends it to the client. The client computes h(h(s.r_1))
and sends it to the server. The server stores the username, r_1, and
h(h(s.r_1)).

All subsequent authentications proceed like the second.

Here's the protocol in a more concise form:

[first authentication]

Client -->       username      --> Server
Client <-- 'initial password?' <-- Server
Client -->      initialpass    --> Server
Client <--          r_0        <-- Server
Client -->      h(h(s.r_0))    --> Server

[subsequent authentications]

Client -->       username      --> Server
Client <--          r_x        <-- Server
Client -->       h(s.r_x)      --> Server
Client <--          r_y        <-- Server
Client -->      h(h(s.r_y))    --> Server


This protocol seems pretty simplistic. I wonder if people have
considered it and found a flaw in it. If not, I would expect people to
be using it in place of S/Key, since it has the advantage of not
requiring the password sequences to be reinitialized. I searched
around on the web and couldn't find anything that seemed relevant. The
only possible flaw that I could think of was the following:

The attacker will have a large number of pairs like

h(s.r_0), r_0
h(s.r_1), r_1
h(s.r_2), r_2
h(s.r_3), r_3
.
.
.

Is there some way to use this knowledge to make inverting h to find s
easier? Of course, that would depend on the particular hash function,
and I don't know enough of the math behind secure hash functions to
answer the question. Also, the random string r_i will need to be long
enough to make collisions sufficiently unlikely (or the server could
keep a list of past random strings to ensure it does not reuse them).

If anyone can think of any flaws in this system or knows of any
relevant literature, I would very much like to hear about it.

Thanks,
John Bethencourt