Score:1

What happens if the column mixing in AES is replaced by simple XOR and subtraction?

gb flag
S-N

This is https://github.com/kokke/tiny-AES-c The column mixing function in the AES algorithm implemented.

static uint8_t xtime(uint8_t x)
{
    return ((x << 1) ^ (((x >> 7) & 1) * 0x1b));
}

// MixColumns function mixes the columns of the state matrix
static void MixColumns(state_t *state)
{
    uint8_t i;
    uint8_t Tmp, Tm, t;
    for (i = 0; i < 4; ++i) {
        t = (*state)[i][0];
        Tmp = (*state)[i][0] ^ (*state)[i][1] ^ (*state)[i][2] ^ (*state)[i][3];
        Tm = (*state)[i][0] ^ (*state)[i][1];
        Tm = xtime(Tm);
        (*state)[i][0] ^= Tm ^ Tmp;
        Tm = (*state)[i][1] ^ (*state)[i][2];
        Tm = xtime(Tm);
        (*state)[i][1] ^= Tm ^ Tmp;
        Tm = (*state)[i][2] ^ (*state)[i][3];
        Tm = xtime(Tm);
        (*state)[i][2] ^= Tm ^ Tmp;
        Tm = (*state)[i][3] ^ t;
        Tm = xtime(Tm);
        (*state)[i][3] ^= Tm ^ Tmp;
    }
}

If I simplify this step to only perform XOR and subtraction operations, is it safe enough?

like this:

#define AES_NB 4

// P is a prime number
#define MIX(x, y, z, p) (x = ((x ^ y) - z) ^ p)

static void MixColumns(state_t *state)
{
    uint32_t i;
    for(i = 0; i < AES_NB; ++i) {
        MIX((*state)[i][0], (*state)[i][3], (*state)[i][1], 0x07);
        MIX((*state)[i][1], (*state)[i][0], (*state)[i][2], 0x0d);
        MIX((*state)[i][2], (*state)[i][1], (*state)[i][3], 0x17);
        MIX((*state)[i][3], (*state)[i][2], (*state)[i][0], 0x29);
    }
}

Will this lead to a decrease in the security of ciphertext?
My personal understanding is:
It will not lead to a decrease in security (even if it does, it should not reach the point where ciphertext becomes unsafe).
Because this operation uses multiple plaintext bytes for mixing, the attacker must first determine the data of at least two plaintext bytes in the blocks, right?

Daniel S avatar
ru flag
It's not clear to me that this step is invertible which is a requirement for a block cipher.
kodlu avatar
sa flag
What does subtraction mean, explicitly? Mathematically AES operates over characteristic 2 where subtraction is addition which is bitwise XOR
kodlu avatar
sa flag
what I mean is clarify your new operation mathematically
mangohost

Post an answer

Most people don’t grasp that asking a lot of questions unlocks learning and improves interpersonal bonding. In Alison’s studies, for example, though people could accurately recall how many questions had been asked in their conversations, they didn’t intuit the link between questions and liking. Across four studies, in which participants were engaged in conversations themselves or read transcripts of others’ conversations, people tended not to realize that question asking would influence—or had influenced—the level of amity between the conversationalists.