2
$\begingroup$

I read one answer to a similar question that put forth that a hash function is distinct from a PRF, however I've also found materials purporting that cryptographic hash functions are PRFs, and I'm not sure now. Also, is HMAC a PRP because of being keyed? I thought that a cryptographic hash function being keyed (i.e., with a constant prepended/appended to the input) was what determined whether it was a PRF or a PRP, however upon searching more I've become increasingly confused. Right now I think that a hash function is a PRF and that an HMAC is a PRP, and that this is because HMAC is keyed.

$\endgroup$
2
$\begingroup$

I read one answer to a similar question that put forth that a hash function is distinct from a PRF, however I've also found materials purporting that cryptographic hash functions are PRFs, and I'm not sure now.

Those latter materials are wrong.

Random function

A mathematical function (i.e. a "pure" function) whose output values depend only on its inputs, but whose outputs are random. Think of it as a (potentially infinite) table with two columns:

  • The first column lists every possible input exactly once;
  • The second column has been filled-in ahead of time with values selected uniformly at random from the function's range.

A random function is an ideal object—something we know can't practically exist at the sizes we're interested.

Pseudorandom function family (PRF)

A deterministic computer algorithm such that it:

  • Takes a secret key and a (not necessarily secret) input;
  • Runs in polynomial time;
  • Has the property that if you choose the key secretly and at random, an adversary would find it so difficult to crack that they wouldn't even be able to tell it apart from a random function in any practical amount of time, even if they know the algorithm and can choose the non-key input to it.

Note that a PRF is intended to act as a practical aspiration—something that cryptographers hope that a practical computer algorithm can achieve. Note that there isn't actually hard proof that it's possible to implement a PRF in real lie—the existence of PRFs is a conjecture.

Note also that I boldfaced secret over and over—that's an important little detail here.

Random oracle model

A type of cryptographic security proof where a hash function is modeled as a random oracle—a public random function that is accessible both to honest parties and adversaries.

Note that just like I boldfaced secret above, here I boldfaced public, because that's a key difference. A PRF takes a secret key that the honest party must choose at random, and thus a PRF is supposed to behave like a random function that only that party is able to evaluate. Whereas crypto hash functions like SHA-256 are designed to resist attacks in scenarios where there's no secret key. For example, an adversary isn't supposed to be able to find two SHA-256 inputs that collide in any practical amount of time, even though no secret about the algorithm or computation is kept from them. So ideally, hash functions should behave like random functions that are known to every party.

Note that another confusion you'll come across often is people who use the term "random oracle" to mean random function. I like to think of it with this analogy: being a random oracle is like being the President of the United States. You have to be a natural born citizen and 35 years or older, but what makes them President isn't that they fulfill those two requirements, but rather the role they play in the political system.

Likewise, a random oracle must be a random function, but what makes that function a random oracle isn't just the fact that it's random, but rather the role it plays in some scenario.


Now, the rest of your questions:

Also, is HMAC a PRP because of being keyed?

HMAC is routinely conjectured to be a PRF. It's not a permutation because there must exist multiple inputs that produce the same output. And thus it cannot be a PRP, which is a subtype of PRFs with the additional stipulation that for each key, the algorithm must implement a one-to-one function (a.k.a. a permutation).

I thought that a cryptographic hash function being keyed (i.e., with a constant prepended/appended to the input) was what determined whether it was a PRF or a PRP, however upon searching more I've become increasingly confused.

Your mistake here is thinking that being "keyed" is a contextual property of how you choose to use the function in one scenario, but you really need to look at it as an intrinsic property of the function itself, or otherwise you'll indeed get confused. SHA-256 has just one input, and that input is for a message that the function doesn't demand that you keep secret. So no, SHA-256 definitely isn't secret keyed function.

If you need a PRF, however, one way to build one is HMAC-SHA-256, a construction that defines a function that does take a separate key (that it demands that you choose secretly at random) and message. Then, under the hood, HMAC-SHA-256 combines those two inputs in a specific way and hands them to SHA-256.

But the fact that HMAC-SHA-256 is a keyed function that's built out of SHA-256 doesn't mean that SHA-256 is "sometimes a keyed function"—it just means that you can build keyed functions out of unkeyed building blocks. Again, "keyed" should be understood as a fixed, intrinsic property of how the function is defined, not a variable contextual fact about how it's used in some scenarios.

| improve this answer | |
$\endgroup$
  • $\begingroup$ I think I understand now. A PRP is just taking an input, such as "abc," and producing an output from it that's a permutation of it, such as "cab." And it's one-to-one because there are 3! possible permutations of the three characters (abc, acb, bac, bca, cab, cba). So, the PRP would be two columns as before, but with the first column being those 6 strings, and the second column being the 6 strings as well but in a random order. So a PRP just pseudorandomly orders an input (bit?) string to produce the output, whereas a PRF doesn't necessarily produce an output that is a reordering of the input? $\endgroup$ – cyborg May 23 at 17:00
  • $\begingroup$ A prp taking 'abc' might also produce 'zfi' or any other bit string. The important difference is that there's a reverse operation, to go from 'zfi' back to 'abc'. Whereas with a PRF no reverse is possible. HMAC is a PRF. A block cipher like AES is a PRP. Keyed permutations like ChaCha20's core or Gimli in a keyed mode are also PRPs, though not really block ciphers. $\endgroup$ – SAI Peregrinus May 25 at 16:02
  • $\begingroup$ @cyborg: The term "permutation" in PRP means a one-to-one function with the same domain and range, which is a slightly different but equivalent definition to the concept you're looking at of the ways that a string's characters can be reordered. See this Q&A here. Think of it this way: the permutation that changes $abc$ to $bac$ is equivalent to the one-to-one function over the set $\{a, b, c\}$ that maps $a \to b$, $b \to a$ and $c \to c$. $\endgroup$ – Luis Casillas May 26 at 5:27
1
$\begingroup$

A PRP is a keyed permutation. For each fixed key, it is one to one and onto, and takes the form $f:\{0,1\}^n\rightarrow \{0,1\}^n$.

A PRF is a function, so it is not necessarily one to one. Under the random oracle model an $\ell$-bit output unkeyed hash is modelled as a random choice from the set of all functions $f:\{0,1\}^\ast\rightarrow \{0,1\}^\ell.$

Clearly, a function which maps a larger domain to a smaller domain cannot be a permutation. So HMAC not a PRP.

| improve this answer | |
$\endgroup$
  • 1
    $\begingroup$ There is no such thing as an unkeyed PRF. $\endgroup$ – Mikero May 23 at 0:55

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.