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