blob: efaa044523a7094ecbbddd1ead52f89fc424cc7e [file] [log] [blame]
Linus Torvalds1da177e2005-04-16 15:20:36 -07001/*
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 Modified by Steve French (sfrench@us.ibm.com) 2002,2004
10
11 This program is free software; you can redistribute it and/or modify
12 it under the terms of the GNU General Public License as published by
13 the Free Software Foundation; either version 2 of the License, or
14 (at your option) any later version.
15
16 This program is distributed in the hope that it will be useful,
17 but WITHOUT ANY WARRANTY; without even the implied warranty of
18 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
19 GNU General Public License for more details.
20
21 You should have received a copy of the GNU General Public License
22 along with this program; if not, write to the Free Software
23 Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.
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#include <linux/slab.h>
48#include "cifsencrypt.h"
49#define uchar unsigned char
50
51static 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
61static 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
71static uchar perm3[64] = { 58, 50, 42, 34, 26, 18, 10, 2,
72 60, 52, 44, 36, 28, 20, 12, 4,
73 62, 54, 46, 38, 30, 22, 14, 6,
74 64, 56, 48, 40, 32, 24, 16, 8,
75 57, 49, 41, 33, 25, 17, 9, 1,
76 59, 51, 43, 35, 27, 19, 11, 3,
77 61, 53, 45, 37, 29, 21, 13, 5,
78 63, 55, 47, 39, 31, 23, 15, 7
79};
80
81static uchar perm4[48] = { 32, 1, 2, 3, 4, 5,
82 4, 5, 6, 7, 8, 9,
83 8, 9, 10, 11, 12, 13,
84 12, 13, 14, 15, 16, 17,
85 16, 17, 18, 19, 20, 21,
86 20, 21, 22, 23, 24, 25,
87 24, 25, 26, 27, 28, 29,
88 28, 29, 30, 31, 32, 1
89};
90
91static uchar perm5[32] = { 16, 7, 20, 21,
92 29, 12, 28, 17,
93 1, 15, 23, 26,
94 5, 18, 31, 10,
95 2, 8, 24, 14,
96 32, 27, 3, 9,
97 19, 13, 30, 6,
98 22, 11, 4, 25
99};
100
101static uchar perm6[64] = { 40, 8, 48, 16, 56, 24, 64, 32,
102 39, 7, 47, 15, 55, 23, 63, 31,
103 38, 6, 46, 14, 54, 22, 62, 30,
104 37, 5, 45, 13, 53, 21, 61, 29,
105 36, 4, 44, 12, 52, 20, 60, 28,
106 35, 3, 43, 11, 51, 19, 59, 27,
107 34, 2, 42, 10, 50, 18, 58, 26,
108 33, 1, 41, 9, 49, 17, 57, 25
109};
110
111static uchar sc[16] = { 1, 1, 2, 2, 2, 2, 2, 2, 1, 2, 2, 2, 2, 2, 2, 1 };
112
113static uchar sbox[8][4][16] = {
114 {{14, 4, 13, 1, 2, 15, 11, 8, 3, 10, 6, 12, 5, 9, 0, 7},
115 {0, 15, 7, 4, 14, 2, 13, 1, 10, 6, 12, 11, 9, 5, 3, 8},
116 {4, 1, 14, 8, 13, 6, 2, 11, 15, 12, 9, 7, 3, 10, 5, 0},
117 {15, 12, 8, 2, 4, 9, 1, 7, 5, 11, 3, 14, 10, 0, 6, 13}},
118
119 {{15, 1, 8, 14, 6, 11, 3, 4, 9, 7, 2, 13, 12, 0, 5, 10},
120 {3, 13, 4, 7, 15, 2, 8, 14, 12, 0, 1, 10, 6, 9, 11, 5},
121 {0, 14, 7, 11, 10, 4, 13, 1, 5, 8, 12, 6, 9, 3, 2, 15},
122 {13, 8, 10, 1, 3, 15, 4, 2, 11, 6, 7, 12, 0, 5, 14, 9}},
123
124 {{10, 0, 9, 14, 6, 3, 15, 5, 1, 13, 12, 7, 11, 4, 2, 8},
125 {13, 7, 0, 9, 3, 4, 6, 10, 2, 8, 5, 14, 12, 11, 15, 1},
126 {13, 6, 4, 9, 8, 15, 3, 0, 11, 1, 2, 12, 5, 10, 14, 7},
127 {1, 10, 13, 0, 6, 9, 8, 7, 4, 15, 14, 3, 11, 5, 2, 12}},
128
129 {{7, 13, 14, 3, 0, 6, 9, 10, 1, 2, 8, 5, 11, 12, 4, 15},
130 {13, 8, 11, 5, 6, 15, 0, 3, 4, 7, 2, 12, 1, 10, 14, 9},
131 {10, 6, 9, 0, 12, 11, 7, 13, 15, 1, 3, 14, 5, 2, 8, 4},
132 {3, 15, 0, 6, 10, 1, 13, 8, 9, 4, 5, 11, 12, 7, 2, 14}},
133
134 {{2, 12, 4, 1, 7, 10, 11, 6, 8, 5, 3, 15, 13, 0, 14, 9},
135 {14, 11, 2, 12, 4, 7, 13, 1, 5, 0, 15, 10, 3, 9, 8, 6},
136 {4, 2, 1, 11, 10, 13, 7, 8, 15, 9, 12, 5, 6, 3, 0, 14},
137 {11, 8, 12, 7, 1, 14, 2, 13, 6, 15, 0, 9, 10, 4, 5, 3}},
138
139 {{12, 1, 10, 15, 9, 2, 6, 8, 0, 13, 3, 4, 14, 7, 5, 11},
140 {10, 15, 4, 2, 7, 12, 9, 5, 6, 1, 13, 14, 0, 11, 3, 8},
141 {9, 14, 15, 5, 2, 8, 12, 3, 7, 0, 4, 10, 1, 13, 11, 6},
142 {4, 3, 2, 12, 9, 5, 15, 10, 11, 14, 1, 7, 6, 0, 8, 13}},
143
144 {{4, 11, 2, 14, 15, 0, 8, 13, 3, 12, 9, 7, 5, 10, 6, 1},
145 {13, 0, 11, 7, 4, 9, 1, 10, 14, 3, 5, 12, 2, 15, 8, 6},
146 {1, 4, 11, 13, 12, 3, 7, 14, 10, 15, 6, 8, 0, 5, 9, 2},
147 {6, 11, 13, 8, 1, 4, 10, 7, 9, 5, 0, 15, 14, 2, 3, 12}},
148
149 {{13, 2, 8, 4, 6, 15, 11, 1, 10, 9, 3, 14, 5, 0, 12, 7},
150 {1, 15, 13, 8, 10, 3, 7, 4, 12, 5, 6, 11, 0, 14, 9, 2},
151 {7, 11, 4, 1, 9, 12, 14, 2, 0, 6, 10, 13, 15, 3, 5, 8},
152 {2, 1, 14, 7, 4, 10, 8, 13, 15, 12, 9, 0, 3, 5, 6, 11}}
153};
154
155static void
156permute(char *out, char *in, uchar * p, int n)
157{
158 int i;
159 for (i = 0; i < n; i++)
160 out[i] = in[p[i] - 1];
161}
162
163static void
164lshift(char *d, int count, int n)
165{
166 char out[64];
167 int i;
168 for (i = 0; i < n; i++)
169 out[i] = d[(i + count) % n];
170 for (i = 0; i < n; i++)
171 d[i] = out[i];
172}
173
174static void
175concat(char *out, char *in1, char *in2, int l1, int l2)
176{
177 while (l1--)
178 *out++ = *in1++;
179 while (l2--)
180 *out++ = *in2++;
181}
182
183static void
184xor(char *out, char *in1, char *in2, int n)
185{
186 int i;
187 for (i = 0; i < n; i++)
188 out[i] = in1[i] ^ in2[i];
189}
190
191static void
192dohash(char *out, char *in, char *key, int forw)
193{
194 int i, j, k;
195 char *pk1;
196 char c[28];
197 char d[28];
198 char *cd;
199 char ki[16][48];
200 char *pd1;
201 char l[32], r[32];
202 char *rl;
203
204 /* Have to reduce stack usage */
205 pk1 = kmalloc(56+56+64+64,GFP_KERNEL);
206 if(pk1 == NULL)
207 return;
208
209 cd = pk1 + 56;
210 pd1= cd + 56;
211 rl = pd1 + 64;
212
213 permute(pk1, key, perm1, 56);
214
215 for (i = 0; i < 28; i++)
216 c[i] = pk1[i];
217 for (i = 0; i < 28; i++)
218 d[i] = pk1[i + 28];
219
220 for (i = 0; i < 16; i++) {
221 lshift(c, sc[i], 28);
222 lshift(d, sc[i], 28);
223
224 concat(cd, c, d, 28, 28);
225 permute(ki[i], cd, perm2, 48);
226 }
227
228 permute(pd1, in, perm3, 64);
229
230 for (j = 0; j < 32; j++) {
231 l[j] = pd1[j];
232 r[j] = pd1[j + 32];
233 }
234
235 for (i = 0; i < 16; i++) {
236 char *er; /* er[48] */
237 char *erk; /* erk[48] */
238 char b[8][6];
239 char *cb; /* cb[32] */
240 char *pcb; /* pcb[32] */
241 char *r2; /* r2[32] */
242
243 er = kmalloc(48+48+32+32+32, GFP_KERNEL);
244 if(er == NULL) {
245 kfree(pk1);
246 return;
247 }
248 erk = er+48;
249 cb = erk+48;
250 pcb = cb+32;
251 r2 = pcb+32;
252
253 permute(er, r, perm4, 48);
254
255 xor(erk, er, ki[forw ? i : 15 - i], 48);
256
257 for (j = 0; j < 8; j++)
258 for (k = 0; k < 6; k++)
259 b[j][k] = erk[j * 6 + k];
260
261 for (j = 0; j < 8; j++) {
262 int m, n;
263 m = (b[j][0] << 1) | b[j][5];
264
265 n = (b[j][1] << 3) | (b[j][2] << 2) | (b[j][3] <<
266 1) | b[j][4];
267
268 for (k = 0; k < 4; k++)
269 b[j][k] =
270 (sbox[j][m][n] & (1 << (3 - k))) ? 1 : 0;
271 }
272
273 for (j = 0; j < 8; j++)
274 for (k = 0; k < 4; k++)
275 cb[j * 4 + k] = b[j][k];
276 permute(pcb, cb, perm5, 32);
277
278 xor(r2, l, pcb, 32);
279
280 for (j = 0; j < 32; j++)
281 l[j] = r[j];
282
283 for (j = 0; j < 32; j++)
284 r[j] = r2[j];
285
286 kfree(er);
287 }
288
289 concat(rl, r, l, 32, 32);
290
291 permute(out, rl, perm6, 64);
292 kfree(pk1);
293}
294
295static void
296str_to_key(unsigned char *str, unsigned char *key)
297{
298 int i;
299
300 key[0] = str[0] >> 1;
301 key[1] = ((str[0] & 0x01) << 6) | (str[1] >> 2);
302 key[2] = ((str[1] & 0x03) << 5) | (str[2] >> 3);
303 key[3] = ((str[2] & 0x07) << 4) | (str[3] >> 4);
304 key[4] = ((str[3] & 0x0F) << 3) | (str[4] >> 5);
305 key[5] = ((str[4] & 0x1F) << 2) | (str[5] >> 6);
306 key[6] = ((str[5] & 0x3F) << 1) | (str[6] >> 7);
307 key[7] = str[6] & 0x7F;
308 for (i = 0; i < 8; i++) {
309 key[i] = (key[i] << 1);
310 }
311}
312
313static void
314smbhash(unsigned char *out, unsigned char *in, unsigned char *key, int forw)
315{
316 int i;
317 char *outb; /* outb[64] */
318 char *inb; /* inb[64] */
319 char *keyb; /* keyb[64] */
320 unsigned char key2[8];
321
322 outb = kmalloc(64 * 3,GFP_KERNEL);
323 if(outb == NULL)
324 return;
325
326 inb = outb + 64;
327 keyb = inb + 64;
328
329 str_to_key(key, key2);
330
331 for (i = 0; i < 64; i++) {
332 inb[i] = (in[i / 8] & (1 << (7 - (i % 8)))) ? 1 : 0;
333 keyb[i] = (key2[i / 8] & (1 << (7 - (i % 8)))) ? 1 : 0;
334 outb[i] = 0;
335 }
336
337 dohash(outb, inb, keyb, forw);
338
339 for (i = 0; i < 8; i++) {
340 out[i] = 0;
341 }
342
343 for (i = 0; i < 64; i++) {
344 if (outb[i])
345 out[i / 8] |= (1 << (7 - (i % 8)));
346 }
347 kfree(outb);
348}
349
350void
351E_P16(unsigned char *p14, unsigned char *p16)
352{
353 unsigned char sp8[8] =
354 { 0x4b, 0x47, 0x53, 0x21, 0x40, 0x23, 0x24, 0x25 };
355 smbhash(p16, sp8, p14, 1);
356 smbhash(p16 + 8, sp8, p14 + 7, 1);
357}
358
359void
360E_P24(unsigned char *p21, unsigned char *c8, unsigned char *p24)
361{
362 smbhash(p24, c8, p21, 1);
363 smbhash(p24 + 8, c8, p21 + 7, 1);
364 smbhash(p24 + 16, c8, p21 + 14, 1);
365}
366
367void
368D_P16(unsigned char *p14, unsigned char *in, unsigned char *out)
369{
370 smbhash(out, in, p14, 0);
371 smbhash(out + 8, in + 8, p14 + 7, 0);
372}
373
374void
375E_old_pw_hash(unsigned char *p14, unsigned char *in, unsigned char *out)
376{
377 smbhash(out, in, p14, 1);
378 smbhash(out + 8, in + 8, p14 + 7, 1);
379}
380#if 0
381/* these routines are currently unneeded, but may be
382 needed later */
383void
384cred_hash1(unsigned char *out, unsigned char *in, unsigned char *key)
385{
386 unsigned char buf[8];
387
388 smbhash(buf, in, key, 1);
389 smbhash(out, buf, key + 9, 1);
390}
391
392void
393cred_hash2(unsigned char *out, unsigned char *in, unsigned char *key)
394{
395 unsigned char buf[8];
396 static unsigned char key2[8];
397
398 smbhash(buf, in, key, 1);
399 key2[0] = key[7];
400 smbhash(out, buf, key2, 1);
401}
402
403void
404cred_hash3(unsigned char *out, unsigned char *in, unsigned char *key, int forw)
405{
406 static unsigned char key2[8];
407
408 smbhash(out, in, key, forw);
409 key2[0] = key[7];
410 smbhash(out + 8, in + 8, key2, forw);
411}
412#endif /* unneeded routines */