128 Bit AES Issue

Question

I'm trying to use the 128bit TI_aes implementation on my 16bit microcontroller and I'm having the weirdest issue.

Every input where two bytes within a word are identical two nibbles within a byte are identical is successfully encrypting and decrypting but every other input is not working.

For example: input:

00112233445566778899aabbccddeeff - Successfully encrypting & decrypting. 182787cebc51b64f1e854deea460bcea - not working.

The only modification I did to the original code is to AND every shift operation with 0xff because the TI_aes implementation is for 8bit microcontroller so in case of a shift left my 16bit microcontroller will still have the MSB bit instead of discarding it.

Example: When shifting 10100111 one left we'll get 01001110 but in 16bit microcontroller it'll be 0000000010100111 ---> 0000000101001110 AND 0xff --> 00000000001001110

Any ideas how comes it successfully encrypts/decrypts certain inputs while others not?

Answer 1

The problem described in the question and its comments is not in the code, but probably in how it is called. At least, on a conformant compiler, it passes the short test program at the end of this answer. We are hinted by the comment "the memory saves each byte in a word block" that there is some problem with the data type used for the 16 octets holding the AES block.

---

Also, a hasty modification of the original code (alluded to in the question) has introduced a huge vulnerability to timing attack. We have gone from about the following

// multiply by 2 in the galois field
unsigned char galois_mul2(unsigned char value) {
    signed char temp;
    // cast to signed value
    temp = (signed char) value;
    // if MSB is 1, then this will signed extend and fill the temp variable with 1's
    temp = temp >> 7;
    // AND with the reduction variable
    temp = temp & 0x1b;
    // finally shift and reduce the value
    return ((value << 1)^temp);
}

which likely executes in time independent of value (but makes a non-portable assumption about what temp >> 7 gives), to the following

unsigned char galois_mul2(unsigned char value) {
    if (value>>7) {
        value = (value << 1) & 0xff;
        return (value^0x1b);
    } else
        return value<<1;
}

which in all likelihood compiles to code with a horrible data timing dependency.

To fix this problem, the standard technique is

unsigned char galois_mul2(unsigned char value) {
    return ( ( 0u - ( value >> 7 ) ) & 0x1b ) ^ ( value << 1 );
}

which, under the sole assumption that unsigned char is an octet, works with any standards-abiding C compiler, and most others. The generated code should still be checked for lack of data-dependent timing variations. It should be possible to remove the 0u, but some compilers in their default setting will object to taking the unary negative of an unsigned, even though that's well-defined. Some compilers for 8-bit CPUs will needlessly juggle with multi-octet intermediary results, and should be hinted that it is pointless using casts, like

return (unsigned char)((unsigned char)-(unsigned char)(value>>7)&0x1b)
     ^ (unsigned char)(value<<1);

---

Depending on target CPU, its settings, and the compiler, aes_enc_dec could have other data-dependent timing variations enabling timing attack, in particular due to cache effects.

Another security issue is that the whole thing is not intended to resist Differential Power Analysis, and yet other classic and potentially devastating attacks, like fault attacks (also see Hagai Bar-El, Hamid Choukri, David Naccache, Michael Tunstall and Claire Whelan The Sorcerer’s Apprentice Guide to Fault Attacks).

---

A short test showing that the code does not exhibit the problem alleged in the question and comments:

int main(void) {
    // a known-good key/plaintext/ciphertext triplet; could be const if environement supports that
    unsigned char rk[] = {0x4e,0xb1,0x19,0x72,0x33,0x1a,0x6f,0xcf,0xdc,0x9e,0x57,0x32,0x92,0x39,0x97,0x31};
    unsigned char rp[] = {0x18,0x27,0x87,0xce,0xbc,0x51,0xb6,0x4f,0x1e,0x85,0x4d,0xee,0xa4,0x60,0xbc,0xea};
    unsigned char rc[] = {0xd8,0x7c,0x9c,0x86,0xd9,0x2c,0xdd,0x8c,0x48,0x54,0x82,0x47,0x19,0xf8,0xc6,0x21};

    unsigned char vb[16], vk[16], vj, vx = 0;   // block, key, index, errors
    for(vj=0;vj<16;++vj) {
        vb[vj] = rp[vj];        // prepare block
        vk[vj] = rk[vj];        // prepare key
    }
    aes_enc_dec(vb, vk, 0);     // encipher
    for(vj=0;vj<16;++vj) {
        vx |= vb[vj]^rc[vj];    // check encryption
        vk[vj] = rk[vj];        // prepare key
    }
    aes_enc_dec(vb, vk, 1);     // decipher
    for(vj=0;vj<16;++vj) {
        vx |= vb[vj]^rp[vj];    // check decryption
    }
    if (vx!=0)                  // if there was some error..
        while(1);               // hang
    return 0;                   // exit with sucess
}