Lightweight cipher using only 8-bit operations

Question

What is the most efficient (in cycles per byte) cryptographically secure symmetric cipher to implement using only 8-bit operations? Algorithms like TEA are great for embedded devices, but it is optimized for 32-bit operations. I am not looking for the most efficient implementation of an algorithm, but rather an algorithm which was designed with this in mind. The MCU in question is a 3.5 MHz Z80 with 16K RAM.

Looking this up, I found resources showing how to implement AES on 4-bit microcontrollers, and how to implement secure hashes on 8-bit microcontrollers, but neither of those answer my actual question.

Answer 1

SPECK was actually designed with 8-bit CPUs in mind. I use Simon and Speck extensively, and there's example source code and comparisons out there, as well as a good paper. The references are good and will lead you the the original sources. AES is generally faster but takes more resources, which you may or may not have.

I do not use AES on a MCU because it will have state information unless it has an AES hardware core. It's easier to keep the changes of the feistel network just as register information and you then do not need to worry about eating into your valuable RAM space.

Answer 2

I second Richie Frame's observation that AES is an excellent choice. I'd use AES-128 in CTR mode, which has the advantage that decryption is the same as encryption (thus is as fast, contrary to some other modes).

Update: SPECK, considered in this other answer, is good if compactness or speed per encryption for narrow block size are the choice criteria. SPECK-32 can be competitive with AES from the standpoint of cycles/byte on a Z80 (as asked in the question) because the state fits in registers. But I doubt SPECK-128 can be competitive with AES from the standpoint of cycles/byte on a Z80, because the multi-bit rotation and large number of rounds are going to be show stoppers; and the state has to be in memory.

AES is good on 8-bit CPU (especially if a wide block is desired) because

• It has a natural implementation with as the only data transformations: XOR between octets, and lookup of two 256-octet tables. Contrary to many modern ciphers, no word rotation is needed, which is extremely desirable in the context, in which that would be slow even when using assembly.
• With an implementation (still natural) separating derivation of round subkeys from encryption itself, speed for large data will be hard to beat, thanks to the carefully crafted structure of AES.
• Typical C compilers can generate fair code, and optimization is relatively easy.
• With the precaution of locating the two 256-octet tables on page boundaries, a natural implementation on a CPU without data cache (such as the Z80) will typically exhibits no data timing dependency (but I have seen small caches, e.g. 16-octet, in the read path of Flash memory).

As illustration, here is reference code:

// ezAES: Public domain AES-128 encryption.
// C99-conformant. Well suited to 8-bit CPUs.
// CAUTION: vulnerable to fault attacks and side-channels, including
// Differential Power Analysis, and possibly data cache timing attack.

// Data types
typedef unsigned char octet_t;      // 8-bit octet
typedef octet_t ezAESblk_t[16];     // AES data block
typedef octet_t ezAESkey_t[16];     // key for AES-128
typedef octet_t ezAESsks_t[11*16];  // subkeys for AES-128

// Sbox for encryption, FIPS-197 figure 7
static const octet_t ezAESs[256] = {
    0x63,0x7c,0x77,0x7b,0xf2,0x6b,0x6f,0xc5,0x30,0x01,0x67,0x2b,0xfe,0xd7,0xab,0x76,0xca,0x82,0xc9,0x7d,0xfa,0x59,0x47,0xf0,0xad,0xd4,0xa2,0xaf,0x9c,0xa4,0x72,0xc0,
    0xb7,0xfd,0x93,0x26,0x36,0x3f,0xf7,0xcc,0x34,0xa5,0xe5,0xf1,0x71,0xd8,0x31,0x15,0x04,0xc7,0x23,0xc3,0x18,0x96,0x05,0x9a,0x07,0x12,0x80,0xe2,0xeb,0x27,0xb2,0x75,
    0x09,0x83,0x2c,0x1a,0x1b,0x6e,0x5a,0xa0,0x52,0x3b,0xd6,0xb3,0x29,0xe3,0x2f,0x84,0x53,0xd1,0x00,0xed,0x20,0xfc,0xb1,0x5b,0x6a,0xcb,0xbe,0x39,0x4a,0x4c,0x58,0xcf,
    0xd0,0xef,0xaa,0xfb,0x43,0x4d,0x33,0x85,0x45,0xf9,0x02,0x7f,0x50,0x3c,0x9f,0xa8,0x51,0xa3,0x40,0x8f,0x92,0x9d,0x38,0xf5,0xbc,0xb6,0xda,0x21,0x10,0xff,0xf3,0xd2,
    0xcd,0x0c,0x13,0xec,0x5f,0x97,0x44,0x17,0xc4,0xa7,0x7e,0x3d,0x64,0x5d,0x19,0x73,0x60,0x81,0x4f,0xdc,0x22,0x2a,0x90,0x88,0x46,0xee,0xb8,0x14,0xde,0x5e,0x0b,0xdb,
    0xe0,0x32,0x3a,0x0a,0x49,0x06,0x24,0x5c,0xc2,0xd3,0xac,0x62,0x91,0x95,0xe4,0x79,0xe7,0xc8,0x37,0x6d,0x8d,0xd5,0x4e,0xa9,0x6c,0x56,0xf4,0xea,0x65,0x7a,0xae,0x08,
    0xba,0x78,0x25,0x2e,0x1c,0xa6,0xb4,0xc6,0xe8,0xdd,0x74,0x1f,0x4b,0xbd,0x8b,0x8a,0x70,0x3e,0xb5,0x66,0x48,0x03,0xf6,0x0e,0x61,0x35,0x57,0xb9,0x86,0xc1,0x1d,0x9e,
    0xe1,0xf8,0x98,0x11,0x69,0xd9,0x8e,0x94,0x9b,0x1e,0x87,0xe9,0xce,0x55,0x28,0xdf,0x8c,0xa1,0x89,0x0d,0xbf,0xe6,0x42,0x68,0x41,0x99,0x2d,0x0f,0xb0,0x54,0xbb,0x16
    };

// Tabulation of (x<<1)^((x>>7)*0x1B)
static const octet_t ezAESt[256] = {
    0x00,0x02,0x04,0x06,0x08,0x0a,0x0c,0x0e,0x10,0x12,0x14,0x16,0x18,0x1a,0x1c,0x1e,0x20,0x22,0x24,0x26,0x28,0x2a,0x2c,0x2e,0x30,0x32,0x34,0x36,0x38,0x3a,0x3c,0x3e,
    0x40,0x42,0x44,0x46,0x48,0x4a,0x4c,0x4e,0x50,0x52,0x54,0x56,0x58,0x5a,0x5c,0x5e,0x60,0x62,0x64,0x66,0x68,0x6a,0x6c,0x6e,0x70,0x72,0x74,0x76,0x78,0x7a,0x7c,0x7e,
    0x80,0x82,0x84,0x86,0x88,0x8a,0x8c,0x8e,0x90,0x92,0x94,0x96,0x98,0x9a,0x9c,0x9e,0xa0,0xa2,0xa4,0xa6,0xa8,0xaa,0xac,0xae,0xb0,0xb2,0xb4,0xb6,0xb8,0xba,0xbc,0xbe,
    0xc0,0xc2,0xc4,0xc6,0xc8,0xca,0xcc,0xce,0xd0,0xd2,0xd4,0xd6,0xd8,0xda,0xdc,0xde,0xe0,0xe2,0xe4,0xe6,0xe8,0xea,0xec,0xee,0xf0,0xf2,0xf4,0xf6,0xf8,0xfa,0xfc,0xfe,
    0x1b,0x19,0x1f,0x1d,0x13,0x11,0x17,0x15,0x0b,0x09,0x0f,0x0d,0x03,0x01,0x07,0x05,0x3b,0x39,0x3f,0x3d,0x33,0x31,0x37,0x35,0x2b,0x29,0x2f,0x2d,0x23,0x21,0x27,0x25,
    0x5b,0x59,0x5f,0x5d,0x53,0x51,0x57,0x55,0x4b,0x49,0x4f,0x4d,0x43,0x41,0x47,0x45,0x7b,0x79,0x7f,0x7d,0x73,0x71,0x77,0x75,0x6b,0x69,0x6f,0x6d,0x63,0x61,0x67,0x65,
    0x9b,0x99,0x9f,0x9d,0x93,0x91,0x97,0x95,0x8b,0x89,0x8f,0x8d,0x83,0x81,0x87,0x85,0xbb,0xb9,0xbf,0xbd,0xb3,0xb1,0xb7,0xb5,0xab,0xa9,0xaf,0xad,0xa3,0xa1,0xa7,0xa5,
    0xdb,0xd9,0xdf,0xdd,0xd3,0xd1,0xd7,0xd5,0xcb,0xc9,0xcf,0xcd,0xc3,0xc1,0xc7,0xc5,0xfb,0xf9,0xff,0xfd,0xf3,0xf1,0xf7,0xf5,0xeb,0xe9,0xef,0xed,0xe3,0xe1,0xe7,0xe5
    };

// Round constants
static const octet_t ezAESr[10] = {
    0x01,0x02,0x04,0x08,0x10,0x20,0x40,0x80,0x1b,0x36
    };


// encrypt one block
void ezAESenc
    (
          ezAESblk_t    oC, // ciphertext output
    const ezAESblk_t    iP, // plaintext input
    const ezAESsks_t    iS  // round subkeys
    ) {
    ezAESblk_t vB;          // current state of the block
    ezAESblk_t vT;          // temporary
    octet_t vn;

    // first AddRoundKey
    vn = 16;
    do {
        --vn;
        vB[vn] = iP[vn] ^ iS[vn];
    } while( vn!=0 );

    // round loop, started 10 times; exits with break in the middle of the last round
    for( ; ; ) {

        // ShiftRows and SubBytes, performed 10 times
        vT[ 0] = ezAESs[vB[ 0]]; vT[ 1] = ezAESs[vB[ 5]]; vT[ 2] = ezAESs[vB[10]]; vT[ 3] = ezAESs[vB[15]];
        vT[ 4] = ezAESs[vB[ 4]]; vT[ 5] = ezAESs[vB[ 9]]; vT[ 6] = ezAESs[vB[14]]; vT[ 7] = ezAESs[vB[ 3]];
        vT[ 8] = ezAESs[vB[ 8]]; vT[ 9] = ezAESs[vB[13]]; vT[10] = ezAESs[vB[ 2]]; vT[11] = ezAESs[vB[ 7]];
        vT[12] = ezAESs[vB[12]]; vT[13] = ezAESs[vB[ 1]]; vT[14] = ezAESs[vB[ 6]]; vT[15] = ezAESs[vB[11]];

        if ( (vn += 16)==10*16 )
            break;

        // MixColumns and AddRoundKey, performed 9 times
#define EZAESMA(x) \
    vB[x+2] = vT[x+0]^vT[x+1];                  /* 1 1 0 0 */               \
    vB[x+3] = vT[x+2]^vT[x+3];                  /* 0 0 1 1 */               \
    vB[x+0] = ezAESt[vB[x+2]]^vT[x+1]^vB[x+3]   /* 2 3 1 1 */ ^iS[x+0+vn];  \
    vB[x+2] ^= ezAESt[vB[x+3]]^vT[x+3]          /* 1 1 2 3 */ ^iS[x+2+vn];  \
    vB[x+3] = vT[x+1]^vT[x+2];                  /* 0 1 1 0 */               \
    vT[x+3] ^= vT[x+0];                         /* 1 0 0 1 */               \
    vB[x+1] = ezAESt[vB[x+3]]^vT[x+2]^vT[x+3]   /* 1 2 3 1 */ ^iS[x+1+vn];  \
    vB[x+3] ^= ezAESt[vT[x+3]]^vT[x+0]          /* 3 1 1 2 */ ^iS[x+3+vn];
        EZAESMA( 0)
        EZAESMA( 4)
        EZAESMA( 8)
        EZAESMA(12)
#undef EZAESMA
        // here the content of vT is immaterial
        }

    // last AddRoundKey
    vn = 16;
    do  {
        --vn;
        oC[vn] = vT[vn] ^ iS[10*16+vn];
    } while( vn!=0 );
}

// prepare round subkeys
void ezAESkey (
          ezAESsks_t    oS, // round subkeys output
    const ezAESkey_t    iK  // key input
    ) {
    octet_t vj, vk;

    // first subkey is the key
    vj = 16;
    do {
        --vj;
        oS[vj] = iK[vj];
    }
    while ( vj!=0 );

     // for each 4-octet word of each 10 other subkeys
    vk = 0;
    do  {
        if( (vj&15)==0 ) {
            oS[16+vj] = ezAESs[oS[13+vj]]^oS[  vj]^ezAESr[vk++];
            oS[17+vj] = ezAESs[oS[14+vj]]^oS[1+vj];
            oS[18+vj] = ezAESs[oS[15+vj]]^oS[2+vj];
            oS[19+vj] = ezAESs[oS[12+vj]]^oS[3+vj];
            }
        else {
            oS[16+vj] = oS[12+vj]^oS[  vj];
            oS[17+vj] = oS[13+vj]^oS[1+vj];
            oS[18+vj] = oS[14+vj]^oS[2+vj];
            oS[19+vj] = oS[15+vj]^oS[3+vj];
            }
    } while( ( vj += 4)!=10*16 );
}

// Minimal test and demo. Returns 0 for OK, 1 for error.
int ezAESchk(void) {
    // test values from FIPS-197 appendix C.1
    const ezAESkey_t key = {
        0x00,0x01,0x02,0x03,0x04,0x05,0x06,0x07,0x08,0x09,0x0a,0x0b,0x0c,0x0d,0x0e,0x0f
    };
    const ezAESblk_t plaintext = {
        0x00,0x11,0x22,0x33,0x44,0x55,0x66,0x77,0x88,0x99,0xaa,0xbb,0xcc,0xdd,0xee,0xff
    };
    const ezAESblk_t ciphertext = {
        0x69,0xc4,0xe0,0xd8,0x6a,0x7b,0x04,0x30,0xd8,0xcd,0xb7,0x80,0x70,0xb4,0xc5,0x5a
    };
    ezAESsks_t subkeys;
    ezAESblk_t result;
    octet_t j, r;

    // derive the round subkeys
    ezAESkey( subkeys, key );

    // encrypt
    ezAESenc( result, plaintext, subkeys );

    // compare result and known-good ciphertext
    for( j = r = 0; j<16; ++j)
        r |= result[j] ^ ciphertext[j];

    return r!=0;    // 0 for OK, 1 for error
};

Answer 3

I do not have benchmarks on this particular processor, so this answer is opinion / guesswork.

Gimli is fast and low-memory, but is just a permutation. Ciphers can be pretty trivially implemented on top of it though. It was designed to be efficient on a wide variety of hardware, and there is a reference implementation for an 8-bit AVR microcontroller. Libhydrogen uses Gimli to construct all of its symmetric primitives, and is optimized for microcontroller use.

All of the eSTREAM profile 1 (software optimized) ciphers could also be considered, though I don't know about their relative performance on 8-bit microcontrollers as the eSTREAM performance tests page does not have any such benchmarks. Being a variant of Salsa ChaCha should also be considered.

Blake2s is a hash function optimized for 8-32-bit systems, and is quite fast.

One particular Arduino cryptographic library I found has some benchmarks of various ciphers, and ChaCha seems good there, though that's one particular set of implementations on a different platform and doesn't include Gimli.

Answer 4

SAFER++ might also be a good choice as it has only 8-bit operations, however it requires 512 bytes of ROM for tables.

Speck has one rotation by 8 and one by 3 per round. Rotation by 8 was probably chosen so bytes can be swapped on 8-bit CPU. It is probably the most compact, which on microcontrollers is often more important than speed.

RC4 is also 8-bit friendly, but not considered secure.

AES is also good on 8-bit CPU, but smallest implementation is vulnerable to side-channel attacks (even more than typical big table based implementation).