algo/md2.c

   1 /**
   2  * \file
   3  * <!--
   4  * This file is part of BeRTOS.
   5  *
   6  * Bertos 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 2 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, write to the Free Software
  18  * Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA  02110-1301  USA
  19  *
  20  * As a special exception, you may use this file as part of a free software
  21  * library without restriction.  Specifically, if other files instantiate
  22  * templates or use macros or inline functions from this file, or you compile
  23  * this file and link it with other files to produce an executable, this
  24  * file does not by itself cause the resulting executable to be covered by
  25  * the GNU General Public License.  This exception does not however
  26  * invalidate any other reasons why the executable file might be covered by
  27  * the GNU General Public License.
  28  *
  29  * Copyright 2007 Develer S.r.l. (http://www.develer.com/)
  30  *
  31  * -->
  32  *
  33  * \brief MD2 Message-Digest algorithm.
  34  *
  35  * The MD2 algorithm work with a constant array of 256 permutationt
  36  * defined in RFC1319. If you don't want to use a standard array of
  37  * permutatione you can use a md2_perm() function that generate an
  38  * array of 256 "casual" permutation. To swich from a standard array
  39  * to md2_perm function you must chanche CONFIG_MD2_STD_PERM defined in
  40  * appconfig.h.
  41  * If you need to store array in program memory you must define
  42  * a macro _PROGMEM (for more info see mware/pgm.h).
  43  *
  44  *
  45  * \version $Id$
  46  * \author Daniele Basile <asterix@develer.com>
  47  */
  48
  49 /*#*
  50  *#* $Log$
  51  *#* Revision 1.17  2007/06/07 16:06:39  batt
  52  *#* Fix some doxygen errors.
  53  *#*
  54  *#* Revision 1.16  2007/02/15 13:29:49  asterix
  55  *#* Add MD2_DIGEST_LEN macro.
  56  *#*
  57  *#* Revision 1.15  2007/02/06 15:53:34  asterix
  58  *#* Add ROTR macro in m2d_perm, add comments, typos.
  59  *#*
  60  *#* Revision 1.13  2007/02/05 18:44:42  asterix
  61  *#* Add md2_perm function.
  62  *#*
  63  *#* Revision 1.12  2007/02/05 16:52:44  asterix
  64  *#* Add define for harvard architecture.
  65  *#*
  66  *#* Revision 1.11  2007/02/02 18:15:31  asterix
  67  *#* Add function MD2_test. Fix bug in md2_update function.
  68  *#*
  69  *#* Revision 1.9  2007/02/02 13:10:01  asterix
  70  *#* Fix some bugs in md2_pad and md2_update fuction.
  71  *#*
  72  *#* Revision 1.8  2007/02/01 14:45:56  asterix
  73  *#* Rewrite md2_update function and fix some bug.
  74  *#*
  75  *#* Revision 1.7  2007/01/31 18:04:15  asterix
  76  *#* Write md2_end function
  77  *#*
  78  *#* Revision 1.4  2007/01/31 13:51:57  asterix
  79  *#* Write md2_compute function.
  80  *#*
  81  *#* Revision 1.2  2007/01/30 17:31:44  asterix
  82  *#* Add function prototypes.
  83  *#*
  84  *#* Revision 1.1  2007/01/30 15:53:26  batt
  85  *#* Add first md2 skel.
  86  *#*
  87  *#*/
  88
  89 #include "md2.h"
  90
  91 #include <string.h>           //memset(), memcpy();
  92 #include <cfg/compiler.h>
  93 #include <cfg/debug.h>        //ASSERT()
  94 #include <cfg/macros.h>       //MIN(), countof(), ROTR();
  95 #include <mware/pgm.h>
  96
  97
  98 #if CONFIG_MD2_STD_PERM
  99         /*
 100         * Official array of 256 byte pemutation contructed from digits of pi, defined
 101         * in the RFC 1319.
 102         */
 103         static const uint8_t PGM_ATTR md2_perm[256] =
 104         {
 105         41, 46, 67, 201, 162, 216, 124, 1, 61, 54, 84, 161, 236, 240, 6,
 106         19, 98, 167, 5, 243, 192, 199, 115, 140, 152, 147, 43, 217, 188,
 107         76, 130, 202, 30, 155, 87, 60, 253, 212, 224, 22, 103, 66, 111, 24,
 108         138, 23, 229, 18, 190, 78, 196, 214, 218, 158, 222, 73, 160, 251,
 109         245, 142, 187, 47, 238, 122, 169, 104, 121, 145, 21, 178, 7, 63,
 110         148, 194, 16, 137, 11, 34, 95, 33, 128, 127, 93, 154, 90, 144, 50,
 111         39, 53, 62, 204, 231, 191, 247, 151, 3, 255, 25, 48, 179, 72, 165,
 112         181, 209, 215, 94, 146, 42, 172, 86, 170, 198, 79, 184, 56, 210,
 113         150, 164, 125, 182, 118, 252, 107, 226, 156, 116, 4, 241, 69, 157,
 114         112, 89, 100, 113, 135, 32, 134, 91, 207, 101, 230, 45, 168, 2, 27,
 115         96, 37, 173, 174, 176, 185, 246, 28, 70, 97, 105, 52, 64, 126, 15,
 116         85, 71, 163, 35, 221, 81, 175, 58, 195, 92, 249, 206, 186, 197,
 117         234, 38, 44, 83, 13, 110, 133, 40, 132, 9, 211, 223, 205, 244, 65,
 118         129, 77, 82, 106, 220, 55, 200, 108, 193, 171, 250, 36, 225, 123,
 119         8, 12, 189, 177, 74, 120, 136, 149, 139, 227, 99, 232, 109, 233,
 120         203, 213, 254, 59, 0, 29, 57, 242, 239, 183, 14, 102, 88, 208, 228,
 121         166, 119, 114, 248, 235, 117, 75, 10, 49, 68, 80, 180, 143, 237,
 122         31, 26, 219, 153, 141, 51, 159, 17, 131, 20
 123         };
 124
 125         #define MD2_PERM(x) PGM_READ_CHAR(&md2_perm[x])
 126 #else
 127         /**
 128          * Md2_perm() function generate an array of 256 "casual" permutation.
 129          */
 130
 131         /**
 132          * Costant define for computing an array of 256 "casual" permutation.
 133          * \{
 134          */
 135         #define K1 5
 136         #define K2 3
 137         #define R  2
 138         #define X  172
 139         /*\}*/
 140
 141         static uint8_t md2_perm(uint8_t i)
 142         {
 143
 144                 i = i * K1;
 145                 i = ROTR(i, R);
 146                 i ^=  X;
 147                 i = i * K2;
 148
 149                 return i;
 150         }
 151
 152         #define MD2_PERM(x) md2_perm(x)
 153
 154 #endif
 155
 156
 157 /**
 158  * Pad function. Put len_pad unsigned char in
 159  * input block.
 160  */
 161 static void md2_pad(void *_block, size_t len_pad)
 162 {
 163         uint8_t *block;
 164
 165         block = (uint8_t *)_block;
 166
 167         ASSERT(len_pad <= CONFIG_MD2_BLOCK_LEN);
 168
 169         /*
 170          * Fill input block with len_pad char.
 171          */
 172         memset(block, len_pad, len_pad);
 173
 174 }
 175
 176 static void md2_compute(void *_state, void *_checksum, void *_block)
 177 {
 178         int i = 0;
 179         uint16_t t = 0;
 180         uint8_t compute_array[COMPUTE_ARRAY_LEN];
 181         uint8_t *state;
 182         uint8_t *checksum;
 183         uint8_t *block;
 184
 185         state = (uint8_t *)_state;
 186         checksum  = (uint8_t *)_checksum;
 187         block = (uint8_t *)_block;
 188
 189         /*
 190          * Copy state and checksum context in compute array.
 191          */
 192         memcpy(compute_array, state, CONFIG_MD2_BLOCK_LEN);
 193         memcpy(compute_array + CONFIG_MD2_BLOCK_LEN, block, CONFIG_MD2_BLOCK_LEN);
 194
 195         /*
 196          * Fill compute array with state XOR block
 197          */
 198         for(i = 0; i < CONFIG_MD2_BLOCK_LEN; i++)
 199                 compute_array[i + (CONFIG_MD2_BLOCK_LEN * 2)] = state[i] ^ block[i];
 200
 201         /*
 202          * Encryt block.
 203          */
 204         for(i = 0; i < NUM_COMPUTE_ROUNDS; i++)
 205         {
 206                 for(int j = 0; j < COMPUTE_ARRAY_LEN; j++)
 207                 {
 208                         compute_array[j] ^= MD2_PERM(t);
 209                         t = compute_array[j];
 210                 }
 211
 212                 t = (t + i) & 0xff; //modulo 256.
 213         }
 214         /*
 215          * Update checksum.
 216          */
 217         t = checksum[CONFIG_MD2_BLOCK_LEN - 1];
 218
 219         for(i = 0; i < CONFIG_MD2_BLOCK_LEN; i++)
 220         {
 221                 checksum[i]  ^= MD2_PERM(block[i] ^ t);
 222                 t = checksum[i];
 223         }
 224
 225         /*
 226          * Update state and clean compute array.
 227          */
 228         memcpy(state, compute_array, CONFIG_MD2_BLOCK_LEN);
 229         memset(compute_array, 0, sizeof(compute_array));
 230 }
 231
 232 /**
 233  * Algorithm initialization.
 234  *
 235  * \param context empty context.
 236  */
 237 void md2_init(Md2Context *context)
 238 {
 239
 240         memset(context, 0, sizeof(Md2Context));
 241
 242 }
 243
 244 /**
 245  * Update block.
 246  */
 247 void md2_update(Md2Context *context, const void *_block_in, size_t block_len)
 248 {
 249
 250         const uint8_t *block_in;
 251         size_t cpy_len;
 252
 253
 254         block_in = (const uint8_t *)_block_in;
 255
 256         while(block_len > 0)
 257         {
 258                 /*
 259                  * Choose a number of block that fill input context buffer.
 260                  */
 261                 cpy_len = MIN(block_len, CONFIG_MD2_BLOCK_LEN - context->counter);
 262
 263
 264                 /*
 265                  * Copy in the buffer input block.
 266                  */
 267                 memcpy(&context->buffer[context->counter], block_in, cpy_len);
 268
 269                 /*
 270                  * Update a context counter, input block length and remaning
 271                  * context buffer block lenght.
 272                  */
 273                 context->counter += cpy_len;
 274                 block_len -= cpy_len;
 275                 block_in += cpy_len;
 276
 277                 /*
 278                  * If buffer is full, compute it.
 279                  */
 280                 if (context->counter >= CONFIG_MD2_BLOCK_LEN)
 281                 {
 282                         md2_compute(context->state, context->checksum, context->buffer);
 283                         context->counter = 0;
 284                 }
 285         }
 286
 287
 288 }
 289 /**
 290  * Ends an MD2 message digest operation.
 291  * This fuction take an context and return a pointer
 292  * to context state.
 293  *
 294  * \param context in input.
 295  * \return a pointer to context state (message digest).
 296  */
 297 uint8_t  *md2_end(Md2Context *context)
 298 {
 299
 300         uint8_t buf[CONFIG_MD2_BLOCK_LEN];
 301
 302         /*
 303          * Fill remaning empty context buffer.
 304          */
 305         md2_pad(buf, CONFIG_MD2_BLOCK_LEN - context->counter);
 306
 307         /*
 308          * Update context buffer and compute it.
 309          */
 310         md2_update(context, buf, CONFIG_MD2_BLOCK_LEN - context->counter);
 311
 312         /*
 313          * Add context checksum to message input.
 314          */
 315         md2_update(context, context->checksum, CONFIG_MD2_BLOCK_LEN);
 316
 317
 318         return context->state; //return a pointer to message digest.
 319 }
 320 /**
 321  * MD2 test fuction.
 322  * This function test MD2 algorithm with a standard string specified
 323  * in RFC 1319.
 324  *
 325  * \note This test work with official array of 256 byte pemutation
 326  * contructed from digits of pi, defined in the RFC 1319.
 327  *
 328  */
 329 bool md2_test(void)
 330 {
 331
 332         Md2Context context;
 333
 334         const char *test[] =
 335         {
 336                 "",
 337                 "message digest",
 338                 "abcdefghijklmnopqrstuvwxyz",
 339                 "12345678901234567890123456789012345678901234567890123456789012345678901234567890"
 340         };
 341
 342
 343         const uint8_t *result[] = {
 344                 "\x83\x50\xe5\xa3\xe2\x4c\x15\x3d\xf2\x27\x5c\x9f\x80\x69\x27\x73",
 345                 "\xab\x4f\x49\x6b\xfb\x2a\x53\x0b\x21\x9f\xf3\x30\x31\xfe\x06\xb0",
 346                 "\x4e\x8d\xdf\xf3\x65\x02\x92\xab\x5a\x41\x08\xc3\xaa\x47\x94\x0b",
 347                 "\xd5\x97\x6f\x79\xd8\x3d\x3a\x0d\xc9\x80\x6c\x3c\x66\xf3\xef\xd8",
 348         };
 349
 350
 351         for (int i = 0; i < countof(test); i++)
 352         {
 353                 md2_init(&context);
 354                 md2_update(&context, test[i], strlen(test[i]));
 355
 356                 if(memcmp(result[i], md2_end(&context), MD2_DIGEST_LEN))
 357                         return false;
 358         }
 359
 360         return true;
 361 }
 362
 363 #if 0
 364
 365 #include <stdio.h>
 366 int main(int argc, char * argv[])
 367 {
 368
 369         if(md2_test())
 370                 printf("MD2 algorithm work well!\n");
 371         else
 372                 printf("MD2 algorithm doesn't work well.\n");
 373
 374 }
 375
 376 #endif
 377