4
$\begingroup$

I have some confusion regarding the difference between MACs and HMACs and PRFs and when to use which term.

If the function is computed using a hash and secret key like the following, is this a HMAC or MAC?

MD5(master_secret + pad2 + MD5(handshake_messages + Sender + master_secret + pad1));

If I have a tag for verifying data, computed using a PRF in the form: PRF(master_secret, finished_label, Hash(handshake_messages))

Again, my question, is this HMAC or MAC or none, just a PRF?

The above functions are what is used in the Finished messages for SSL 3.0 and TLS 1.2 respectively. The literature use MAC generally. I am not sure if this is the correct term used to refer to them.

Can I refer to HMAC and PRF by MAC?

$\endgroup$
  • $\begingroup$ HMAC is the type of MAC built from hash functions. Not all MAC are PRFs, for examply poly1305 is a MAC, but is unsuitable as an PRF. $\endgroup$ – DannyNiu Aug 15 '17 at 4:56
  • $\begingroup$ @DannyNiu so the first one I post is an HMAC? $\endgroup$ – user6875880 Aug 15 '17 at 5:27
  • $\begingroup$ Yes. As for PRF, I'm not sure about its definition, because in some literatures it as two arguments - a key and a piece of data, in others, the number of arguments varies. $\endgroup$ – DannyNiu Aug 15 '17 at 6:06
  • $\begingroup$ It's not HMAC-MD5. And since MD5 is broken, it's not a secure PRF/MAC either. $\endgroup$ – CodesInChaos Aug 15 '17 at 11:15
  • $\begingroup$ For the first part of your question, see HMAC vs MAC functions and What is the difference between MAC and HMAC? $\endgroup$ – Ilmari Karonen Aug 15 '17 at 15:17
9
$\begingroup$

A PRF or pseudorandom function family is a family of functions $F_k\colon \{0,1\}^n \to \{0,1\}^m$ such that if $k$ is uniformly distributed, then $F_k$ appears to be uniformly distributed among all functions $G\colon \{0,1\}^n \to \{0,1\}^m$. A PRF $F_k$ is secure if an adversary who does not know the key $k$ can't distinguish $F_k$ from a uniform random choice of function $G\colon \{0,1\}^n \to \{0,1\}^m$ with more than negligible probability of success beyond flipping a coin—the adversary's only strategy is to correctly guess the key $k$ which is usually drawn uniformly from a space of usually $2^{128}$ or $2^{256}$ possibilities, which no adversary will ever stumble upon by chance.

The existence of PRFs remains a conjecture, related to P = NP; at best we conjecture that function families are PRFs, and sometimes find counterexamples to the conjectures. Some PRFs have long or variable-length inputs, e.g. keyed BLAKE2b; some PRFs have short inputs, e.g. ChaCha or the compression function inside MD5.

A MAC or message authentication code is a family of functions $M_k\colon \{0,1\}^* \to \{0,1\}^T$ with which one can construct and verify a $T$-bit tag $t = M_k(m)$ on a message $m$ with a secret key $k$. A MAC is secure if an adversary, upon seeing some number of past (possibly adaptively) chosen messages and tags $(m_i, t_i)$ with $t_i = M_k(m_i)$, can't forge a tag $t' = M_k(m')$ for a message $m'$ not previously seen with better than negligible probability.

Many MACs are one-time authenticators, meaning the secret key can be used for only one message, such as Poly1305 and GHASH (of AES-GCM). One-time authenticators are useful because they can be extremely fast and can come with an unconditional information-theoretic security proof of forgery probabilities, and it is easy to use a PRF with a nonce to create a new OTA key for each message.

A long-input PRF $F_k$ can also serve as a MAC, because an adversary having seen $\{F_k(m_i)\}_i$ can't even distinguish that from $\{G(m_i)\}_i$ for a uniform random choice of $G$, so the best strategy the adversary has is to pick some $k'$ uniformly at random, try forging $t' = M_{k'}(m')$ for some message $m'$, and hope that $k = k'$, whose success probability is bounded by the probability that $M_{k'}(m')$ happens to coincide with $M_k(m')$ or that $k = k'$, which are both negligible.

$\newcommand{\concat}{\mathop{\Vert}}$HMAC is a specific construction of a long-input PRF out of a short-input PRF chained in a Merkle-Damgård construction $H$, such as MD5 or SHA-256. Naively using the function $$F_k\colon m \mapsto H(k \concat m)$$ for uniform random key $k$ does not give a PRF when $H$ is either MD5, SHA-1, SHA-256, or SHA-512, because even if I don't know $k$, knowing $F_k(m)$ enables me to easily compute $F_k(m \concat p \concat m')$ for some padding $p$ and an arbitrary suffix $m'$. This is called a length extension attack. HMAC works around this for an MD hash function $H$ by using $$F_k\colon m \mapsto H\bigl((\mathrm{opad} \oplus k) \concat H\bigl((\mathrm{ipad} \oplus k) \concat m\bigr)\bigr),$$ where $\mathrm{opad}$ and $\mathrm{ipad}$ are constant strings defined in the standard.

(The full details are finicky, e.g. if $k$ is not exactly the length of one block of the short-input PRF underlying $H$. You can also use HMAC on non-MD functions such as SHA-3, but the usual reference for an HMAC security reduction relies on MD. The security reduction story for HMAC is complicated, and there has been some more recent work on it; however, the strategy for modern designs like SHA-3 and BLAKE2 is to just make prefix-keyed $F_k\colon m \mapsto H(k \concat m)$ work as a PRF without the contortions of HMAC, and to define a standard domain-separated keyed PRF variant of the function.)

Since for certain fixed hash functions $H$, HMAC-$H$ is conjectured to be a PRF, and since a PRF always makes a MAC, you can use HMAC-$H$ to make a (rather slow) MAC.

Is your construction an HMAC for some fixed hash function $H$? No.

Is your construction a PRF? No: if an adversary can control $\mathrm{handshake\_messages}$, then they can almost certainly find a collision in $$\operatorname{MD5}(\mathrm{handshake\_messages} \concat \mathrm{Sender} \concat \mathrm{master\_secret} \concat \mathrm{pad}_1),$$ which would enable them to distinguish $F_k$ (your construction) from a uniform random $G\colon \{0,1\}^\ell \to \{0,1\}^T$ without knowing $k$ ($\mathrm{master\_secret}$) by simply evaluating it on the colliding messages and seeing whether it's the same, which for the overwhelming majority of functions $G$ will not be the case.

Is your construction a MAC? Again, no, because if the adversary can find a colliding pair of handshake message sets, then they can ask you to make a tag on one of them, and then they can use the same tag to produce a forgery on the other one.

Does this mean you can immediately attack a system in practice that works this way? Maybe, maybe not. What it means is that the crypto is not engineered out of reliable well-understood parts that could give confidence in the security of the whole system. Thus to understand the security of the whole system you cannot simply (a) assess the security of the parts, and (b) assess the security of how they are wired; you must assess the whole thing as a giant unit ball of hair. And most cryptographers and auditors don't want to bother doing that because it's a lot more work than well-done crypto engineering.

$\endgroup$
4
$\begingroup$

You need to understand the difference between security goals vs. specific algorithms. PRF and MAC are security goals—they're definitions that stipulate properties that we would like cryptographic algorithms to offer, so that our applications can then be built to rely on those properties. For example the definition of a MAC tells us (in much more precise detail than what follows) that a MAC must be secret keyed function that is resistant to forgery attacks.

HMAC on the other hand is a specific algorithm (or rather a family thereof, parametrized by the hash function used to instantiate it). As the name hints, HMAC is an algorithm that is intended to meet the MAC security goal. But just like apples are not the only fruits, HMAC is not the only MAC—there are others like Poly1305, CMAC, UMAC, etc. HMAC is just the most famous one.

PRF is another common security goal. Simplified a good deal, a PRF is a secret keyed function such that an adversary cannot efficiently tell its outputs apart from those of a random function. The PRF goal is stronger than the MAC goal in the following sense: any algorithm that satisfies the requirements to be a PRF automatically satisfies the requirements to be a MAC as well, but not vice-versa: algorithms do exist that meet the MAC requirements (roughly, forgery resistance) but fail the PRF requirements (roughly, indistinguishability from a random function).

There are some technical contexts where a MAC is sufficient (e.g., message authentication), but there are others where a PRF is required (e.g., key derivation from a uniform random key). HMAC, when instantiated with SHA-1 or SHA-2, is generally taken to be a PRF as well as a MAC, so it is widely used in both contexts.

$\endgroup$
  • $\begingroup$ If I'm understanding you correctly, a MAC would be sufficient in cases where the message being MAC'ed is not sensitive. Whereas a PRF would be preferred (required?) if the message is sensitive. Please confirm if that lines up with your answer. $\endgroup$ – Eddie May 28 '18 at 1:14
  • $\begingroup$ @Eddie: Given a secure MAC, it is trivial to define a contrived derivative MAC that meets the security requirement but does reveal information about the messages. That's a bit of a contrived scenario, I think, however. Given that sensitive messages are normally encrypted anyway, you can always safely apply a MAC to a ciphertext. The other thing to add is that PRFs have other applications that are not message authentication. $\endgroup$ – Luis Casillas May 30 '18 at 20:13
2
$\begingroup$

Adding a little to the other, general (and excellent) answers:

PRF in general is a mathematical abstraction with the properties described -- which like most mathematical abstractions are chosen/defined to be something mathematicians, in this case cryptographers, find useful to think and reason about.

But in TLS protocols PRF is locally defined as a specific function (or a few) designed and intended to be a mathematical PRF, and used for key derivation during handshake (per sections 5 8 6.3 of RFCs 2246 4346 5246) and for the Finished message which you have asked other Qs about (per section 7.4.9). To be exact:

  • TLS 1.0 and 1.1 define PRF as the xor of doubled HMAC-MD5 and doubled HMAC-SHA1.

  • TLS 1.2 allows PRF to depend on the ciphersuite, but defines a default all current suites use, which is doubled HMAC-SHA256 or doubled HMAC-SHA384.

  • SSL 3 defined similar algorithms for key derivation and Finished without using the name PRF, which use nested hashes in a fashion similar to HMAC but not using actual HMAC which at the time hadn't been standardized, in section 5.6.9 (which you partly quoted) and slightly different in sections 6.1 and 6.2.2 of RFC 6101.

In all these variations, the PRF result in Finished functions as a MAC for the handshake sequence to detect any tampering -- except attacks that break the key-exchange method quickly enough to substitute a correctly forged Finished, like FREAK and Logjam.

And in all these protocols because the Finished message follows Change Cipher Spec it is encrypted and MACed like all other data within an SSL/TLS session. SSL 3 uses its own MAC algorithm which again is similar to HMAC but not actual HMAC; TLS 1.0 and 1.1 always use HMAC, with a hash depending on the ciphersuite; TLS 1.2 uses HMAC for CBC ciphers and RC4 (but RC4 is now broken and prohibited), but also supports AEAD ciphers which have their own integrated MACs (currently GCM, CCM, and Poly1305 with ChaCha20).

$\endgroup$
1
$\begingroup$

A MAC is a Message Authentication Code. It takes a key and a message (and possibly some associated data) as input, and produces a tag as an output. Anyone with the key and message (and other data) can authenticate that the tag is correct. Anyone without the key can't produce the tag. MACs are used to ensure that ciphertext is not malleable: attackers modifying the encrypted cyphertext message won't produce a valid output.

HMAC is a type of MAC built using a hash function. All HMAC constructions are MACs but not all MACs are HMACs, just as all cars are automobiles but not all automobiles are cars. The HMAC construction is needed to allow hash functions that suffer from length-extension attacks (Merkle–Damgård constructions for one) to be used as a MAC. Other constructions (like Keccak's sponge) aren't vulnerable to this and thus have other ways to be used as a MAC. Keccack's version is KMAC: cSHAKE128(Key||Message||Output Length||Optional Customization String)

A Pseudo-Random Function acts like a deterministic random function in a manner similar to the way a Pseudo-Random Number Generator acts like a Random Number Generator. A deterministic random function is a function that for any input the output is randomly but uniquely chosen from among all possible outputs. For any given input the output is always the same, and no two inputs share an output. A true random function requires arbitrary (empty through infinite) output length to avoid violating the pigeonhole principle since there are an infinite number of possible inputs. If the input length is restricted to a finite value the output length can also be restricted. A pseudo-random function attempts to behave like a random function using a deterministic series of steps. Any cryptographic hash function should be a pseudo-random function.

Hash functions are a proper subset of PRFs. HMACs are a proper subset of MACs. MACs and PRFs intersect, but are not identical: there are MACs that aren't PRFs and PRFs that aren't MACs.

$\endgroup$
  • 2
    $\begingroup$ HMAC is not just any MAC built using a hash function, but a specific algorithm for turning a (Merkle-Damgård style) hash function into MAC (and also a PRF). A more fitting simile might be that all VW Beetles are cars, but not all cars (or even all cars made by VW) are Beetles. $\endgroup$ – Ilmari Karonen Aug 15 '17 at 15:03
  • 3
    $\begingroup$ Also, cryptographic hash functions like SHA-1/2/3 are not PRFs, since they're not keyed, and thus can be trivially distinguished from a truly random function simply by comparing the output of the function with that of the (known) hash algorithm. Also, any secure PRF with a suitable domain and range can be securely used as a MAC. Thus, any PRFs that fail to be secure MACs essentially only fail due to a technicality. $\endgroup$ – Ilmari Karonen Aug 15 '17 at 15:15
  • 1
    $\begingroup$ “all cars are automobiles but not all automobiles are cars” — that's a bad example. In many dialects of English, either car and automobile are synonymous, or automobile isn't used at all. $\endgroup$ – Gilles Aug 15 '17 at 17:35
  • $\begingroup$ Missing a negation somehwere in ‘All HMAC constructions are MACs but all MACs are HMACs’? Need to qualify the underlying hash function for that to work, too. The term ‘deterministic random function’ is not widely accepted in the literature, and is a confusing contrast with ‘pseudorandom function’, when I assume you mean uniform random choice of function with the same domain and codomain—but then you mention infinitely many inputs, and there is no uniform distribution on any set of functions that can have infinitely many inputs, so you seem to be confounding ideas. (Concur with @IlmariKaronen.) $\endgroup$ – Squeamish Ossifrage Aug 15 '17 at 18:22

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.