src/modules/rlm_smb/smbdes.c

   1 /*
   2    Unix SMB/Netbios implementation.
   3    Version 1.9.
   4
   5    a partial implementation of DES designed for use in the
   6    SMB authentication protocol
   7
   8    Copyright (C) Andrew Tridgell 1997
   9    Copyright 2006 The FreeRADIUS server project
  10
  11    This program is free software; you can redistribute it and/or modify
  12    it under the terms of the GNU General Public License as published by
  13    the Free Software Foundation; either version 2 of the License, or
  14    (at your option) any later version.
  15
  16    This program is distributed in the hope that it will be useful,
  17    but WITHOUT ANY WARRANTY; without even the implied warranty of
  18    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  19    GNU General Public License for more details.
  20
  21    You should have received a copy of the GNU General Public License
  22    along with this program; if not, write to the Free Software
  23    Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.
  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
  53
  54 static int perm1[56] = {57, 49, 41, 33, 25, 17,  9,
  55                          1, 58, 50, 42, 34, 26, 18,
  56                         10,  2, 59, 51, 43, 35, 27,
  57                         19, 11,  3, 60, 52, 44, 36,
  58                         63, 55, 47, 39, 31, 23, 15,
  59                          7, 62, 54, 46, 38, 30, 22,
  60                         14,  6, 61, 53, 45, 37, 29,
  61                         21, 13,  5, 28, 20, 12,  4};
  62
  63 static int perm2[48] = {14, 17, 11, 24,  1,  5,
  64                          3, 28, 15,  6, 21, 10,
  65                         23, 19, 12,  4, 26,  8,
  66                         16,  7, 27, 20, 13,  2,
  67                         41, 52, 31, 37, 47, 55,
  68                         30, 40, 51, 45, 33, 48,
  69                         44, 49, 39, 56, 34, 53,
  70                         46, 42, 50, 36, 29, 32};
  71
  72 static int perm3[64] = {58, 50, 42, 34, 26, 18, 10,  2,
  73                         60, 52, 44, 36, 28, 20, 12,  4,
  74                         62, 54, 46, 38, 30, 22, 14,  6,
  75                         64, 56, 48, 40, 32, 24, 16,  8,
  76                         57, 49, 41, 33, 25, 17,  9,  1,
  77                         59, 51, 43, 35, 27, 19, 11,  3,
  78                         61, 53, 45, 37, 29, 21, 13,  5,
  79                         63, 55, 47, 39, 31, 23, 15,  7};
  80
  81 static int perm4[48] = {   32,  1,  2,  3,  4,  5,
  82                             4,  5,  6,  7,  8,  9,
  83                             8,  9, 10, 11, 12, 13,
  84                            12, 13, 14, 15, 16, 17,
  85                            16, 17, 18, 19, 20, 21,
  86                            20, 21, 22, 23, 24, 25,
  87                            24, 25, 26, 27, 28, 29,
  88                            28, 29, 30, 31, 32,  1};
  89
  90 static int perm5[32] = {      16,  7, 20, 21,
  91                               29, 12, 28, 17,
  92                                1, 15, 23, 26,
  93                                5, 18, 31, 10,
  94                                2,  8, 24, 14,
  95                               32, 27,  3,  9,
  96                               19, 13, 30,  6,
  97                               22, 11,  4, 25};
  98
  99
 100 static int perm6[64] ={ 40,  8, 48, 16, 56, 24, 64, 32,
 101                         39,  7, 47, 15, 55, 23, 63, 31,
 102                         38,  6, 46, 14, 54, 22, 62, 30,
 103                         37,  5, 45, 13, 53, 21, 61, 29,
 104                         36,  4, 44, 12, 52, 20, 60, 28,
 105                         35,  3, 43, 11, 51, 19, 59, 27,
 106                         34,  2, 42, 10, 50, 18, 58, 26,
 107                         33,  1, 41,  9, 49, 17, 57, 25};
 108
 109
 110 static int sc[16] = {1, 1, 2, 2, 2, 2, 2, 2, 1, 2, 2, 2, 2, 2, 2, 1};
 111
 112 static int sbox[8][4][16] = {
 113         {{14,  4, 13,  1,  2, 15, 11,  8,  3, 10,  6, 12,  5,  9,  0,  7},
 114          {0, 15,  7,  4, 14,  2, 13,  1, 10,  6, 12, 11,  9,  5,  3,  8},
 115          {4,  1, 14,  8, 13,  6,  2, 11, 15, 12,  9,  7,  3, 10,  5,  0},
 116          {15, 12,  8,  2,  4,  9,  1,  7,  5, 11,  3, 14, 10,  0,  6, 13}},
 117
 118         {{15,  1,  8, 14,  6, 11,  3,  4,  9,  7,  2, 13, 12,  0,  5, 10},
 119          {3, 13,  4,  7, 15,  2,  8, 14, 12,  0,  1, 10,  6,  9, 11,  5},
 120          {0, 14,  7, 11, 10,  4, 13,  1,  5,  8, 12,  6,  9,  3,  2, 15},
 121          {13,  8, 10,  1,  3, 15,  4,  2, 11,  6,  7, 12,  0,  5, 14,  9}},
 122
 123         {{10,  0,  9, 14,  6,  3, 15,  5,  1, 13, 12,  7, 11,  4,  2,  8},
 124          {13,  7,  0,  9,  3,  4,  6, 10,  2,  8,  5, 14, 12, 11, 15,  1},
 125          {13,  6,  4,  9,  8, 15,  3,  0, 11,  1,  2, 12,  5, 10, 14,  7},
 126          {1, 10, 13,  0,  6,  9,  8,  7,  4, 15, 14,  3, 11,  5,  2, 12}},
 127
 128         {{7, 13, 14,  3,  0,  6,  9, 10,  1,  2,  8,  5, 11, 12,  4, 15},
 129          {13,  8, 11,  5,  6, 15,  0,  3,  4,  7,  2, 12,  1, 10, 14,  9},
 130          {10,  6,  9,  0, 12, 11,  7, 13, 15,  1,  3, 14,  5,  2,  8,  4},
 131          {3, 15,  0,  6, 10,  1, 13,  8,  9,  4,  5, 11, 12,  7,  2, 14}},
 132
 133         {{2, 12,  4,  1,  7, 10, 11,  6,  8,  5,  3, 15, 13,  0, 14,  9},
 134          {14, 11,  2, 12,  4,  7, 13,  1,  5,  0, 15, 10,  3,  9,  8,  6},
 135          {4,  2,  1, 11, 10, 13,  7,  8, 15,  9, 12,  5,  6,  3,  0, 14},
 136          {11,  8, 12,  7,  1, 14,  2, 13,  6, 15,  0,  9, 10,  4,  5,  3}},
 137
 138         {{12,  1, 10, 15,  9,  2,  6,  8,  0, 13,  3,  4, 14,  7,  5, 11},
 139          {10, 15,  4,  2,  7, 12,  9,  5,  6,  1, 13, 14,  0, 11,  3,  8},
 140          {9, 14, 15,  5,  2,  8, 12,  3,  7,  0,  4, 10,  1, 13, 11,  6},
 141          {4,  3,  2, 12,  9,  5, 15, 10, 11, 14,  1,  7,  6,  0,  8, 13}},
 142
 143         {{4, 11,  2, 14, 15,  0,  8, 13,  3, 12,  9,  7,  5, 10,  6,  1},
 144          {13,  0, 11,  7,  4,  9,  1, 10, 14,  3,  5, 12,  2, 15,  8,  6},
 145          {1,  4, 11, 13, 12,  3,  7, 14, 10, 15,  6,  8,  0,  5,  9,  2},
 146          {6, 11, 13,  8,  1,  4, 10,  7,  9,  5,  0, 15, 14,  2,  3, 12}},
 147
 148         {{13,  2,  8,  4,  6, 15, 11,  1, 10,  9,  3, 14,  5,  0, 12,  7},
 149          {1, 15, 13,  8, 10,  3,  7,  4, 12,  5,  6, 11,  0, 14,  9,  2},
 150          {7, 11,  4,  1,  9, 12, 14,  2,  0,  6, 10, 13, 15,  3,  5,  8},
 151          {2,  1, 14,  7,  4, 10,  8, 13, 15, 12,  9,  0,  3,  5,  6, 11}}};
 152
 153 static void permute(char *out, char *in, int *p, int n)
 154 {
 155         int i;
 156         for (i=0;i<n;i++)
 157                 out[i] = in[p[i]-1];
 158 }
 159
 160 static void lshift(char *d, int count, int n)
 161 {
 162         char out[64];
 163         int i;
 164         for (i=0;i<n;i++)
 165                 out[i] = d[(i+count)%n];
 166         for (i=0;i<n;i++)
 167                 d[i] = out[i];
 168 }
 169
 170 static void concat(char *out, char *in1, char *in2, int l1, int l2)
 171 {
 172         while (l1--)
 173                 *out++ = *in1++;
 174         while (l2--)
 175                 *out++ = *in2++;
 176 }
 177
 178 static void xor(char *out, char *in1, char *in2, int n)
 179 {
 180         int i;
 181         for (i=0;i<n;i++)
 182                 out[i] = in1[i] ^ in2[i];
 183 }
 184
 185 static void dohash(char *out, char *in, char *key)
 186 {
 187         int i, j, k;
 188         char pk1[56];
 189         char c[28];
 190         char d[28];
 191         char cd[56];
 192         char ki[16][48];
 193         char pd1[64];
 194         char l[32], r[32];
 195         char rl[64];
 196
 197         permute(pk1, key, perm1, 56);
 198
 199         for (i=0;i<28;i++)
 200                 c[i] = pk1[i];
 201         for (i=0;i<28;i++)
 202                 d[i] = pk1[i+28];
 203
 204         for (i=0;i<16;i++) {
 205                 lshift(c, sc[i], 28);
 206                 lshift(d, sc[i], 28);
 207
 208                 concat(cd, c, d, 28, 28);
 209                 permute(ki[i], cd, perm2, 48);
 210         }
 211
 212         permute(pd1, in, perm3, 64);
 213
 214         for (j=0;j<32;j++) {
 215                 l[j] = pd1[j];
 216                 r[j] = pd1[j+32];
 217         }
 218
 219         for (i=0;i<16;i++) {
 220                 char er[48];
 221                 char erk[48];
 222                 char b[8][6];
 223                 char cb[32];
 224                 char pcb[32];
 225                 char r2[32];
 226
 227                 permute(er, r, perm4, 48);
 228
 229                 xor(erk, er, ki[i], 48);
 230
 231                 for (j=0;j<8;j++)
 232                         for (k=0;k<6;k++)
 233                                 b[j][k] = erk[j*6 + k];
 234
 235                 for (j=0;j<8;j++) {
 236                         int m, n;
 237                         m = (b[j][0]<<1) | b[j][5];
 238
 239                         n = (b[j][1]<<3) | (b[j][2]<<2) | (b[j][3]<<1) | b[j][4];
 240
 241                         for (k=0;k<4;k++)
 242                                 b[j][k] = (sbox[j][m][n] & (1<<(3-k)))?1:0;
 243                 }
 244
 245                 for (j=0;j<8;j++)
 246                         for (k=0;k<4;k++)
 247                                 cb[j*4+k] = b[j][k];
 248                 permute(pcb, cb, perm5, 32);
 249
 250                 xor(r2, l, pcb, 32);
 251
 252                 for (j=0;j<32;j++)
 253                         l[j] = r[j];
 254
 255                 for (j=0;j<32;j++)
 256                         r[j] = r2[j];
 257         }
 258
 259         concat(rl, r, l, 32, 32);
 260
 261         permute(out, rl, perm6, 64);
 262 }
 263
 264 static void str_to_key(unsigned char *str,unsigned char *key)
 265 {
 266         int i;
 267
 268         key[0] = str[0]>>1;
 269         key[1] = ((str[0]&0x01)<<6) | (str[1]>>2);
 270         key[2] = ((str[1]&0x03)<<5) | (str[2]>>3);
 271         key[3] = ((str[2]&0x07)<<4) | (str[3]>>4);
 272         key[4] = ((str[3]&0x0F)<<3) | (str[4]>>5);
 273         key[5] = ((str[4]&0x1F)<<2) | (str[5]>>6);
 274         key[6] = ((str[5]&0x3F)<<1) | (str[6]>>7);
 275         key[7] = str[6]&0x7F;
 276         for (i=0;i<8;i++) {
 277                 key[i] = (key[i]<<1);
 278         }
 279 }
 280
 281
 282 static void smbhash(unsigned char *out, unsigned char *in, unsigned char *key)
 283 {
 284         int i;
 285         char outb[64];
 286         char inb[64];
 287         char keyb[64];
 288         unsigned char key2[8];
 289
 290         str_to_key(key, key2);
 291
 292         for (i=0;i<64;i++) {
 293                 inb[i] = (in[i/8] & (1<<(7-(i%8)))) ? 1 : 0;
 294                 keyb[i] = (key2[i/8] & (1<<(7-(i%8)))) ? 1 : 0;
 295                 outb[i] = 0;
 296         }
 297
 298         dohash(outb, inb, keyb);
 299
 300         for (i=0;i<8;i++) {
 301                 out[i] = 0;
 302         }
 303
 304         for (i=0;i<64;i++) {
 305                 if (outb[i])
 306                         out[i/8] |= (1<<(7-(i%8)));
 307         }
 308 }
 309
 310 void E_P16(unsigned char *p14,unsigned char *p16)
 311 {
 312         unsigned char sp8[8] = {0x4b, 0x47, 0x53, 0x21, 0x40, 0x23, 0x24, 0x25};
 313         smbhash(p16, sp8, p14);
 314         smbhash(p16+8, sp8, p14+7);
 315 }
 316
 317 void E_P24(unsigned char *p21, unsigned char *c8, unsigned char *p24)
 318 {
 319         smbhash(p24, c8, p21);
 320         smbhash(p24+8, c8, p21+7);
 321         smbhash(p24+16, c8, p21+14);
 322 }
 323
 324 void cred_hash1(unsigned char *out,unsigned char *in,unsigned char *key)
 325 {
 326         unsigned char buf[8];
 327
 328         smbhash(buf, in, key);
 329         smbhash(out, buf, key+9);
 330 }
 331
 332 void cred_hash2(unsigned char *out,unsigned char *in,unsigned char *key)
 333 {
 334         unsigned char buf[8];
 335         static unsigned char key2[8];
 336
 337         smbhash(buf, in, key);
 338         key2[0] = key[7];
 339         smbhash(out, buf, key2);
 340 }
 341