crypto/des/set_key.c

   1 /*
   2  * Copyright 1995-2016 The OpenSSL Project Authors. All Rights Reserved.
   3  *
   4  * Licensed under the OpenSSL license (the "License").  You may not use
   5  * this file except in compliance with the License.  You can obtain a copy
   6  * in the file LICENSE in the source distribution or at
   7  * https://www.openssl.org/source/license.html
   8  */
   9
  10 /*-
  11  * set_key.c v 1.4 eay 24/9/91
  12  * 1.4 Speed up by 400% :-)
  13  * 1.3 added register declarations.
  14  * 1.2 unrolled make_key_sched a bit more
  15  * 1.1 added norm_expand_bits
  16  * 1.0 First working version
  17  */
  18 #include <openssl/crypto.h>
  19 #include "des_locl.h"
  20
  21 /* defaults to false */
  22 OPENSSL_IMPLEMENT_GLOBAL(int, DES_check_key, 0)
  23
  24 static const unsigned char odd_parity[256] = {
  25     1, 1, 2, 2, 4, 4, 7, 7, 8, 8, 11, 11, 13, 13, 14, 14,
  26     16, 16, 19, 19, 21, 21, 22, 22, 25, 25, 26, 26, 28, 28, 31, 31,
  27     32, 32, 35, 35, 37, 37, 38, 38, 41, 41, 42, 42, 44, 44, 47, 47,
  28     49, 49, 50, 50, 52, 52, 55, 55, 56, 56, 59, 59, 61, 61, 62, 62,
  29     64, 64, 67, 67, 69, 69, 70, 70, 73, 73, 74, 74, 76, 76, 79, 79,
  30     81, 81, 82, 82, 84, 84, 87, 87, 88, 88, 91, 91, 93, 93, 94, 94,
  31     97, 97, 98, 98, 100, 100, 103, 103, 104, 104, 107, 107, 109, 109, 110,
  32     110,
  33     112, 112, 115, 115, 117, 117, 118, 118, 121, 121, 122, 122, 124, 124, 127,
  34     127,
  35     128, 128, 131, 131, 133, 133, 134, 134, 137, 137, 138, 138, 140, 140, 143,
  36     143,
  37     145, 145, 146, 146, 148, 148, 151, 151, 152, 152, 155, 155, 157, 157, 158,
  38     158,
  39     161, 161, 162, 162, 164, 164, 167, 167, 168, 168, 171, 171, 173, 173, 174,
  40     174,
  41     176, 176, 179, 179, 181, 181, 182, 182, 185, 185, 186, 186, 188, 188, 191,
  42     191,
  43     193, 193, 194, 194, 196, 196, 199, 199, 200, 200, 203, 203, 205, 205, 206,
  44     206,
  45     208, 208, 211, 211, 213, 213, 214, 214, 217, 217, 218, 218, 220, 220, 223,
  46     223,
  47     224, 224, 227, 227, 229, 229, 230, 230, 233, 233, 234, 234, 236, 236, 239,
  48     239,
  49     241, 241, 242, 242, 244, 244, 247, 247, 248, 248, 251, 251, 253, 253, 254,
  50     254
  51 };
  52
  53 void DES_set_odd_parity(DES_cblock *key)
  54 {
  55     unsigned int i;
  56
  57     for (i = 0; i < DES_KEY_SZ; i++)
  58         (*key)[i] = odd_parity[(*key)[i]];
  59 }
  60
  61 int DES_check_key_parity(const_DES_cblock *key)
  62 {
  63     unsigned int i;
  64
  65     for (i = 0; i < DES_KEY_SZ; i++) {
  66         if ((*key)[i] != odd_parity[(*key)[i]])
  67             return 0;
  68     }
  69     return 1;
  70 }
  71
  72 /*-
  73  * Weak and semi weak keys as taken from
  74  * %A D.W. Davies
  75  * %A W.L. Price
  76  * %T Security for Computer Networks
  77  * %I John Wiley & Sons
  78  * %D 1984
  79  */
  80 #define NUM_WEAK_KEY    16
  81 static const DES_cblock weak_keys[NUM_WEAK_KEY] = {
  82     /* weak keys */
  83     {0x01, 0x01, 0x01, 0x01, 0x01, 0x01, 0x01, 0x01},
  84     {0xFE, 0xFE, 0xFE, 0xFE, 0xFE, 0xFE, 0xFE, 0xFE},
  85     {0x1F, 0x1F, 0x1F, 0x1F, 0x0E, 0x0E, 0x0E, 0x0E},
  86     {0xE0, 0xE0, 0xE0, 0xE0, 0xF1, 0xF1, 0xF1, 0xF1},
  87     /* semi-weak keys */
  88     {0x01, 0xFE, 0x01, 0xFE, 0x01, 0xFE, 0x01, 0xFE},
  89     {0xFE, 0x01, 0xFE, 0x01, 0xFE, 0x01, 0xFE, 0x01},
  90     {0x1F, 0xE0, 0x1F, 0xE0, 0x0E, 0xF1, 0x0E, 0xF1},
  91     {0xE0, 0x1F, 0xE0, 0x1F, 0xF1, 0x0E, 0xF1, 0x0E},
  92     {0x01, 0xE0, 0x01, 0xE0, 0x01, 0xF1, 0x01, 0xF1},
  93     {0xE0, 0x01, 0xE0, 0x01, 0xF1, 0x01, 0xF1, 0x01},
  94     {0x1F, 0xFE, 0x1F, 0xFE, 0x0E, 0xFE, 0x0E, 0xFE},
  95     {0xFE, 0x1F, 0xFE, 0x1F, 0xFE, 0x0E, 0xFE, 0x0E},
  96     {0x01, 0x1F, 0x01, 0x1F, 0x01, 0x0E, 0x01, 0x0E},
  97     {0x1F, 0x01, 0x1F, 0x01, 0x0E, 0x01, 0x0E, 0x01},
  98     {0xE0, 0xFE, 0xE0, 0xFE, 0xF1, 0xFE, 0xF1, 0xFE},
  99     {0xFE, 0xE0, 0xFE, 0xE0, 0xFE, 0xF1, 0xFE, 0xF1}
 100 };
 101
 102 int DES_is_weak_key(const_DES_cblock *key)
 103 {
 104     int i;
 105
 106     for (i = 0; i < NUM_WEAK_KEY; i++)
 107         if (memcmp(weak_keys[i], key, sizeof(DES_cblock)) == 0)
 108             return 1;
 109     return 0;
 110 }
 111
 112 /*-
 113  * NOW DEFINED IN des_local.h
 114  * See ecb_encrypt.c for a pseudo description of these macros.
 115  * #define PERM_OP(a,b,t,n,m) ((t)=((((a)>>(n))^(b))&(m)),\
 116  *      (b)^=(t),\
 117  *      (a)=((a)^((t)<<(n))))
 118  */
 119
 120 #define HPERM_OP(a,t,n,m) ((t)=((((a)<<(16-(n)))^(a))&(m)),\
 121         (a)=(a)^(t)^(t>>(16-(n))))
 122
 123 static const DES_LONG des_skb[8][64] = {
 124     {
 125      /* for C bits (numbered as per FIPS 46) 1 2 3 4 5 6 */
 126      0x00000000L, 0x00000010L, 0x20000000L, 0x20000010L,
 127      0x00010000L, 0x00010010L, 0x20010000L, 0x20010010L,
 128      0x00000800L, 0x00000810L, 0x20000800L, 0x20000810L,
 129      0x00010800L, 0x00010810L, 0x20010800L, 0x20010810L,
 130      0x00000020L, 0x00000030L, 0x20000020L, 0x20000030L,
 131      0x00010020L, 0x00010030L, 0x20010020L, 0x20010030L,
 132      0x00000820L, 0x00000830L, 0x20000820L, 0x20000830L,
 133      0x00010820L, 0x00010830L, 0x20010820L, 0x20010830L,
 134      0x00080000L, 0x00080010L, 0x20080000L, 0x20080010L,
 135      0x00090000L, 0x00090010L, 0x20090000L, 0x20090010L,
 136      0x00080800L, 0x00080810L, 0x20080800L, 0x20080810L,
 137      0x00090800L, 0x00090810L, 0x20090800L, 0x20090810L,
 138      0x00080020L, 0x00080030L, 0x20080020L, 0x20080030L,
 139      0x00090020L, 0x00090030L, 0x20090020L, 0x20090030L,
 140      0x00080820L, 0x00080830L, 0x20080820L, 0x20080830L,
 141      0x00090820L, 0x00090830L, 0x20090820L, 0x20090830L,
 142      },
 143     {
 144      /* for C bits (numbered as per FIPS 46) 7 8 10 11 12 13 */
 145      0x00000000L, 0x02000000L, 0x00002000L, 0x02002000L,
 146      0x00200000L, 0x02200000L, 0x00202000L, 0x02202000L,
 147      0x00000004L, 0x02000004L, 0x00002004L, 0x02002004L,
 148      0x00200004L, 0x02200004L, 0x00202004L, 0x02202004L,
 149      0x00000400L, 0x02000400L, 0x00002400L, 0x02002400L,
 150      0x00200400L, 0x02200400L, 0x00202400L, 0x02202400L,
 151      0x00000404L, 0x02000404L, 0x00002404L, 0x02002404L,
 152      0x00200404L, 0x02200404L, 0x00202404L, 0x02202404L,
 153      0x10000000L, 0x12000000L, 0x10002000L, 0x12002000L,
 154      0x10200000L, 0x12200000L, 0x10202000L, 0x12202000L,
 155      0x10000004L, 0x12000004L, 0x10002004L, 0x12002004L,
 156      0x10200004L, 0x12200004L, 0x10202004L, 0x12202004L,
 157      0x10000400L, 0x12000400L, 0x10002400L, 0x12002400L,
 158      0x10200400L, 0x12200400L, 0x10202400L, 0x12202400L,
 159      0x10000404L, 0x12000404L, 0x10002404L, 0x12002404L,
 160      0x10200404L, 0x12200404L, 0x10202404L, 0x12202404L,
 161      },
 162     {
 163      /* for C bits (numbered as per FIPS 46) 14 15 16 17 19 20 */
 164      0x00000000L, 0x00000001L, 0x00040000L, 0x00040001L,
 165      0x01000000L, 0x01000001L, 0x01040000L, 0x01040001L,
 166      0x00000002L, 0x00000003L, 0x00040002L, 0x00040003L,
 167      0x01000002L, 0x01000003L, 0x01040002L, 0x01040003L,
 168      0x00000200L, 0x00000201L, 0x00040200L, 0x00040201L,
 169      0x01000200L, 0x01000201L, 0x01040200L, 0x01040201L,
 170      0x00000202L, 0x00000203L, 0x00040202L, 0x00040203L,
 171      0x01000202L, 0x01000203L, 0x01040202L, 0x01040203L,
 172      0x08000000L, 0x08000001L, 0x08040000L, 0x08040001L,
 173      0x09000000L, 0x09000001L, 0x09040000L, 0x09040001L,
 174      0x08000002L, 0x08000003L, 0x08040002L, 0x08040003L,
 175      0x09000002L, 0x09000003L, 0x09040002L, 0x09040003L,
 176      0x08000200L, 0x08000201L, 0x08040200L, 0x08040201L,
 177      0x09000200L, 0x09000201L, 0x09040200L, 0x09040201L,
 178      0x08000202L, 0x08000203L, 0x08040202L, 0x08040203L,
 179      0x09000202L, 0x09000203L, 0x09040202L, 0x09040203L,
 180      },
 181     {
 182      /* for C bits (numbered as per FIPS 46) 21 23 24 26 27 28 */
 183      0x00000000L, 0x00100000L, 0x00000100L, 0x00100100L,
 184      0x00000008L, 0x00100008L, 0x00000108L, 0x00100108L,
 185      0x00001000L, 0x00101000L, 0x00001100L, 0x00101100L,
 186      0x00001008L, 0x00101008L, 0x00001108L, 0x00101108L,
 187      0x04000000L, 0x04100000L, 0x04000100L, 0x04100100L,
 188      0x04000008L, 0x04100008L, 0x04000108L, 0x04100108L,
 189      0x04001000L, 0x04101000L, 0x04001100L, 0x04101100L,
 190      0x04001008L, 0x04101008L, 0x04001108L, 0x04101108L,
 191      0x00020000L, 0x00120000L, 0x00020100L, 0x00120100L,
 192      0x00020008L, 0x00120008L, 0x00020108L, 0x00120108L,
 193      0x00021000L, 0x00121000L, 0x00021100L, 0x00121100L,
 194      0x00021008L, 0x00121008L, 0x00021108L, 0x00121108L,
 195      0x04020000L, 0x04120000L, 0x04020100L, 0x04120100L,
 196      0x04020008L, 0x04120008L, 0x04020108L, 0x04120108L,
 197      0x04021000L, 0x04121000L, 0x04021100L, 0x04121100L,
 198      0x04021008L, 0x04121008L, 0x04021108L, 0x04121108L,
 199      },
 200     {
 201      /* for D bits (numbered as per FIPS 46) 1 2 3 4 5 6 */
 202      0x00000000L, 0x10000000L, 0x00010000L, 0x10010000L,
 203      0x00000004L, 0x10000004L, 0x00010004L, 0x10010004L,
 204      0x20000000L, 0x30000000L, 0x20010000L, 0x30010000L,
 205      0x20000004L, 0x30000004L, 0x20010004L, 0x30010004L,
 206      0x00100000L, 0x10100000L, 0x00110000L, 0x10110000L,
 207      0x00100004L, 0x10100004L, 0x00110004L, 0x10110004L,
 208      0x20100000L, 0x30100000L, 0x20110000L, 0x30110000L,
 209      0x20100004L, 0x30100004L, 0x20110004L, 0x30110004L,
 210      0x00001000L, 0x10001000L, 0x00011000L, 0x10011000L,
 211      0x00001004L, 0x10001004L, 0x00011004L, 0x10011004L,
 212      0x20001000L, 0x30001000L, 0x20011000L, 0x30011000L,
 213      0x20001004L, 0x30001004L, 0x20011004L, 0x30011004L,
 214      0x00101000L, 0x10101000L, 0x00111000L, 0x10111000L,
 215      0x00101004L, 0x10101004L, 0x00111004L, 0x10111004L,
 216      0x20101000L, 0x30101000L, 0x20111000L, 0x30111000L,
 217      0x20101004L, 0x30101004L, 0x20111004L, 0x30111004L,
 218      },
 219     {
 220      /* for D bits (numbered as per FIPS 46) 8 9 11 12 13 14 */
 221      0x00000000L, 0x08000000L, 0x00000008L, 0x08000008L,
 222      0x00000400L, 0x08000400L, 0x00000408L, 0x08000408L,
 223      0x00020000L, 0x08020000L, 0x00020008L, 0x08020008L,
 224      0x00020400L, 0x08020400L, 0x00020408L, 0x08020408L,
 225      0x00000001L, 0x08000001L, 0x00000009L, 0x08000009L,
 226      0x00000401L, 0x08000401L, 0x00000409L, 0x08000409L,
 227      0x00020001L, 0x08020001L, 0x00020009L, 0x08020009L,
 228      0x00020401L, 0x08020401L, 0x00020409L, 0x08020409L,
 229      0x02000000L, 0x0A000000L, 0x02000008L, 0x0A000008L,
 230      0x02000400L, 0x0A000400L, 0x02000408L, 0x0A000408L,
 231      0x02020000L, 0x0A020000L, 0x02020008L, 0x0A020008L,
 232      0x02020400L, 0x0A020400L, 0x02020408L, 0x0A020408L,
 233      0x02000001L, 0x0A000001L, 0x02000009L, 0x0A000009L,
 234      0x02000401L, 0x0A000401L, 0x02000409L, 0x0A000409L,
 235      0x02020001L, 0x0A020001L, 0x02020009L, 0x0A020009L,
 236      0x02020401L, 0x0A020401L, 0x02020409L, 0x0A020409L,
 237      },
 238     {
 239      /* for D bits (numbered as per FIPS 46) 16 17 18 19 20 21 */
 240      0x00000000L, 0x00000100L, 0x00080000L, 0x00080100L,
 241      0x01000000L, 0x01000100L, 0x01080000L, 0x01080100L,
 242      0x00000010L, 0x00000110L, 0x00080010L, 0x00080110L,
 243      0x01000010L, 0x01000110L, 0x01080010L, 0x01080110L,
 244      0x00200000L, 0x00200100L, 0x00280000L, 0x00280100L,
 245      0x01200000L, 0x01200100L, 0x01280000L, 0x01280100L,
 246      0x00200010L, 0x00200110L, 0x00280010L, 0x00280110L,
 247      0x01200010L, 0x01200110L, 0x01280010L, 0x01280110L,
 248      0x00000200L, 0x00000300L, 0x00080200L, 0x00080300L,
 249      0x01000200L, 0x01000300L, 0x01080200L, 0x01080300L,
 250      0x00000210L, 0x00000310L, 0x00080210L, 0x00080310L,
 251      0x01000210L, 0x01000310L, 0x01080210L, 0x01080310L,
 252      0x00200200L, 0x00200300L, 0x00280200L, 0x00280300L,
 253      0x01200200L, 0x01200300L, 0x01280200L, 0x01280300L,
 254      0x00200210L, 0x00200310L, 0x00280210L, 0x00280310L,
 255      0x01200210L, 0x01200310L, 0x01280210L, 0x01280310L,
 256      },
 257     {
 258      /* for D bits (numbered as per FIPS 46) 22 23 24 25 27 28 */
 259      0x00000000L, 0x04000000L, 0x00040000L, 0x04040000L,
 260      0x00000002L, 0x04000002L, 0x00040002L, 0x04040002L,
 261      0x00002000L, 0x04002000L, 0x00042000L, 0x04042000L,
 262      0x00002002L, 0x04002002L, 0x00042002L, 0x04042002L,
 263      0x00000020L, 0x04000020L, 0x00040020L, 0x04040020L,
 264      0x00000022L, 0x04000022L, 0x00040022L, 0x04040022L,
 265      0x00002020L, 0x04002020L, 0x00042020L, 0x04042020L,
 266      0x00002022L, 0x04002022L, 0x00042022L, 0x04042022L,
 267      0x00000800L, 0x04000800L, 0x00040800L, 0x04040800L,
 268      0x00000802L, 0x04000802L, 0x00040802L, 0x04040802L,
 269      0x00002800L, 0x04002800L, 0x00042800L, 0x04042800L,
 270      0x00002802L, 0x04002802L, 0x00042802L, 0x04042802L,
 271      0x00000820L, 0x04000820L, 0x00040820L, 0x04040820L,
 272      0x00000822L, 0x04000822L, 0x00040822L, 0x04040822L,
 273      0x00002820L, 0x04002820L, 0x00042820L, 0x04042820L,
 274      0x00002822L, 0x04002822L, 0x00042822L, 0x04042822L,
 275      }
 276 };
 277
 278 int DES_set_key(const_DES_cblock *key, DES_key_schedule *schedule)
 279 {
 280     if (DES_check_key) {
 281         return DES_set_key_checked(key, schedule);
 282     } else {
 283         DES_set_key_unchecked(key, schedule);
 284         return 0;
 285     }
 286 }
 287
 288 /*-
 289  * return 0 if key parity is odd (correct),
 290  * return -1 if key parity error,
 291  * return -2 if illegal weak key.
 292  */
 293 int DES_set_key_checked(const_DES_cblock *key, DES_key_schedule *schedule)
 294 {
 295     if (!DES_check_key_parity(key))
 296         return -1;
 297     if (DES_is_weak_key(key))
 298         return -2;
 299     DES_set_key_unchecked(key, schedule);
 300     return 0;
 301 }
 302
 303 void DES_set_key_unchecked(const_DES_cblock *key, DES_key_schedule *schedule)
 304 {
 305     static const int shifts2[16] =
 306         { 0, 0, 1, 1, 1, 1, 1, 1, 0, 1, 1, 1, 1, 1, 1, 0 };
 307     register DES_LONG c, d, t, s, t2;
 308     register const unsigned char *in;
 309     register DES_LONG *k;
 310     register int i;
 311
 312 #ifdef OPENBSD_DEV_CRYPTO
 313     memcpy(schedule->key, key, sizeof(schedule->key));
 314     schedule->session = NULL;
 315 #endif
 316     k = &schedule->ks->deslong[0];
 317     in = &(*key)[0];
 318
 319     c2l(in, c);
 320     c2l(in, d);
 321
 322     /*
 323      * do PC1 in 47 simple operations. Thanks to John Fletcher
 324      * for the inspiration.
 325      */
 326     PERM_OP(d, c, t, 4, 0x0f0f0f0fL);
 327     HPERM_OP(c, t, -2, 0xcccc0000L);
 328     HPERM_OP(d, t, -2, 0xcccc0000L);
 329     PERM_OP(d, c, t, 1, 0x55555555L);
 330     PERM_OP(c, d, t, 8, 0x00ff00ffL);
 331     PERM_OP(d, c, t, 1, 0x55555555L);
 332     d = (((d & 0x000000ffL) << 16L) | (d & 0x0000ff00L) |
 333          ((d & 0x00ff0000L) >> 16L) | ((c & 0xf0000000L) >> 4L));
 334     c &= 0x0fffffffL;
 335
 336     for (i = 0; i < ITERATIONS; i++) {
 337         if (shifts2[i]) {
 338             c = ((c >> 2L) | (c << 26L));
 339             d = ((d >> 2L) | (d << 26L));
 340         } else {
 341             c = ((c >> 1L) | (c << 27L));
 342             d = ((d >> 1L) | (d << 27L));
 343         }
 344         c &= 0x0fffffffL;
 345         d &= 0x0fffffffL;
 346         /*
 347          * could be a few less shifts but I am to lazy at this point in time
 348          * to investigate
 349          */
 350         s = des_skb[0][(c) & 0x3f] |
 351             des_skb[1][((c >> 6L) & 0x03) | ((c >> 7L) & 0x3c)] |
 352             des_skb[2][((c >> 13L) & 0x0f) | ((c >> 14L) & 0x30)] |
 353             des_skb[3][((c >> 20L) & 0x01) | ((c >> 21L) & 0x06) |
 354                        ((c >> 22L) & 0x38)];
 355         t = des_skb[4][(d) & 0x3f] |
 356             des_skb[5][((d >> 7L) & 0x03) | ((d >> 8L) & 0x3c)] |
 357             des_skb[6][(d >> 15L) & 0x3f] |
 358             des_skb[7][((d >> 21L) & 0x0f) | ((d >> 22L) & 0x30)];
 359
 360         /* table contained 0213 4657 */
 361         t2 = ((t << 16L) | (s & 0x0000ffffL)) & 0xffffffffL;
 362         *(k++) = ROTATE(t2, 30) & 0xffffffffL;
 363
 364         t2 = ((s >> 16L) | (t & 0xffff0000L));
 365         *(k++) = ROTATE(t2, 26) & 0xffffffffL;
 366     }
 367 }
 368
 369 int DES_key_sched(const_DES_cblock *key, DES_key_schedule *schedule)
 370 {
 371     return DES_set_key(key, schedule);
 372 }