Seeking input: maintaining a server session without any server state

I'm not a security expert, so I'm looking for people to poke gaping holes in an authentication scheme I've devised, or point me to a better, existing scheme that fulfills the same goals:

Overview of Problem

I have an interface in which the client maintains session lifecycle (it's an HTTP session on a web server, but it doesn't really matter).

The stateless server provides some services that require the caller to be authenticated (the server has the ability to perform this authentication).

However, it's desirable for the server not to have to authenticate the caller on each invocation, e.g., by passing credentials in each call. (The authentication process can be expensive.)

It's also desirable not to maintain session state on the server. For one thing, it's just asking for a brittle solution to have independent session timeouts on both client and server (the one on the client can't be gotten rid of), and a server timeout seems necessary in order to have a reliable session lifetime on the server (rather than relying on the client to explicitly end the session at an appropriate time). For another thing, the server isn't set up to store this sort of state.

The server has an explicit authenticate method. The problem is then: how does the server verify that, when another method is called, the caller has previously authenticated using the authenticate method, without storing any session state on the server?

Proposed Solution

Here's a scheme I've come up with:

The authenticate method accepts credentials as input parameters. Upon successful authentication, the server returns two things:

• A timestamp indicating the time that authentication was performed.
• An encrypted version of the tuple of { username, timestamp }, encrypted with a private key

On further method calls, the client passes both of these values back to the server. The server then decrypts the encrypted { username, timestamp } tuple. If the decrypted timestamp matches the unencrypted value that was also sent by the client, the server knows that the client has previously authenticated (as that's the only way to acquire a valid encrypted value). The decrypted username tells the server which user has been authenticated.

The validity period of an encrypted key can be enforced by only allowing timestamps that are within x hours of the current time. This isn't the same as a session timeout, but it limits the window within which a compromised timestamp could be used by a malicious party.

So

I fear that this scheme is naive in a dozen ways. What weaknesses or b开发者_运维技巧ad logic do you see?

---

In case anybody cares (which seems unlikely given the amount of attention this question has gotten!), we ended up implementing a scheme much as described above.

A few of the details vary, though:

• The server creates a session token based upon the user name, the session-start timestamp (passed back to the user), and a salt.
• The client does not pass this token back to the server. Instead, an MD5 hash is created from the entire request content concatenated with this token.
• The MD5 hash is sent to the server along with the timestamp and the the user name (and the request). The server then re-creates the session token and performs the same hashing algorithm. If the MD5 hashes match: valid request.