The objective of this paper is to propose a cryptographic protocol which provides authenticity in the exchange of information between two entities without using any shared secret and by using only oneway chains. Such a protocol may have many applications and may be of interest especially in constrained environments where computational power is limited since one-way chains may be constructed using some of the simplest cryptographic one-way functions. We propose and investigate two approaches based on one-way chains, which we call: delayed message authentication and direct message authentication. Both of them have some shortcomings and a final hybrid approach, which combines their advantages without inheriting their weaknesses, appears to be quite useful and effective.