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