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 1997
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
50 static int 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 int 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 int 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 int 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 int 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 int 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 int sc[16] = {1, 1, 2, 2, 2, 2, 2, 2, 1, 2, 2, 2, 2, 2, 2, 1};
107
108 static int 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
permute(char * out,char * in,int * p,int n)149 static void permute(char *out, char *in, int *p, int n)
150 {
151 int i;
152 for (i=0;i<n;i++)
153 out[i] = in[p[i]-1];
154 }
155
lshift(char * d,int count,int n)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
concat(char * out,char * in1,char * in2,int l1,int l2)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
xor(char * out,char * in1,char * in2,int n)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
dohash(char * out,char * in,char * key)181 static void dohash(char *out, char *in, char *key)
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[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
str_to_key(unsigned char * str,unsigned char * key)260 static void str_to_key(unsigned char *str,unsigned char *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
smbhash(unsigned char * out,unsigned char * in,unsigned char * key)278 static void smbhash(unsigned char *out, unsigned char *in, unsigned char *key)
279 {
280 int i;
281 char outb[64];
282 char inb[64];
283 char keyb[64];
284 unsigned char key2[8];
285
286 str_to_key(key, key2);
287
288 for (i=0;i<64;i++) {
289 inb[i] = (in[i/8] & (1<<(7-(i%8)))) ? 1 : 0;
290 keyb[i] = (key2[i/8] & (1<<(7-(i%8)))) ? 1 : 0;
291 outb[i] = 0;
292 }
293
294 dohash(outb, inb, keyb);
295
296 for (i=0;i<8;i++) {
297 out[i] = 0;
298 }
299
300 for (i=0;i<64;i++) {
301 if (outb[i])
302 out[i/8] |= (1<<(7-(i%8)));
303 }
304 }
305
E_P16(unsigned char * p14,unsigned char * p16)306 void E_P16(unsigned char *p14,unsigned char *p16)
307 {
308 unsigned char sp8[8] = {0x4b, 0x47, 0x53, 0x21, 0x40, 0x23, 0x24, 0x25};
309 smbhash(p16, sp8, p14);
310 smbhash(p16+8, sp8, p14+7);
311 }
312
E_P24(unsigned char * p21,unsigned char * c8,unsigned char * p24)313 void E_P24(unsigned char *p21, unsigned char *c8, unsigned char *p24)
314 {
315 smbhash(p24, c8, p21);
316 smbhash(p24+8, c8, p21+7);
317 smbhash(p24+16, c8, p21+14);
318 }
319
cred_hash1(unsigned char * out,unsigned char * in,unsigned char * key)320 void cred_hash1(unsigned char *out,unsigned char *in,unsigned char *key)
321 {
322 unsigned char buf[8];
323
324 smbhash(buf, in, key);
325 smbhash(out, buf, key+9);
326 }
327
cred_hash2(unsigned char * out,unsigned char * in,unsigned char * key)328 void cred_hash2(unsigned char *out,unsigned char *in,unsigned char *key)
329 {
330 unsigned char buf[8];
331 static unsigned char key2[8];
332
333 smbhash(buf, in, key);
334 key2[0] = key[7];
335 smbhash(out, buf, key2);
336 }
337
338