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 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 $$ 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.

Note: Some of the probability arguments in the analysis of CBC-MAC are incorrect and some of the stated results contradict known facts on the collision bound of CBC-HASH. 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.