A Simple Microcontroller Coprocessing Encryption Engine (Part 1)

The need for encryption

You probably already recognize the need for a simple encryption engine that can be integrated with a low cost microcontroller to provide secure communications within a network. This is becoming even more important as more sensor devices are being attached to the internet. In this blog I am going to try and address this issue with a simple solution that we can use to provide both security and integrity for our data.

One of the major challenges with encryption is that it is a computationally intensive activity; and we only have very limited processing power available in our remote sensors. In order to overcome this challenge academic research has been focused upon security methods that we can use with only limited resources.

The University of California has presented an approach based upon the work at Berkeley by Perrig, Szewczyk, Wen, Culler and Tygar. So an integral part of this work is their proposal for a set of security protocols for sensor networks, called SPINS, that employs a simple encryption algorithm to secure the network. In their paper they presented a solution using the RC5 encryption algorithm – but this algorithm is patented by RSA Security.  So while we cannot freely use RC5 there are other free symmetrical encryption algorithms that also lend themselves to being implemented with limited resources. Therefore I have chosen one of these free algorithms to use in the design of this Encryption Engine.

The proposed implementation

The Encryption Engine I am going to design is intended to operate in conjunction with a small microcontroller. So the Encryption Engine will shoulder the burden of computing the encryption of the data sent from the microcontroller. By way of an example, we might use a microcontroller like the Arduino’s ATmega328P to pass data to our Encryption Engine. This approach means that the Encryption Engine can easily be integrated with an existing design and will have a minimal impact on the microcontroller code. I have chosen to implement the Encryption Engine in a small CPLD (Complex Programmable Logic Device) as these offer a rich feature set in a small package and at a low cost point

My design will make it very easy for you to adapt it to fit any particular purpose you may have in your projects. So for design simplicity I have chosen to interface between the microcontroller and the CPLD with an SPI interface with the clear text being output on the MOSI and the cypher test being returned on the MISO.

A suitable algorithm

I initially thought that the Advanced Encryption Standard (AES) would be a good candidate for the encryption algorithm. Unfortunately while this algorithm was originally designed to be implemented in resource constrained applications it still uses quite a large amount of memory for the S-Box structure which is 256 bytes in size.

I then considered the Tiny Encryption Algorithm (TEA) developed by Wheeler and Needham, which is particularly attractive due to its minimal resource implementation. This algorithm was originally published in October 1997. Consequently it has been subject to extensive cryptanalysis to identify its weaknesses. As a result of this analysis the original algorithm was extended to XXTEA, or Block TEA, which addresses some of the original algorithm’s weaknesses.

While there are still some known issues with XXTEA it still remains unbreakable for practical purposes. When this is combined with its simplicity it lends itself to securing simple networks using very limited resources. So on this basis I am going to initially work with this algorithm.

System security

Whether the algorithm’s weaknesses represent a real security threat in  your application will depend on the type of information that you are protecting. Ultimately this is a system design issue – which is the level where all of your security needs should always be addressed.

Some people may argue that you should never use an algorithm with known weaknesses. While this argument does have merits I think it needs to be balanced against cost and resources and I believe that there is a justifiable case for using this solution in many applications.

Depending on how much success I have with this simple approach I may revisit the overall design and implement an AES based version at a later stage for comparison purposes if the CPLD resources will permit it!

There is one last point I would as you to consider. In order to exploit the main weakness with the algorithm the attacker needs to gather a large set of plaintext/cyphertext pair in order to establish your secret key. I will deliberately make it very difficult to match up these pairs within my implementation which will reduce the risk of this weakness being exploited.

Implementation details

As I previously mentioned I am going to implement The Encryption Engine in a small CPLD  with a low cost microcontroller. So I will initially target the design at a Lattice MachOX2 device. I like these devices as these are available in a range of packages with some as small as 2.5mm square. I will write the CPLD design in VHDL and I will aim to be as hardware agnostic as possible. This approach will hopefully enable you to re-target the design on to other CLPD and FPGA families with the minimum amount of effort should you want to.

Wheeler and Needham presented the provisional routine for the implementation of their algorithm in the C programming language. So I have provided this below but with the inclusion of parentheses to clarify the order of the operations. As a result of the lack of parentheses in the original paper some ambiguity has arisen in the implementation of the algorithm. Consequently there are a number of implementation variants in the field that are mutually incompatible. Also this code has been used to generate a set of test vectors that agree with the implementation available on GitHub.

These results correspond with the generally accepted ‘correct’ implementation of the algorithm and have been subject to the extensive cryptanalysis previously mentioned.

Algorithm

#define DELTA 0x9e3779b9
#define MX (((z>>5^y<<2) + (y>>3^z<<4)) ^ ((sum^y) + (key[(p&3)^e] ^ z)))

void btea(uint32_t *v, int n, uint32_t const key[4]) {
    uint32_t y, z, sum;
    unsigned p, rounds, e;
    if (n > 1) {          /* Coding Part */
      rounds = 6 + 52/n;
      sum = 0;
      z = v[n-1];
      do {
        sum += DELTA;
        e = (sum >> 2) & 3;
        for (p=0; p<n-1; p++) {
          y = v[p+1];
          z = v[p] += MX;
        }
        y = v[0];
        z = v[n-1] += MX;
      } while (–rounds);
    } else if (n < -1) {  /* Decoding Part */
      n = -n;
      rounds = 6 + 52/n;
      sum = rounds*DELTA;
      y = v[0];
      do {
        e = (sum >> 2) & 3;
        for (p=n-1; p>0; p–) {
          z = v[p-1];
          y = v[p] -= MX;
        }
        z = v[n-1];
        y = v[0] -= MX;
        sum -= DELTA;
      } while (–rounds);
    }
  }

Design validation

Good design dictates that it is essential to have a set of test vectors generated by a third party in order to validate the design of the Encryption Engine.  Consequently these vectors will guarantee that the implementation is accurate. I have extracted the following table of the test vectors from the reference design on GitHub. So I will use these to verify the design of the CPLD  in simulation and I can also use them to verify the operation of the final hardware.

Key Plaintext Cyphertext
0000000000000000000000000000000 0000000000000000 ab043705808c5d57
0102040810204080fffefcf8f0e0c080 0000000000000000 d1e78be2c746728a
9e3779b99b9773e9b979379e6b695156 ffffffffffffffff 67ed0ea8e8973fc5
0102040810204080fffefcf8f0e0c080 fffefcf8f0e0c080 8c3707c01c7fccc4
6a6f686e636b656e64616c6c6a6f686e 4100000000000000 014e7a34874eeb29
6a6f686e636b656e64616c6c6a6f686e 4142000000000000 e9d39f636e9ed090
6a6f686e636b656e64616c6c6a6f686e 4142430000000000 d20ec51c06feaf0e
6a6f686e636b656e64616c6c6a6f686e 4142434400000000 b1551d6ffcd4b61b
6a6f686e636b656e64616c6c6a6f686e 4142434445000000 0ff91e518b9837e3
6a6f686e636b656e64616c6c6a6f686e 4142434445460000 7003fc98b6788a77
6a6f686e636b656e64616c6c6a6f686e 4142434445464700 93951ad360650022
6a6f686e636b656e64616c6c6a6f686e 4142434445464748 cdeb72b9c903ce52

So in the next part of this article I will explain how we can use this algorithm to secure our data. Also I will explain why we only need to implement the encryption part of the algorithm within our system.