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