Paper 2009/004
On Stateless Schemes for Message Authentication Using Pseudorandom Functions
Palash Sarkar
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 PRFproperty of the cipher block chaining (CBC) mode of operation of a block cipher for message authentication code (MAC). Several existing variants of CBCMAC 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 gameplaying technique which is used in most papers on this topic.
Note: Some of the probability arguments in the analysis of CBCMAC are incorrect and some of the stated results contradict known facts on the collision bound of CBCHASH. This was pointed out by an anonymous reviewer of the paper. But, I believe the approach taken in the paper to be essentially correct and the flaws are due to an oversight on my part. The analysis can be corrected to obtain similar bounds. For the moment, I have chosen to withdraw the paper since I wish to carefully go through each of the proofs. Being a rather long paper, this will take some time. I hope to post a revised version after satisfying myself regarding the proofs.
Metadata
 Available format(s)
  withdrawn 
 Category
 Cryptographic protocols
 Publication info
 Published elsewhere. Unknown where it was published
 Keywords
 pseudorandom functionmessage authenticationCBCMACCMACprotected counter sumPMAC
 Contact author(s)
 palash @ isical ac in
 History
 20090126: withdrawn
 20090104: received
 See all versions
 Short URL
 https://ia.cr/2009/004
 License

CC BY