9

The term PRF is mentioned in the documentation of the IKE (Internet Key Exchange) protocol.

  • What is a PRF?

  • What is the difference between a PRF and a hash function?

  • What PRFs are used in the IKE protocol?

user46306
  • 91
  • 1
  • 2
  • 3

1 Answers1

10

PRF stands for PseudoRandom Function. A PRF will map input to output in a deterministic fashion (same input always maps to same output for same PRF) that appears indistinguishable from randomness to an attacker who doesn't know the internals of the PRF (and hasn't seen the PRF already process that exact same input, even if they've seen the PRF process many similar inputs).

Generally PRFs are taken at random from a PRF Family. You can think of PRF Family as being a function taking an additional input (a random seed, also sometimes referred to as a random key) which selects a particular PRF (that maps input to output). So if you have a 128-bit seed in your PRF family then there are 2^128 (340,282,366,920,938,463,463,374,607,431,768,211,456) possible PRFs that you could be using from that family. This is contrast to hash functions, where there are only dozens of commonly used hash functions (MD5, SHA-1, SHA-256, SHA-512, etc).

Let's say you knew that "Hello" mapped to 8b1a9953c4611296a827abf8c47804d7 (in hex). An attacker can quickly figure out that I'm using MD5 and could then generate outputs for any input they wanted.

However, HMAC - hash-based MAC is a family of PRFs. So if you take the HMAC construction: H(K1 ++ H(K2 ++ m)), where ++ means concatenation, H is an ordinary hash function, and K1 and K2 are two keys which are defined to be derived from the same key using K1 = K XOR 0x5c5c...5c and K2 = K XOR 0x3636...36. Now if I told you that my PRF (a HMAC using a particular key K) maps "Hello" to 53a7e60d93a6853780d622f3b5bd641f there would be no way for an attacker (who doesn't know K, but may know I'm using HMAC-MD5) to generate the output for an input they've never seen before.

The actual PRFs used in the IKE protocol are negotiated between the client and server. The ones specified in the RFC for IKEv2 are HMAC_MD5, HMAC_SHA1, HMAC_TIGER (three HMACs generated from different hash functions), and AES128_XCBC. In the original IKE RFC, the PRFs to use were not defined: "There are currently no pseudo-random functions defined.".


Note the difference between a PRF and a PRF family will often not be explicitly made. In the literature you will often two inputs (a key, a plaintext) and generate one input.

In cryptography two related concepts come up - the PRP (PseudoRandom Permutation) and the PRG (PseudoRandom Generator).

A pseudorandom permutation (PRP) is a PRF that is one-to-one - that is a specific type of PRF where each output of the PRF (using the same key) can only be generated from exactly one input. This allows one to invert the function and undo the effect of the application of its application -- thus you can apply the PRP (requiring knowledge of a secret key) to plaintext to create a ciphertext, and then apply the inverse of the PRP to the ciphertext (using the secret key) to decrypt it. For example, a block cipher like AES-128 is a PRP -- it takes a block of input that is 128-bits as well as 128-bit key, and maps the plaintext block to a unique 128-bit ciphertext block. Then these operations can be reversed to map the ciphertext block to the original plaintext block (using the inverse of AES-128 with that secret key).

A pseudorandom generator (PRG) is a function that emits a stream of bits that appears random based on some initial seed (e.g., a random key). This bit-stream can be XORed with a long plaintext message to encrypt it (so the ciphertext appears random), and then you can decrypt it by XORing the PRG's bit-stream with the ciphertext. One way to generate a PRG is to take a block cipher like AES-128, and use it in CTR mode. That is you encrypt successive blocks incremented by one with the same key, and then concatenate the output together, e.g., PRG(K) = AES(K, 0) ++ AES(K, 1) ++ AES(K, 2) ++ AES(K, 3) ++ ... (where ++ means concatenation).

dr jimbob
  • 38,768
  • 8
  • 92
  • 161