Is TEA suitable for encrypting/authenticating many short messages?

Question

I know that TEA has its weaknesses, but is easy to implement. My question is whether it would be suitable for my use case: The main reason for using encryption is not so much secrecy, but authentication and protection against interference.

• I have a number (max 20-30) of GPS trackers, which send their location by radio in intervals to a base station.
• Each message consists of a tracker ID, a timestamp, the location, and a checksum, so max 16 bytes, but in a fixed format.
• Each message will be similar to the previous one, as the time increment will be constant, and the location will not change very much between two subsequent messages.
• The time frame is about three hours, with probably about 800 messages sent per device during that period. So roughly 20k messages in total.
• the code of the system will probably be public (so security through obscurity will definitely not work)

What I want to avoid from happening is anyone sending fake messages that are mistaken for real positions; decoding the message content is not a problem, as anyone can observe the trackers moving around anyway if they wanted to. So if it takes more than three hours to crack the key and enable sending fake messages, that would not be an issue, as that means the window in which a single key is used would be over.

I guess what I really need to know is:

1. Is TEA (or XTEA, or XXTEA) at all suitable for this use case? And if so, vanilla or X/XX? Or is there another algorithm that would be better suited? For example, just a hash checksum?
2. Are there any other ways I could improve security (eg use a different key for each tracker, randomly vary the format of the message (location first vs timestamp first), compress the message (only store difference to previous location, eg, to remove some redundancy))

My main design goals are reasonable security (it's competitive sports, not secret missile plans), simplicity of use and implementation (I am a developer, not a cryptography expert), and low computational overhead (this will run on an ESP32 micro-controller).

I have some basic thoughts on this, but would appreciate some expert advice!

UPDATE: Since this was asked in one of the answers: the trackers will be initialised in close proximity on power-up, and the base station can transmit a 'secret' key via Bluetooth Low Energy to each tracker. I do realise that Bluetooth is not really secure, but given the proximity this is in my view a negligible risk.

Answer 1

What I want to avoid from happening is anyone sending fake messages

The simplest option for this is

• A secret key $K$ in trackers and base station that adversaries ("anyone") can not get at. This is the hard part, and the original question was short on this. While BLE pairing is imperfect, at least that's a defensible plan.
• A Message Authentication Code of the message, made and checked using that key. That MAC would be appended to the message, sent un-encrypted.

Is TEA (or XTEA, or XXTEA) at all suitable for this use case?

Yes, it's possible to make a Message Authentication Code out of TEA, if you can manage to have a random 16-byte secret key $K$ shared by trackers and base only. For a fixed 16-byte message, that's two 8-byte blocks $M_0\mathbin\|M_1$, and $\text{TEA}_K(\text{TEA}_K(M_0)\oplus M_1)$ would be a fine 8-byte MAC, per the CBC-MAC construction (if message size is variable, an appropriate padding is required; a variable number of messages blocks remains safe if it's possible to determine that number from the first block).

vanilla or X/XX?

Any would be safe in the context, but I'd use vanilla, because it's the best studied and simplest. Neither XTEA nor XXTEA meet their more ambitious design goals, see this.

Is there another algorithm that would be better suited?

Another recommendable Message Authentication Code is HMAC-SHA-256. It's better suited if you have SHA-256 at hand, and more widely recognized as safe.

If for some reason we want to encipher (despite that not being necessary to meet the stated security goals), we want authenticated encryption (as envisioned in another answer). That can be built on top TEA, but adds sizable complexity. In particular, that's probably going to need two keys (one for encryption, the other for authentication, at least internally); and there's the issue of ensuring unique (if not unpredictable) IV.

Are there any other ways I could improve security ?

Using a different key for each tracker is useful if adversaries need to hack several trackers instead of one to do whatever their nefarious plan is. The base station needs to choose the key according to the tracker ID (found from the message, which at least in this segment must not be encrypted).

For good MACs, it's immaterial if there are many messages that are extremely similar. The other ideas in the question thus add complexity and at best little security, I'd say their net balance from a security standpoint is negative.

It's useful that the base station squelches out (or flags as suspicious) messages which timestamp is inconsistent with the current GPS time (later or earlier by more than some allowances, respectively tiny and small). That prevents replay (and is easier to make immune to temporary glitches than comparing timestamps to that of earlier authenticated messages from the same tracker).

Especially combined with per-tracker key, it's useful that the base station validates data from each tracker by checking that the distance since the earlier position (obtained from an authenticated message from that tracker) is physically possible (e.g. distance less than the product of timestamp difference with some maximum speed).

Adding Diffie-Hellman key exchange in the setup phase would make it impossible that a passive eavesdropping of the initial BLE connection reveals the key (even if that connection somewhat does not use the best of the many options in BLE pairing). It won't guard against all active attacks, but these are much more difficult to carry, especially from a distance.

Answer 2

The main reason for using encryption is not so much secrecy, but authentication and protection against interference.

In that case, what you want is an authenticated encryption scheme. While TEA, as a block cipher, may be used to implement such a scheme by using it in some suitable AE mode (such as SIV), there are also a number of dedicated lightweight authenticated encryption schemes that you may wish to look into.

In particular, I'd suggest taking a look at Ascon, which was selected as the primary choice for the use case 1 (lightweight authenticated encryption) in the final round of the CAESAR competition last year. While not quite as simple as TEA, the reference implementation isn't all that complicated.

---

Since your message length is fixed and very short, you could obtain a simple authenticated encryption scheme just by using a block cipher with a block size longer than your message length, padding your messages up to the block size e.g. with zero bytes, encrypting the padded message directly with the raw block cipher (i.e. in "ECB mode") and verifying the correctness of the padding after decryption.

However, for this you'd want a block cipher with a block size of (at least) 128 bits (= 16 bytes), which TEA doesn't have. XXTEA could work, though.

With 4 bytes of padding, the odds of an attacker randomly guessing a valid ciphertext would be 1/2³² per attempt, which seems likely to be low enough for your purposes. This would be a deterministic encryption scheme, so it would leak whether or not two plaintexts are equal, but that shouldn't be an issue for you since your messages include presumably unique timestamps anyway.

---

As for the security of TEA or other crypto primitives for your purposes, the first thing I'd like to note is that it seems extremely unlikely that anyone would develop and implement a novel cryptanalytic attack just to interfere with your system. Thus, you should be fine as long as the scheme you're using:

• has withstood any serious cryptanalysis at all (i.e. it's not just some random homebrew cipher kludged together by someone with no crypto experience),
• has no known practical attacks (i.e. with complexity well under 2⁶⁴ or so operations) with published attack code that someone could just download and run, and
• the way you're using it isn't broken in some way that would allow someone to bypass the actual cipher entirely.

In fact, you might be fine even if one or more of the above happened to be false, as long as none of your potential opponents has the skills or motivation to analyze your scheme and develop an attack against it. But as long as you're using a cipher with no simple practical attacks, and use it correctly, you should be safe even if someone with some crypto skills does decide to try to attack your system.

Honestly, your biggest weakness is likely to be the last point. That's how most cryptosystems get broken in practice — not by breaking the underlying ciphers or other crypto primitives, but by finding bugs or design flaws in the way they're used.

To give a simple analogy, the strongest lock on your door won't help if you leave a window open or leave the key under your doormat. With crypto, as with physical security, the whole system is only as secure as its weakest link. And the weakest link in your system is almost certainly not the block cipher, whether it's TEA or AES.

Answer 3

Yes you can use TEA. What you want is to add a MAC, a message authentication code. And you can use TEA as the underlying cipher. You need not encrypt the data if it isn't required, it's even better not to. TEA uses a 64 bit block. You could do CBC-MAC which will add a 64 bit authentication and it won't be cracked in hours.