Would it be required that a client perform a pre call for each request, or for a window of requests possibly.
I have seen this sort of thing in SOAP aka WS-Security with their SecureToken.
I mite try put something together an example and see how it works out.
Thanks for the comment.
When the request "seed" is used, it gets removed from the list of active seeds, so it can not be used again.
There is still a man in the middle attack:
1) The attacker intercepts our request, send it to the server, and reply to the real client with an error code. 2) This will force the real client to send the request again, this time the attacker will not interfere with the request.
The result is that the request was performed two times instead of one.
This session key could then be incorporated into each of the HMAC signatures and would be refreshed on a regular basis similar to how IPSEC does it.
I have used AH in the passed for log data which required the receiver to verify the source for auditing purposes, but this was quite some time ago, these days most systems just either use SSL or IPSEC with ESP.
Reinventing the wheel is probably not the best idea in this case.
Will add a note on this to my blog post for completeness.
For more information on IPsec see http://en.wikipedia.org/wiki/IPsec