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)
- 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).
- 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.
- 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$).
- 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).