]> git.cryptolib.org Git - arm-crypto-lib.git/blob - bmw/bmw_small.c
including even/odd-trick for BMW
[arm-crypto-lib.git] / bmw / bmw_small.c
1 /* bmw_small.c */
2 /*
3     This file is part of the ARM-Crypto-Lib.
4     Copyright (C) 2006-2010  Daniel Otte (daniel.otte@rub.de)
5
6     This program is free software: you can redistribute it and/or modify
7     it under the terms of the GNU General Public License as published by
8     the Free Software Foundation, either version 3 of the License, or
9     (at your option) any later version.
10
11     This program is distributed in the hope that it will be useful,
12     but WITHOUT ANY WARRANTY; without even the implied warranty of
13     MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
14     GNU General Public License for more details.
15
16     You should have received a copy of the GNU General Public License
17     along with this program.  If not, see <http://www.gnu.org/licenses/>.
18 */
19 /*
20  * \file    bmw_small.c
21  * \author  Daniel Otte
22  * \email   daniel.otte@rub.de
23  * \date    2009-04-27
24  * \license GPLv3 or later
25  *
26  */
27
28 #include <stdint.h>
29 #include <string.h>
30 #include "bmw_small.h"
31 #include "memxor/memxor.h"
32
33 #define SHL32(a,n) ((a)<<(n))
34 #define SHR32(a,n) ((a)>>(n))
35 #define ROTL32(a,n) (((a)<<(n))|((a)>>(32-(n))))
36 #define ROTR32(a,n) (((a)>>(n))|((a)<<(32-(n))))
37
38
39 #define TWEAK   1
40 #if TWEAK
41 #  define BUG24   0
42 #else
43 #  define BUG24   1
44 #endif
45
46 #define F0_HACK 0
47
48 #define DEBUG 0
49
50 #ifndef F0_HACK
51 #  define F0_HACK 0
52 #endif
53
54 #if DEBUG
55  #include "cli.h"
56
57  void ctx_dump(const bmw_small_ctx_t* ctx){
58         uint8_t i;
59         cli_putstr("\r\n==== ctx dump ====");
60         for(i=0; i<16;++i){
61                 cli_putstr("\r\n h[");
62                 cli_hexdump(&i, 1);
63                 cli_putstr("] = ");
64                 cli_hexdump_rev(&(ctx->h[i]), 4);
65         }
66         cli_putstr("\r\n counter = ");
67         cli_hexdump(&(ctx->counter), 4);
68  }
69
70  void dump_x(const uint32_t* q, uint8_t elements, char x){
71         uint8_t i;
72         cli_putstr("\r\n==== ");
73         cli_putc(x);
74         cli_putstr(" dump ====");
75         for(i=0; i<elements;++i){
76                 cli_putstr("\r\n ");
77                 cli_putc(x);
78                 cli_putstr("[");
79                 cli_hexdump(&i, 1);
80                 cli_putstr("] = ");
81                 cli_hexdump_rev(&(q[i]), 4);
82         }
83  }
84 #else
85  #define ctx_dump(x)
86  #define dump_x(a,b,c)
87 #endif
88
89 #define S32_0(x) ( (SHR32((x),   1)) ^ \
90                        (SHL32((x),   3)) ^ \
91                        (ROTL32((x),  4)) ^ \
92                        (ROTR32((x), 13)) )
93
94 #define S32_1(x) ( (SHR32((x),   1)) ^ \
95                        (SHL32((x),   2)) ^ \
96                        (ROTL32((x),  8)) ^ \
97                        (ROTR32((x),  9)) )
98
99 #define S32_2(x) ( (SHR32((x),   2)) ^ \
100                        (SHL32((x),   1)) ^ \
101                        (ROTL32((x), 12)) ^ \
102                        (ROTR32((x),  7)) )
103
104 #define S32_3(x) ( (SHR32((x),   2)) ^ \
105                        (SHL32((x),   2)) ^ \
106                        (ROTL32((x), 15)) ^ \
107                        (ROTR32((x),  3)) )
108
109 #define S32_4(x) ( (SHR32((x),   1)) ^ (x))
110
111 #define S32_5(x) ( (SHR32((x),   2)) ^ (x))
112
113 #define R32_1(x)   (ROTL32((x),  3))
114 #define R32_2(x)   (ROTL32((x),  7))
115 #define R32_3(x)   (ROTL32((x), 13))
116 #define R32_4(x)   (ROTL32((x), 16))
117 #define R32_5(x)   (ROTR32((x), 13))
118 #define R32_6(x)   (ROTR32((x),  9))
119 #define R32_7(x)   (ROTR32((x),  5))
120 /*
121 #define K 0x05555555L
122 static
123 uint32_t k_lut[] PROGMEM = {
124         16L*K, 17L*K, 18L*K, 19L*K, 20L*K, 21L*K, 22L*K, 23L*K,
125         24L*K, 25L*K, 26L*K, 27L*K, 28L*K, 29L*K, 30L*K, 31L*K
126 };
127 */
128 /* same as above but precomputed to avoid compiler warnings */
129
130 static
131 uint32_t k_lut[] = {
132         0x55555550L, 0x5aaaaaa5L, 0x5ffffffaL,
133         0x6555554fL, 0x6aaaaaa4L, 0x6ffffff9L,
134         0x7555554eL, 0x7aaaaaa3L, 0x7ffffff8L,
135         0x8555554dL, 0x8aaaaaa2L, 0x8ffffff7L,
136         0x9555554cL, 0x9aaaaaa1L, 0x9ffffff6L,
137         0xa555554bL };
138
139 static
140 uint32_t bmw_small_expand1(uint8_t j, const uint32_t* q, const void* m, const void* h){
141         uint32_t r;
142         /* r = 0x05555555*(j+16); */
143
144         r = (   ROTL32(((uint32_t*)m)[j&0xf],      ((j+0)&0xf)+1  )
145                + ROTL32(((uint32_t*)m)[(j+3)&0xf],  ((j+3)&0xf)+1  )
146                - ROTL32(((uint32_t*)m)[(j+10)&0xf], ((j+10)&0xf)+1 )
147                + k_lut[j]
148              ) ^ ((uint32_t*)h)[(j+7)&0xf];
149         r += S32_1(q[j+ 0]) + S32_2(q[j+ 1]) + S32_3(q[j+ 2]) + S32_0(q[j+ 3])
150        + S32_1(q[j+ 4]) + S32_2(q[j+ 5]) + S32_3(q[j+ 6]) + S32_0(q[j+ 7])
151            + S32_1(q[j+ 8]) + S32_2(q[j+ 9]) + S32_3(q[j+10]) + S32_0(q[j+11])
152        + S32_1(q[j+12]) + S32_2(q[j+13]) + S32_3(q[j+14]) + S32_0(q[j+15]);
153         return r;
154 }
155
156 static
157 uint32_t bmw_small_expand2(uint8_t j, const uint32_t* q, const void* m, const void* h){
158         uint32_t r;
159         r  = (   ROTL32(((uint32_t*)m)[j&0xf],      ((j+0)&0xf)+1  )
160                + ROTL32(((uint32_t*)m)[(j+3)&0xf],  ((j+3)&0xf)+1  )
161                - ROTL32(((uint32_t*)m)[(j+10)&0xf], ((j+10)&0xf)+1 )
162                + k_lut[j]
163              ) ^ ((uint32_t*)h)[(j+7)&0xf];
164         r +=      (q[j+ 0]) + R32_1(q[j+ 1]) +      (q[j+ 2]) + R32_2(q[j+ 3])
165        +      (q[j+ 4]) + R32_3(q[j+ 5]) +      (q[j+ 6]) + R32_4(q[j+ 7])
166            +      (q[j+ 8]) + R32_5(q[j+ 9]) +      (q[j+10]) + R32_6(q[j+11])
167        +      (q[j+12]) + R32_7(q[j+13]) + S32_4(q[j+14]) + S32_5(q[j+15]);
168         return r;
169 }
170
171 #if F0_HACK==2
172 /* to understand this implementation take a look at f0-opt-table.txt */
173 static uint16_t hack_table[5] = { 0x0311, 0xDDB3, 0x2A79, 0x07AA, 0x51C2 };
174 static uint8_t  offset_table[5] = { 4+16, 6+16, 9+16, 12+16, 13+16 };
175
176 static
177 void bmw_small_f0(uint32_t* q, uint32_t* h, const void* m){
178         uint16_t hack_reg;
179         uint8_t c,i,j;
180         uint32_t(*s[])(uint32_t)={ bmw_small_s0, bmw_small_s1, bmw_small_s2,
181                                    bmw_small_s3, bmw_small_s4 };
182         for(i=0; i<16; ++i){
183                 ((uint32_t*)h)[i] ^= ((uint32_t*)m)[i];
184         }
185         dump_x(h, 16, 'T');
186         memset(q, 0, 4*16);
187         c=4;
188         do{
189                 i=15;
190                 j=offset_table[c];
191                 hack_reg=hack_table[c];
192                 do{
193                         if(hack_reg&1){
194                                 q[i]-= h[j&15];
195                         }else{
196                                 q[i]+= h[j&15];
197                         }
198                         --j;
199                         hack_reg>>= 1;
200                 }while(i--!=0);
201         }while(c--!=0);
202         dump_x(q, 16, 'W');
203         for(i=0; i<16; ++i){
204                 q[i] = s[i%5](q[i]);
205         }
206         for(i=0; i<16; ++i){
207                 ((uint32_t*)h)[i] ^= ((uint32_t*)m)[i];
208         }
209         for(i=0; i<16; ++i){
210                 q[i] += h[(i+1)&0xf];
211         }
212 }
213 #endif /* F0_HACK==2*/
214
215 #if F0_HACK==1
216 static
217 uint8_t f0_lut[] PROGMEM = {
218          5<<1, ( 7<<1)+1, (10<<1)+0, (13<<1)+0, (14<<1)+0,
219          6<<1, ( 8<<1)+1, (11<<1)+0, (14<<1)+0, (15<<1)+1,
220          0<<1, ( 7<<1)+0, ( 9<<1)+0, (12<<1)+1, (15<<1)+0,
221          0<<1, ( 1<<1)+1, ( 8<<1)+0, (10<<1)+1, (13<<1)+0,
222          1<<1, ( 2<<1)+0, ( 9<<1)+0, (11<<1)+1, (14<<1)+1,
223          3<<1, ( 2<<1)+1, (10<<1)+0, (12<<1)+1, (15<<1)+0,
224          4<<1, ( 0<<1)+1, ( 3<<1)+1, (11<<1)+1, (13<<1)+0,
225          1<<1, ( 4<<1)+1, ( 5<<1)+1, (12<<1)+1, (14<<1)+1,
226          2<<1, ( 5<<1)+1, ( 6<<1)+1, (13<<1)+0, (15<<1)+1,
227          0<<1, ( 3<<1)+1, ( 6<<1)+0, ( 7<<1)+1, (14<<1)+0,
228          8<<1, ( 1<<1)+1, ( 4<<1)+1, ( 7<<1)+1, (15<<1)+0,
229          8<<1, ( 0<<1)+1, ( 2<<1)+1, ( 5<<1)+1, ( 9<<1)+0,
230          1<<1, ( 3<<1)+0, ( 6<<1)+1, ( 9<<1)+1, (10<<1)+0,
231          2<<1, ( 4<<1)+0, ( 7<<1)+0, (10<<1)+0, (11<<1)+0,
232          3<<1, ( 5<<1)+1, ( 8<<1)+0, (11<<1)+1, (12<<1)+1,
233         12<<1, ( 4<<1)+1, ( 6<<1)+1, ( 9<<1)+1, (13<<1)+0
234 };
235
236 static
237 void bmw_small_f0(uint32_t* q, uint32_t* h, const void* m){
238         uint8_t i,j=-1,v,sign,l=0;
239         uint32_t(*s[])(uint32_t)={ bmw_small_s0, bmw_small_s1, bmw_small_s2,
240                                    bmw_small_s3, bmw_small_s4 };
241         for(i=0; i<16; ++i){
242                 ((uint32_t*)h)[i] ^= ((uint32_t*)m)[i];
243         }
244         dump_x(h, 16, 'T');
245         // memset(q, 0, 4*16);
246         for(i=0; i<5*16; ++i){
247                 v = pgm_read_byte(f0_lut+i);
248                 sign = v&1;
249                 v >>=1;
250                 if(i==l){
251                         j++;
252                         l+=5;
253                         q[j] = h[v];
254                         continue;
255                 }
256                 if(sign){
257                         q[j] -= h[v];
258                 }else{
259                         q[j] += h[v];
260                 }
261         }
262         dump_x(q, 16, 'W');
263         for(i=0; i<16; ++i){
264                 q[i] = s[i%5](q[i]);
265         }
266         for(i=0; i<16; ++i){
267                 ((uint32_t*)h)[i] ^= ((uint32_t*)m)[i];
268         }
269         for(i=0; i<16; ++i){
270                 q[i] += h[(i+1)&0xf];
271         }
272 }
273 #endif /* F0_HACK==1 */
274
275 #if F0_HACK==0
276 static
277 void bmw_small_f0(uint32_t* q, uint32_t* h, const void* m){
278         uint8_t i;
279         for(i=0; i<16; ++i){
280                 ((uint32_t*)h)[i] ^= ((uint32_t*)m)[i];
281         }
282         dump_x(h, 16, 'T');
283         q[ 0] = (h[ 5] - h[ 7] + h[10] + h[13] + h[14]);
284         q[ 1] = (h[ 6] - h[ 8] + h[11] + h[14] - h[15]);
285         q[ 2] = (h[ 0] + h[ 7] + h[ 9] - h[12] + h[15]);
286         q[ 3] = (h[ 0] - h[ 1] + h[ 8] - h[10] + h[13]);
287         q[ 4] = (h[ 1] + h[ 2] + h[ 9] - h[11] - h[14]);
288         q[ 5] = (h[ 3] - h[ 2] + h[10] - h[12] + h[15]);
289         q[ 6] = (h[ 4] - h[ 0] - h[ 3] - h[11] + h[13]);
290         q[ 7] = (h[ 1] - h[ 4] - h[ 5] - h[12] - h[14]);
291         q[ 8] = (h[ 2] - h[ 5] - h[ 6] + h[13] - h[15]);
292         q[ 9] = (h[ 0] - h[ 3] + h[ 6] - h[ 7] + h[14]);
293         q[10] = (h[ 8] - h[ 1] - h[ 4] - h[ 7] + h[15]);
294         q[11] = (h[ 8] - h[ 0] - h[ 2] - h[ 5] + h[ 9]);
295         q[12] = (h[ 1] + h[ 3] - h[ 6] - h[ 9] + h[10]);
296         q[13] = (h[ 2] + h[ 4] + h[ 7] + h[10] + h[11]);
297         q[14] = (h[ 3] - h[ 5] + h[ 8] - h[11] - h[12]);
298         q[15] = (h[12] - h[ 4] - h[ 6] - h[ 9] + h[13]);
299         dump_x(q, 16, 'W');
300     q[ 0] = S32_0(q[ 0]);
301     q[ 1] = S32_1(q[ 1]);
302     q[ 2] = S32_2(q[ 2]);
303     q[ 3] = S32_3(q[ 3]);
304     q[ 4] = S32_4(q[ 4]);
305     q[ 5] = S32_0(q[ 5]);
306     q[ 6] = S32_1(q[ 6]);
307     q[ 7] = S32_2(q[ 7]);
308     q[ 8] = S32_3(q[ 8]);
309     q[ 9] = S32_4(q[ 9]);
310     q[10] = S32_0(q[10]);
311     q[11] = S32_1(q[11]);
312     q[12] = S32_2(q[12]);
313     q[13] = S32_3(q[13]);
314     q[14] = S32_4(q[14]);
315     q[15] = S32_0(q[15]);
316         for(i=0; i<16; ++i){
317                 ((uint32_t*)h)[i] ^= ((uint32_t*)m)[i];
318         }
319         for(i=0; i<16; ++i){
320                 q[i] += h[(i+1)&0xf];
321         }
322 }
323 #endif /* F0_HACK==0 */
324
325 static
326 void bmw_small_f1(uint32_t* q, const void* m, const void* h){
327         uint8_t i;
328         q[16] = bmw_small_expand1(0, q, m, h);
329         q[17] = bmw_small_expand1(1, q, m, h);
330         for(i=2; i<16; ++i){
331                 q[16+i] = bmw_small_expand2(i, q, m, h);
332         }
333 }
334
335 static
336 void bmw_small_f2(uint32_t* h, uint32_t* q, const void* m){
337         uint32_t xl=0, xh;
338         uint8_t i;
339         for(i=16;i<24;++i){
340                 xl ^= q[i];
341         }
342         xh = xl;
343         for(i=24;i<32;++i){
344                 xh ^= q[i];
345         }
346 #if DEBUG
347         cli_putstr("\r\n XL = ");
348         cli_hexdump_rev(&xl, 4);
349         cli_putstr("\r\n XH = ");
350         cli_hexdump_rev(&xh, 4);
351 #endif
352         memcpy(h, m, 16*4);
353         h[0] ^= SHL32(xh, 5) ^ SHR32(q[16], 5);
354         h[1] ^= SHR32(xh, 7) ^ SHL32(q[17], 8);
355         h[2] ^= SHR32(xh, 5) ^ SHL32(q[18], 5);
356         h[3] ^= SHR32(xh, 1) ^ SHL32(q[19], 5);
357         h[4] ^= SHR32(xh, 3) ^ q[20];
358         h[5] ^= SHL32(xh, 6) ^ SHR32(q[21], 6);
359         h[6] ^= SHR32(xh, 4) ^ SHL32(q[22], 6);
360         h[7] ^= SHR32(xh,11) ^ SHL32(q[23], 2);
361         for(i=0; i<8; ++i){
362                 h[i] += xl ^ q[24+i] ^ q[i];
363         }
364         for(i=0; i<8; ++i){
365                 h[8+i] ^= xh ^ q[24+i];
366                 h[8+i] += ROTL32(h[(4+i)%8],i+9);
367         }
368 /*
369         h[ 8] += SHL32(xl, 8) ^ q[23] ^ q[ 8];
370         h[ 9] += SHR32(xl, 6) ^ q[16] ^ q[ 9];
371         h[10] += SHL32(xl, 6) ^ q[17] ^ q[10];
372         h[11] += SHL32(xl, 4) ^ q[18] ^ q[11];
373         h[12] += SHR32(xl, 3) ^ q[19] ^ q[12];
374         h[13] += SHR32(xl, 4) ^ q[20] ^ q[13];
375         h[14] += SHR32(xl, 7) ^ q[21] ^ q[14];
376         h[15] += SHR32(xl, 2) ^ q[22] ^ q[15];
377 */
378         memxor(q+9, q+16, 7*4);
379         q[8] ^= q[23];
380         h[ 8] += SHL32(xl, 8) ^ q[ 8];
381         h[ 9] += SHR32(xl, 6) ^ q[ 9];
382         h[10] += SHL32(xl, 6) ^ q[10];
383         h[11] += SHL32(xl, 4) ^ q[11];
384         h[12] += SHR32(xl, 3) ^ q[12];
385         h[13] += SHR32(xl, 4) ^ q[13];
386         h[14] += SHR32(xl, 7) ^ q[14];
387         h[15] += SHR32(xl, 2) ^ q[15];
388
389 }
390
391 void bmw_small_nextBlock(bmw_small_ctx_t* ctx, const void* block){
392         uint32_t q[32];
393         dump_x(block, 16, 'M');
394         bmw_small_f0(q, ctx->h, block);
395         dump_x(q, 16, 'Q');
396         bmw_small_f1(q, block, ctx->h);
397         dump_x(q, 32, 'Q');
398         bmw_small_f2(ctx->h, q, block);
399         ctx->counter += 1;
400         ctx_dump(ctx);
401 }
402
403 void bmw_small_lastBlock(bmw_small_ctx_t* ctx, const void* block, uint16_t length_b){
404         uint8_t buffer[64];
405         while(length_b >= BMW_SMALL_BLOCKSIZE){
406                 bmw_small_nextBlock(ctx, block);
407                 length_b -= BMW_SMALL_BLOCKSIZE;
408                 block = (uint8_t*)block + BMW_SMALL_BLOCKSIZE_B;
409         }
410         memset(buffer, 0, 64);
411         memcpy(buffer, block, (length_b+7)/8);
412         buffer[length_b>>3] |= 0x80 >> (length_b&0x07);
413         if(length_b+1>64*8-64){
414                 bmw_small_nextBlock(ctx, buffer);
415                 memset(buffer, 0, 64-8);
416                 ctx->counter -= 1;
417         }
418         *((uint64_t*)&(buffer[64-8])) = (uint64_t)(ctx->counter*512LL)+(uint64_t)length_b;
419         bmw_small_nextBlock(ctx, buffer);
420 #if TWEAK
421         uint8_t i;
422         uint32_t q[32];
423         memset(buffer, 0xaa, 64);
424         for(i=0; i<16;++i){
425                 buffer[i*4] = i+0xa0;
426         }
427 //      dump_x(buffer, 16, 'A');
428         dump_x(ctx->h, 16, 'M');
429         bmw_small_f0(q, (uint32_t*)buffer, ctx->h);
430         dump_x(buffer, 16, 'a');
431         dump_x(q, 16, 'Q');
432         bmw_small_f1(q, ctx->h, (uint32_t*)buffer);
433         dump_x(q, 32, 'Q');
434         bmw_small_f2((uint32_t*)buffer, q, ctx->h);
435         memcpy(ctx->h, buffer, 64);
436 #endif
437 }
438
439 void bmw224_init(bmw224_ctx_t* ctx){
440         uint8_t i;
441         ctx->h[0] = 0x00010203;
442         for(i=1; i<16; ++i){
443                 ctx->h[i] = ctx->h[i-1]+ 0x04040404;
444         }
445 #if BUG24
446         ctx->h[13] = 0x24353637;
447 #endif
448         ctx->counter=0;
449         ctx_dump(ctx);
450 }
451
452 void bmw256_init(bmw256_ctx_t* ctx){
453         uint8_t i;
454         ctx->h[0] = 0x40414243;
455         for(i=1; i<16; ++i){
456                 ctx->h[i] = ctx->h[i-1]+ 0x04040404;
457         }
458         ctx->counter=0;
459         ctx_dump(ctx);
460 }
461
462 void bmw224_nextBlock(bmw224_ctx_t* ctx, const void* block){
463         bmw_small_nextBlock(ctx, block);
464 }
465
466 void bmw256_nextBlock(bmw256_ctx_t* ctx, const void* block){
467         bmw_small_nextBlock(ctx, block);
468 }
469
470 void bmw224_lastBlock(bmw224_ctx_t* ctx, const void* block, uint16_t length_b){
471         bmw_small_lastBlock(ctx, block, length_b);
472 }
473
474 void bmw256_lastBlock(bmw256_ctx_t* ctx, const void* block, uint16_t length_b){
475         bmw_small_lastBlock(ctx, block, length_b);
476 }
477
478 void bmw224_ctx2hash(void* dest, const bmw224_ctx_t* ctx){
479         memcpy(dest, &(ctx->h[9]), 224/8);
480 }
481
482 void bmw256_ctx2hash(void* dest, const bmw256_ctx_t* ctx){
483         memcpy(dest, &(ctx->h[8]), 256/8);
484 }
485
486 void bmw224(void* dest, const void* msg, uint32_t length_b){
487         bmw_small_ctx_t ctx;
488         bmw224_init(&ctx);
489         while(length_b>=BMW_SMALL_BLOCKSIZE){
490                 bmw_small_nextBlock(&ctx, msg);
491                 length_b -= BMW_SMALL_BLOCKSIZE;
492                 msg = (uint8_t*)msg + BMW_SMALL_BLOCKSIZE_B;
493         }
494         bmw_small_lastBlock(&ctx, msg, length_b);
495         bmw224_ctx2hash(dest, &ctx);
496 }
497
498 void bmw256(void* dest, const void* msg, uint32_t length_b){
499         bmw_small_ctx_t ctx;
500         bmw256_init(&ctx);
501         while(length_b>=BMW_SMALL_BLOCKSIZE){
502                 bmw_small_nextBlock(&ctx, msg);
503                 length_b -= BMW_SMALL_BLOCKSIZE;
504                 msg = (uint8_t*)msg + BMW_SMALL_BLOCKSIZE_B;
505         }
506         bmw_small_lastBlock(&ctx, msg, length_b);
507         bmw256_ctx2hash(dest, &ctx);
508 }
509