Thread: aes mix columns

  1. #1
    Registered User
    Join Date
    May 2006
    Posts
    57

    Unhappy 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;
    }

  2. #2
    and the Hat of Guessing tabstop's Avatar
    Join Date
    Nov 2007
    Posts
    14,336
    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.

  3. #3
    Registered User
    Join Date
    May 2006
    Posts
    57
    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
    +----+----+----+----+
    |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

  4. #4
    Registered User
    Join Date
    May 2006
    Posts
    57
    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:
    123 state:
    +----+----+----+----+
    |0x01|0x02|0x03|0x04|
    +----+----+----+----+
    |0x05|0x06|0x07|0x08|
    +----+----+----+----+
    |0x09|0x0A|0x0B|0x0C|
    +----+----+----+----+
    |0x0D|0x0E|0x0F|0x10|
    +----+----+----+----+

    MC Tests: 100/100 wrong
    Last edited by zxcv; 01-04-2008 at 12:24 AM.

  5. #5
    and the Hat of Guessing tabstop's Avatar
    Join Date
    Nov 2007
    Posts
    14,336
    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.

  6. #6
    Registered User
    Join Date
    May 2006
    Posts
    57
    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

  7. #7
    and the Hat of Guessing tabstop's Avatar
    Join Date
    Nov 2007
    Posts
    14,336
    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.

  8. #8
    Registered User
    Join Date
    May 2006
    Posts
    57
    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

  9. #9
    and the Hat of Guessing tabstop's Avatar
    Join Date
    Nov 2007
    Posts
    14,336
    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?

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. mix mode and processing the mix mode
    By stanlvw in forum Windows Programming
    Replies: 3
    Last Post: 07-24-2008, 01:50 PM
  2. Replies: 16
    Last Post: 11-23-2007, 01:48 PM
  3. Program that prints numbers in columns
    By rayrayj52 in forum C++ Programming
    Replies: 12
    Last Post: 09-20-2004, 02:43 PM
  4. reading a columns input data file
    By vk13wp in forum C Programming
    Replies: 6
    Last Post: 04-28-2003, 01:32 PM
  5. Number of columns in ListControl
    By MPSoutine in forum Windows Programming
    Replies: 3
    Last Post: 03-28-2003, 02:29 PM