Paper 2009/003

Separating two roles of hashing in one-way message authentication

L. H. Nguyen and A. W. Roscoe


We analyse two new and related families of one-way authentication protocols, where a party wants to authenticate its public information to another. In the first, the objective is to do without shared passwords or a PKI, making use of low-bandwidth empirical/authentic channels where messages cannot be faked or modified. The analysis of these leads to a new security principle, termed separation of security concerns, under which protocols should be designed to tackle one-shot attacks and combinatorial search separately. This also leads us develop a new class of protocols for the case such as PKI where a relatively expensive signature mechanism exists. We demonstrate as part of this work that a popular protocol in the area, termed MANA I, neither optimises human effort nor offers as much security as had previously been believed. We offer a number of improved versions for MANA I that provides more security for half the empirical work, using a more general empirical channel.

Note: This is a long version of another paper, which has been published in Proceedings of FCS-ARSPA-WITS'08 workshop. This includes detailed security proofs of several protocols introduced in the short version of the paper.

Available format(s)
Publication info
Published elsewhere. This paper was published in the Proceedings of FCS-ARSPA-WITS 2008
Contact author(s)
long nguyen @ comlab ox ac uk
2009-11-28: last of 2 revisions
2009-01-04: received
See all versions
Short URL
Creative Commons Attribution


      author = {L.  H.  Nguyen and A.  W.  Roscoe},
      title = {Separating two roles of hashing in one-way message authentication},
      howpublished = {Cryptology ePrint Archive, Paper 2009/003},
      year = {2009},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.