lib/smblib/smbdes.c

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