Cryptology ePrint Archive: Report 2005/390

3C- A Provably Secure Pseudorandom Function and Message Authentication Code.A New mode of operation for Cryptographic Hash Function

Praveen Gauravaram and William Millan and Juanma Gonzalez Nieto and Edward Dawson

Abstract: We propose a new cryptographic construction called 3C, which works as a pseudorandom function (PRF), message authentication code (MAC) and cryptographic hash function. The 3C-construction is obtained by modifying the Merkle-Damgard iterated construction used to construct iterated hash functions. We assume that the compression functions of Merkle-Damgard iterated construction realize a family of fixed-length-input pseudorandom functions (FI-PRFs). A concrete security analysis for the family of 3C- variable-length-input pseudorandom functions (VI-PRFs) is provided in a precise and quantitative manner. The 3C- VI-PRF is then used to realize the 3C- MAC construction called one-key NMAC (O-NMAC). O-NMAC is a more efficient variant of NMAC and HMAC in the applications where key changes frequently and the key cannot be cached. The 3C-construction works as a new mode of hash function operation for the hash functions based on Merkle-Damgard construction such as MD5 and SHA-1. The generic 3C- hash function is more resistant against the recent differential multi-block collision attacks than the Merkle-Damgard hash functions and the extension attacks do not work on the 3C- hash function. The 3C-X hash function is the simplest and efficient variant of the generic 3C hash function and it is the simplest modification to the Merkle-Damgard hash function that one can achieve. We provide the security analysis for the functions 3C and 3C-X against multi-block collision attacks and generic attacks on hash functions. We combine the wide-pipe hash function with the 3C hash function for even better security against some generic attacks and differential attacks. The 3C-construction has all these features at the expense of one extra iteration of the compression function over the Merkle-Damgard construction.

Category / Keywords: secret-key cryptography /

Date: received 28 Oct 2005, last revised 6 Nov 2005

Contact author: p gauravaram at isrc qut edu au

Available format(s): Postscript (PS) | Compressed Postscript (PS.GZ) | PDF | BibTeX Citation

Note: This is a draft version of the work in progress. For any comments, suggestions and corrections please contact the author and your help is very much appreciated and acknowledged in the final draft.

Version: 20051107:040607 (All versions of this report)

Short URL:

[ Cryptology ePrint archive ]