11

I am currently designing a communication protocol for an embedded system. I've decided that authentication (but not encryption) is important, so I decided to add 4 bytes of truncated HMAC signature to every packet. At the same time, I also want to be able to do data verification to ensure that the data arrives correctly and hasn't been corrupted in transit. So I was thinking of appending a CRC32 to every packet. However, wouldn't the HMAC signature also be good enough for verifying the integrity of the packet?

Is there any point in adding both an HMAC signature and a CRC32? Or is an HMAC enough?

9a3eedi
  • 2,101
  • 3
  • 23
  • 29
  • If you haven't read through them, it may be instructional to skim through some existing protocol specs. [ETSI TS 138.212](https://www.etsi.org/deliver/etsi_ts/138200_138299/138212/15.02.00_60/ts_138212v150200p.pdf) includes a crc in § 5.1, but they're using it for CRC-aided polar and ldpc codes. Higher (MAC/IP) layers have more sophisticated integrity checks, which sounds like more what you're doing. There's no question though, if you're doing any CA-fec you *should* be using CRC because you'll be computing it multiple times per packet. – Steve Cox Feb 22 '21 at 18:37
  • Why is encryption not important? We might not need to see the answer, but you would need to find it nevertheless. – Oleg Lobachev Feb 23 '21 at 19:33
  • @OlegLobachev I don't really care if people see the data, but I do care that the device accepts commands from the right person – 9a3eedi Feb 24 '21 at 05:52
  • 1
    @OlegLobachev a good example of this sort of requirement would be a civilian remote control drone protocol. If there is telemetry data or video payload you might want some of that encrypted, but the minutiae of how much throttle to apply to each rotor probably just needs to be authenticated, (and there might be FAA regulations that require you to send those commands in the clear) – Steve Cox Feb 24 '21 at 11:32

6 Answers6

22

The CRC32 does not give you any guarantees that the HMAC does not also give you. Put another way, the HMAC gives you all the guarantees the CRC32 gives you and more: the CRC32 protects against unintentional alteration due to common transmission problems such as noise and interference, the HMAC also protects against intentional alteration.

The CRC32, however, may be less compute-intensive to verify. So, if your communication channel is very noisy and your receiver device is CPU-constrained, it may make sense to use the additional CRC32 to quickly throw away corrupted packets without having to verify the more expensive HMAC and only do the expensive HMAC verification on packets you know were at least not corrupted during transmission.

This balance may tip, however, if your chosen CPU has built-in acceleration for the cryptographic primitives used in the HMAC.

In the particular case of a noisy channel, it would probably make even more sense to use an Error Correction Code or some other mechanism for Forward Error Correction like a Hamming or Reed-Solomon code instead of only a mere Error Detection Code like CRC32.

Jörg W Mittag
  • 101,921
  • 24
  • 218
  • 318
  • 3
    Though, if I recall correctly, CRCs give known guarantees about the sort of errors they always detect, e.g. odd numbers of errors, or errors up to some maximum length. For truncated cryptographic hashes, you probably won't have that, just the statistics. – ilkkachu Feb 22 '21 at 18:47
  • 4
    @ilkkachu crc's can detect any errors that aren't congruent to 0 mod P (where P is the generator polynomial). They can always detect an odd number of errors because no odd polynomials = 0 mod P. They don't guarantee any detectability of any number of even errors because x^(n) = x^(n + 2^N - 1) mod P (N is the order of P), but their error detection performance within their period is considered to be excellent. – Steve Cox Feb 22 '21 at 19:01
  • @SteveCox: They can't promise to detect all two-bit errors in a packet whose length exceeds their period (since two erroneous bits which are spaced one period apart will cancel each other out), but when using a CRC32 I think most packets are apt to be much shorter than the CRC period. – supercat Feb 22 '21 at 22:18
  • @supercat yes, i believe that's what I said – Steve Cox Feb 22 '21 at 23:33
  • @SteveCox: You said their error detection within their period is excellent, but I certainly didn't read your comment as saying that they will detect all two-bit errors for packets shorter than their period. – supercat Feb 23 '21 at 00:02
  • @supercat I didn't explicitly point out the case of 2 bit errors within the period because the only thing that had been brought up was "errors up to some maximum length". Yes, the fact that x^n is incongruent to x^n+k for all k < 2^N-1 guarantees 2 bit error detection within the period. But this doesn't generalize at all. This doesn't hold for 4 or more even bits (this fact is generally true, but its immediately obvious with trinomial crcs). So i'd say describing error detection performance as "excellent" is just about the strongest claim you can make – Steve Cox Feb 23 '21 at 01:12
  • 11
    **This is completely wrong.** Not only does a 4 byte HMAC _not_ provide security against intentional modification (only a full HMAC can do that), but it is more vulnerable to accidental collisions as an _n_-bit CRC is guaranteed to detect any burst errors up to length _n + 1_, with the sole exception of the case where the CRC polynomial divides the burst error polynomial. – forest Feb 23 '21 at 01:20
  • 5
    Also, OP says this is for authentication, which is a security principle. Neither a CRC nor a truncated HMAC is sufficient for authentication. – forest Feb 23 '21 at 01:47
  • Why doesn't a 4 byte truncated HMAC provide security from intentional modification? What does a truncated HMAC protect against? Also, doesn't this depend on the packet size? – 9a3eedi Feb 23 '21 at 05:21
  • @SteveCox: Some kinds of errors will occur in largely independent fashion for multiple bits within a packet, so the probability of a double-bit error would be much higher than four a four-or-more-bits error, and thus a guarantee that all errors involving less than four bits will be caught may be useful even if it doesn't generalize to four-bit errors. – supercat Feb 23 '21 at 06:38
  • 1
    But *if* your HMAC is strong enough for authentication (i.e. you don't truncate it at all), like this answer says you don't need the CRC. This answer's proposed fast-discard benefit would only make sense if the majority of your packets were lost to noise (otherwise you're just doing extra work to verify the CRC before the HMAC on clean packets), so the only thing that would make sense is forward error correction (ECC), as this answer suggests (but not strongly enough). Discarding most of your packets is horrible and never an efficient use of available bandwidth. – Peter Cordes Feb 23 '21 at 10:17
  • Does this apply if your truncated HMAC is used for relatively small sized packets (say 128 or 256 bytes maximum). Doesn't the likelihood of a collision decrease much more if your packet size is small? – 9a3eedi Feb 23 '21 at 11:54
  • 4
    @9a3eedi: No, it doesn't (at least not to any significant degree), not until the packet gets shorter than the MAC token. – Ilmari Karonen Feb 23 '21 at 11:58
  • 3
    @PeterCordes: If the attacker can conduct an off-line attack, a 32-bit MAC wouldn't be worth much. If an off-line attack isn't possible, and the target of the packet can only receive 1,000 packets/second from the attacker, brute-forcing a 32-bit MAC would take weeks. For a device to discarding most packets that are targeted to it may be a poor use of bandwidth, but many radios are prone to interpret random noise as packets (the more eagerly a radio regards a weak signal as a packet, the more false packets it will report, but the greater its ability to usefully receive weak signals). – supercat Feb 23 '21 at 16:31
  • @supercat: my crypto is rusty, I forgot how HMAC worked, that what you're hashing involved a shared secret. So you're not just looking for a SHA-1 collision. So you can't test yourself locally to look for collision before sending. Yeah, it's not nearly as bad as real-time brute-force privately, if you don't have the secret key. (And truncated HMACs are no more likely to leak it than full HMACs.) – Peter Cordes Feb 24 '21 at 00:29
16

If you need secure authentication, use only the untruncated HMAC.

Assuming you don't care about security (which would be the case if you used a 4-byte HMAC), a CRC is actually better for detecting small accidental errors. An n-bit CRC is guaranteed to detect any burst error up to n + 1 bits in length, with the sole exception of a burst error whose polynomial divides the CRC polynomial, in which case the probability of the error going undetected is 1 (i.e. always goes through undetected). For detecting small errors, a CRC is superior. For larger errors which do not divide the CRC polynomial, they are equal, providing a 2-n probability of failure.

Note that this assumes the size of the digest is the same, i.e. CRC64 vs an 8-byte (64-bit) truncated HMAC or CRC32 vs a 4-byte (32-bit) truncated HMAC. Be aware that neither 64 bits nor 32 bits is sufficient to protect against an intentional error that bypasses detection.

John Kugelman
  • 202
  • 2
  • 7
forest
  • 414
  • 2
  • 9
10

The purpose of a Message Authentication Code (MAC), of which the HMAC is an example, is to prove both the authenticity and the integrity of the message.

The integrity protection is often framed as a protection against modification of the message by attackers, but it works equally for detecting accidental modification by bit-flips in the transport of the message. Thus, you don't need an additional CRC check to detect those bit-flips.

Bart van Ingen Schenau
  • 71,712
  • 20
  • 110
  • 179
3

CRC in addition to HMAC is pointless if you only verify the checksum at the final recipient, i.e. as a purely end-to-end protocol. However, it can be useful if the checksum is verified at intermediate steps that don't know the secret key. In particular, if the message is relayed through several hops, intermediate hops can delete messages with an invalid CRC.

Once the message has arrived at the final recipient, a CRC allows you to cheaply discard corrupted messages. This aspect is rarely useful in practice. If you're worried about accidental corruption, error correction codes will give you better results than a CRC: resending is a lot more expensive than fixing an error. If you're worried about a denial of service by a flood of invalid message, using a CRC doesn't really gain much: you might save a tiny amount of CPU power because CRC is faster to calculate than HMAC, but an attacker who can flood your CPU can typically flood your radio receiver anyway. One case where this is not true and a CRC can help is if your receiver consists of a fast application CPU combined with a slow secure element, and only the secure element has the HMAC key.

Note that a 32-bit MAC is very short and is only good if you don't mind that it's possible to attack a fleet of devices with a small, but nonzero rate of success. If you deploy a million devices and they can each process one message per second, a somewhat resourceful adversary can inject several fake messages every day. How bad this is depends on how much you can tolerate the occasional fake.

Gilles 'SO- stop being evil'
  • 2,680
  • 1
  • 21
  • 26
  • 1
    Re: "If you're worried about a denial of service by a flood of invalid message, using a CRC doesn't really gain much": I don't think a CRC gains *anything* in that case, because it's easy for the attacker to generate invalid messages that pass the CRC. – ruakh Feb 23 '21 at 06:01
  • What if it's one or two devices, with a short lifetime of a month or two, and very high latency and low bandwidth? – 9a3eedi Feb 23 '21 at 12:20
0

If you think about adding 32 bit CRC and 32 bit truncated HMAC: 32 bit truncated HMAC may be just about forgeable. Calculating HMAC not for the message, but message + CRC, might make it bit harder. What makes it a lot harder to forge would be to throw away the CRC and use a 64 bit truncated HMAC.

gnasher729
  • 42,090
  • 4
  • 59
  • 119
-1

Use the right tool for the job.

CRCs provide superior error detection to a same size HMAC function because CRCs detect all burst errors less than the CRC size and all odd numbered of bits errors.

Its also faster to compute CRCs.

cwallach
  • 327
  • 1
  • 7
  • 3
    If I didn't need the authentication, I would've kept the CRC only as it's much faster (important for embedded). However, I do need authentication, so should I keep both? – 9a3eedi Feb 22 '21 at 09:43
  • 1
    @9a3eedi If you do need authentication, then you should use only the full-length HMAC (despite what the currently accepted but incorrect as-is answer says). – forest Feb 23 '21 at 02:41
  • HMAC detects all burst errors with probability that is essentially 1. If you use a 256-bit HMAC digest, the chances that HMAC fails to detect a burst error is lower than the chances of a cosmic ray causing a bitflip error in memory that causes your computation to be erroneous in some other way. If you use a 32-bit HMAC, the chances of failing to detect a burst error are 1/2^32, which is so small that it's not really worth optimizing for. – D.W. Feb 23 '21 at 04:54