How to properly cypher 16 bytes message containing a CRC checksum?

Question

This question arose from a new context under early developments. If cryptographic operations are not well chosen or badly sequenced, please do notice it along your answer or comments: I am a layman in cryptography. If you think this post should be improved, any constructive feedbacks are welcome, I am new to this stack.

Imagine I have an IoT sensor that needs to send few bytes of data over a wireless network. The physical payload from sensors is about 11 bytes, then we would like to construct from this a network payload as this:

• Pad physical payload to 12 bytes;
• Compute checksum using CRC32 and append to padded physical payload;
• Encrypt 16 bytes with a cryptographic algorithm such AES with CBC mode.

Provided it is a good idea to proceed as stated above: How must I setup the cryptographic part to make it robust, mainly:

• Is this cryptographic standard relevant for this kind of task?
• How do I chose the key size?
• How do I chose the Block size?

Last but not least, is it known if: Does CRC32 stored in a message reduce the strength of the cryptography as it introduces a relationship among bits in the message?

Answer 1

Is this cryptographic standard relevant for this kind of task?

Yes to a degree, but with what's in the description (and assuming the CRC is checked after AES-CBC decryption)

1. There is no protection against replay of earlier captured messages. The usual options to protect from replay are a two-way protocol where the receiver generates a nounce made part of the message carrying sensor data, or/and a sequence counter maintained by the sender (but only the former solution insures freshness).
2. This is symmetric crypto, hence the sender is bound to contain a secret that allows decryption, and the receiver is bound to contain a secret that allows forgery of information. Both issues can be fixed by asymmetric crypto.
3. CRC-then-encrypt in general does not give integrity protection, and if encryption was with a stream cipher or the common AES-CTR, it would be trivial to alter the data in real time. The use of CBC encryption happens to save the day (because AES encryption of one block is not malleable), but that's a lucky choice more than by design. And if the message was larger than 12+4 bytes and thus did not fit a single AES block, I would not bet the house that there is no cryptanalytic attack on the integrity protection.
4. The integrity protection is only 32-bit. An adversary submitting 1000 random ciphertexts per second to each of 1000 receiving systems will sneak one thru the decryption and CRC check more often than once in 1h 15' ($2^{32}/10^6$ s) on average.

The academic solution to 3 and 4 is authenticated encryption, designed for both confidentiality and integrity. One of the most well-known is AES-GCM. It is improved in AES-GCM-SIV.

How do I chose the key size?

There are three for AES: 128, 192 or 256-bit. They are safe/fastest, safer/faster, or safest/fast. In the context, AES-128 is technically sufficient, because the real threat is that the key somewhat leaks (gets extracted from either the receiver or sensor). AES-256 looks better on the spec sheet, likely is fast enough, and I do not see that it can make key extraction easier; so why not?

How do I chose the Block size?

You did: AES can only be used with 16-byte block.

With AES-CBC (if kept against my recommendation of authenticated encryption) one choice you have is the padding mode, and the best is "no padding", since any padding will cause an extra 16 bytes of ciphertext.

Other, much harder things to determine for a real system are:

• how the Initialisation Vector for encryption is generated;
• how the keys are drawn;
• how they are injected in the devices that need them;
• how key leak is made unlikely;
• how keys are rotated (changed, periodically or to recover from a suspected leak).

Does CRC32 stored in a message reduce the strength of the cryptography as it introduces a relationship among bits in the message?

No, unless there was an exploitable weakness of AES iself, which can be discounted. Modern ciphers are designed to safely encrypt known plaintext, and thus are safe for redundant plaintext.

Answer 2

Appending the CRC to the data and then encrypting the whole block before sending will severely compromise the error detection capabilities of the CRC. In fact, a single bit error during transmission can cause you to decrypt a completely garbage message and still have a valid CRC check with a non-negligible probability.

A CRC is designed to detect a small set of bit errors due to line noise. Every transmission line (ie: serial cable, RF link, etc.) suffers form the effects of noise. It's impossible to eliminate it. Instead, a designer is interested in knowing how often this noise will affect data bits being sent over the line. This is measured as a bit error rate (BER). Conceptually, you send a large number of bits over a link and count how many were correctly received vs how many were not. The ratio of the bad bits to the total is an estimate of the BER. For a practical link, this has to be pretty low, otherwise there will be a large number of message retries. Generally, the lower the BER, the more effective speed you have as there will be fewer errors to recover from.

A CRC is designed with a small BER in mind. Choosing a good primitive polynomial will gaurantee certain classes of bit errors will be 100% detected (ex: 1-bit, bursts up to size of polynomial, odd errors, etc.). There is a small upper limit of how many bit errors can be reliably detected. If you exceed this number, the CRC may fail and report a false positive.

Now a properly designed block cipher (ex: AES) has the property of good diffusion, meaning that a single bit change in the plaintext will cause the ciphertext to have about 50% of its bits changed. With respect to the impact of encrytion on data going through a link, encryption acts as a massive amplifier of the BER. A single bit error in the ciphertext, when decrypted, will lead to about 50% of the plaintext bits being wrong. This will drastically exceed the limits of the CRC to detect and the CRC will most likly fail to detect this situation.

Example :

• You format your data into 12 bytes.
• You calculate and append the CRC for a total of 16 bytes.
• You encrypt with AES and transmit the packet.
• Ambient noise causes a single bit flip to occur anywhere in the packet.
• Receiver decrypts packet
• Approximately 50% of data & crc bits are now wrong
• Receiver calculates CRC and it passes (because there are now too many bit errors to detect)
• You have garbage data, but a valid CRC!

The CRC must always be appended to the actual data being sent, otherwise you violate the entire assumption of how the CRC works.

Suggested solutions:

• Pad the packet to 16 bytes with some random data;
• Encrypt the packet
• Calculate the CRC and append to the packet

Note that this will now be a 20 byte packet (assuming 32-bit CRC)

If packet size is a design constraint, then the following solution can be used:

• Using a balanced Feistel Network on a 12 byte block and using AES as the mixing function, create a 12-byte block cipher.
• Encrypt the 12 byte data
• Compute the CRC of the encrypted data and append to the encrypted data for a 16 byte packet
• Send with confidence that transmission errors wll be detected :)

If you are going to implement the second suggestion (Feistel Network), I strongly suggest you verify your design carefully for correctness as rolling your own crypto is iherently insecure.

See here for some info on how to do this : Using AES for smaller blocks in a Feistel network