Merge branch 'for-linus' of git://git.kernel.org/pub/scm/linux/kernel/git/roland...
[linux-2.6] / fs / cifs / 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    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
51 static 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
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
71 static 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
81 static 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
91 static 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
101 static 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
111 static uchar sc[16] = { 1, 1, 2, 2, 2, 2, 2, 2, 1, 2, 2, 2, 2, 2, 2, 1 };
112
113 static 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
155 static void
156 permute(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
163 static void
164 lshift(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
174 static void
175 concat(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
183 static void
184 xor(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
191 static void
192 dohash(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)[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         ki = kmalloc(16*48, GFP_KERNEL);
210         if (ki == NULL) {
211                 kfree(pk1);
212                 return;
213         }
214
215         cd = pk1 + 56;
216         pd1 = cd  + 56;
217         rl = pd1 + 64;
218
219         permute(pk1, key, perm1, 56);
220
221         for (i = 0; i < 28; i++)
222                 c[i] = pk1[i];
223         for (i = 0; i < 28; i++)
224                 d[i] = pk1[i + 28];
225
226         for (i = 0; i < 16; i++) {
227                 lshift(c, sc[i], 28);
228                 lshift(d, sc[i], 28);
229
230                 concat(cd, c, d, 28, 28);
231                 permute(ki[i], cd, perm2, 48);
232         }
233
234         permute(pd1, in, perm3, 64);
235
236         for (j = 0; j < 32; j++) {
237                 l[j] = pd1[j];
238                 r[j] = pd1[j + 32];
239         }
240
241         for (i = 0; i < 16; i++) {
242                 char *er;  /* er[48]  */
243                 char *erk; /* erk[48] */
244                 char b[8][6];
245                 char *cb;  /* cb[32]  */
246                 char *pcb; /* pcb[32] */
247                 char *r2;  /* r2[32]  */
248
249                 er = kmalloc(48+48+32+32+32, GFP_KERNEL);
250                 if (er == NULL) {
251                         kfree(pk1);
252                         kfree(ki);
253                         return;
254                 }
255                 erk = er+48;
256                 cb  = erk+48;
257                 pcb = cb+32;
258                 r2  = pcb+32;
259
260                 permute(er, r, perm4, 48);
261
262                 xor(erk, er, ki[forw ? i : 15 - i], 48);
263
264                 for (j = 0; j < 8; j++)
265                         for (k = 0; k < 6; k++)
266                                 b[j][k] = erk[j * 6 + k];
267
268                 for (j = 0; j < 8; j++) {
269                         int m, n;
270                         m = (b[j][0] << 1) | b[j][5];
271
272                         n = (b[j][1] << 3) | (b[j][2] << 2) | (b[j][3] <<
273                                                                1) | b[j][4];
274
275                         for (k = 0; k < 4; k++)
276                                 b[j][k] =
277                                     (sbox[j][m][n] & (1 << (3 - k))) ? 1 : 0;
278                 }
279
280                 for (j = 0; j < 8; j++)
281                         for (k = 0; k < 4; k++)
282                                 cb[j * 4 + k] = b[j][k];
283                 permute(pcb, cb, perm5, 32);
284
285                 xor(r2, l, pcb, 32);
286
287                 for (j = 0; j < 32; j++)
288                         l[j] = r[j];
289
290                 for (j = 0; j < 32; j++)
291                         r[j] = r2[j];
292
293                 kfree(er);
294         }
295
296         concat(rl, r, l, 32, 32);
297
298         permute(out, rl, perm6, 64);
299         kfree(pk1);
300         kfree(ki);
301 }
302
303 static void
304 str_to_key(unsigned char *str, unsigned char *key)
305 {
306         int i;
307
308         key[0] = str[0] >> 1;
309         key[1] = ((str[0] & 0x01) << 6) | (str[1] >> 2);
310         key[2] = ((str[1] & 0x03) << 5) | (str[2] >> 3);
311         key[3] = ((str[2] & 0x07) << 4) | (str[3] >> 4);
312         key[4] = ((str[3] & 0x0F) << 3) | (str[4] >> 5);
313         key[5] = ((str[4] & 0x1F) << 2) | (str[5] >> 6);
314         key[6] = ((str[5] & 0x3F) << 1) | (str[6] >> 7);
315         key[7] = str[6] & 0x7F;
316         for (i = 0; i < 8; i++)
317                 key[i] = (key[i] << 1);
318 }
319
320 static void
321 smbhash(unsigned char *out, unsigned char *in, unsigned char *key, int forw)
322 {
323         int i;
324         char *outb; /* outb[64] */
325         char *inb;  /* inb[64]  */
326         char *keyb; /* keyb[64] */
327         unsigned char key2[8];
328
329         outb = kmalloc(64 * 3, GFP_KERNEL);
330         if (outb == NULL)
331                 return;
332
333         inb  = outb + 64;
334         keyb = inb +  64;
335
336         str_to_key(key, key2);
337
338         for (i = 0; i < 64; i++) {
339                 inb[i] = (in[i / 8] & (1 << (7 - (i % 8)))) ? 1 : 0;
340                 keyb[i] = (key2[i / 8] & (1 << (7 - (i % 8)))) ? 1 : 0;
341                 outb[i] = 0;
342         }
343
344         dohash(outb, inb, keyb, forw);
345
346         for (i = 0; i < 8; i++)
347                 out[i] = 0;
348
349         for (i = 0; i < 64; i++) {
350                 if (outb[i])
351                         out[i / 8] |= (1 << (7 - (i % 8)));
352         }
353         kfree(outb);
354 }
355
356 void
357 E_P16(unsigned char *p14, unsigned char *p16)
358 {
359         unsigned char sp8[8] =
360             { 0x4b, 0x47, 0x53, 0x21, 0x40, 0x23, 0x24, 0x25 };
361         smbhash(p16, sp8, p14, 1);
362         smbhash(p16 + 8, sp8, p14 + 7, 1);
363 }
364
365 void
366 E_P24(unsigned char *p21, unsigned char *c8, unsigned char *p24)
367 {
368         smbhash(p24, c8, p21, 1);
369         smbhash(p24 + 8, c8, p21 + 7, 1);
370         smbhash(p24 + 16, c8, p21 + 14, 1);
371 }
372
373 #if 0 /* currently unsued */
374 static void
375 D_P16(unsigned char *p14, unsigned char *in, unsigned char *out)
376 {
377         smbhash(out, in, p14, 0);
378         smbhash(out + 8, in + 8, p14 + 7, 0);
379 }
380
381 static void
382 E_old_pw_hash(unsigned char *p14, unsigned char *in, unsigned char *out)
383 {
384         smbhash(out, in, p14, 1);
385         smbhash(out + 8, in + 8, p14 + 7, 1);
386 }
387 /* these routines are currently unneeded, but may be
388         needed later */
389 void
390 cred_hash1(unsigned char *out, unsigned char *in, unsigned char *key)
391 {
392         unsigned char buf[8];
393
394         smbhash(buf, in, key, 1);
395         smbhash(out, buf, key + 9, 1);
396 }
397
398 void
399 cred_hash2(unsigned char *out, unsigned char *in, unsigned char *key)
400 {
401         unsigned char buf[8];
402         static unsigned char key2[8];
403
404         smbhash(buf, in, key, 1);
405         key2[0] = key[7];
406         smbhash(out, buf, key2, 1);
407 }
408
409 void
410 cred_hash3(unsigned char *out, unsigned char *in, unsigned char *key, int forw)
411 {
412         static unsigned char key2[8];
413
414         smbhash(out, in, key, forw);
415         key2[0] = key[7];
416         smbhash(out + 8, in + 8, key2, forw);
417 }
418 #endif /* unneeded routines */