0
$\begingroup$

I want to implement a protocol which requires Integrity and Authentication for its messages. I found a lot of algorithms such as HMAC, UMAC, and Poly1305 which provide Integrity and Authentication. So I get confused for which one must I use. Please, could I know which one is better?

$\endgroup$
  • $\begingroup$ You do realize that any question 'which algorithm performs better' is almost always extremely dependent on the environment (if you're using a CPU, then which CPU, language, etc) $\endgroup$ – poncho Mar 13 '18 at 15:04
  • $\begingroup$ it is a protocol so any language or a CPU must be work with it, although I will implement the protocol by using C++. $\endgroup$ – Aymn Alaney Mar 13 '18 at 15:44
  • 1
    $\begingroup$ Most languages and CPUs can handle pretty much any algorithm. However, you specifically asked about performance; it's very easy that algorithm X is faster on CPU A, while algorithm Y is faster on CPU B. $\endgroup$ – poncho Mar 13 '18 at 16:44
  • $\begingroup$ On which hardware? For example GHash is only fast one hardware with support for binary field arithmetic. And for HMAC you also need to specify which underlying hash algorithm you want to use, since it's only a construction, not a fully specified MAC function. $\endgroup$ – CodesInChaos Mar 13 '18 at 16:56
  • 1
    $\begingroup$ HMAC and UMAC are classes of algorithms, so conparing them to Poly1305 is meaningless. $\endgroup$ – Melab Mar 14 '18 at 4:12
2
$\begingroup$

First of all, HMAC—with any particular hash function, say HMAC-SHA256—is a different type of thing from UMAC and Poly1305. So it would be misleading to compare them directly.

HMAC-SHA256 is a pseudorandom function family, or PRF, with long inputs and short outputs, meaning a keyed family of functions $H_k\colon \{0,1\}^* \to \{0,1\}^{256}$ such that if the 256-bit key $k$ is uniformly distributed, then $H_k$ appears to be uniformly distributed among all functions $F\colon \{0,1\}^* \to \{0,1\}^{256}$. You can use this to authenticate messages by using $t = H_k(m)$ as an authentication tag, because an adversary not knowing $k$ can't guess $H_k(m)$ much better than an adversary not knowing $F$ can guess $F(m)$, which in turn they have a $2^{-256}$ chance of guessing in one try.

UMAC and Poly1305 are one-time authenticators. You can use a key $k$ once to authenticate a single message $m$ by using $t = \operatorname{Poly1305}_k(m)$ as an authentication tag. If you ever reveal $\operatorname{Poly1305}_k(m)$ and $\operatorname{Poly1305}_k(m')$ where $m \ne m'$, an adversary can trivially compute $k$ and forge authentication tags on any message of their choice. But you can extend these to work on many messages, each with a distinct sequence number or noncolliding random token $n$ called a nonce, by composing them with a PRF, and instead using, e.g., $t = \operatorname{Poly1305}_{k_n}(m)$, where $k_n = \operatorname{HMAC-SHA256}_k(n)$. You must never reuse the same $(k, n)$ pair with two different messages.

For more on message authentication codes, one-time authenticators, HMACs, and pseudorandom function families, an earlier question has several good answers.

Typically, these days, Poly1305 is used in a predefined composition called NaCl crypto_secretbox_xsalsa20poly1305 or one of libsodium's variants of it, which uses the PRF XSalsa20 both to derive the one-time keys $k_n$ and as a stream cipher to derive one-time pads for encrypting a message, at the same time. This authenticated encryption composition, crypto_secretbox_xsalsa20poly1305, is much faster on pretty much any CPU than any authenticated encryption involving HMAC. (Possible exception: Maybe on a tiny microcontroller you will have hardware support for HMAC-SHA256, but not for XSalsa20 or Poly1305.)

Does that mean HMAC-SHA256 is useless? No. You don't always have a message sequence number in a conversation. For example, if you are distributing a bearer token in a mostly stateless web application, in order to use Poly1305 as an authenticator you would have to include a ${\geq}192$-bit randomly chosen nonce as an input to a PRF to select the key, which together with the 128-bit Poly1305 output would cost 320 bits of space for an authenticator tag, while for essentially the same security (for short messages and low volumes of data) you could use the 128-bit truncation of HMAC-SHA256 instead, or BLAKE2s-128, or KMAC128-128.

$\endgroup$
  • $\begingroup$ Would it make sense to add KMAC (Keccak MAC) to this "comparison"? KMAC isn't a MAC in the usual sense, and is distinct from HMAC-Keccak (since Keccak doesn't need protection against length extension). $\endgroup$ – Ruben De Smet Mar 13 '18 at 20:03
  • 2
    $\begingroup$ @RubenDeSmet: KMAC is a MAC in the usual sense (i.e., resists existential forgery under adaptive chosen message attack). If your application calls for a MAC (or a PRF)), KMAC is every bit as functionally appropriate as HMAC. When you say that "KMAC isn't a MAC in the usual sense" I think you might be confusing "HMAC" and "MAC." Think of it this way: HMAC is to MAC as citrus is to fruit. $\endgroup$ – Luis Casillas Mar 13 '18 at 20:53
  • $\begingroup$ Yes, sorry, I meant to say KMAC isn't a HMAC in the usual sense. Typo. I meant, the question was partly about performance, so at that point it would make sense to include it. $\endgroup$ – Ruben De Smet Mar 14 '18 at 8:19

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.