aes mix columns

Hello

Im slowly trying to write a AES program but I cant seem to get the MC part to work.

The code compiles fine, but if you apply the inverse to the function you dont get the orginal back *most* but not all of them time.

I have no idea why.

Anyone mind taking a look?
Thanks

Code:

---

#include <stdio.h>
#include <stdlib.h>
#include <time.h>

unsigned char gf_mult(unsigned char a, unsigned char b) {
        int i;
        int retval;
       
        /* If there isnt a "overflow", normal multiplication can be used */
        retval = a * b;
        if(retval < 128)
                return retval;
        else
                retval = 0;
       
        /* GF multiplication with insane bit shifting */
        for(i = 0; i < 8; i++) {
                if((b & 1) == 1)
                        retval ^= a;
               
                if((a & 0x80) == 0x80) {
                        a <<= 1;
                        a  ^= 0x1b;
                } else {
                        a <<= 1;
                }
               
                b >>= 1;
        }
       
        return (unsigned char)retval;
}

void print_state(unsigned char *state) {
        int i;
        int j;
       
        printf("+----+----+----+----+\n");
       
        for(i = 0; i < 4; ++i) {
                printf("|");
               
                for(j = 0; j < 4; ++j)
                        printf("0x%02X|", (&state[i])[j]);
               
                printf("\n");
                printf("+----+----+----+----+\n");
        }
}

void rand_state(unsigned char *state) {
        int i;
        int j;
       
        srand ( time(NULL) );
        for(i = 0; i < 4; ++i) {
                for(j = 0; j < 4; ++j)
                        (&state[i])[j] = (rand() % 256);
        }
}

void copy_state(unsigned char *src, unsigned char *dst) {
        int i;
        int j;
       
        for(i = 0; i < 4; ++i) {
                for(j = 0; j < 4; ++j)
                        (&dst[i])[j] = (&src[i])[j];
        }
}

int state_equal(unsigned char *a, unsigned char *b) {
        int i;
        int j;
       
        for(i = 0; i < 4; ++i) {
                for(j = 0; j < 4; ++j) {
                        if( (&a[i])[j] != (&b[i])[j] )
                                return 1;
                }
        }
       
        return 0;
}

void MixColumns(unsigned char *in, unsigned char *out){
        int c = 0;
       
        for(c = 0; c < 4; ++c) {
                (&out[0])[c] = gf_mult(0x02, (&in[0])[c]) ^ gf_mult(0x03, (&in[1])[c])
                                                ^ (&in[2])[c] ^ (&in[3])[c];
                (&out[1])[c] = (&in[0])[c] ^ gf_mult(0x02, (&in[1])[c])
                                                ^ gf_mult(0x03, (&in[2])[c]) ^ (&in[3])[c];
                (&out[2])[c] = (&in[0])[c] ^ (&in[1])[c] ^ gf_mult(0x02, (&in[2])[c])
                                                ^ gf_mult(0x03, (&in[3])[c]);
                (&out[3])[c] = gf_mult(0x03, (&in[0])[c]) ^ (&in[1])[c] ^ (&in[2])[c]
                                                ^ gf_mult(0x02, (&in[3])[c]);
        }
}

void InvMixColumns(unsigned char *in, unsigned char *out){
        int c = 0;
       
        for(c = 0; c < 4; ++c) {
                (&out[0])[c] = gf_mult(0x0E, (&in[0])[c]) ^ gf_mult(0x0B, (&in[1])[c])
                                        ^ gf_mult(0x0D, (&in[2])[c]) ^ gf_mult(0x09, (&in[3])[c]);
                (&out[1])[c] = gf_mult(0x09, (&in[0])[c]) ^ gf_mult(0x0E, (&in[1])[c])
                                        ^ gf_mult(0x0B, (&in[2])[c]) ^ gf_mult(0x0D, (&in[3])[c]);
                (&out[2])[c] = gf_mult(0x0D, (&in[0])[c]) ^ gf_mult(0x09, (&in[1])[c])
                                        ^ gf_mult(0x0E, (&in[2])[c]) ^ gf_mult(0x0B, (&in[3])[c]);
                (&out[3])[c] = gf_mult(0x0B, (&in[0])[c]) ^ gf_mult(0x0D, (&in[1])[c])
                                        ^ gf_mult(0x09, (&in[2])[c]) ^ gf_mult(0x0E, (&in[3])[c]);
        }
}

int TestMixColumns(unsigned char *state) {
        unsigned char mc[4][4];
        unsigned char inv_mc[4][4];
        int retval;
       
        MixColumns(state, *mc);
        InvMixColumns(*mc, *inv_mc);
       
        retval = state_equal(state, *inv_mc);
        if(retval != 0) {
                printf("in:\n");
                print_state(state);
                printf("\nout:\n");
                print_state(*inv_mc);
        }
       
        return retval;
}

int main (int argc, const char * argv[]) {
        int i;
        int count;
        unsigned char in[4][4];
       
        for(i = 0; i < 1000; ++i) {
                rand_state(*in);
               
                if(TestMixColumns(*in) != 0)
                        ++count;
        }
       
        printf("\n\n%i/1000 wrong\n", count);
       
    return 0;
}

---

Perhaps I've gotten lost somewhere in the code, but when I'm looking at MixColumns or InvMixColumns (or any of the functions, really), I don't think we know anymore that in and out are arrays of 4 characters. So, (&out[0])[1] and (&out[1])[0] represent the same thing, to the compiler. Try a print_state and see if you don't see a symmetry.

Code:

---

void state123(unsigned char *state) {
        int x = 0;
        int i;
        int j;
       
        for(i = 0; i < 4; ++i) {
                for(j = 0; j < 4; ++j) {
                        (&state[i])[j] = x;
                        ++x;
                }
        }
}

state123(*in);
print_state(*in);

---

gives

Quote:

---

+----+----+----+----+
|0x00|0x04|0x08|0x0C|
+----+----+----+----+
|0x04|0x08|0x0C|0x0D|
+----+----+----+----+
|0x08|0x0C|0x0D|0x0E|
+----+----+----+----+
|0x0C|0x0D|0x0E|0x0F|
+----+----+----+----+

---

I think your right. Time to refresh on 2d arrays.

Thanks

Ok, 2nd attempt. This time I remember arrays == pointers. Code makes alittle more sense to me atleast but still wrong.

Any suggestions anychance? Back to being stumped already.

Thanks

Code:

---

#include <stdio.h>
#include <stdlib.h>
#include <time.h>

unsigned char gf_mult(unsigned char a, unsigned char b) {
        int i;
        int retval;
       
        /* If there isnt a "overflow", normal multiplication can be used */
        retval = a * b;
        if(retval < 128)
                return retval;
        else
                retval = 0;
       
        /* GF multiplication with insane bit shifting */
        for(i = 0; i < 8; i++) {
                if((b & 1) == 1)
                        retval ^= a;
               
                if((a & 0x80) == 0x80) {
                        a <<= 1;
                        a  ^= 0x1b;
                } else {
                        a <<= 1;
                }
               
                b >>= 1;
        }
       
        return (unsigned char)retval;
}

void print_state(unsigned char state[4][4]) {
        int i;
        int j;
       
        printf("+----+----+----+----+\n");
       
        for(i = 0; i < 4; ++i) {
                printf("|");
               
                for(j = 0; j < 4; ++j)
                        printf("0x&#37;02X|", state[i][j]);
               
                printf("\n");
                printf("+----+----+----+----+\n");
        }
}

void state123(unsigned char state[4][4]) {
        int x = 1;
        int i;
        int j;
       
        for(i = 0; i < 4; ++i) {
                for(j = 0; j < 4; ++j) {
                        state[i][j] = x;
                        ++x;
                }
        }
}

void rand_state(unsigned char state[4][4]) {
        int i;
        int j;
       
        srand ( time(NULL) );
        for(i = 0; i < 4; ++i) {
                for(j = 0; j < 4; ++j)
                        state[i][j] = (rand() % 256);
        }
}

void copy_state(unsigned char src[4][4], unsigned char dst[4][4]) {
        int i;
        int j;
       
        for(i = 0; i < 4; ++i) {
                for(j = 0; j < 4; ++j)
                        dst[i][j] = src[i][j];
        }
}

int state_equal(unsigned char a[4][4], unsigned char b[4][4]) {
        int i;
        int j;
       
        for(i = 0; i < 4; ++i) {
                for(j = 0; j < 4; ++j) {
                        if(a[i][j] != b[i][j])
                                return 1;
                }
        }
       
        return 0;
}

void MixColumns(unsigned char in[4][4], unsigned char out[4][4]) {
        int c;
        for(c = 0; c < 4; ++c) {
                out[0][c] = gf_mult(0x02, in[0][c]) ^ gf_mult(0x03, in[1][c])
                                ^ in[2][c] ^ in[3][c];
                out[1][c] = in[0][c] ^ gf_mult(0x02, in[1][c])
                                ^ gf_mult(0x03, in[2][c]) ^ in[3][c];
                out[2][c] = in[0][c] ^ in[1][c] ^ gf_mult(0x02, in[2][c])
                                ^ gf_mult(0x03, in[3][c]);
                out[3][c] = gf_mult(0x03, in[0][c]) ^ in[1][c] ^ in[2][c]
                                ^ gf_mult(0x02, in[3][c]);
        }
}

void InvMixColumns(unsigned char in[4][4], unsigned char out[4][4]) {
        int c;
        for(c = 0; c < 4; ++c) {
                out[0][c] = gf_mult(0x0E, in[0][c]) ^ gf_mult(0x0B, in[1][c])
                          ^ gf_mult(0x0D, in[2][c]) ^ gf_mult(0x09, in[3][c]);
                out[1][c] = gf_mult(0x09, in[0][c]) ^ gf_mult(0x0E, in[1][c])
                          ^ gf_mult(0x0B, in[2][c]) ^ gf_mult(0x0D, in[3][c]);
                out[2][c] = gf_mult(0x0D, in[0][c]) ^ gf_mult(0x09, in[1][c])
                          ^ gf_mult(0x0E, in[2][c]) ^ gf_mult(0x0B, in[3][c]);
                out[3][c] = gf_mult(0x0B, in[0][c]) ^ gf_mult(0x0D, in[1][c])
                          ^ gf_mult(0x09, in[2][c]) ^ gf_mult(0x0E, in[3][c]);
        }
}

int TestMixColumns(unsigned char state[4][4]) {
        unsigned char mc[4][4];
        unsigned char inv_mc[4][4];
       
        MixColumns(state, mc);
        InvMixColumns(mc, inv_mc);
       
        return state_equal(state, inv_mc);
}

int RandomMixColumnsTests(int tests) {
        int i;
        int wrong = 0;
        unsigned char in[4][4];
       
        for(i = 0; i < tests; ++i) {
                rand_state(in);
               
                if(TestMixColumns(in) != 0)
                        ++wrong;
        }
       
        printf("%i/%i wrong\n", wrong, tests);
        return wrong;
}

int main (int argc, const char * argv[]) {
        unsigned char in[4][4];
        state123(in);
        printf("123 state:\n");
        print_state(in);
       
        printf("\nMC Tests: ");
        RandomMixColumnsTests(100);
       
        return 0;
}

---

output:

Quote:

---

123 state:
+----+----+----+----+
|0x01|0x02|0x03|0x04|
+----+----+----+----+
|0x05|0x06|0x07|0x08|
+----+----+----+----+
|0x09|0x0A|0x0B|0x0C|
+----+----+----+----+
|0x0D|0x0E|0x0F|0x10|
+----+----+----+----+

MC Tests: 100/100 wrong

---

I checked out your "shortcut" in gf_mult, and found that the shortcut did not always give the same answer as the algorithm did (for instance 3x3 = 5, not 9, 5x5 = 17, not 25). Maybe remove the shortcut, as I don't think it's valid in a finite field anyway.

Ok, i removed the if leaving :

Code:

---

unsigned char gf_mult(unsigned char a, unsigned char b) {
        int i;
        int retval;
       
        /* GF multiplication with insane bit shifting */
        for(i = 0; i < 8; i++) {
                if((b & 1) == 1)
                        retval ^= a;
               
                if((a & 0x80) == 0x80) {
                        a <<= 1;
                        a  ^= 0x1b;
                } else {
                        a <<= 1;
                }
               
                b >>= 1;
        }
       
        return (unsigned char)retval;
}

---

It still get 100% wrong though. Im not even sure what else to look at now.

Thanks

You still need to initialize retval to 0 before you start.

I didn't see anything else that looked wrong on a first go-through; if that doesn't fix it, then we'll look again, I guess.

Doh! Yep, your right. Completely missed that. Think ive been starring at this for too long...

But unfortunately its still wrong. It seems to get most of the squares right though. Thats whats really bugging me now

Thanks

I've run your code as posted quite a few times now, and I get 0/100 wrong every time.... Can you print out one that doesn't work?