4
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ UMAC of what data? Are UMAC's and TEA's key fixed, if not how are they derived? In what operating mode is TEA used ? What are all the usages made of Nonce (generation, check if any, usage for key derivation / UMAC / TEA)? $\endgroup$ – fgrieu Sep 14 '18 at 14:34
  • $\begingroup$ The keys are fixed. I actually have no idea about operating mode - looking at implementation the function gets 8 bytes of data and returns 8 bytes of encrypted data. It seems that the nonce is used in conjunction with the umac key to generate the umac hash $\endgroup$ – Victor Iorinescu Sep 14 '18 at 15:32
6
$\begingroup$

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

$\endgroup$
  • $\begingroup$ I don't understand what you mean by "The UMAC illustration in C code considered as reference in the question is secure only for single use of its key" - if I have to change the key every time I send a message what is the point of the nonce? $\endgroup$ – Victor Iorinescu Sep 26 '18 at 14:04
  • $\begingroup$ @Victor Iorinescu: With the code linked you do have to change secret at each use ! The role of the nonce is to serve as input to a secret function (or to public function with long term secret key) computing the secret for each nonce. $\endgroup$ – fgrieu Sep 26 '18 at 17:00
  • 1
    $\begingroup$ Oooo I understand now; I thought the nonce is used directly. I always wondered how using an incremental nonce, that starts from low values won't create bigger security problems. But going through a function first makes complete sense. $\endgroup$ – Victor Iorinescu Sep 28 '18 at 11:56
  • 1
    $\begingroup$ @Victor Iorinescu: the system I propose checks 50 bits out of the 64 bits that it deciphers, hence has probability $2^{-50}$ to let a random error undetected (on top of CRC). That's better than the $2^{-24}$ of the UMAC variant you have been considering. Really, it is superior on all counts (including shorter transmitted message size, speed, ease of implementation, robustness against side-channel attacks). That's possible (only) because you have a small payload; for something larger, I'd recommend a MAC. $\endgroup$ – fgrieu Sep 28 '18 at 12:53
  • 1
    $\begingroup$ @Victor Iorinescu: the nonce is included in the message, thus it is known to the verifier, verified, and counts in the security against forgery (and random errors) even when the adversary can choose it freely. I now explain why in the answer. If there's no CRC, indeed that can't be counted towards detecting random errors. I have fixed the statement w.r.t. resistance to timing attack (previously I assumed that the nonce check was performed first and in constant time). $\endgroup$ – fgrieu Oct 4 '18 at 12:23
3
$\begingroup$

First the good things:

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.

$\endgroup$
  • $\begingroup$ The message length is fixed the 16 bytes presented. My actual data at its max is 14bits<2bytes. $\endgroup$ – Victor Iorinescu Sep 14 '18 at 18:02
  • $\begingroup$ The 1 byte header has 2 purposes: the first 4 bits as a message start identificator and the rest of the 4 bits as a message version - now version 1 (maybe in the future I'll have a bigger microcontroller with a bigger message, maybe encrypted with other algorithm wich will be version 2 - thus I'll be able to decrypt both types of messages) $\endgroup$ – Victor Iorinescu Sep 14 '18 at 18:02
  • 1
    $\begingroup$ Yes, TEA an UMAC are suited for the task at hand. But what the question links to as UMAC code is actually code for a part of UMAC, and requires use of a block cipher (possibly TEA with another key) to become UMAC. $\endgroup$ – fgrieu Sep 16 '18 at 6:33
  • $\begingroup$ @fgrieu I don't understand what you mean "requires use of a block cipher"; isn't calling that function as instructed "It assumes that secret is a multiple of 24 bits, msg is not longer than secret and result already contains the 24 secret bits e.g. f(nonce). nonce does not need to be contained in msg. " with the nonce always changing enough? $\endgroup$ – Victor Iorinescu Sep 26 '18 at 14:00
  • $\begingroup$ @Victor Iorinescu: I'm paraphrasing RFC4418: UMAC enjoys a rigorous security analysis, and its only internal "cryptographic" component is a block cipher. The wiki phrase you quote computes secret as f(nonce) which makes secret single-use, and something in that f must be secret (since nonce is public). Implementation of that secret function f can be with a block cipher (including TEA) and a long-term secret key (but not the one used for encryption). As pointed in my answer, this is unnecessarily complex in your case. $\endgroup$ – fgrieu Sep 26 '18 at 17:12

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.