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