Reimplementing the x86 AESENC instruction in python

Question

I'm having troubles implementing the AESENC x86 instruction in python.

I'm reverse engineering the decryption of a indie video game. They use AES but they xor some generated data around and the key expansion is not standard, so I need to use custom round keys. I'm nearly complete, but I'm stumped in that the game uses the AESENC x86 instruction, which performs a single round of AES. This seemed trivial to implement but I'm not getting the same results.

To be more precise, when setting breakpoints and looking at memory

AESENC(E98E03FAEAD91A951F6269D0D4DAFAD6, C62E6AD8CC162D7E210D91A142F2927B) 

returns:

AABCA9C13C842D3112C48E822B050CF8

While my python implementation returns:

aabca9c13b88ae173e2ea2680d02007b

This seems to be only matching the first 4 bytes. My guess is that the mix_columns step is being done wrong, I've tried other implementations, but none seems to be matching the x86 instruction. I'm using the implementation found in the book The Design of Rijndael Section 4.1.2

The only documentation I found on AESENC was here, which unfortunately doesn't go into details on how the functions are implemented. If anyone know where I can get implementation specifics on the AESENC please do :)

Here's my full python implementation of AESENC so far:

SBOX = (
    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,
)

def list2hex(list):
    hex = ""
    for e in list:
        hex += "{:02x}".format(e)
    return hex

def hex2list(hex):
    lst = []
    if len(hex) % 2 == 0:
        for i in range(len(hex)/2):
            lst.append(int(hex[i*2:i*2+2], 16))
    return lst

def xor(bytelist1, bytelist2):
    res = []
    length = min(len(bytelist1), len(bytelist2))
    for i in range(length):
        res.append(bytelist1[i] ^ bytelist2[i])
    return res

def aesenc(state, roundkey, last=False):
    def shift_rows(state):
        state[4], state[5], state[6], state[7] = state[5], state[6], state[7], state[4]
        state[8], state[9], state[10], state[11] = state[10], state[11], state[8], state[9]
        state[12], state[13], state[14], state[15] = state[15], state[12], state[13], state[14]

    def sub_bytes(state):
        for i in range(16):
            state[i] = SBOX[state[i]]

    def mix_columns(state):
        xtime = lambda a: (((a << 1) ^ 0x1B) & 0xFF) if (a & 0x80) else (a << 1)

        def mix_column(col):
            t = col[0] ^ col[1] ^ col[2] ^ col[3]
            u = col[0]
            col[0] ^= t ^ xtime(col[0] ^ col[1])
            col[1] ^= t ^ xtime(col[1] ^ col[2])
            col[2] ^= t ^ xtime(col[2] ^ col[3])
            col[3] ^= t ^ xtime(col[3] ^ u)
            return _col

        return mix_column(state[0::4]) + \
                mix_column(state[1::4]) + \
                mix_column(state[2::4]) + \
                mix_column(state[3::4])

    sub_bytes(state)
    shift_rows(state)
    if not last:
        state = mix_columns(state)
    return xor(state, roundkey)

data = hex2list("E98E03FAEAD91A951F6269D0D4DAFAD6")
key = hex2list("C62E6AD8CC162D7E210D91A142F2927B")

res = aesenc(data, key)
print list2hex(res)

Answer 1

Three problems:

1. mix_column returns _col (typo underscore?)
2. The return value of mix_columns just concatenates the columns together like rows instead of slotting them back into columns - effectively transposing the result.

3. AESENC takes its parameters and returns its results as columns concatenated together. Your aesenc takes the parameters and returns the results as rows concatenated together:

   AESENC(E98E03FAEAD91A951F6269D0D4DAFAD6, C62E6AD8CC162D7E210D91A142F2927B)
          data = E9 EA 1F D4                key = C6 CC 21 42
                 8E D9 62 DA                      2E 16 0D F2
                 03 1A 69 FA                      6A 2D 91 92
                 FA 95 D0 D6                      D8 7E A1 7B
   

This is the script adjusted so that it emits the same values as the AESENC instruction:

SBOX = (
    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,
)

def transpose4x4(m):
    return m[0::4] + m[1::4] + m[2::4] + m[3::4]

def list2hex(list):
    hex = ""
    for e in list:
        hex += "{:02x}".format(e)
    return hex

def hex2list(hex):
    lst = []
    if len(hex) % 2 == 0:
    for i in range(len(hex)/2):
        lst.append(int(hex[i*2:i*2+2], 16))
    return lst

def xor(bytelist1, bytelist2):
    res = []
    length = min(len(bytelist1), len(bytelist2))
    for i in range(length):
        res.append(bytelist1[i] ^ bytelist2[i])
    return res

def aesenc(state, roundkey, last=False):
    def shift_rows(state):
        state[4], state[5], state[6], state[7] = state[5], state[6], state[7], state[4]
        state[8], state[9], state[10], state[11] = state[10], state[11], state[8], state[9]
        state[12], state[13], state[14], state[15] = state[15], state[12], state[13], state[14]

    def sub_bytes(state):
        for i in range(16):
            state[i] = SBOX[state[i]]

    def mix_columns(state):
        xtime = lambda a: (((a << 1) ^ 0x1B) & 0xFF) if (a & 0x80) else (a << 1)

        def mix_column(col):
            t = col[0] ^ col[1] ^ col[2] ^ col[3]
            u = col[0]
            col[0] ^= t ^ xtime(col[0] ^ col[1])
            col[1] ^= t ^ xtime(col[1] ^ col[2])
            col[2] ^= t ^ xtime(col[2] ^ col[3])
            col[3] ^= t ^ xtime(col[3] ^ u)
            return col

        out = [None]*16
        for i in range(0,4):
          out[i::4] = mix_column(state[i::4])
        return out

    sub_bytes(state)
    shift_rows(state)
    if not last:
        state = mix_columns(state)
    return xor(state, roundkey)

data = transpose4x4(hex2list("E98E03FAEAD91A951F6269D0D4DAFAD6"))
key = transpose4x4(hex2list("C62E6AD8CC162D7E210D91A142F2927B"))

res = transpose4x4(aesenc(data, key))
print list2hex(res)

Answer 2

The documentation that you found to appears to be just a copy of the AESENC page from Intel's "Software Developer's Manual. The manual itself goes into much more detail on the implementation of AES in section 12.13.

Note the importance of understanding the 'endianness' of the implementation. (Intel's differs from the FIPS standard.)

Answer 3

To know what the result of my mix_columns should be, I XORed the round key with the result, which gave me what I had, but with the bytes in the wrong order. Changing the return statement of the mix_columns from

return mix_column(state[0::4]) + \
        mix_column(state[1::4]) + \
        mix_column(state[2::4]) + \
        mix_column(state[3::4])

to

return shift_rows(mix_column(state[0::4]) + \
                    mix_column(state[3::4]) + \
                    mix_column(state[2::4]) + \
                    mix_column(state[1::4]))

returns me the bytes in the right order, which seems odd to me. Not only are the columns shifted, but also the individual bytes inside it.

While this technically answers the question and returns what I want, it feels hacky and wrong, so the question still stands: What did I miss?

I won't mark this answer as correct since I still don't understand what went wrong.