Help with terms: hash function and a pseudorandom function

Question

I am a little bit confused about the terms hash function and pseudorandom function. As far as I know, I can use a cryptographic strong hash function as a PRF. The hash function has a IV and is completely public - everybody can look at the construction and at the details. A good hash function maps the input in a pseudorandom way to its output (deterministic).

So a pseudorandom function is quite similar. Here you do not take a fix hash function, rather than you take a function from a set of functions. That model is implied by using a keyed function. So there are often keyed hash functions used for example the HMAC is taken as a PRF.

So in a limited view, is it right to say that a attacker does not know my "internal conditions" of my PRF? (I mean my current Setting: which key i use and which hash function, or if I use HMAC, he does not know my key and my constants and my hash function.)

Answer 1

There's two problems with your question:

1. The term "hash function" is not as clearly defined as you think.
2. The most common definition among cryptographers does not imply pseudorandomness.

Generally, you want to be very careful in distinguishing between:

• Security definitions, like:
  • Pseudorandom function
  • Collision resistant hash function
• Cryptographic algorithms, like:
  • SHA-2
  • HMAC
  • AES
• Arguments that some given algorithm meets specified security definitions.

"Pseudorandom function" and "collision-resistant hash function" are security definitions:

• A pseudorandom function is a keyed function that an adversary who doesn't know the key cannot efficiently distinguish from a randomly selected function over the same domain and range.
• A collision-resistant hash function (CRHF) is a function that features:
  • Compression (turns variable-sized inputs into fixed-size outputs);
  • Preimage resistance
  • Second preimage resistance
  • Collision resistance

Now, you need to understand that the security definition for collision-resistant hash functions does not imply the one for pseudorandom functions:

• A pseudorandom function need not compress its input. Example: AES, or any block cipher (which are designed to be pseudorandom permutations on fixed size blocks).
• A function that provides preimage, second preimage and collision resistance may nevertheless be efficiently distinguishable from a random function.

This means that if all that you assume of your hash function is that it meets the CRHF requirements, you cannot conclude that it also provides the PRF requirements. First because CRHFs may be unkeyed; second because a keyed CRHF may be distinguishable from a random function.

In practice, however, the common hash function algorithms that we use are argued (or just assumed) to meet not just the collision-resistant hash function definition, but also:

1. To be suitable building blocks for a pseudorandom function, using HMAC or some other construction;
2. Often they're also treated as random oracles: a public function (no secret key) that produces random outputs.

Some cryptographers get nervous when you assume #2, though, because they'd like to minimize the assumptions that we make about our primitives' security.