On chosen target forced prefix preimage resistance

In this paper we analyze the Chosen Target Forced Prefix (CTFP) preimage resistance security notion for hash functions firstly introduced in [Kelsey, J.-Kohno, T.: Herding hash functions and the Nostradamus attack, in: Advances in Cryptology-EUROCRYPT ’06, 25th Annual Internat. Conf. on the Theory and Appl. of Cryptographic Techniques (S. Vaudenay, ed.), St. Peters- burg, Russia, 2006, Lecture Notes in Comput. Sci., Vol. 4004, Springer-Verlag, Berlin, 2006, pp. 183-200]. We give a formal definition of this property in hash function family settings and work out all the implications and separations be- tween the CTFP preimage resistance and other standard notions of hash function security (preimage resistance, collision resistance, etc.). This paper follows the work of [Rogaway, P.-Shrimpton, T.: Cryptographic hash-function basics: Def- initions, implications, and separations for preimage resistance, second-preimage resistance, and collision resistance, in: Fast Software Encryption, 11th Interna- tional Workshop-FSE ’04 (B. Roy et al., eds.), Delhi, India, 2004, Lecture Notes in Comput. Sci., Vol. 3017, Springer-Verlag, Berlin, 2004, pp. 371-388], where they define seven basic notions of hash function security and examine all the relationships among these notions. We also define a new property for security of hash function families-always CTFP preimage resistance, which guarantees CTFP security for all the hash functions in the family.