wsutil/des.c

   1 /*
   2    Unix SMB/CIFS implementation.
   3
   4    a partial implementation of DES designed for use in the
   5    SMB authentication protocol
   6
   7    Copyright (C) Andrew Tridgell 1998
   8
   9    $Id$
  10
  11    This program is free software; you can redistribute it and/or modify
  12    it under the terms of the GNU General Public License as published by
  13    the Free Software Foundation; either version 2 of the License, or
  14    (at your option) any later version.
  15
  16    This program is distributed in the hope that it will be useful,
  17    but WITHOUT ANY WARRANTY; without even the implied warranty of
  18    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  19    GNU General Public License for more details.
  20
  21    You should have received a copy of the GNU General Public License
  22    along with this program; if not, write to the Free Software
  23    Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA.
  24 */
  25
  26 #include "config.h"
  27 #include <glib.h>
  28
  29 #include "des.h"
  30
  31 /* NOTES:
  32
  33    This code makes no attempt to be fast! In fact, it is a very
  34    slow implementation
  35
  36    This code is NOT a complete DES implementation. It implements only
  37    the minimum necessary for SMB authentication, as used by all SMB
  38    products (including every copy of Microsoft Windows95 ever sold)
  39
  40    In particular, it can only do a unchained forward DES pass. This
  41    means it is not possible to use this code for encryption/decryption
  42    of data, instead it is only useful as a "hash" algorithm.
  43
  44    There is no entry point into this code that allows normal DES operation.
  45
  46    I believe this means that this code does not come under ITAR
  47    regulations but this is NOT a legal opinion. If you are concerned
  48    about the applicability of ITAR regulations to this code then you
  49    should confirm it for yourself (and maybe let me know if you come
  50    up with a different answer to the one above)
  51 */
  52
  53
  54 #define uchar unsigned char
  55
  56 static const uchar perm1[56] = {57, 49, 41, 33, 25, 17,  9,
  57                          1, 58, 50, 42, 34, 26, 18,
  58                         10,  2, 59, 51, 43, 35, 27,
  59                         19, 11,  3, 60, 52, 44, 36,
  60                         63, 55, 47, 39, 31, 23, 15,
  61                          7, 62, 54, 46, 38, 30, 22,
  62                         14,  6, 61, 53, 45, 37, 29,
  63                         21, 13,  5, 28, 20, 12,  4};
  64
  65 static const uchar perm2[48] = {14, 17, 11, 24,  1,  5,
  66                          3, 28, 15,  6, 21, 10,
  67                         23, 19, 12,  4, 26,  8,
  68                         16,  7, 27, 20, 13,  2,
  69                         41, 52, 31, 37, 47, 55,
  70                         30, 40, 51, 45, 33, 48,
  71                         44, 49, 39, 56, 34, 53,
  72                         46, 42, 50, 36, 29, 32};
  73
  74 static const uchar perm3[64] = {58, 50, 42, 34, 26, 18, 10,  2,
  75                         60, 52, 44, 36, 28, 20, 12,  4,
  76                         62, 54, 46, 38, 30, 22, 14,  6,
  77                         64, 56, 48, 40, 32, 24, 16,  8,
  78                         57, 49, 41, 33, 25, 17,  9,  1,
  79                         59, 51, 43, 35, 27, 19, 11,  3,
  80                         61, 53, 45, 37, 29, 21, 13,  5,
  81                         63, 55, 47, 39, 31, 23, 15,  7};
  82
  83 static const uchar perm4[48] = {   32,  1,  2,  3,  4,  5,
  84                             4,  5,  6,  7,  8,  9,
  85                             8,  9, 10, 11, 12, 13,
  86                            12, 13, 14, 15, 16, 17,
  87                            16, 17, 18, 19, 20, 21,
  88                            20, 21, 22, 23, 24, 25,
  89                            24, 25, 26, 27, 28, 29,
  90                            28, 29, 30, 31, 32,  1};
  91
  92 static const uchar perm5[32] = {      16,  7, 20, 21,
  93                               29, 12, 28, 17,
  94                                1, 15, 23, 26,
  95                                5, 18, 31, 10,
  96                                2,  8, 24, 14,
  97                               32, 27,  3,  9,
  98                               19, 13, 30,  6,
  99                               22, 11,  4, 25};
 100
 101
 102 static const uchar perm6[64] ={ 40,  8, 48, 16, 56, 24, 64, 32,
 103                         39,  7, 47, 15, 55, 23, 63, 31,
 104                         38,  6, 46, 14, 54, 22, 62, 30,
 105                         37,  5, 45, 13, 53, 21, 61, 29,
 106                         36,  4, 44, 12, 52, 20, 60, 28,
 107                         35,  3, 43, 11, 51, 19, 59, 27,
 108                         34,  2, 42, 10, 50, 18, 58, 26,
 109                         33,  1, 41,  9, 49, 17, 57, 25};
 110
 111
 112 static const uchar sc[16] = {1, 1, 2, 2, 2, 2, 2, 2, 1, 2, 2, 2, 2, 2, 2, 1};
 113
 114 static const uchar sbox[8][4][16] = {
 115         {{14,  4, 13,  1,  2, 15, 11,  8,  3, 10,  6, 12,  5,  9,  0,  7},
 116          {0, 15,  7,  4, 14,  2, 13,  1, 10,  6, 12, 11,  9,  5,  3,  8},
 117          {4,  1, 14,  8, 13,  6,  2, 11, 15, 12,  9,  7,  3, 10,  5,  0},
 118          {15, 12,  8,  2,  4,  9,  1,  7,  5, 11,  3, 14, 10,  0,  6, 13}},
 119
 120         {{15,  1,  8, 14,  6, 11,  3,  4,  9,  7,  2, 13, 12,  0,  5, 10},
 121          {3, 13,  4,  7, 15,  2,  8, 14, 12,  0,  1, 10,  6,  9, 11,  5},
 122          {0, 14,  7, 11, 10,  4, 13,  1,  5,  8, 12,  6,  9,  3,  2, 15},
 123          {13,  8, 10,  1,  3, 15,  4,  2, 11,  6,  7, 12,  0,  5, 14,  9}},
 124
 125         {{10,  0,  9, 14,  6,  3, 15,  5,  1, 13, 12,  7, 11,  4,  2,  8},
 126          {13,  7,  0,  9,  3,  4,  6, 10,  2,  8,  5, 14, 12, 11, 15,  1},
 127          {13,  6,  4,  9,  8, 15,  3,  0, 11,  1,  2, 12,  5, 10, 14,  7},
 128          {1, 10, 13,  0,  6,  9,  8,  7,  4, 15, 14,  3, 11,  5,  2, 12}},
 129
 130         {{7, 13, 14,  3,  0,  6,  9, 10,  1,  2,  8,  5, 11, 12,  4, 15},
 131          {13,  8, 11,  5,  6, 15,  0,  3,  4,  7,  2, 12,  1, 10, 14,  9},
 132          {10,  6,  9,  0, 12, 11,  7, 13, 15,  1,  3, 14,  5,  2,  8,  4},
 133          {3, 15,  0,  6, 10,  1, 13,  8,  9,  4,  5, 11, 12,  7,  2, 14}},
 134
 135         {{2, 12,  4,  1,  7, 10, 11,  6,  8,  5,  3, 15, 13,  0, 14,  9},
 136          {14, 11,  2, 12,  4,  7, 13,  1,  5,  0, 15, 10,  3,  9,  8,  6},
 137          {4,  2,  1, 11, 10, 13,  7,  8, 15,  9, 12,  5,  6,  3,  0, 14},
 138          {11,  8, 12,  7,  1, 14,  2, 13,  6, 15,  0,  9, 10,  4,  5,  3}},
 139
 140         {{12,  1, 10, 15,  9,  2,  6,  8,  0, 13,  3,  4, 14,  7,  5, 11},
 141          {10, 15,  4,  2,  7, 12,  9,  5,  6,  1, 13, 14,  0, 11,  3,  8},
 142          {9, 14, 15,  5,  2,  8, 12,  3,  7,  0,  4, 10,  1, 13, 11,  6},
 143          {4,  3,  2, 12,  9,  5, 15, 10, 11, 14,  1,  7,  6,  0,  8, 13}},
 144
 145         {{4, 11,  2, 14, 15,  0,  8, 13,  3, 12,  9,  7,  5, 10,  6,  1},
 146          {13,  0, 11,  7,  4,  9,  1, 10, 14,  3,  5, 12,  2, 15,  8,  6},
 147          {1,  4, 11, 13, 12,  3,  7, 14, 10, 15,  6,  8,  0,  5,  9,  2},
 148          {6, 11, 13,  8,  1,  4, 10,  7,  9,  5,  0, 15, 14,  2,  3, 12}},
 149
 150         {{13,  2,  8,  4,  6, 15, 11,  1, 10,  9,  3, 14,  5,  0, 12,  7},
 151          {1, 15, 13,  8, 10,  3,  7,  4, 12,  5,  6, 11,  0, 14,  9,  2},
 152          {7, 11,  4,  1,  9, 12, 14,  2,  0,  6, 10, 13, 15,  3,  5,  8},
 153          {2,  1, 14,  7,  4, 10,  8, 13, 15, 12,  9,  0,  3,  5,  6, 11}}};
 154
 155 static void permute(char *out, const char *in, const uchar *p, int n)
 156 {
 157         int i;
 158         for (i=0;i<n;i++)
 159                 out[i] = in[p[i]-1];
 160 }
 161
 162 static void lshift(char *d, int count, int n)
 163 {
 164         char out[64];
 165         int i;
 166         for (i=0;i<n;i++)
 167                 out[i] = d[(i+count)%n];
 168         for (i=0;i<n;i++)
 169                 d[i] = out[i];
 170 }
 171
 172 static void concat(char *out, char *in1, char *in2, int l1, int l2)
 173 {
 174         while (l1--)
 175                 *out++ = *in1++;
 176         while (l2--)
 177                 *out++ = *in2++;
 178 }
 179
 180 static void exor(char *out, char *in1, char *in2, int n)
 181 {
 182         int i;
 183         for (i=0;i<n;i++)
 184                 out[i] = in1[i] ^ in2[i];
 185 }
 186
 187 static void dohash(char *out, char *in, char *key, int forw)
 188 {
 189         int i, j, k;
 190         char pk1[56];
 191         char c[28];
 192         char d[28];
 193         char cd[56];
 194         char ki[16][48];
 195         char pd1[64];
 196         char l[32], r[32];
 197         char rl[64];
 198
 199         permute(pk1, key, perm1, 56);
 200
 201         for (i=0;i<28;i++)
 202                 c[i] = pk1[i];
 203         for (i=0;i<28;i++)
 204                 d[i] = pk1[i+28];
 205
 206         for (i=0;i<16;i++) {
 207                 lshift(c, sc[i], 28);
 208                 lshift(d, sc[i], 28);
 209
 210                 concat(cd, c, d, 28, 28);
 211                 permute(ki[i], cd, perm2, 48);
 212         }
 213
 214         permute(pd1, in, perm3, 64);
 215
 216         for (j=0;j<32;j++) {
 217                 l[j] = pd1[j];
 218                 r[j] = pd1[j+32];
 219         }
 220
 221         for (i=0;i<16;i++) {
 222                 char er[48];
 223                 char erk[48];
 224                 char b[8][6];
 225                 char cb[32];
 226                 char pcb[32];
 227                 char r2[32];
 228
 229                 permute(er, r, perm4, 48);
 230
 231                 exor(erk, er, ki[forw ? i : 15 - i], 48);
 232
 233                 for (j=0;j<8;j++)
 234                         for (k=0;k<6;k++)
 235                                 b[j][k] = erk[j*6 + k];
 236
 237                 for (j=0;j<8;j++) {
 238                         int m, n;
 239                         m = (b[j][0]<<1) | b[j][5];
 240
 241                         n = (b[j][1]<<3) | (b[j][2]<<2) | (b[j][3]<<1) | b[j][4];
 242
 243                         for (k=0;k<4;k++)
 244                                 b[j][k] = (sbox[j][m][n] & (1<<(3-k)))?1:0;
 245                 }
 246
 247                 for (j=0;j<8;j++)
 248                         for (k=0;k<4;k++)
 249                                 cb[j*4+k] = b[j][k];
 250                 permute(pcb, cb, perm5, 32);
 251
 252                 exor(r2, l, pcb, 32);
 253
 254                 for (j=0;j<32;j++)
 255                         l[j] = r[j];
 256
 257                 for (j=0;j<32;j++)
 258                         r[j] = r2[j];
 259         }
 260
 261         concat(rl, r, l, 32, 32);
 262
 263         permute(out, rl, perm6, 64);
 264 }
 265
 266 static void str_to_key(const unsigned char *str,unsigned char *key)
 267 {
 268         int i;
 269
 270         key[0] = str[0]>>1;
 271         key[1] = ((str[0]&0x01)<<6) | (str[1]>>2);
 272         key[2] = ((str[1]&0x03)<<5) | (str[2]>>3);
 273         key[3] = ((str[2]&0x07)<<4) | (str[3]>>4);
 274         key[4] = ((str[3]&0x0F)<<3) | (str[4]>>5);
 275         key[5] = ((str[4]&0x1F)<<2) | (str[5]>>6);
 276         key[6] = ((str[5]&0x3F)<<1) | (str[6]>>7);
 277         key[7] = str[6]&0x7F;
 278         for (i=0;i<8;i++) {
 279                 key[i] = (key[i]<<1);
 280         }
 281 }
 282
 283
 284 void crypt_des_ecb(unsigned char *out, const unsigned char *in, const unsigned char *key, int forw)
 285 {
 286         int i;
 287         char outb[64];
 288         char inb[64];
 289         char keyb[64];
 290         unsigned char key2[8];
 291
 292         str_to_key(key, key2);
 293
 294         for (i=0;i<64;i++) {
 295                 inb[i] = (in[i/8] & (1<<(7-(i%8)))) ? 1 : 0;
 296                 keyb[i] = (key2[i/8] & (1<<(7-(i%8)))) ? 1 : 0;
 297                 outb[i] = 0;
 298         }
 299
 300         dohash(outb, inb, keyb, forw);
 301
 302         for (i=0;i<8;i++) {
 303                 out[i] = 0;
 304         }
 305
 306         for (i=0;i<64;i++) {
 307                 if (outb[i])
 308                         out[i/8] |= (1<<(7-(i%8)));
 309         }
 310 }
 311