git.zerfleddert.de Git - proxmark3-svn/blob - armsrc/des.c

   1 /* des.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     des.c
  21  * \author   Daniel Otte
  22  * \email    daniel.otte@rub.de
  23  * \date     2007-06-16
  24  * \brief    DES and EDE-DES implementation
  25  * \license      GPLv3 or later
  26  *
  27  */
  28
  29 #include "des.h"
  30
  31 const uint8_t sbox[256]  = {
  32   /* S-box 1 */
  33   0xE4, 0xD1, 0x2F, 0xB8, 0x3A, 0x6C, 0x59, 0x07,
  34   0x0F, 0x74, 0xE2, 0xD1, 0xA6, 0xCB, 0x95, 0x38,
  35   0x41, 0xE8, 0xD6, 0x2B, 0xFC, 0x97, 0x3A, 0x50,
  36   0xFC, 0x82, 0x49, 0x17, 0x5B, 0x3E, 0xA0, 0x6D,
  37   /* S-box 2 */
  38   0xF1, 0x8E, 0x6B, 0x34, 0x97, 0x2D, 0xC0, 0x5A,
  39   0x3D, 0x47, 0xF2, 0x8E, 0xC0, 0x1A, 0x69, 0xB5,
  40   0x0E, 0x7B, 0xA4, 0xD1, 0x58, 0xC6, 0x93, 0x2F,
  41   0xD8, 0xA1, 0x3F, 0x42, 0xB6, 0x7C, 0x05, 0xE9,
  42   /* S-box 3 */
  43   0xA0, 0x9E, 0x63, 0xF5, 0x1D, 0xC7, 0xB4, 0x28,
  44   0xD7, 0x09, 0x34, 0x6A, 0x28, 0x5E, 0xCB, 0xF1,
  45   0xD6, 0x49, 0x8F, 0x30, 0xB1, 0x2C, 0x5A, 0xE7,
  46   0x1A, 0xD0, 0x69, 0x87, 0x4F, 0xE3, 0xB5, 0x2C,
  47   /* S-box 4 */
  48   0x7D, 0xE3, 0x06, 0x9A, 0x12, 0x85, 0xBC, 0x4F,
  49   0xD8, 0xB5, 0x6F, 0x03, 0x47, 0x2C, 0x1A, 0xE9,
  50   0xA6, 0x90, 0xCB, 0x7D, 0xF1, 0x3E, 0x52, 0x84,
  51   0x3F, 0x06, 0xA1, 0xD8, 0x94, 0x5B, 0xC7, 0x2E,
  52   /* S-box 5 */
  53   0x2C, 0x41, 0x7A, 0xB6, 0x85, 0x3F, 0xD0, 0xE9,
  54   0xEB, 0x2C, 0x47, 0xD1, 0x50, 0xFA, 0x39, 0x86,
  55   0x42, 0x1B, 0xAD, 0x78, 0xF9, 0xC5, 0x63, 0x0E,
  56   0xB8, 0xC7, 0x1E, 0x2D, 0x6F, 0x09, 0xA4, 0x53,
  57   /* S-box 6 */
  58   0xC1, 0xAF, 0x92, 0x68, 0x0D, 0x34, 0xE7, 0x5B,
  59   0xAF, 0x42, 0x7C, 0x95, 0x61, 0xDE, 0x0B, 0x38,
  60   0x9E, 0xF5, 0x28, 0xC3, 0x70, 0x4A, 0x1D, 0xB6,
  61   0x43, 0x2C, 0x95, 0xFA, 0xBE, 0x17, 0x60, 0x8D,
  62   /* S-box 7 */
  63   0x4B, 0x2E, 0xF0, 0x8D, 0x3C, 0x97, 0x5A, 0x61,
  64   0xD0, 0xB7, 0x49, 0x1A, 0xE3, 0x5C, 0x2F, 0x86,
  65   0x14, 0xBD, 0xC3, 0x7E, 0xAF, 0x68, 0x05, 0x92,
  66   0x6B, 0xD8, 0x14, 0xA7, 0x95, 0x0F, 0xE2, 0x3C,
  67   /* S-box 8 */
  68   0xD2, 0x84, 0x6F, 0xB1, 0xA9, 0x3E, 0x50, 0xC7,
  69   0x1F, 0xD8, 0xA3, 0x74, 0xC5, 0x6B, 0x0E, 0x92,
  70   0x7B, 0x41, 0x9C, 0xE2, 0x06, 0xAD, 0xF3, 0x58,
  71   0x21, 0xE7, 0x4A, 0x8D, 0xFC, 0x90, 0x35, 0x6B
  72 };
  73
  74 const uint8_t e_permtab[] ={
  75          4,  6,                                         /* 4 bytes in 6 bytes out*/
  76         32,  1,  2,  3,  4,  5,
  77          4,  5,  6,  7,  8,  9,
  78          8,  9, 10, 11, 12, 13,
  79         12, 13, 14, 15, 16, 17,
  80         16, 17, 18, 19, 20, 21,
  81         20, 21, 22, 23, 24, 25,
  82         24, 25, 26, 27, 28, 29,
  83         28, 29, 30, 31, 32,  1
  84 };
  85
  86 const uint8_t p_permtab[] ={
  87          4,  4,                                         /* 32 bit -> 32 bit */
  88         16,  7, 20, 21,
  89         29, 12, 28, 17,
  90          1, 15, 23, 26,
  91          5, 18, 31, 10,
  92          2,  8, 24, 14,
  93         32, 27,  3,  9,
  94         19, 13, 30,  6,
  95         22, 11,  4, 25
  96 };
  97
  98 const uint8_t ip_permtab[] ={
  99          8,  8,                                         /* 64 bit -> 64 bit */
 100         58, 50, 42, 34, 26, 18, 10, 2,
 101         60, 52, 44, 36, 28, 20, 12, 4,
 102         62, 54, 46, 38, 30, 22, 14, 6,
 103         64, 56, 48, 40, 32, 24, 16, 8,
 104         57, 49, 41, 33, 25, 17,  9, 1,
 105         59, 51, 43, 35, 27, 19, 11, 3,
 106         61, 53, 45, 37, 29, 21, 13, 5,
 107         63, 55, 47, 39, 31, 23, 15, 7
 108 };
 109
 110 const uint8_t inv_ip_permtab[] ={
 111          8, 8,                                          /* 64 bit -> 64 bit */
 112         40, 8, 48, 16, 56, 24, 64, 32,
 113         39, 7, 47, 15, 55, 23, 63, 31,
 114         38, 6, 46, 14, 54, 22, 62, 30,
 115         37, 5, 45, 13, 53, 21, 61, 29,
 116         36, 4, 44, 12, 52, 20, 60, 28,
 117         35, 3, 43, 11, 51, 19, 59, 27,
 118         34, 2, 42, 10, 50, 18, 58, 26,
 119         33, 1, 41,  9, 49, 17, 57, 25
 120 };
 121
 122 const uint8_t pc1_permtab[] ={
 123          8,  7,                                         /* 64 bit -> 56 bit*/
 124         57, 49, 41, 33, 25, 17,  9,
 125          1, 58, 50, 42, 34, 26, 18,
 126         10,  2, 59, 51, 43, 35, 27,
 127         19, 11,  3, 60, 52, 44, 36,
 128         63, 55, 47, 39, 31, 23, 15,
 129          7, 62, 54, 46, 38, 30, 22,
 130         14,  6, 61, 53, 45, 37, 29,
 131         21, 13,  5, 28, 20, 12,  4
 132 };
 133
 134 const uint8_t pc2_permtab[] ={
 135          7,      6,                                     /* 56 bit -> 48 bit */
 136         14, 17, 11, 24,  1,  5,
 137          3, 28, 15,  6, 21, 10,
 138         23, 19, 12,  4, 26,  8,
 139         16,  7, 27, 20, 13,  2,
 140         41, 52, 31, 37, 47, 55,
 141         30, 40, 51, 45, 33, 48,
 142         44, 49, 39, 56, 34, 53,
 143         46, 42, 50, 36, 29, 32
 144 };
 145
 146 const uint8_t splitin6bitword_permtab[] = {
 147          8,  8,                                         /* 64 bit -> 64 bit */
 148         64, 64,  1,  6,  2,  3,  4,  5,
 149         64, 64,  7, 12,  8,  9, 10, 11,
 150         64, 64, 13, 18, 14, 15, 16, 17,
 151         64, 64, 19, 24, 20, 21, 22, 23,
 152         64, 64, 25, 30, 26, 27, 28, 29,
 153         64, 64, 31, 36, 32, 33, 34, 35,
 154         64, 64, 37, 42, 38, 39, 40, 41,
 155         64, 64, 43, 48, 44, 45, 46, 47
 156 };
 157
 158 const uint8_t shiftkey_permtab[] = {
 159          7,  7,                                         /* 56 bit -> 56 bit */
 160          2,  3,  4,  5,  6,  7,  8,  9,
 161         10, 11, 12, 13, 14, 15, 16, 17,
 162         18, 19, 20, 21, 22, 23, 24, 25,
 163         26, 27, 28,  1,
 164         30, 31, 32, 33, 34, 35, 36, 37,
 165         38, 39, 40, 41, 42, 43, 44, 45,
 166         46, 47, 48, 49, 50, 51, 52, 53,
 167         54, 55, 56, 29
 168 };
 169
 170 const uint8_t shiftkeyinv_permtab[] = {
 171          7,  7,
 172         28,  1,  2,  3,  4,  5,  6,  7,
 173          8,  9, 10, 11, 12, 13, 14, 15,
 174         16, 17, 18, 19, 20, 21, 22, 23,
 175         24, 25, 26, 27,
 176         56, 29, 30, 31, 32, 33, 34, 35,
 177         36, 37, 38, 39, 40, 41, 42, 43,
 178         44, 45, 46, 47, 48, 49, 50, 51,
 179         52, 53, 54, 55
 180 };
 181
 182 /*
 183 1 0
 184 1 0
 185 2 1
 186 2 1
 187 2 1
 188 2 1
 189 2 1
 190 2 1
 191 ----
 192 1 0
 193 2 1
 194 2 1
 195 2 1
 196 2 1
 197 2 1
 198 2 1
 199 1 0
 200 */
 201 #define ROTTABLE      0x7EFC
 202 #define ROTTABLE_INV  0x3F7E
 203 /******************************************************************************/
 204
 205 void permute(const uint8_t *ptable, const uint8_t *in, uint8_t *out){
 206         uint8_t ob; /* in-bytes and out-bytes */
 207         uint8_t byte, bit; /* counter for bit and byte */
 208         ob = ptable[1];
 209         ptable = &(ptable[2]);
 210         for(byte=0; byte<ob; ++byte){
 211                 uint8_t x,t=0;
 212                 for(bit=0; bit<8; ++bit){
 213                         x = *ptable++ - 1;
 214                                 t<<=1;
 215                         if((in[x/8]) & (0x80>>(x%8)) ){
 216                                 t|=0x01;
 217                         }
 218                 }
 219                 out[byte]=t;
 220         }
 221 }
 222
 223 /******************************************************************************/
 224
 225 void changeendian32(uint32_t * a){
 226         *a = (*a & 0x000000FF) << 24 |
 227                  (*a & 0x0000FF00) <<  8 |
 228                  (*a & 0x00FF0000) >>  8 |
 229                  (*a & 0xFF000000) >> 24;
 230 }
 231
 232 /******************************************************************************/
 233 static inline
 234 void shiftkey(uint8_t *key){
 235         uint8_t k[7];
 236         memcpy(k, key, 7);
 237         permute((uint8_t*)shiftkey_permtab, k, key);
 238 }
 239
 240 /******************************************************************************/
 241 static inline
 242 void shiftkey_inv(uint8_t *key){
 243         uint8_t k[7];
 244         memcpy(k, key, 7);
 245         permute((uint8_t*)shiftkeyinv_permtab, k, key);
 246
 247 }
 248
 249 /******************************************************************************/
 250 static inline
 251 uint64_t splitin6bitwords(uint64_t a){
 252         uint64_t ret=0;
 253         a &= 0x0000ffffffffffffLL;
 254         permute((uint8_t*)splitin6bitword_permtab, (uint8_t*)&a, (uint8_t*)&ret);
 255         return ret;
 256 }
 257
 258 /******************************************************************************/
 259
 260 static inline
 261 uint8_t substitute(uint8_t a, uint8_t * sbp){
 262         uint8_t x;
 263         x = sbp[a>>1];
 264         x = (a&1)?x&0x0F:x>>4;
 265         return x;
 266
 267 }
 268
 269 /******************************************************************************/
 270
 271 uint32_t des_f(uint32_t r, uint8_t* kr){
 272         uint8_t i;
 273         uint32_t t=0,ret;
 274         uint64_t data;
 275         uint8_t *sbp; /* sboxpointer */
 276         permute((uint8_t*)e_permtab, (uint8_t*)&r, (uint8_t*)&data);
 277         for(i=0; i<6; ++i)
 278                 ((uint8_t*)&data)[i] ^= kr[i];
 279
 280         /* Sbox substitution */
 281         data = splitin6bitwords(data);
 282         sbp=(uint8_t*)sbox;
 283         for(i=0; i<8; ++i){
 284                 uint8_t x;
 285                 x = substitute(((uint8_t*)&data)[i], sbp);
 286                 t<<=4;
 287                 t |= x;
 288                 sbp += 32;
 289         }
 290         changeendian32(&t);
 291
 292         permute((uint8_t*)p_permtab,(uint8_t*)&t, (uint8_t*)&ret);
 293
 294         return ret;
 295 }
 296
 297 /******************************************************************************/
 298
 299 typedef struct {
 300         union {
 301                 uint8_t  v8[8];
 302                 uint32_t v32[2];
 303         } d;
 304 } data_t;
 305 #define R (data.d.v32[1])
 306 #define L (data.d.v32[0])
 307
 308 void des_enc(void* out, const void* in, const void* key){
 309
 310         uint8_t kr[6], k[7];
 311         uint8_t i;
 312         data_t data;
 313
 314         permute((uint8_t*)ip_permtab, (uint8_t*)in, data.d.v8);
 315         permute((uint8_t*)pc1_permtab, (const uint8_t*)key, k);
 316
 317         for(i=0; i<8; ++i){
 318                 shiftkey(k);
 319                 if(ROTTABLE&((1<<((i<<1)+0))) )
 320                         shiftkey(k);
 321                 permute((uint8_t*)pc2_permtab, k, kr);
 322                 L ^= des_f(R, kr);
 323
 324                 shiftkey(k);
 325                 if(ROTTABLE&((1<<((i<<1)+1))) )
 326                         shiftkey(k);
 327                 permute((uint8_t*)pc2_permtab, k, kr);
 328                 R ^= des_f(L, kr);
 329
 330         }
 331         /* L <-> R*/
 332         R ^= L;
 333         L ^= R;
 334         R ^= L;
 335
 336         permute((uint8_t*)inv_ip_permtab, data.d.v8, (uint8_t*)out);
 337 }
 338
 339 /******************************************************************************/
 340
 341 void des_dec(void* out, const void* in, const uint8_t* key){
 342
 343         uint8_t kr[6],k[7];
 344         int8_t i;
 345         data_t data;
 346
 347         permute((uint8_t*)ip_permtab, (uint8_t*)in, data.d.v8);
 348         permute((uint8_t*)pc1_permtab, (const uint8_t*)key, k);
 349         for(i=7; i>=0; --i){
 350
 351                 permute((uint8_t*)pc2_permtab, k, kr);
 352                 L ^= des_f(R, kr);
 353                 shiftkey_inv(k);
 354                 if(ROTTABLE&((1<<((i<<1)+1))) ){
 355                         shiftkey_inv(k);
 356                 }
 357
 358                 permute((uint8_t*)pc2_permtab, k, kr);
 359                 R ^= des_f(L, kr);
 360                 shiftkey_inv(k);
 361                 if(ROTTABLE&((1<<((i<<1)+0))) ){
 362                         shiftkey_inv(k);
 363                 }
 364
 365         }
 366         /* L <-> R*/
 367         R ^= L;
 368         L ^= R;
 369         R ^= L;
 370
 371         permute((uint8_t*)inv_ip_permtab, data.d.v8, (uint8_t*)out);
 372 }
 373
 374 /******************************************************************************/
 375
 376 void tdes_enc(void* out, void* in, const void* key){
 377         des_enc(out,  in, (uint8_t*)key + 0);
 378         des_dec(out, out, (uint8_t*)key + 8);
 379         des_enc(out, out, (uint8_t*)key +16);
 380 }
 381
 382 /******************************************************************************/
 383
 384 void tdes_dec(void* out, void* in, const uint8_t* key){
 385         des_dec(out,  in, (uint8_t*)key +16);
 386         des_enc(out, out, (uint8_t*)key + 8);
 387         des_dec(out, out, (uint8_t*)key + 0);
 388 }
 389
 390  void tdes_2key_enc(void* out, const void* in, size_t length, const void* key, unsigned char iv[8]){
 391
 392         if( length % 8 ) return;
 393
 394         uint8_t i;
 395         uint8_t* tin = (uint8_t*) in;
 396         uint8_t* tout = (uint8_t*) out;
 397
 398         while( length > 0 )
 399         {
 400                 for( i = 0; i < 8; i++ )
 401                                 tout[i] = (unsigned char)( tin[i] ^ iv[i] );
 402
 403                 des_enc(tout,  tin, (uint8_t*)key + 0);
 404                 des_dec(tout, tout, (uint8_t*)key + 8);
 405                 des_enc(tout, tout, (uint8_t*)key + 0);
 406
 407                 memcpy( iv, tout, 8 );
 408
 409                 tin  += 8;
 410                 tout += 8;
 411                 length -= 8;
 412         }
 413  }
 414
 415  void tdes_2key_dec(void* out, const void* in, size_t length, const void* key, unsigned char iv[8]){
 416
 417         if( length % 8 ) return;
 418
 419         uint8_t i;
 420         unsigned char temp[8];
 421         uint8_t* tin = (uint8_t*) in;
 422         uint8_t* tout = (uint8_t*) out;
 423
 424         while( length > 0 )
 425         {
 426                 memcpy( temp, tin, 8 );
 427
 428                 des_dec(tout,  tin, (uint8_t*)key + 0);
 429                 des_enc(tout, tout, (uint8_t*)key + 8);
 430                 des_dec(tout, tout, (uint8_t*)key + 0);
 431
 432                 for( i = 0; i < 8; i++ )
 433                         tout[i] = (unsigned char)( tout[i] ^ iv[i] );
 434
 435                 memcpy( iv, temp, 8 );
 436
 437                 tin  += 8;
 438                 tout += 8;
 439                 length -= 8;
 440         }
 441  }
 442
 443
 444 /******************************************************************************/
 445
 446