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
49static 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
58static 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
67static 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
76static 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
85static 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
95static 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
105static const uint8_t sc[16] = {1, 1, 2, 2, 2, 2, 2, 2, 1, 2, 2, 2, 2, 2, 2, 1};
106
107static 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
148static 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
155static 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
165static 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
173static 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
180static 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
259static 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*/
279void 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
307void 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
314void 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
321void 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
327void 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 */
334void 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 */
342void 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 */
353void 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 */
361void 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. */
370void 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}
382