des.c

   1 /* des.c
   2  *
   3  * The des block cipher.
   4  *
   5  */
   6
   7 /* nettle, low-level cryptographics library
   8  *
   9  * Copyright (C) 2001 Niels Möller
  10  *
  11  * The nettle library is free software; you can redistribute it and/or modify
  12  * it under the terms of the GNU Lesser General Public License as published by
  13  * the Free Software Foundation; either version 2.1 of the License, or (at your
  14  * option) any later version.
  15  *
  16  * The nettle library is distributed in the hope that it will be useful, but
  17  * WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY
  18  * or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU Lesser General Public
  19  * License for more details.
  20  *
  21  * You should have received a copy of the GNU Lesser General Public License
  22  * along with the nettle library; see the file COPYING.LIB.  If not, write to
  23  * the Free Software Foundation, Inc., 59 Temple Place - Suite 330, Boston,
  24  * MA 02111-1307, USA.
  25  */
  26
  27 /*      des - fast & portable DES encryption & decryption.
  28  *      Copyright (C) 1992  Dana L. How
  29  *      Please see the file `descore.README' for the complete copyright notice.
  30  */
  31
  32 #if HAVE_CONFIG_H
  33 # include "config.h"
  34 #endif
  35
  36 #include <assert.h>
  37
  38 #include "des.h"
  39
  40 #include "desCode.h"
  41
  42 /* various tables */
  43
  44 static const uint32_t
  45 des_keymap[] = {
  46 #include        "keymap.h"
  47 };
  48
  49 static const uint8_t
  50 rotors[] = {
  51 #include        "rotors.h"
  52 };
  53
  54 static ENCRYPT(DesSmallFipsEncrypt,TEMPSMALL, LOADFIPS,KEYMAPSMALL,SAVEFIPS)
  55 static DECRYPT(DesSmallFipsDecrypt,TEMPSMALL, LOADFIPS,KEYMAPSMALL,SAVEFIPS)
  56
  57 /* If parity bits are used, keys should have odd parity. We use a
  58    small table, to not waste any memory on this fairly obscure DES
  59    feature. */
  60
  61 static const unsigned
  62 parity_16[16] =
  63 { 0, 1, 1, 0, 1, 0, 0, 1, 1, 0, 0, 1, 0, 1, 1, 0 };
  64
  65 #define PARITY(x) (parity_16[(x)&0xf] ^ parity_16[((x)>>4) & 0xf])
  66
  67 int
  68 des_check_parity(unsigned length, const uint8_t *key)
  69 {
  70   unsigned i;
  71   for (i = 0; i<length; i++)
  72     if (!PARITY(key[i]))
  73       return 0;
  74
  75   return 1;
  76 }
  77
  78 void
  79 des_fix_parity(unsigned length, uint8_t *dst,
  80                const uint8_t *src)
  81 {
  82   unsigned i;
  83   for (i = 0; i<length; i++)
  84     dst[i] = src[i] ^ PARITY(src[i]) ^ 1;
  85 }
  86
  87 /* Weak and semiweak keys, excluding parity:
  88  *
  89  * 00 00 00 00  00 00 00 00
  90  * 7f 7f 7f 7f  7f 7f 7f 7f
  91  * 0f 0f 0f 0f  07 07 07 07
  92  * 70 70 70 70  78 78 78 78
  93  *
  94  * 00 7f 00 7f  00 7f 00 7f
  95  * 7f 00 7f 00  7f 00 7f 00
  96  *
  97  * 0f 70 0f 70  07 78 07 78
  98  * 70 0f 70 0f  78 07 78 07
  99  *
 100  * 00 70 00 70  00 78 00 78
 101  * 70 00 70 00  78 00 78 00
 102  *
 103  * 0f 7f 0f 7f  07 7f 07 7f
 104  * 7f 0f 7f 0f  7f 07 7f 07
 105  *
 106  * 00 0f 00 0f  00 07 00 07
 107  * 0f 00 0f 00  07 00 07 00
 108  *
 109  * 70 7f 70 7f  78 7f 78 7f
 110  * 7f 70 7f 70  7f 78 7f 78
 111  */
 112
 113 static int
 114 des_weak_p(const uint8_t *key)
 115 {
 116   /* Hash function generated using gperf. */
 117   static const unsigned char asso_values[0x81] =
 118     {
 119       16,  9, 26, 26, 26, 26, 26, 26, 26, 26,
 120       26, 26, 26, 26, 26,  6,  2, 26, 26, 26,
 121       26, 26, 26, 26, 26, 26, 26, 26, 26, 26,
 122       26, 26, 26, 26, 26, 26, 26, 26, 26, 26,
 123       26, 26, 26, 26, 26, 26, 26, 26, 26, 26,
 124       26, 26, 26, 26, 26, 26, 26, 26, 26, 26,
 125       26, 26, 26, 26, 26, 26, 26, 26, 26, 26,
 126       26, 26, 26, 26, 26, 26, 26, 26, 26, 26,
 127       26, 26, 26, 26, 26, 26, 26, 26, 26, 26,
 128       26, 26, 26, 26, 26, 26, 26, 26, 26, 26,
 129       26, 26, 26, 26, 26, 26, 26, 26, 26, 26,
 130       26, 26,  3,  1, 26, 26, 26, 26, 26, 26,
 131       26, 26, 26, 26, 26, 26, 26,  0,  0
 132     };
 133
 134   static const int8_t weak_key_hash[26][4] =
 135     {
 136       /*  0 */ {0x7f,0x7f, 0x7f,0x7f},
 137       /*  1 */ {0x7f,0x70, 0x7f,0x78},
 138       /*  2 */ {0x7f,0x0f, 0x7f,0x07},
 139       /*  3 */ {0x70,0x7f, 0x78,0x7f},
 140       /*  4 */ {0x70,0x70, 0x78,0x78},
 141       /*  5 */ {0x70,0x0f, 0x78,0x07},
 142       /*  6 */ {0x0f,0x7f, 0x07,0x7f},
 143       /*  7 */ {0x0f,0x70, 0x07,0x78},
 144       /*  8 */ {0x0f,0x0f, 0x07,0x07},
 145       /*  9 */ {0x7f,0x00, 0x7f,0x00},
 146       /* 10 */ {-1,-1,-1,-1},
 147       /* 11 */ {-1,-1,-1,-1},
 148       /* 12 */ {0x70,0x00, 0x78,0x00},
 149       /* 13 */ {-1,-1,-1,-1},
 150       /* 14 */ {-1,-1,-1,-1},
 151       /* 15 */ {0x0f,0x00, 0x07,0x00},
 152       /* 16 */ {0x00,0x7f, 0x00,0x7f},
 153       /* 17 */ {0x00,0x70, 0x00,0x78},
 154       /* 18 */ {0x00,0x0f, 0x00,0x07},
 155       /* 19 */ {-1,-1,-1,-1},
 156       /* 20 */ {-1,-1,-1,-1},
 157       /* 21 */ {-1,-1,-1,-1},
 158       /* 22 */ {-1,-1,-1,-1},
 159       /* 23 */ {-1,-1,-1,-1},
 160       /* 24 */ {-1,-1,-1,-1},
 161       /* 25 */ {0x00,0x00, 0x00,0x00}
 162     };
 163
 164   int8_t k0 = key[0] >> 1;
 165   int8_t k1 = key[1] >> 1;
 166
 167   unsigned hash = asso_values[k1 + 1] + asso_values[k0];
 168   const int8_t *candidate = weak_key_hash[hash];
 169
 170   if (hash > 25)
 171     return 0;
 172   if (k0 != candidate[0]
 173       || k1 != candidate[1])
 174     return 0;
 175
 176   if ( (key[2] >> 1) != k0
 177        || (key[3] >> 1) != k1)
 178     return 0;
 179
 180   k0 = key[4] >> 1;
 181   k1 = key[5] >> 1;
 182   if (k0 != candidate[2]
 183       || k1 != candidate[3])
 184     return 0;
 185   if ( (key[6] >> 1) != k0
 186        || (key[7] >> 1) != k1)
 187     return 0;
 188
 189   return 1;
 190 }
 191
 192 int
 193 des_set_key(struct des_ctx *ctx, const uint8_t *key)
 194 {
 195   register uint32_t n, w;
 196   register char * b0, * b1;
 197   char bits0[56], bits1[56];
 198   uint32_t *method;
 199   const uint8_t *k;
 200
 201   /* explode the bits */
 202   n = 56;
 203   b0 = bits0;
 204   b1 = bits1;
 205   k = key;
 206   do {
 207     w = (256 | *k++) << 2;
 208     do {
 209       --n;
 210       b1[n] = 8 & w;
 211       w >>= 1;
 212       b0[n] = 4 & w;
 213     } while ( w >= 16 );
 214   } while ( n );
 215
 216   /* put the bits in the correct places */
 217   n = 16;
 218   k = rotors;
 219   method = ctx->key;
 220
 221   do {
 222     w   = (b1[k[ 0   ]] | b0[k[ 1   ]]) << 4;
 223     w  |= (b1[k[ 2   ]] | b0[k[ 3   ]]) << 2;
 224     w  |=  b1[k[ 4   ]] | b0[k[ 5   ]];
 225     w <<= 8;
 226     w  |= (b1[k[ 6   ]] | b0[k[ 7   ]]) << 4;
 227     w  |= (b1[k[ 8   ]] | b0[k[ 9   ]]) << 2;
 228     w  |=  b1[k[10   ]] | b0[k[11   ]];
 229     w <<= 8;
 230     w  |= (b1[k[12   ]] | b0[k[13   ]]) << 4;
 231     w  |= (b1[k[14   ]] | b0[k[15   ]]) << 2;
 232     w  |=  b1[k[16   ]] | b0[k[17   ]];
 233     w <<= 8;
 234     w  |= (b1[k[18   ]] | b0[k[19   ]]) << 4;
 235     w  |= (b1[k[20   ]] | b0[k[21   ]]) << 2;
 236     w  |=  b1[k[22   ]] | b0[k[23   ]];
 237
 238     method[0] = w;
 239
 240     w   = (b1[k[ 0+24]] | b0[k[ 1+24]]) << 4;
 241     w  |= (b1[k[ 2+24]] | b0[k[ 3+24]]) << 2;
 242     w  |=  b1[k[ 4+24]] | b0[k[ 5+24]];
 243     w <<= 8;
 244     w  |= (b1[k[ 6+24]] | b0[k[ 7+24]]) << 4;
 245     w  |= (b1[k[ 8+24]] | b0[k[ 9+24]]) << 2;
 246     w  |=  b1[k[10+24]] | b0[k[11+24]];
 247     w <<= 8;
 248     w  |= (b1[k[12+24]] | b0[k[13+24]]) << 4;
 249     w  |= (b1[k[14+24]] | b0[k[15+24]]) << 2;
 250     w  |=  b1[k[16+24]] | b0[k[17+24]];
 251     w <<= 8;
 252     w  |= (b1[k[18+24]] | b0[k[19+24]]) << 4;
 253     w  |= (b1[k[20+24]] | b0[k[21+24]]) << 2;
 254     w  |=  b1[k[22+24]] | b0[k[23+24]];
 255
 256     ROR(w, 4, 28);              /* could be eliminated */
 257     method[1] = w;
 258
 259     k   += 48;
 260     method      += 2;
 261   } while ( --n );
 262
 263   return !des_weak_p (key);
 264 }
 265
 266 void
 267 des_encrypt(const struct des_ctx *ctx,
 268             unsigned length, uint8_t *dst,
 269             const uint8_t *src)
 270 {
 271   assert(!(length % DES_BLOCK_SIZE));
 272
 273   while (length)
 274     {
 275       DesSmallFipsEncrypt(dst, ctx->key, src);
 276       length -= DES_BLOCK_SIZE;
 277       src += DES_BLOCK_SIZE;
 278       dst += DES_BLOCK_SIZE;
 279     }
 280 }
 281
 282 void
 283 des_decrypt(const struct des_ctx *ctx,
 284             unsigned length, uint8_t *dst,
 285             const uint8_t *src)
 286 {
 287   assert(!(length % DES_BLOCK_SIZE));
 288
 289   while (length)
 290     {
 291       DesSmallFipsDecrypt(dst, ctx->key, src);
 292       length -= DES_BLOCK_SIZE;
 293       src += DES_BLOCK_SIZE;
 294       dst += DES_BLOCK_SIZE;
 295     }
 296 }