Is this algorithm good enough for small radio messages?

Question

This question is related to:

How to implement security - authenticity/confidentiality/integrity for 6/14 bits radio messages?

I am looking for a message that an attacker listening to the radio trafic will need at least 2 weeks to break it.

I came with this solution:

• 1 byte header
• 3 bytes UMAC
• 4 bytes Nonce (incremental number)
• 8 bytes data (encrypted with TEA)

Each party has its own keys for UMAC and TEA already known by the other party.

I would like to use the wiki umac implementation which has about 30 lines of C code and the wiki TEA implementation with 10 lines for encryption and the same for decryption. The small code is very helpful with my tiny microcontroller ram/flash size.

So, is it enough for my requirements? Can the message size be further decreased by implementing umac for unencrypted data and then encrypt umac+nonce+data altogether?

Edit - Clarifications on creating the message:

Compute TEA encryption for the 8 byte data with TEA key.

Compute UMAC with umac key and nonce for the previous encrypted data.

The keys don't change.

Answer 1

The question, even complemented with three useful comments, leaves me worried about the security of the system envisioned, for several reasons (from most to least serious)

1. The UMAC illustration in C code considered as reference in the question is secure only for single use of its key. Actual UMAC requires a block cipher, which is not stated in the question, and its code is sizably larger. While that block cipher could be TEA, that must not be TEA with the same key as the one used for encryption (that would at least invalidate the security argument of UMAC, and perhaps open to attacks).
2. It is not stated what the receiving device does when the UMAC check fails. If it allows other checks, including with another nounce, a 3-byte MAC seems hardly good enough: a forgery requires an average $2^{23}$ attempts (twice that if the nounce is forced to change), and at 100 per second that's less than a day. If on the other hand the receiving device stops operating when the UMAC check fails, there's a reliability problem. Rate-limiting is hard to make right, especially to make it resistant to Denial Of Service and/or random power loss.
3. A naive byte-per-byte implementation of the UMAC check could be very vulnerable to timing attack (reducing the average number of attempts to only about $3\cdot2^7$).
4. A less naive implementation doing the UMAC final check in constant time could still be vulnerable, because UMAC requires multiplication, and that's far from always constant time on a "tiny microcontroller".

---

Since the payload is so small (14 bits), there's a much simpler solution without UMAC (thus reducing code and removing 3 bytes in the message) that solves much of the above (in particular increases the expected number of attempts for forgery to almost $2^{49}$ attempts).

The idea is that

• The sender enciphers with TEA and the fixed shared key a 64-bit block concatenating:
  • the 32-bit Nonce/incremental number
  • 18 bits at zero
  • the 14-bit payload
• The message (13 bytes rather than 16 in the question) is:
  • 1 byte header
  • 4 bytes Nonce (incremental number)
  • 8 bytes cryptogram (Nonce, zeroes, payload encrypted with TEA)
• The receiver(s) deciphers the cryptogram, checks that the deciphered 64-bit result starts with the Nonce (extracted from the message) and 18 bits at zero, and considers the message invalid otherwise. If a check of the Nonce is performed (e.g. that it is incremental), that check occurs only for valid messages.

This is demonstrably insensitive to timing attack as long as:

• The implementation of TEA is constant-time (see note)
• The 32-bit Nonce
  • is checked first and in constant time, e.g. using a single 32-bit compare,
  • or is checked together with the 18 bits at zero and in constant time.
• Nothing with data-dependent timing is performed with the 14-bit deciphered payload when the above integrity check fails.
• The TEA cipher is unbroken (as its stands).

Update per comment: the 32 bits of Nonce do count towards integrity. Argument: an adversary trying to make a forgery can either:

• Reuse a 64-bit TEA cryptogram previously used in a genuine message, and then can either
  • Uses the Nonce in that genuine message; the message will pass the cryptographic check, but will be identical to the original message, thus does not count as forgery (beside, the repetition of the Nonce may allow rejecting the message, since the Nonce is supposed to be incremental)
  • Use a different Nonce; the message will be rejected, thus does not count as forgery.
• Use a 64-bit TEA cryptogram that never was used in a former genuine message; assuming security of the TEA block cipher (and given that there can be as most $2^{32}$ genuine messages with a 32-bit the Nonce), the adversary has essentially no information about the result of the decryption of that block by the verifier. Whatever the value of the Nonce submitted to the verifier, the verifier will perform that TEA decryption, then a comparison including the Nonce bits, and the adversary has no way to predict the correct Nonce other than by trying (that's where at least the Nonce must be checked in constant time). Hence each additional bit of Nonce doubles the number of queries to the verifier (hence the duration of the attack) for a given forgery probability.

Update: if the header needs to be authenticated, change the 64-bit block format to 8-bit header, 32-bit Nonce, 10 bits at zero, 14-bit message; keep checking every bits except the message after decryption; and check at least header+Nonce (anything the adversary can vary) first and in constant time.

---

Note: In practice, it is hard to accidentally make TEA not resistant to timing attack. That would require the following two lines of code to exhibit a timing dependency w.r.t. v0 v1 k0 k1 k2 or k3, which is near impossible with 32-bit registers, and plausible only with smaller registers and code that does not use addition-with-carry or rotate-thru-carry.

    v1 -= ((v0<<4) + k2) ^ (v0 + sum) ^ ((v0>>5) + k3);
    v0 -= ((v1<<4) + k0) ^ (v1 + sum) ^ ((v1>>5) + k1);

(I often met C compilers for 8-bit CPUs that generate code with data-dependent timing for addition of a small constant to a variable, or addition of variables of different size; but never one that did that for addition of variables of the same size, as would be the case here in practice).

---

Note: in practice, the hardest part is generating and checking the nounce robustly, in the presence of random power loss and/or DoS. Write and erase in EEPROM or Flash is not atomic, sometime fails, and occasionally leaves the memory cells in a state where the value read varies (with temperature, supply voltage, or random noise).

Answer 2

First the good things:

• The scheme is encrypt-then-authenticate.
• TEA and UMAC are both suited for the task at hand and the TEA weaknesses do not matter here, even though fgrieu has found some problems with the described use of UMAC.

Now the two issues:

First, the encryption is deterministic. This is mainly a problem for the privacy of the messages. In particular if you send an 8 bytes message, say "ATTACK!\0" (in C notation) and later send the same message again under the same key, you will get the same ciphertext both times and an adversary can e.g. infer that they're going to get attacked soon. Now the fix for this is quite simple in that you can simply use CTR-Mode, that is you use the nonce that you already have and encrypt as $E_K(m)=\operatorname{TEA}(\text{Nonce}\parallel 0^{32})\oplus m$ where $\parallel$ denotes concatenation, $\oplus$ bit-wise XOR and $0^{32}$ 32 zero-valued bits.

Second the header and the message length is not authenticated. If the header actually contains semantic information, like eg the intended recipient, it should be fed into the UMAC as well to ensure that e.g. the message cannot be delivered to the wrong recipient and accepted. An additional potential issue is that the message length is not explicitely fed into the UMAC as of now. This is mostly a defense-in-depth measure and can be especially useful if variable-length associated data or variable-length ciphertexts show up at some point.