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