8
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ @forest: if you happen to time AES, SPECK, or/and other contenders on your Z80 platform, please post the summary of your benchmarks (e.g. in an update of the question). $\endgroup$ – fgrieu Feb 25 '18 at 10:08
  • 2
    $\begingroup$ It's always amazing that there are still using the Zilog Z80. I've got one here embedded in a Philips MSX-2 computer (VG8235) which I used when I was 11/12 years old (it's the 3rd one, the previous ones having been tossed away by various buggers when I didn't have any room to store them). It's got one big advantage over modern CPU's: the I/O PIN's are fully buffered, these buggers are hard to destroy. One of mine survived a full short-out on the pins. $\endgroup$ – Maarten - reinstate Monica Feb 25 '18 at 14:55
8
$\begingroup$

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.

$\endgroup$
9
$\begingroup$

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
};
$\endgroup$
  • $\begingroup$ One of the issues with AES is, while it may be faster, having more state information requires more memory accesses. I have enough RAM that a kilobyte of state information is not the end of the world, but extremely frequent memory accesses can be harmful to speed. PUSH takes 11 cycles and POP takes 10 on the Z80 architecture, for example. Memory accesses take a minimum of 4 cycles. So while AES, with state information, may be faster in cycles-per-byte than another cipher, the memory access delays on a Z80 can reduce the effective throughput. I'd probably have to test it to see for sure. $\endgroup$ – forest Feb 24 '18 at 8:45
  • $\begingroup$ @forest: yes, memory accesses are costly, and AES is not designed to reduce them to the max on a machine with few registers. However the implementation of MixColumns (and its bundling with AddRoundKey) allows some locality. E.g. if we have registers to spare, in EZAESMA the first affectation of vB[x+2], the first two affectations of vB[x+3] and the affectation of vT[x+3] need not hit memory; these really are local temps. And in the end, because AES performs relatively few operations per octet of ciphertext, it can be faster than SIMON or SPECK on cycles/byte. $\endgroup$ – fgrieu Feb 24 '18 at 11:49
  • $\begingroup$ I decided against AES in the end because multiplication on the Z80 is very, very slow. $\endgroup$ – forest Apr 3 '18 at 20:49
  • $\begingroup$ @forest: but there is no multiplication needed for AES (or in my reference code)! $\endgroup$ – fgrieu Apr 3 '18 at 21:04
  • $\begingroup$ I thought it involved polynomial multiplication. $\endgroup$ – forest Apr 3 '18 at 21:05
3
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ From gimli.cr.yp.to/perf.html, for ATMega at least, it looks like Salsa20 is significantly faster than Gimli small, with Gimli fast requiring far too many bytes of ROM. It looks like Gimli wouldn't provide me with any advantages over Salsa20/ChaCha20. $\endgroup$ – forest Feb 23 '18 at 5:22

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.