International Association for Cryptologic Research

International Association
for Cryptologic Research


Paper: On Stateless Schemes for Message Authentication Using Pseudorandom Functions

Palash Sarkar
Search ePrint
Search Google
Abstract: We consider the construction and analysis of pseudorandom functions (PRF) for message authentication. Earlier work due to Bernstein and Vaudenay show how to reduce the analysis of PRFs to some probability calculations. We revisit this result and use it to prove some general results on constructions which use a PRF with ``small'' domain to build a PRF with ``large'' domain. These results are then used to analyse several existing and new constructions. Important among them is a simplified proof of a bound on the PRF-property of the cipher block chaining (CBC) mode of operation of a block cipher for message authentication code (MAC). Several existing variants of CBC-MAC are analysed using our framework and new schemes are described. One of the new schemes improve upon the NIST standard CMAC scheme by reducing the number of block cipher invocations by one for messages which are longer than $n$ bits. Next, we consider parallelizable constructions. An improved version of the well known PMAC scheme is described; the improvement consists of removing the requirement of a discrete log computation in the design stage of PMAC. An earlier parallel construction called the protected counter sum (PCS) had been proposed by Bernstein. PCS uses a keyed compressing function rather than a block cipher. We describe a variant of PMAC which works with keyed compressing function and compared to PCS requires lesser number of invocations. All our constructions are in the stateless setting, i.e., a setting where the sender and the receiver do not share any state (apart from the common secret key). One of the aspects of our work is the simple and direct approach to the analysis of PRFs. In particular, we avoid the extensive and heavy machinery of game-playing technique which is used in most papers on this topic.
  title={On Stateless Schemes for Message Authentication Using Pseudorandom Functions},
  booktitle={IACR Eprint archive},
  keywords={cryptographic protocols / pseudorandom function, message authentication, CBC-MAC, CMAC, protected counter sum, PMAC},
  note={ 14270 received 1 Jan 2009, withdrawn 25 Jan 2009},
  author={Palash Sarkar},