Encryption for very low data rate embedded systems

If your latest IOT project needs to run on batteries for a few years and you need to send some important data over the airwaves or across a serial line then you are in a bit of a poor situation when it comes to normal encryption.

While adding 1 to the ACSII character and sending the message backwards worked for Tin-Tin and looked like a good idea when you were 10 years old, you really are are going to look a bit silly when your device gets hacked and an impostor can read key data or more seriously send false messages which will be interpreted as one from your sensor.

Proper encryption is generally known as public key encryption requires quite a complicated algorithm to compute and requires a private key stored in your IOT device and a public key stored in the remote device to decode it. You default low power AT-Mega or PIC 8-bit microprocessors struggle a bit in this situation and the normal course of action is to bite the bullet and upgrade to a 32 bit core, but what if I said there is another way which requires no messy complicated math or algorithms and is totally unbreakable?

Well there is a simple solution, one which uses the oldest (and most unbreakable) encryption method known to man, it’s called the One Time Pad or OTP. It is however really only suitable for very low data rate sensors as this method requires a random byte for every single encrypted byte you want to transmit. Here’s the big thing though, you only want to encrypt the actual data values and the checksum not the header, preamble and other fluff, in fact this should really not be encrypted using your key as repeating the same header bytes over and over again will make your encryption scheme several-giga-orders of magnitude easier to decrypt!

Also if the data is unimportant (and that is a thing you need to decide carefully) and your happy anyone can read it (say temperature readings in a field) then the only thing you need to protect against is `man in the middle` attack in which somebody else sends your message with false data in it. In these cases you really only need to encrypt the CRC to produce a digital signature so you can check the data is true and has not been compromised.

So for the theoretical temperature sensor above, if we to do the math

2 bytes/temperature reading
24 temperature readings a day
365 days a year
5 years operation

= 87.6KB of data

Now that seems like a lot in the micro-controller world, but in the above case the pattern would not repeat until 5 years have passed and if you seriously think somebody is going to intercept every message so they can work on their 5 year master plan to disrupt your operation with bad data then you are seriously working for the wrong businesses!

In cryptography there is a well known fact that if you xor a random byte with another random byte you get (wait for it) a different random byte so here is where you can be clever at the expense of a small loss of security so it you have three arrays of random numbers crypto[3][256] then you can make 24 million new numbers using:

NewRandom[a*b*c] = crypto[0][a] ^ crypto[1][b] ^ crypto[2][c]

The NSA/GCHQ will possibly be able to attack this with enough data points however everytime you increase the array size and add another element into the xor chain the math becomes too hard to predict even when you know the algorithm and the unencypted source byte. Anyway more about this in a future post (with code I promise)

So back to the simple OTP, for super secure I need 87.6KB of ROM.

Both the sender and the receiver need this same random data pattern, and it will need to be random as the normal RAND() functions of your favourite programming language are not actually that random. DES encrypting such a random stream would make it pretty near random as we can get without going to silly extremes.

To do the actual encryption the two bytes of data will need to be XOR’d with two of the OTP/RND key bytes and the next position in the OTP/RND ROM table incremented (below). The receiving system does exactly the same XOR function on the encrypted data and out pops the good data.

Thats all there is to it, there really is no need to do any further encryption as the OTP is theoretically unbreakable without the KEY. (so don’t ruin it by publishing the header on Github!)

If you have more data and your microprocessor is maxed out of flash then the method I have used is to use serial SPI flash which costs a few dollars. 64MB Serial flash in an SOIC8 package can store 8MB of of KEY data which could be used for bigger or more frequent messages but if your getting that big you really need to go to a bigger micro and one of proper PKE or DES encryption libraries.

And of course, once your fully encrypted then you can add a 1 to the ASCII message and transmit it backwards just to piss off the NSA 🙂

More to follow