I know this is Ruby-specific, but we plan to implement this system
using Ruby and ActionWebService.  We need to create a secure web
service for B2B integration (ick, sounds too Enterprise-y).  The
request follows the following path:

Client Web Site -> Our Web Service (ActiveWebService) -> Our Database,
and back.

We'd like to eliminate the overhead of a challenge/response type of
system. We've come up with this:

The client GPG Signs a UUID+Time. This way an interception of the token
is worthless since it's only good for one request. Since the time
portion of tokens are sequential, we don't need to store a lot of them.
We can just provide a 1 minute window around our latest token.

So tokens are only good for one request. We have to store the latest
token. Since the tokens are signed, tokens can't be generated by a
third party without first compromising the client's private key.

Can anyone poke holes in this idea for us? Or do you have any better
ideas?

Thanks!
Scott