From: bg Date: Thu, 5 Nov 2009 10:09:51 +0000 (+0000) Subject: another hack for f0 in BMW X-Git-Url: https://git.cryptolib.org/?p=avr-crypto-lib.git;a=commitdiff_plain;h=9370f0f89a5021cfeefbf35054f82e37533c7249 another hack for f0 in BMW --- diff --git a/bmw/bmw_small.c b/bmw/bmw_small.c index 8a4b165..273738c 100644 --- a/bmw/bmw_small.c +++ b/bmw/bmw_small.c @@ -44,10 +44,14 @@ # define BUG24 1 #endif -#define F0_HACK 1 +#define F0_HACK 2 #define DEBUG 0 +#ifndef F0_HACK +# define F0_HACK 0 +#endif + #if DEBUG #include "cli.h" @@ -83,6 +87,7 @@ #define dump_x(a,b,c) #endif +static uint32_t bmw_small_s0(uint32_t x){ uint32_t r; r = SHR32(x, 1) @@ -92,6 +97,7 @@ uint32_t bmw_small_s0(uint32_t x){ return r; } +static uint32_t bmw_small_s1(uint32_t x){ uint32_t r; r = SHR32(x, 1) @@ -101,6 +107,7 @@ uint32_t bmw_small_s1(uint32_t x){ return r; } +static uint32_t bmw_small_s2(uint32_t x){ uint32_t r; r = SHR32(x, 2) @@ -110,6 +117,7 @@ uint32_t bmw_small_s2(uint32_t x){ return r; } +static uint32_t bmw_small_s3(uint32_t x){ uint32_t r; r = SHR32(x, 2) @@ -119,6 +127,7 @@ uint32_t bmw_small_s3(uint32_t x){ return r; } +static uint32_t bmw_small_s4(uint32_t x){ uint32_t r; r = SHR32(x, 1) @@ -126,6 +135,7 @@ uint32_t bmw_small_s4(uint32_t x){ return r; } +static uint32_t bmw_small_s5(uint32_t x){ uint32_t r; r = SHR32(x, 2) @@ -133,42 +143,49 @@ uint32_t bmw_small_s5(uint32_t x){ return r; } +static uint32_t bmw_small_r1(uint32_t x){ uint32_t r; r = ROTL32(x, 3); return r; } +static uint32_t bmw_small_r2(uint32_t x){ uint32_t r; r = ROTL32(x, 7); return r; } +static uint32_t bmw_small_r3(uint32_t x){ uint32_t r; r = ROTL32(x, 13); return r; } +static uint32_t bmw_small_r4(uint32_t x){ uint32_t r; r = ROTL32(x, 16); return r; } +static uint32_t bmw_small_r5(uint32_t x){ uint32_t r; r = ROTR32(x, 13); return r; } +static uint32_t bmw_small_r6(uint32_t x){ uint32_t r; r = ROTR32(x, 9); return r; } +static uint32_t bmw_small_r7(uint32_t x){ uint32_t r; r = ROTR32(x, 5); @@ -193,7 +210,7 @@ uint32_t k_lut[] PROGMEM = { 0x9555554cL, 0x9aaaaaa1L, 0x9ffffff6L, 0xa555554bL }; - +static uint32_t bmw_small_expand1(uint8_t j, const uint32_t* q, const void* m, const void* h){ uint32_t(*s[])(uint32_t) = {bmw_small_s1, bmw_small_s2, bmw_small_s3, bmw_small_s0}; uint32_t r=0; @@ -217,6 +234,7 @@ uint32_t bmw_small_expand1(uint8_t j, const uint32_t* q, const void* m, const vo return r; } +static uint32_t bmw_small_expand2(uint8_t j, const uint32_t* q, const void* m, const void* h){ uint32_t(*rf[])(uint32_t) = {bmw_small_r1, bmw_small_r2, bmw_small_r3, bmw_small_r4, bmw_small_r5, bmw_small_r6, @@ -251,7 +269,53 @@ uint32_t bmw_small_expand2(uint8_t j, const uint32_t* q, const void* m, const vo return r; } -#if F0_HACK +#if F0_HACK==2 +/* to understand this implementation take a look at f0-opt-table.txt */ +uint16_t hack_table[5] PROGMEM = { 0x0311, 0xDDB3, 0x2A79, 0x07AA, 0x51C2 }; +uint8_t offset_table[5] PROGMEM = { 4+16, 6+16, 9+16, 12+16, 13+16 }; + +static +void bmw_small_f0(uint32_t* q, uint32_t* h, const void* m){ + uint16_t hack_reg; + uint8_t c,i,j; + uint32_t(*s[])(uint32_t)={ bmw_small_s0, bmw_small_s1, bmw_small_s2, + bmw_small_s3, bmw_small_s4 }; + for(i=0; i<16; ++i){ + ((uint32_t*)h)[i] ^= ((uint32_t*)m)[i]; + } + dump_x(h, 16, 'T'); + memset(q, 0, 4*16); + c=4; + do{ + i=15; + j=pgm_read_byte(offset_table+c); + hack_reg=pgm_read_word(&(hack_table[c])); + do{ + if(hack_reg&1){ + q[i]-= h[j&15]; + }else{ + q[i]+= h[j&15]; + } + --j; + hack_reg>>= 1; + }while(i--!=0); + }while(c--!=0); + dump_x(q, 16, 'W'); + for(i=0; i<16; ++i){ + q[i] = s[i%5](q[i]); + } +#if TWEAK + for(i=0; i<16; ++i){ + ((uint32_t*)h)[i] ^= ((uint32_t*)m)[i]; + } + for(i=0; i<16; ++i){ + q[i] += h[(i+1)&0xf]; + } +#endif +} +#endif /* F0_HACK==2*/ + +#if F0_HACK==1 static uint8_t f0_lut[] PROGMEM = { 5<<1, ( 7<<1)+1, (10<<1)+0, (13<<1)+0, (14<<1)+0, @@ -272,6 +336,7 @@ uint8_t f0_lut[] PROGMEM = { 12<<1, ( 4<<1)+1, ( 6<<1)+1, ( 9<<1)+1, (13<<1)+0 }; +static void bmw_small_f0(uint32_t* q, uint32_t* h, const void* m){ uint8_t i,j=-1,v,sign,l=0; uint32_t(*s[])(uint32_t)={ bmw_small_s0, bmw_small_s1, bmw_small_s2, @@ -308,10 +373,12 @@ void bmw_small_f0(uint32_t* q, uint32_t* h, const void* m){ for(i=0; i<16; ++i){ q[i] += h[(i+1)&0xf]; } -#endif +#endif /* TWEAK */ } +#endif /* F0_HACK==1 */ -#else +#if F0_HACK==0 +static void bmw_small_f0(uint32_t* q, uint32_t* h, const void* m){ uint8_t i; uint32_t(*s[])(uint32_t)={ bmw_small_s0, bmw_small_s1, bmw_small_s2, @@ -347,10 +414,11 @@ void bmw_small_f0(uint32_t* q, uint32_t* h, const void* m){ for(i=0; i<16; ++i){ q[i] += h[(i+1)&0xf]; } -#endif +#endif /* TWEAK */ } -#endif +#endif /* F0_HACK==0 */ +static void bmw_small_f1(uint32_t* q, const void* m, const void* h){ uint8_t i; q[16] = bmw_small_expand1(0, q, m, h); @@ -360,6 +428,7 @@ void bmw_small_f1(uint32_t* q, const void* m, const void* h){ } } +static void bmw_small_f2(uint32_t* h, const uint32_t* q, const void* m){ uint32_t xl=0, xh; uint8_t i; diff --git a/bmw/f0-opt-table.txt b/bmw/f0-opt-table.txt new file mode 100644 index 0000000..a975644 --- /dev/null +++ b/bmw/f0-opt-table.txt @@ -0,0 +1,75 @@ + q[ 0] = (+ h[ 5] - h[ 7] + h[10] + h[13] + h[14]); + q[ 1] = (+ h[ 6] - h[ 8] + h[11] + h[14] - h[15]); + q[ 2] = (+ h[ 7] + h[ 9] - h[12] + h[15] + h[ 0]); + q[ 3] = (+ h[ 8] - h[10] + h[13] + h[ 0] - h[ 1]); + q[ 4] = (+ h[ 9] - h[11] - h[14] + h[ 1] + h[ 2]); + q[ 5] = (+ h[10] - h[12] + h[15] - h[ 2] + h[ 3]); + q[ 6] = (- h[11] + h[13] - h[ 0] - h[ 3] + h[ 4]); + q[ 7] = (- h[12] - h[14] + h[ 1] - h[ 4] - h[ 5]); + q[ 8] = (+ h[13] - h[15] + h[ 2] - h[ 5] - h[ 6]); + q[ 9] = (+ h[14] + h[ 0] - h[ 3] + h[ 6] - h[ 7]); + q[10] = (+ h[15] - h[ 1] - h[ 4] - h[ 7] + h[ 8]); + q[11] = (- h[ 0] - h[ 2] - h[ 5] + h[ 8] + h[ 9]); + q[12] = (+ h[ 1] + h[ 3] - h[ 6] - h[ 9] + h[10]); + q[13] = (+ h[ 2] + h[ 4] + h[ 7] + h[10] + h[11]); + q[14] = (+ h[ 3] - h[ 5] + h[ 8] - h[11] - h[12]); + q[15] = (- h[ 4] - h[ 6] - h[ 9] + h[12] + h[13]); + +########################################################## + +1 := - +0 := + + + + +---------- 0x0311 + | +-------- 0xDDB3 + | | +------ 0x2A79 + | | | +---- 0x07AA + | | | | +-- 0x51C2 + | | | | | +--------------- + 0: 0 1 0 0 0 + - + + + + 1: 0 1 0 0 1 + - + + - + 2: 0 0 1 0 0 + + - + + + 3: 0 1 0 0 1 + - + + - +--------------- + 4: 0 1 1 0 0 + - - + + + 5: 0 1 0 1 0 + - + - + + 6: 1 0 1 1 0 - + - - + + 7: 1 1 0 1 1 - - + - - +--------------- + 8: 0 1 0 1 1 + - + - - + 9: 0 0 1 0 1 + + - + - +10: 0 1 1 1 0 + - - - + +11: 1 1 1 0 0 - - - + + +--------------- +12: 0 0 1 1 0 + + - - + +13: 0 0 0 0 0 + + + + + +14: 0 1 0 1 1 + - + - - +15: 1 1 1 0 0 - - - + + +--------------- + | | | | | + | | | | +-- 0x438A + | | | +---- 0x55E0 + | | +------ 0x9E54 + | +-------- 0xCDBB + +---------- 0x88C0 + +#################################################### + + + + + + + + + + + + + + + + +