The value of authentication protocols which minimise (or even eliminate) the need for stored state in addressing DoS attacks is well-established — the seminal paper of Aura and Nikander [1] is of particular importance in this context. However, although there is now a substantial literature on this topic, it would seem that many aspects of stateless security protocols remain to be explored. In this paper we consider the design of a novel stateless authentication protocol which has certain implementation advantages. Specifically, neither party needs to maintain significant stored state. The protocol is developed as a series of refinements, at each step eliminating certain undesirable properties arising in previous steps.