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