source4/libcli/util/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
  24 #include "includes.h"
  25 #include "lib/crypto/crypto.h"
  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
  50 static const uint8_t perm1[56] = {57, 49, 41, 33, 25, 17,  9,
  51                          1, 58, 50, 42, 34, 26, 18,
  52                         10,  2, 59, 51, 43, 35, 27,
  53                         19, 11,  3, 60, 52, 44, 36,
  54                         63, 55, 47, 39, 31, 23, 15,
  55                          7, 62, 54, 46, 38, 30, 22,
  56                         14,  6, 61, 53, 45, 37, 29,
  57                         21, 13,  5, 28, 20, 12,  4};
  58
  59 static const uint8_t perm2[48] = {14, 17, 11, 24,  1,  5,
  60                          3, 28, 15,  6, 21, 10,
  61                         23, 19, 12,  4, 26,  8,
  62                         16,  7, 27, 20, 13,  2,
  63                         41, 52, 31, 37, 47, 55,
  64                         30, 40, 51, 45, 33, 48,
  65                         44, 49, 39, 56, 34, 53,
  66                         46, 42, 50, 36, 29, 32};
  67
  68 static const uint8_t perm3[64] = {58, 50, 42, 34, 26, 18, 10,  2,
  69                         60, 52, 44, 36, 28, 20, 12,  4,
  70                         62, 54, 46, 38, 30, 22, 14,  6,
  71                         64, 56, 48, 40, 32, 24, 16,  8,
  72                         57, 49, 41, 33, 25, 17,  9,  1,
  73                         59, 51, 43, 35, 27, 19, 11,  3,
  74                         61, 53, 45, 37, 29, 21, 13,  5,
  75                         63, 55, 47, 39, 31, 23, 15,  7};
  76
  77 static const uint8_t perm4[48] = {   32,  1,  2,  3,  4,  5,
  78                             4,  5,  6,  7,  8,  9,
  79                             8,  9, 10, 11, 12, 13,
  80                            12, 13, 14, 15, 16, 17,
  81                            16, 17, 18, 19, 20, 21,
  82                            20, 21, 22, 23, 24, 25,
  83                            24, 25, 26, 27, 28, 29,
  84                            28, 29, 30, 31, 32,  1};
  85
  86 static const uint8_t perm5[32] = {      16,  7, 20, 21,
  87                               29, 12, 28, 17,
  88                                1, 15, 23, 26,
  89                                5, 18, 31, 10,
  90                                2,  8, 24, 14,
  91                               32, 27,  3,  9,
  92                               19, 13, 30,  6,
  93                               22, 11,  4, 25};
  94
  95
  96 static const uint8_t perm6[64] ={ 40,  8, 48, 16, 56, 24, 64, 32,
  97                         39,  7, 47, 15, 55, 23, 63, 31,
  98                         38,  6, 46, 14, 54, 22, 62, 30,
  99                         37,  5, 45, 13, 53, 21, 61, 29,
 100                         36,  4, 44, 12, 52, 20, 60, 28,
 101                         35,  3, 43, 11, 51, 19, 59, 27,
 102                         34,  2, 42, 10, 50, 18, 58, 26,
 103                         33,  1, 41,  9, 49, 17, 57, 25};
 104
 105
 106 static const uint8_t sc[16] = {1, 1, 2, 2, 2, 2, 2, 2, 1, 2, 2, 2, 2, 2, 2, 1};
 107
 108 static const uint8_t sbox[8][4][16] = {
 109         {{14,  4, 13,  1,  2, 15, 11,  8,  3, 10,  6, 12,  5,  9,  0,  7},
 110          {0, 15,  7,  4, 14,  2, 13,  1, 10,  6, 12, 11,  9,  5,  3,  8},
 111          {4,  1, 14,  8, 13,  6,  2, 11, 15, 12,  9,  7,  3, 10,  5,  0},
 112          {15, 12,  8,  2,  4,  9,  1,  7,  5, 11,  3, 14, 10,  0,  6, 13}},
 113
 114         {{15,  1,  8, 14,  6, 11,  3,  4,  9,  7,  2, 13, 12,  0,  5, 10},
 115          {3, 13,  4,  7, 15,  2,  8, 14, 12,  0,  1, 10,  6,  9, 11,  5},
 116          {0, 14,  7, 11, 10,  4, 13,  1,  5,  8, 12,  6,  9,  3,  2, 15},
 117          {13,  8, 10,  1,  3, 15,  4,  2, 11,  6,  7, 12,  0,  5, 14,  9}},
 118
 119         {{10,  0,  9, 14,  6,  3, 15,  5,  1, 13, 12,  7, 11,  4,  2,  8},
 120          {13,  7,  0,  9,  3,  4,  6, 10,  2,  8,  5, 14, 12, 11, 15,  1},
 121          {13,  6,  4,  9,  8, 15,  3,  0, 11,  1,  2, 12,  5, 10, 14,  7},
 122          {1, 10, 13,  0,  6,  9,  8,  7,  4, 15, 14,  3, 11,  5,  2, 12}},
 123
 124         {{7, 13, 14,  3,  0,  6,  9, 10,  1,  2,  8,  5, 11, 12,  4, 15},
 125          {13,  8, 11,  5,  6, 15,  0,  3,  4,  7,  2, 12,  1, 10, 14,  9},
 126          {10,  6,  9,  0, 12, 11,  7, 13, 15,  1,  3, 14,  5,  2,  8,  4},
 127          {3, 15,  0,  6, 10,  1, 13,  8,  9,  4,  5, 11, 12,  7,  2, 14}},
 128
 129         {{2, 12,  4,  1,  7, 10, 11,  6,  8,  5,  3, 15, 13,  0, 14,  9},
 130          {14, 11,  2, 12,  4,  7, 13,  1,  5,  0, 15, 10,  3,  9,  8,  6},
 131          {4,  2,  1, 11, 10, 13,  7,  8, 15,  9, 12,  5,  6,  3,  0, 14},
 132          {11,  8, 12,  7,  1, 14,  2, 13,  6, 15,  0,  9, 10,  4,  5,  3}},
 133
 134         {{12,  1, 10, 15,  9,  2,  6,  8,  0, 13,  3,  4, 14,  7,  5, 11},
 135          {10, 15,  4,  2,  7, 12,  9,  5,  6,  1, 13, 14,  0, 11,  3,  8},
 136          {9, 14, 15,  5,  2,  8, 12,  3,  7,  0,  4, 10,  1, 13, 11,  6},
 137          {4,  3,  2, 12,  9,  5, 15, 10, 11, 14,  1,  7,  6,  0,  8, 13}},
 138
 139         {{4, 11,  2, 14, 15,  0,  8, 13,  3, 12,  9,  7,  5, 10,  6,  1},
 140          {13,  0, 11,  7,  4,  9,  1, 10, 14,  3,  5, 12,  2, 15,  8,  6},
 141          {1,  4, 11, 13, 12,  3,  7, 14, 10, 15,  6,  8,  0,  5,  9,  2},
 142          {6, 11, 13,  8,  1,  4, 10,  7,  9,  5,  0, 15, 14,  2,  3, 12}},
 143
 144         {{13,  2,  8,  4,  6, 15, 11,  1, 10,  9,  3, 14,  5,  0, 12,  7},
 145          {1, 15, 13,  8, 10,  3,  7,  4, 12,  5,  6, 11,  0, 14,  9,  2},
 146          {7, 11,  4,  1,  9, 12, 14,  2,  0,  6, 10, 13, 15,  3,  5,  8},
 147          {2,  1, 14,  7,  4, 10,  8, 13, 15, 12,  9,  0,  3,  5,  6, 11}}};
 148
 149 static void permute(char *out, const char *in, const uint8_t *p, int n)
 150 {
 151         int i;
 152         for (i=0;i<n;i++)
 153                 out[i] = in[p[i]-1];
 154 }
 155
 156 static void lshift(char *d, int count, int n)
 157 {
 158         char out[64];
 159         int i;
 160         for (i=0;i<n;i++)
 161                 out[i] = d[(i+count)%n];
 162         for (i=0;i<n;i++)
 163                 d[i] = out[i];
 164 }
 165
 166 static void concat(char *out, char *in1, char *in2, int l1, int l2)
 167 {
 168         while (l1--)
 169                 *out++ = *in1++;
 170         while (l2--)
 171                 *out++ = *in2++;
 172 }
 173
 174 static void xor(char *out, char *in1, char *in2, int n)
 175 {
 176         int i;
 177         for (i=0;i<n;i++)
 178                 out[i] = in1[i] ^ in2[i];
 179 }
 180
 181 static void dohash(char *out, char *in, char *key, int forw)
 182 {
 183         int i, j, k;
 184         char pk1[56];
 185         char c[28];
 186         char d[28];
 187         char cd[56];
 188         char ki[16][48];
 189         char pd1[64];
 190         char l[32], r[32];
 191         char rl[64];
 192
 193         permute(pk1, key, perm1, 56);
 194
 195         for (i=0;i<28;i++)
 196                 c[i] = pk1[i];
 197         for (i=0;i<28;i++)
 198                 d[i] = pk1[i+28];
 199
 200         for (i=0;i<16;i++) {
 201                 lshift(c, sc[i], 28);
 202                 lshift(d, sc[i], 28);
 203
 204                 concat(cd, c, d, 28, 28);
 205                 permute(ki[i], cd, perm2, 48);
 206         }
 207
 208         permute(pd1, in, perm3, 64);
 209
 210         for (j=0;j<32;j++) {
 211                 l[j] = pd1[j];
 212                 r[j] = pd1[j+32];
 213         }
 214
 215         for (i=0;i<16;i++) {
 216                 char er[48];
 217                 char erk[48];
 218                 char b[8][6];
 219                 char cb[32];
 220                 char pcb[32];
 221                 char r2[32];
 222
 223                 permute(er, r, perm4, 48);
 224
 225                 xor(erk, er, ki[forw ? i : 15 - i], 48);
 226
 227                 for (j=0;j<8;j++)
 228                         for (k=0;k<6;k++)
 229                                 b[j][k] = erk[j*6 + k];
 230
 231                 for (j=0;j<8;j++) {
 232                         int m, n;
 233                         m = (b[j][0]<<1) | b[j][5];
 234
 235                         n = (b[j][1]<<3) | (b[j][2]<<2) | (b[j][3]<<1) | b[j][4];
 236
 237                         for (k=0;k<4;k++)
 238                                 b[j][k] = (sbox[j][m][n] & (1<<(3-k)))?1:0;
 239                 }
 240
 241                 for (j=0;j<8;j++)
 242                         for (k=0;k<4;k++)
 243                                 cb[j*4+k] = b[j][k];
 244                 permute(pcb, cb, perm5, 32);
 245
 246                 xor(r2, l, pcb, 32);
 247
 248                 for (j=0;j<32;j++)
 249                         l[j] = r[j];
 250
 251                 for (j=0;j<32;j++)
 252                         r[j] = r2[j];
 253         }
 254
 255         concat(rl, r, l, 32, 32);
 256
 257         permute(out, rl, perm6, 64);
 258 }
 259
 260 static void str_to_key(const uint8_t *str,uint8_t *key)
 261 {
 262         int i;
 263
 264         key[0] = str[0]>>1;
 265         key[1] = ((str[0]&0x01)<<6) | (str[1]>>2);
 266         key[2] = ((str[1]&0x03)<<5) | (str[2]>>3);
 267         key[3] = ((str[2]&0x07)<<4) | (str[3]>>4);
 268         key[4] = ((str[3]&0x0F)<<3) | (str[4]>>5);
 269         key[5] = ((str[4]&0x1F)<<2) | (str[5]>>6);
 270         key[6] = ((str[5]&0x3F)<<1) | (str[6]>>7);
 271         key[7] = str[6]&0x7F;
 272         for (i=0;i<8;i++) {
 273                 key[i] = (key[i]<<1);
 274         }
 275 }
 276
 277 /*
 278   basic des crypt using a 56 bit (7 byte) key
 279 */
 280 void des_crypt56(uint8_t out[8], const uint8_t in[8], const uint8_t key[7], int forw)
 281 {
 282         int i;
 283         char outb[64];
 284         char inb[64];
 285         char keyb[64];
 286         uint8_t key2[8];
 287
 288         str_to_key(key, key2);
 289
 290         for (i=0;i<64;i++) {
 291                 inb[i] = (in[i/8] & (1<<(7-(i%8)))) ? 1 : 0;
 292                 keyb[i] = (key2[i/8] & (1<<(7-(i%8)))) ? 1 : 0;
 293                 outb[i] = 0;
 294         }
 295
 296         dohash(outb, inb, keyb, forw);
 297
 298         for (i=0;i<8;i++) {
 299                 out[i] = 0;
 300         }
 301
 302         for (i=0;i<64;i++) {
 303                 if (outb[i])
 304                         out[i/8] |= (1<<(7-(i%8)));
 305         }
 306 }
 307
 308 void E_P16(const uint8_t *p14,uint8_t *p16)
 309 {
 310         const uint8_t sp8[8] = {0x4b, 0x47, 0x53, 0x21, 0x40, 0x23, 0x24, 0x25};
 311         des_crypt56(p16, sp8, p14, 1);
 312         des_crypt56(p16+8, sp8, p14+7, 1);
 313 }
 314
 315 void E_P24(const uint8_t *p21, const uint8_t *c8, uint8_t *p24)
 316 {
 317         des_crypt56(p24, c8, p21, 1);
 318         des_crypt56(p24+8, c8, p21+7, 1);
 319         des_crypt56(p24+16, c8, p21+14, 1);
 320 }
 321
 322 void D_P16(const uint8_t *p14, const uint8_t *in, uint8_t *out)
 323 {
 324         des_crypt56(out, in, p14, 0);
 325         des_crypt56(out+8, in+8, p14+7, 0);
 326 }
 327
 328 void E_old_pw_hash( uint8_t *p14, const uint8_t *in, uint8_t *out)
 329 {
 330         des_crypt56(out, in, p14, 1);
 331         des_crypt56(out+8, in+8, p14+7, 1);
 332 }
 333
 334 /* des encryption with a 128 bit key */
 335 void des_crypt128(uint8_t out[8], const uint8_t in[8], const uint8_t key[16])
 336 {
 337         uint8_t buf[8];
 338         des_crypt56(buf, in, key, 1);
 339         des_crypt56(out, buf, key+9, 1);
 340 }
 341
 342 /* des encryption with a 64 bit key */
 343 void des_crypt64(uint8_t out[8], const uint8_t in[8], const uint8_t key[8], int forw)
 344 {
 345         uint8_t buf[8];
 346         uint8_t key2[8];
 347         ZERO_STRUCT(key2);
 348         des_crypt56(buf, in, key, forw);
 349         key2[0] = key[7];
 350         des_crypt56(out, buf, key2, forw);
 351 }
 352
 353 /* des encryption with a 112 bit (14 byte) key */
 354 void des_crypt112(uint8_t out[8], const uint8_t in[8], const uint8_t key[14], int forw)
 355 {
 356         uint8_t buf[8];
 357         des_crypt56(buf, in, key, forw);
 358         des_crypt56(out, buf, key+7, forw);
 359 }
 360
 361 /* des encryption of a 16 byte lump of data with a 112 bit key */
 362 void des_crypt112_16(uint8_t out[16], uint8_t in[16], const uint8_t key[14], int forw)
 363 {
 364         des_crypt56(out, in, key, forw);
 365         des_crypt56(out + 8, in + 8, key+7, forw);
 366 }
 367
 368 /* initialise the arcfour sbox with key */
 369 void arcfour_init(struct arcfour_state *state, const DATA_BLOB *key)
 370 {
 371         int ind;
 372         uint8_t j = 0;
 373         for (ind = 0; ind < sizeof(state->sbox); ind++) {
 374                 state->sbox[ind] = (uint8_t)ind;
 375         }
 376
 377         for (ind = 0; ind < sizeof(state->sbox); ind++) {
 378                 uint8_t tc;
 379
 380                 j += (state->sbox[ind] + key->data[ind%key->length]);
 381
 382                 tc = state->sbox[ind];
 383                 state->sbox[ind] = state->sbox[j];
 384                 state->sbox[j] = tc;
 385         }
 386         state->index_i = 0;
 387         state->index_j = 0;
 388 }
 389
 390 /* crypt the data with arcfour */
 391 void arcfour_crypt_sbox(struct arcfour_state *state, uint8_t *data, int len)
 392 {
 393         int ind;
 394
 395         for (ind = 0; ind < len; ind++) {
 396                 uint8_t tc;
 397                 uint8_t t;
 398
 399                 state->index_i++;
 400                 state->index_j += state->sbox[state->index_i];
 401
 402                 tc = state->sbox[state->index_i];
 403                 state->sbox[state->index_i] = state->sbox[state->index_j];
 404                 state->sbox[state->index_j] = tc;
 405
 406                 t = state->sbox[state->index_i] + state->sbox[state->index_j];
 407                 data[ind] = data[ind] ^ state->sbox[t];
 408         }
 409 }
 410
 411 /*
 412   arcfour encryption with a blob key
 413 */
 414 void arcfour_crypt_blob(uint8_t *data, int len, const DATA_BLOB *key)
 415 {
 416         struct arcfour_state state;
 417         arcfour_init(&state, key);
 418         arcfour_crypt_sbox(&state, data, len);
 419 }
 420
 421 /*
 422   a variant that assumes a 16 byte key. This should be removed
 423   when the last user is gone
 424 */
 425 void arcfour_crypt(uint8_t *data, const uint8_t keystr[16], int len)
 426 {
 427         DATA_BLOB key = data_blob(keystr, 16);
 428
 429         arcfour_crypt_blob(data, len, &key);
 430
 431         data_blob_free(&key);
 432 }
 433
 434
 435 /* Decode a sam password hash into a password.  The password hash is the
 436    same method used to store passwords in the NT registry.  The DES key
 437    used is based on the RID of the user. */
 438 void sam_rid_crypt(uint_t rid, const uint8_t *in, uint8_t *out, int forw)
 439 {
 440         uint8_t s[14];
 441
 442         s[0] = s[4] = s[8] = s[12] = (uint8_t)(rid & 0xFF);
 443         s[1] = s[5] = s[9] = s[13] = (uint8_t)((rid >> 8) & 0xFF);
 444         s[2] = s[6] = s[10]        = (uint8_t)((rid >> 16) & 0xFF);
 445         s[3] = s[7] = s[11]        = (uint8_t)((rid >> 24) & 0xFF);
 446
 447         des_crypt56(out, in, s, forw);
 448         des_crypt56(out+8, in+8, s+7, forw);
 449 }