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