On the construction of digest functions for manual authentication protocols

A digest function is a sort of universal hash that takes a key and a message as its inputs. This paper will study these functions’ properties and design in the context of their application in manual authentication technology. Frequently a digest function needs to have a very short output (e.g. 16–32 bits) and no key is used to digest more than one message. These together with other characteristics represent a new kind of game played between an attacker and honest parties, which is very different from other authentication mechanisms, notably message authentication codes or MACs. Short digests can be constructed directly or by ”condensing” longer functions. We offer an improved method for the latter but concentrate mainly on direct constructions. We propose a digest algorithm which uses word multiplications to obtain a very fast implementation. This digest scheme enjoys strong and provable security properties, namely for a single-word or b-bit output digest function the collision probability is = 21−b on equal and arbitrarily length inputs. The scheme is related to the multiplicative universal hash function of Dietzfelbinger et al., and it improves on several well-studied and efficient universal hashing algorithms, including MMH and NH. 1 Motivation and contribution We investigate the design, construction and security of a new cryptographic primitive termed a digest function, whose specification arises from its use in manual authentication technology [4, 16, 27, 36, 37, 38, 39]. A digest function digest(k,m), which takes a key k and a message m, has similarities to both -balanced and -almost universal hash functions [26, 53]. However, the majority of uses of this function in practice require it to have a very short output (16–32 bits as in a password), and thus our constructions introduced here are designed to take advantage of this feature, namely this feature opens the way for efficient and parallelisable constructions as opposed to the cascade structure underlying many long-output (universal) hash functions. Although other similar cryptographic primitives such as short-output universal hash functions MMH [18] and NH [9] have been designed and used to build message authentication codes, we note that these short-output primitives are not often used on their own in cryptographic mechanisms. In this paper we will focus on the application and security properties of digest functions in manual authentication protocols, which use this function together with existing human trust and interactions to authenticate data without the need for PKI, shared private keys and passwords. Here is an example of how this technology works: for electronic