4
$\begingroup$

Consider a "MAC" that uses a symmetric key $K$ to generate an authentication tag $t$ for a message $M$ in the following way:

Concatenate a timestamp with the message (to prevent replay attacks) $$ m = \mathit{Timestamp}\mathbin\Vert M $$ Divide into suitable number of blocks. $$ m = m_0\mathbin\Vert m_1\mathbin\Vert m_2\mathbin\Vert\cdots\mathbin\Vert m_n $$ Compute CRC of a symmetric key concatenated between each block. (CRC algorithm is known - CRC-16/CCITT/CRC32). $$ t = \operatorname{CRC}(K\mathbin\Vert m_0\mathbin\Vert K\mathbin\Vert m_1\mathbin\Vert K\mathbin\Vert m_2\mathbin\Vert\cdots\mathbin\Vert K\mathbin\Vert m_n) $$ Send $C=\mathit{Timestamp}\mathbin\Vert M\mathbin\Vert t$ as the message.

Is this scheme suitable for message authentication against known plaintext attack given a large enough key size, with the assumption that it is infeasible to brute-force all $t$ during the time when $\mathit{Timestamp}$ is valid?


I have seen the following papers, however, they both say that the CRC polynomial must be a secret.

https://eprint.iacr.org/2015/035.pdf

https://eprint.iacr.org/2015/1138.pdf


Slightly related, but it uses an encrypted CRC as a MAC. I'm asking about using CRC as a MAC where the Key is included in the CRC calculations.

Is there a generic attack on encrypted CRC32 when used as a MAC?


Edit: Use case: I have hardware CRC module in a microcontroller that can evaluate CRC asynchronously with the core performing other computations. I am seeing if I can use this CRC module for message authentication as well.

$\endgroup$
  • $\begingroup$ Summarizing Squeamish Ossifrage's answer: No, a keyed CRC can't be used as a MAC; and a narrow (32-bit or less) hardware CRC module is not very useful towards building a secure MAC. $\endgroup$ – fgrieu Mar 14 '18 at 7:16
  • $\begingroup$ Besides what has already been mentioned, note that “CRC polynomial must be a secret" already hints at the main problem: there are only (let’s just call it) a hand full of polynomials for specific CRC lengths. This would already enable us to beat brute-force timings. $\endgroup$ – e-sushi Mar 14 '18 at 16:35
  • $\begingroup$ Yes, I found those papers interesting in the sense that I thought the idea was both insecure and against Kerchoff's principles. Thanks for the confirmation, @fgrieu $\endgroup$ – kodlu Mar 15 '18 at 3:52
12
$\begingroup$

Trivial forgery: If you know the CRC polynomial, then you can add (‘xor’) any multiple of it to the message without changing the CRC.

Short answer. If the hardware can only evaluate CRCs with fixed polynomials determined by the hardware designer, it's of little use to you for making a MAC. If you can choose the polynomial and the hardware keeps it secret, well, you've already found some references on how to do this!

The standard way to make a MAC out of a CRC, which we might call a polynomial division MAC and is sometimes called Rabin fingerprinting after a similar idea by Rabin, is to choose a secret irreducible polynomial $g \in \operatorname{GF}(2)[x]$ and a secret polynomial $h \in \operatorname{GF}(2)[x]$ both of degree $d$, uniformly at random; then, to authenticate a single message polynomial $m \in \operatorname{GF}(2)[x]$, transmit the polynomial $h + (m \cdot x^d \bmod g)$ as an authentication tag.

(The Rabin fingerprint is simply $m \bmod g$; it preserves addition of any degree ${<}d$ polynomial to $m$, enabling trivial forgery even if masked by $h$, so it is useless as an in-band authenticator, though it is more convenient for other purposes.)

By a standard result of number theory (alternative exposition), when $d$ is prime, there are $(2^d - 2)/d$ irreducible polynomials of degree $d$; for composite $d$ there are fewer, so prime $d$ gives the most efficient key space. But this does not cover all $d$-bit strings, and to generate a key, choosing an irreducible polynomial uniformly at random, e.g. using the algorithm in Rabin's paper (pp. 3–4), is costly. Using a product of irreducible polynomials whose degrees sum to $d$ enables cheaper key generation, but key space and tag space is wasted even more than with an irreducible $g$—the forgery probability is exponential in the number of irreducible factors.

Worse, computing polynomial division in $\operatorname{GF}(2)[x]$ by an arbitrary divisor is costly. Some CRC hardware admits programmable generator polynomials, but typical hardware uses a fixed polynomial, such as the Intel CRC32 instruction, which is useless for this—not to mention that a 32-bit tag is too small to provide any security. And in software implementations one is tempted to use table lookups to get any semblance of performance—invariably leaking secrets through timing side channels. So it's dangerous to design this into any protocols, because you're designing the temptation of timing side channels into the protocols.

There are perfectly good efficient MACs already for hardware and software: polynomial evaluation MACs. Fix a field $k$; a one-time key is a pair of elements $r, s \in k$ chosen uniformly at random, a message is a polynomial $m$ in $k$ of degree at most $n$, and the authenticator of the message is $t = m(r) + s$. The adversary's probability of success at forging a tag $t'$ on a message $m' \ne m$ given $m$ and $t$ is no more than $\#k/n$, by a standard argument of counting roots of the polynomial $m'(r) - m(r) + t - t'$ in the variable $r$. The most common examples are Poly1305, where $k$ is the prime field $\mathbb Z/(2^{130} - 5)\mathbb Z$ convenient in software, and GHASH, where $k$ is the binary field $\operatorname{GF}(2^{128})$ convenient in hardware.

Generating keys—picking elements of a field uniformly at random—is fast: for a binary field, uniform random bit strings work; for a large prime field (${>}2^{128}$), rejection sampling on uniform random bit strings works, and the probability of rejection is so small you can ignore it safely. Derive $r$ and $s$ from a PRF of a message sequence number or a sufficiently large random token and you get a many-time MAC.

The only reason to reach for a polynomial division MAC instead of a polynomial evaluation MAC is the bizarre scenario where (a) you do not have fast binary polynomial multiplication or integer arithmetic available, yet (b) you do have hardware that can efficiently evaluate polynomial division by arbitrary degree-${\geq}128$ divisors, and these performance constraints override all other considerations in your protocol design.

$\endgroup$

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.