Encryption For The Most Meager Of Devices

It seems that new stories of insecure-by-design IoT devices surface weekly, as the uneasy boundary is explored between the appliance and the Internet-connected computer. Manufacturers like shifting physical items rather than software patches, and firmware developers may not always be from the frontline of Internet security.

An interesting aside on the security of IoT traffic comes from [boz], who has taken a look at encryption of very low data rate streams from underpowered devices. Imagine perhaps that you have an Internet-connected sensor which supplies only a few readings a day that you would like to keep private. Given that your sensor has to run on tiny power resources so a super-powerful processor is out of the question, how do you secure your data? Simple encryption schemes are too easily broken.

He makes the argument for encryption from a rather unexpected source: a one-time pad. We imagine a one-time pad as a book with pages of numbers, perhaps as used by spies in Cold-War-era East Berlin or something. Surely storing one of those would be a major undertaking! In fact a one-time pad is simply a sequence of random keys that are stepped through, one per message, and if your message is only relatively few bytes a day then you have no need to generate more than a few K of pad data to securely encrypt it for years. Given that even pretty meager modern microcontrollers have significant amounts of flash at their disposal, pad storage for sensor data of this type is no longer a hurdle.

Where some controversy might creep in is the suggestion that a pad could be recycled when its last entry has been used. You don’t have to be a cryptologist to know that reusing a one-time pad weakens the integrity of the cypher, but he has a valid answer there too, If the repeat cycle is five years, your opponent must have serious dedication to capture all packets, and at that point it’s worth asking yourself just how sensitive the sensor data in question really is.

56 thoughts on “Encryption For The Most Meager Of Devices

    1. I don’t have much knowledge of cryprography, so someone please correct me if this would weaken it or something but — you could transmit an unencrypted packet counter alongside your encrypted packet. Also, whatever’s on the receiving end in the example “remote sensor” application will likely have more processing power available, so it could easily check incoming data using a range of possible entries in the OTP table, assuming that there’s a way to determine of the decoded packet is valid.

      A thing to look at would be car remote locking keyfobs. They’re (hopefully) encrypted, and it’s quite easy to lose many packets if you’re out of range when you press the button.

        1. “Good idea about the keyfobs, one should always study notorious failures so as not to make the same mistakes.”

          I think statistically most auto related crime is very low tech. Pulling on door handles, smash-and-grab, that kind of thing.

          1. Yes, much like “Why would thieves tunnel into a safety deposit box vault when they could just punch old ladies in the street?”

            Because one is for stealing small change, and the other is for a larger payoff.

    2. I was thinking the same thing, but it should be simple enough.

      Make sure there’s some integrity check in the message, or some known value. Something like a header and footer indicating the start and stop of the message would be fine. Then if the decoded message is not readable, you can try decoding it a few more times going forward through your pad a little ways, or backward just in case. If you can’t find it within a specified range, send a plaintext request for retransmission.

    1. Encryption can be used for other functions, one to hide information and the other to validate information.

      While your little network of sensors might not be much of a problem. A network of sensors in a multi-tenant building could be. Suddenly my neighbors apartment could get much colder or warmer when they decide to keep that wild party running into the wee-morning hours. ;-)

      1. And you could fiddle with the smart meter that’s allowing electricity to their lights and stereo…these have a blackout option that they quietly don’t mention except in the fine print of your service contract.

  1. I don’t think the point of encrypting sensor data is to prevent others from using the data as much as making it harder to hijack via emulation to create some desired reaction from the device receiving said data.

    The car fob example, the usefulness of the data is only for tricking the reveiver, in this example, so as to gain access to the cars interior.

    Similarly, a remote temp sensor may be controlling something that one would not like having any interference from its intended function. Even if the interference is unintended, it’s useful, more so ifit is intended.

  2. I think just implementing private public key encryption is better, since speed doesn’t really matter, since it’s only 2 messages per 24 hours, sending it with a little bit of delay, would be fine. And since he is talking about adding flash memory for it in certain cases, I don’t think storage matters.

    1. You are Correct.

      A One time pad is the most secure form of encryption, even more so than all other encryption methods as there is no algorithm to attack – assuming the random key is truly random.

      But this assumes the key is private on both the sender and receiver and as you say you *don*t repeat the key.

      If you repeat the key you create a mathematical way to attack and break the system, this is still very hard with small message lengths and data that does not contain written words to do traffic analysis but it is possible. I worked in decryption 20 years ago in GCHQ and then it was brute force analysis and traffic matching, both would be difficult (read very expensive) to do on random sensor data (and there are easier physical attack vectors to get the information). With a challenge response system you are sending your data and adding the question “what are the three bytes starting at address xxxxx, the other system would look this data up and respond with the key which is transmitted back to the sender and can be verified, this would be a much easier scenario to break if you repeat the key, however the argument is who has the patience to collect all your messages and wait a year or two to get the key knowing you may have replaced the key in that time (see point 3 below).

      From experience I know that many car fobs, immobilizers, garage door openers etc used one time pad challenge response methods as above as it was quick and easy to implement (for the older immobilizers I remember the key was stored on the car than could be flashed back to the keys eaprom with some weird procedure and a yellow key fob)

      I think the argument is that this is for real low power micros and low data rates and you now do not have the excuse not to encrypt the messages in fact you have more choice:

      1. Not to encrypt (lets face it not everything needs encrypting)
      2. To use this OTP method and make it unbreakable
      3. To do the above and re-flash a new key when you replace the battery – duhhh, didnt think of that one did you :-)
      4. To do the above and repeat the key after X number of years in which case it is breakable but still hard.
      5. To do “proper” DES or public private key encryption, whatever, but in which case your device will need to be a 32 bit one and/or wake up from sleep for a lot longer to do the math.
      6. Buy a chip with hardware encryption.

      Of course on the other plus side the OTP algorithm is also the only encryption method you will ever be able to understand :-)

    2. Yep – at this point, it’s not a one time pad, but going from 128 bit encryption to 128 kilobyte encryption is going to be a bear to break the code. Add in that it’s probably not transmitting plaintext, and that an attacker has no idea how long the key is, and this is probably going to be secure enough. Unless you put the same key on a bunch of different devices.

      1. And honestly, what’s wrong with repeating the pad as long as the plaintext is otherwise private?
        You’d need the messages using the entire pad plus the plaintext to derive the pad.

        1. Because you only need the letter e to fall on the same part of the pad a few times then it’s vulnerable to frequency analysis… plus there are methods of plaintext injection, that tell you nothing if the pad is never repeated. For example, Alice and Bob have a short, repeating OTP encrypted com channel, so Carol sends Bob some juicy gossip she knows he’ll repeat verbatim to Alice. Then Carol knows her intercept contains that text.

  3. I’ve gotta admit that I really have never understood the rationale behind a paper one-time pad. Isn’t this printed and therefore there are multiple copies of it in circulation? Or is this based on the same principle as the Ovaltine decoder ring and Hackaday is going to start sending encrypted messages to its readers?

    1. I assume it’s like those printed books of raffle tickets. Some mechanism in the printing press that allows a completely unique set of characters in each book, with just the formatting and page numbers staying the same.

      Since it’s a bit of a niche product, they might just as well laser-print each one on demand. Or a hundred at a time, say.

  4. No idea how to actually use a one time pad, or I’d consider buying one. Nearly as useless as GPG; the documentation is not good enough to actually understand what you’re supposed to do with it.

  5. Apparently their micro controllers have a lot more spare EEPROM than mine do — there is a notable benefit of a NLSR over this. Also you’d need to replace both ends if you broke one half. Resyncing is actually pretty simple, you just embed a known value in the clear text, and then itrerate through the OTP decrypting values until you find it and that is the starting point in the pad. This is similar to how time-based and count-based authenticatiors work — they compute a range of values and then use those to determine the current time your token has or the current counter and then note the offset or value for future use (count-based units usually want two values in a row to ensure you aren’t spoofing them).

  6. If the solution is ultimately “well, nobody would bother monitoring this for 5 years anyway” then it’s not a very serious encryption system. And producing a half-arsed encryption system, that’s probably good enough bearing in mind nobody cares about the moisture levels in your field anyway, is easy.

    A one-time pad is just a truly random version of a PRNG, which you could just XOR at each end with your data. All this guy’s doing is choosing to store the key, the pad, in memory rather than generating it algorithmically.

    There’s no real point to this. The correct answer to “how to do strong encryption with limited resources” isn’t just “fuck it, we’ll do weak encryption”. There’s possibility for some ingenuity here but nobody’s bothered to try.

  7. It isn’t that hard to greatly extend the life of a one time pad. You traverse the one-time pad at random with the bits treated like they are mapped to a torus, sender and receiver have a unique shared secret keyed random number generator that returns 3 bits for 8 directions to the next bit in the bit field. A re-sync just requires the sender to tell the receiver what offset (t) the state machine generating the random numbers should be at (this assumes that the receiver is big and fast and can blast through the state steps quickly to get to the right position to decode the next packet after a resync), this can be secured with a smaller simple pad just for that purpose, one where the offset from bit zero is sent un-encrypted. An attacker could still cause it to burn up bits from the second pad by corrupting packets etc., forcing lots of restart negotiations, but not without you noticing that there were problems and even then they still are not to the point where they know what the next bit in the main pad will be.

  8. “rather than generating it algorithmically”
    Not quite, as he can generate it from a more random source than a PRNG and save it to both devices.

    I have been using a lot of random numbers recently – and I’m using the hardware generator in the 8266. A lot of people around the world are looking at it (and writing papers) and it seems pretty good and is based on random physical stuff in the wifi freq range…

    However, that raises another issue ie on any IoT that has wifi – won’t it have enough power and memory to do real encryption? The 8266 certainly does, I’m using 256bit AES between my 8266’s and my server, including some random salt values (also using the 8266 hardware random number generator).

    I don’t think it will be that easy for anyone to hack the comms – they would probably need to break the 256 bit keys – and they can’t do that with differential analysis because of the salt. And they aren’t going to get the key with a dictionary program either, as I initially generated those with another 8266 hardware generator.

    So, if they don’t have physical access to the device to get the key out the rom, I suspect they aren’t going to be intercepting the data – and it was all quite easy to do, so stuffed if I know why everyone doesn’t do it by default…

  9. Sorry? “All this guy’s doing is choosing to store the key, the pad, in memory rather than generating it algorithmically.” Well, there wouldn’t be much use for it otherwise, would there? Come on, is it that hard to think for two seconds before posting a self superior comment like that? If you generate it algorithmically, how do you propose decrypting it on the other end? :) Obviously you need at least two identical copies, shared in advance, for a one time pad to work. It seems this little detail is lost on some. But once you do that, and used correctly, the one time pad is one of the only encryption methods proven to be impossible to decrypt. So I wouldn’t call that ‘weak encryption’.. sure, you shouldn’t reuse the pad obviously but that was just proposed as a cheap easy work around for dealing with limited space.

  10. Well… If the device is battery powered, it will need to be recharged at some point. When it’s hanging off the charger, there is ample power available. And so during the recharge, a whole new one-time pad could be programmed into the device.

    And for devices that are plugged-in 24/7, periodically updating the (tables) would defeat (almost) any would-be hacker who is trying to find out your table. Wouldn’t it?

  11. Another answer to the limited reuse–scramble the OTP when (or as) it is used, say the first xor’d with the last (going to the *middle*) and you can go another 50% longer. Then take the first and middle, another 50% extension. You can keep doing these semantics (every other bit, inverted, every third bit, run through a mod formula…) for a while for a fairly low cost.

  12. Maybe I’d be thinking of using a “storage friendly” size of OTP as a seed for a “not too terrible” PRNG and use that for a period/amount of data less than the statistical likelihood of compromise and then move to next seed. I think you could push a gigabyte a day for millennia with modest OTP size.

  13. Neat idea. On the subject of OTP and its reuse (even after years): the impetus for this is public-key will kill your battery and turn an average 8-bitter into hot slag. There are some fairly efficient symmetric encryption algorithms, the main problem is securely distributing keys to them. Historically, cryptosystems tended to use the expensive Diffie-Hellman (public key) algorithm to create a secure tunnel for exchanging symmetric keys, then send the actual payload using the less intensive symmetric algorithm. This idea might be used to deal with exhaustion of the original OTP contents more securely (use last page to securely send AES/etc. keys, used for sending future messages or a new OTP).

  14. Yeah, they are actually some rather light weight ciphers that gives reasonable protection. TEA and it’s newer versions XTEA can be easily implemented in arduino and gives good enough protection and easier to manage than a large OTP.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s