lib/smblib/smbdes.c

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