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