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 "libradius.h"
  47 #include <string.h>
  48 #include <ctype.h>
  49
  50
  51 #define uchar unsigned char
  52
  53 static const uchar perm1[56] = {57, 49, 41, 33, 25, 17,  9,
  54                          1, 58, 50, 42, 34, 26, 18,
  55                         10,  2, 59, 51, 43, 35, 27,
  56                         19, 11,  3, 60, 52, 44, 36,
  57                         63, 55, 47, 39, 31, 23, 15,
  58                          7, 62, 54, 46, 38, 30, 22,
  59                         14,  6, 61, 53, 45, 37, 29,
  60                         21, 13,  5, 28, 20, 12,  4};
  61
  62 static const uchar perm2[48] = {14, 17, 11, 24,  1,  5,
  63                          3, 28, 15,  6, 21, 10,
  64                         23, 19, 12,  4, 26,  8,
  65                         16,  7, 27, 20, 13,  2,
  66                         41, 52, 31, 37, 47, 55,
  67                         30, 40, 51, 45, 33, 48,
  68                         44, 49, 39, 56, 34, 53,
  69                         46, 42, 50, 36, 29, 32};
  70
  71 static const uchar perm3[64] = {58, 50, 42, 34, 26, 18, 10,  2,
  72                         60, 52, 44, 36, 28, 20, 12,  4,
  73                         62, 54, 46, 38, 30, 22, 14,  6,
  74                         64, 56, 48, 40, 32, 24, 16,  8,
  75                         57, 49, 41, 33, 25, 17,  9,  1,
  76                         59, 51, 43, 35, 27, 19, 11,  3,
  77                         61, 53, 45, 37, 29, 21, 13,  5,
  78                         63, 55, 47, 39, 31, 23, 15,  7};
  79
  80 static const uchar perm4[48] = {   32,  1,  2,  3,  4,  5,
  81                             4,  5,  6,  7,  8,  9,
  82                             8,  9, 10, 11, 12, 13,
  83                            12, 13, 14, 15, 16, 17,
  84                            16, 17, 18, 19, 20, 21,
  85                            20, 21, 22, 23, 24, 25,
  86                            24, 25, 26, 27, 28, 29,
  87                            28, 29, 30, 31, 32,  1};
  88
  89 static const uchar perm5[32] = {      16,  7, 20, 21,
  90                               29, 12, 28, 17,
  91                                1, 15, 23, 26,
  92                                5, 18, 31, 10,
  93                                2,  8, 24, 14,
  94                               32, 27,  3,  9,
  95                               19, 13, 30,  6,
  96                               22, 11,  4, 25};
  97
  98
  99 static const uchar perm6[64] ={ 40,  8, 48, 16, 56, 24, 64, 32,
 100                         39,  7, 47, 15, 55, 23, 63, 31,
 101                         38,  6, 46, 14, 54, 22, 62, 30,
 102                         37,  5, 45, 13, 53, 21, 61, 29,
 103                         36,  4, 44, 12, 52, 20, 60, 28,
 104                         35,  3, 43, 11, 51, 19, 59, 27,
 105                         34,  2, 42, 10, 50, 18, 58, 26,
 106                         33,  1, 41,  9, 49, 17, 57, 25};
 107
 108
 109 static const uchar sc[16] = {1, 1, 2, 2, 2, 2, 2, 2, 1, 2, 2, 2, 2, 2, 2, 1};
 110
 111 static const uchar sbox[8][4][16] = {
 112         {{14,  4, 13,  1,  2, 15, 11,  8,  3, 10,  6, 12,  5,  9,  0,  7},
 113          {0, 15,  7,  4, 14,  2, 13,  1, 10,  6, 12, 11,  9,  5,  3,  8},
 114          {4,  1, 14,  8, 13,  6,  2, 11, 15, 12,  9,  7,  3, 10,  5,  0},
 115          {15, 12,  8,  2,  4,  9,  1,  7,  5, 11,  3, 14, 10,  0,  6, 13}},
 116
 117         {{15,  1,  8, 14,  6, 11,  3,  4,  9,  7,  2, 13, 12,  0,  5, 10},
 118          {3, 13,  4,  7, 15,  2,  8, 14, 12,  0,  1, 10,  6,  9, 11,  5},
 119          {0, 14,  7, 11, 10,  4, 13,  1,  5,  8, 12,  6,  9,  3,  2, 15},
 120          {13,  8, 10,  1,  3, 15,  4,  2, 11,  6,  7, 12,  0,  5, 14,  9}},
 121
 122         {{10,  0,  9, 14,  6,  3, 15,  5,  1, 13, 12,  7, 11,  4,  2,  8},
 123          {13,  7,  0,  9,  3,  4,  6, 10,  2,  8,  5, 14, 12, 11, 15,  1},
 124          {13,  6,  4,  9,  8, 15,  3,  0, 11,  1,  2, 12,  5, 10, 14,  7},
 125          {1, 10, 13,  0,  6,  9,  8,  7,  4, 15, 14,  3, 11,  5,  2, 12}},
 126
 127         {{7, 13, 14,  3,  0,  6,  9, 10,  1,  2,  8,  5, 11, 12,  4, 15},
 128          {13,  8, 11,  5,  6, 15,  0,  3,  4,  7,  2, 12,  1, 10, 14,  9},
 129          {10,  6,  9,  0, 12, 11,  7, 13, 15,  1,  3, 14,  5,  2,  8,  4},
 130          {3, 15,  0,  6, 10,  1, 13,  8,  9,  4,  5, 11, 12,  7,  2, 14}},
 131
 132         {{2, 12,  4,  1,  7, 10, 11,  6,  8,  5,  3, 15, 13,  0, 14,  9},
 133          {14, 11,  2, 12,  4,  7, 13,  1,  5,  0, 15, 10,  3,  9,  8,  6},
 134          {4,  2,  1, 11, 10, 13,  7,  8, 15,  9, 12,  5,  6,  3,  0, 14},
 135          {11,  8, 12,  7,  1, 14,  2, 13,  6, 15,  0,  9, 10,  4,  5,  3}},
 136
 137         {{12,  1, 10, 15,  9,  2,  6,  8,  0, 13,  3,  4, 14,  7,  5, 11},
 138          {10, 15,  4,  2,  7, 12,  9,  5,  6,  1, 13, 14,  0, 11,  3,  8},
 139          {9, 14, 15,  5,  2,  8, 12,  3,  7,  0,  4, 10,  1, 13, 11,  6},
 140          {4,  3,  2, 12,  9,  5, 15, 10, 11, 14,  1,  7,  6,  0,  8, 13}},
 141
 142         {{4, 11,  2, 14, 15,  0,  8, 13,  3, 12,  9,  7,  5, 10,  6,  1},
 143          {13,  0, 11,  7,  4,  9,  1, 10, 14,  3,  5, 12,  2, 15,  8,  6},
 144          {1,  4, 11, 13, 12,  3,  7, 14, 10, 15,  6,  8,  0,  5,  9,  2},
 145          {6, 11, 13,  8,  1,  4, 10,  7,  9,  5,  0, 15, 14,  2,  3, 12}},
 146
 147         {{13,  2,  8,  4,  6, 15, 11,  1, 10,  9,  3, 14,  5,  0, 12,  7},
 148          {1, 15, 13,  8, 10,  3,  7,  4, 12,  5,  6, 11,  0, 14,  9,  2},
 149          {7, 11,  4,  1,  9, 12, 14,  2,  0,  6, 10, 13, 15,  3,  5,  8},
 150          {2,  1, 14,  7,  4, 10,  8, 13, 15, 12,  9,  0,  3,  5,  6, 11}}};
 151
 152 static void permute(char *out, const char *in, const uchar *p, int n)
 153 {
 154         int i;
 155         for (i=0;i<n;i++)
 156                 out[i] = in[p[i]-1];
 157 }
 158
 159 static void lshift(char *d, int count, int n)
 160 {
 161         char out[64];
 162         int i;
 163         for (i=0;i<n;i++)
 164                 out[i] = d[(i+count)%n];
 165         for (i=0;i<n;i++)
 166                 d[i] = out[i];
 167 }
 168
 169 static void concat(char *out, char *in1, char *in2, int l1, int l2)
 170 {
 171         while (l1--)
 172                 *out++ = *in1++;
 173         while (l2--)
 174                 *out++ = *in2++;
 175 }
 176
 177 static void xor(char *out, char *in1, char *in2, int n)
 178 {
 179         int i;
 180         for (i=0;i<n;i++)
 181                 out[i] = in1[i] ^ in2[i];
 182 }
 183
 184 static void dohash(char *out, char *in, char *key)
 185 {
 186         int i, j, k;
 187         char pk1[56];
 188         char c[28];
 189         char d[28];
 190         char cd[56];
 191         char ki[16][48];
 192         char pd1[64];
 193         char l[32], r[32];
 194         char rl[64];
 195
 196         permute(pk1, key, perm1, 56);
 197
 198         for (i=0;i<28;i++)
 199                 c[i] = pk1[i];
 200         for (i=0;i<28;i++)
 201                 d[i] = pk1[i+28];
 202
 203         for (i=0;i<16;i++) {
 204                 lshift(c, sc[i], 28);
 205                 lshift(d, sc[i], 28);
 206
 207                 concat(cd, c, d, 28, 28);
 208                 permute(ki[i], cd, perm2, 48);
 209         }
 210
 211         permute(pd1, in, perm3, 64);
 212
 213         for (j=0;j<32;j++) {
 214                 l[j] = pd1[j];
 215                 r[j] = pd1[j+32];
 216         }
 217
 218         for (i=0;i<16;i++) {
 219                 char er[48];
 220                 char erk[48];
 221                 char b[8][6];
 222                 char cb[32];
 223                 char pcb[32];
 224                 char r2[32];
 225
 226                 permute(er, r, perm4, 48);
 227
 228                 xor(erk, er, ki[i], 48);
 229
 230                 for (j=0;j<8;j++)
 231                         for (k=0;k<6;k++)
 232                                 b[j][k] = erk[j*6 + k];
 233
 234                 for (j=0;j<8;j++) {
 235                         int m, n;
 236                         m = (b[j][0]<<1) | b[j][5];
 237
 238                         n = (b[j][1]<<3) | (b[j][2]<<2) | (b[j][3]<<1) | b[j][4];
 239
 240                         for (k=0;k<4;k++)
 241                                 b[j][k] = (sbox[j][m][n] & (1<<(3-k)))?1:0;
 242                 }
 243
 244                 for (j=0;j<8;j++)
 245                         for (k=0;k<4;k++)
 246                                 cb[j*4+k] = b[j][k];
 247                 permute(pcb, cb, perm5, 32);
 248
 249                 xor(r2, l, pcb, 32);
 250
 251                 for (j=0;j<32;j++)
 252                         l[j] = r[j];
 253
 254                 for (j=0;j<32;j++)
 255                         r[j] = r2[j];
 256         }
 257
 258         concat(rl, r, l, 32, 32);
 259
 260         permute(out, rl, perm6, 64);
 261 }
 262
 263 static void str_to_key(unsigned char *str,unsigned char *key)
 264 {
 265         int i;
 266
 267         key[0] = str[0]>>1;
 268         key[1] = ((str[0]&0x01)<<6) | (str[1]>>2);
 269         key[2] = ((str[1]&0x03)<<5) | (str[2]>>3);
 270         key[3] = ((str[2]&0x07)<<4) | (str[3]>>4);
 271         key[4] = ((str[3]&0x0F)<<3) | (str[4]>>5);
 272         key[5] = ((str[4]&0x1F)<<2) | (str[5]>>6);
 273         key[6] = ((str[5]&0x3F)<<1) | (str[6]>>7);
 274         key[7] = str[6]&0x7F;
 275         for (i=0;i<8;i++) {
 276                 key[i] = (key[i]<<1);
 277         }
 278 }
 279
 280
 281 static void smbhash(unsigned char *out, const unsigned char *in, unsigned char *key)
 282 {
 283         int i;
 284         char outb[64];
 285         char inb[64];
 286         char keyb[64];
 287         unsigned char key2[8];
 288
 289         str_to_key(key, key2);
 290
 291         for (i=0;i<64;i++) {
 292                 inb[i] = (in[i/8] & (1<<(7-(i%8)))) ? 1 : 0;
 293                 keyb[i] = (key2[i/8] & (1<<(7-(i%8)))) ? 1 : 0;
 294                 outb[i] = 0;
 295         }
 296
 297         dohash(outb, inb, keyb);
 298
 299         for (i=0;i<8;i++) {
 300                 out[i] = 0;
 301         }
 302
 303         for (i=0;i<64;i++) {
 304                 if (outb[i])
 305                         out[i/8] |= (1<<(7-(i%8)));
 306         }
 307 }
 308
 309 /*
 310  *      Converts the password to uppercase, and creates the LM
 311  *      password hash.
 312  */
 313 void smbdes_lmpwdhash(const unsigned char *password,unsigned char *lmhash)
 314 {
 315         int i;
 316         unsigned char p14[14];
 317         static unsigned char sp8[8] = {0x4b, 0x47, 0x53, 0x21, 0x40, 0x23, 0x24, 0x25};
 318
 319         memset(p14, 0, sizeof(p14));
 320         for (i = 0; i < 14 && password[i]; i++) {
 321                 p14[i] = toupper((int) password[i]);
 322         }
 323
 324         smbhash(lmhash, sp8, p14);
 325         smbhash(lmhash+8, sp8, p14+7);
 326 }
 327
 328 /*
 329  *      Take the NT or LM password, and return the MSCHAP response
 330  *
 331  *      The win_password MUST be exactly 16 bytes long.
 332  */
 333 void smbdes_mschap(const unsigned char *win_password,
 334                  const unsigned char *challenge, unsigned char *response)
 335 {
 336         unsigned char p21[21];
 337
 338         memset(p21, 0, sizeof(p21));
 339         memcpy(p21, win_password, 16);
 340
 341         smbhash(response, challenge, p21);
 342         smbhash(response+8, challenge, p21+7);
 343         smbhash(response+16, challenge, p21+14);
 344 }