Import wpa_supplicant 0.5.8
[dragonfly.git] / contrib / wpa_supplicant-0.5.8 / des.c
1 /*
2  * DES and 3DES-EDE ciphers
3  *
4  * Modifications to LibTomCrypt implementation:
5  * Copyright (c) 2006, Jouni Malinen <j@w1.fi>
6  *
7  * This program is free software; you can redistribute it and/or modify
8  * it under the terms of the GNU General Public License version 2 as
9  * published by the Free Software Foundation.
10  *
11  * Alternatively, this software may be distributed under the terms of BSD
12  * license.
13  *
14  * See README and COPYING for more details.
15  */
16
17 #include "includes.h"
18
19 #include "common.h"
20 #include "crypto.h"
21
22
23 #ifdef INTERNAL_DES
24
25 /*
26  * This implementation is based on a DES implementation included in
27  * LibTomCrypt. The version here is modified to fit in wpa_supplicant/hostapd
28  * coding style.
29  */
30
31 /* LibTomCrypt, modular cryptographic library -- Tom St Denis
32  *
33  * LibTomCrypt is a library that provides various cryptographic
34  * algorithms in a highly modular and flexible manner.
35  *
36  * The library is free for all purposes without any express
37  * guarantee it works.
38  *
39  * Tom St Denis, tomstdenis@gmail.com, http://libtomcrypt.com
40  */
41
42 /**
43   DES code submitted by Dobes Vandermeer
44 */
45
46 #define ROLc(x, y) \
47         ((((unsigned long) (x) << (unsigned long) ((y) & 31)) | \
48           (((unsigned long) (x) & 0xFFFFFFFFUL) >> \
49            (unsigned long) (32 - ((y) & 31)))) & 0xFFFFFFFFUL)
50 #define RORc(x, y) \
51         (((((unsigned long) (x) & 0xFFFFFFFFUL) >> \
52            (unsigned long) ((y) & 31)) | \
53           ((unsigned long) (x) << (unsigned long) (32 - ((y) & 31)))) & \
54          0xFFFFFFFFUL)
55
56
57 static const u32 bytebit[8] =
58 {
59         0200, 0100, 040, 020, 010, 04, 02, 01 
60 };
61
62 static const u32 bigbyte[24] =
63 {
64         0x800000UL,  0x400000UL,  0x200000UL,  0x100000UL,
65         0x80000UL,   0x40000UL,   0x20000UL,   0x10000UL,
66         0x8000UL,    0x4000UL,    0x2000UL,    0x1000UL,
67         0x800UL,     0x400UL,     0x200UL,     0x100UL,
68         0x80UL,      0x40UL,      0x20UL,      0x10UL,
69         0x8UL,       0x4UL,       0x2UL,       0x1L 
70 };
71
72 /* Use the key schedule specific in the standard (ANSI X3.92-1981) */
73
74 static const u8 pc1[56] = {
75         56, 48, 40, 32, 24, 16,  8,  0, 57, 49, 41, 33, 25, 17,  
76          9,  1, 58, 50, 42, 34, 26, 18, 10,  2, 59, 51, 43, 35, 
77         62, 54, 46, 38, 30, 22, 14,  6, 61, 53, 45, 37, 29, 21,
78         13,  5, 60, 52, 44, 36, 28, 20, 12,  4, 27, 19, 11,  3 
79 };
80
81 static const u8 totrot[16] = {
82         1,   2,  4,  6,
83         8,  10, 12, 14, 
84         15, 17, 19, 21, 
85         23, 25, 27, 28
86 };
87
88 static const u8 pc2[48] = {
89         13, 16, 10, 23,  0,  4,      2, 27, 14,  5, 20,  9,
90         22, 18, 11,  3, 25,  7,     15,  6, 26, 19, 12,  1,
91         40, 51, 30, 36, 46, 54,     29, 39, 50, 44, 32, 47,
92         43, 48, 38, 55, 33, 52,     45, 41, 49, 35, 28, 31
93 };
94
95
96 static const u32 SP1[64] =
97 {
98         0x01010400UL, 0x00000000UL, 0x00010000UL, 0x01010404UL,
99         0x01010004UL, 0x00010404UL, 0x00000004UL, 0x00010000UL,
100         0x00000400UL, 0x01010400UL, 0x01010404UL, 0x00000400UL,
101         0x01000404UL, 0x01010004UL, 0x01000000UL, 0x00000004UL,
102         0x00000404UL, 0x01000400UL, 0x01000400UL, 0x00010400UL,
103         0x00010400UL, 0x01010000UL, 0x01010000UL, 0x01000404UL,
104         0x00010004UL, 0x01000004UL, 0x01000004UL, 0x00010004UL,
105         0x00000000UL, 0x00000404UL, 0x00010404UL, 0x01000000UL,
106         0x00010000UL, 0x01010404UL, 0x00000004UL, 0x01010000UL,
107         0x01010400UL, 0x01000000UL, 0x01000000UL, 0x00000400UL,
108         0x01010004UL, 0x00010000UL, 0x00010400UL, 0x01000004UL,
109         0x00000400UL, 0x00000004UL, 0x01000404UL, 0x00010404UL,
110         0x01010404UL, 0x00010004UL, 0x01010000UL, 0x01000404UL,
111         0x01000004UL, 0x00000404UL, 0x00010404UL, 0x01010400UL,
112         0x00000404UL, 0x01000400UL, 0x01000400UL, 0x00000000UL,
113         0x00010004UL, 0x00010400UL, 0x00000000UL, 0x01010004UL
114 };
115
116 static const u32 SP2[64] =
117 {
118         0x80108020UL, 0x80008000UL, 0x00008000UL, 0x00108020UL,
119         0x00100000UL, 0x00000020UL, 0x80100020UL, 0x80008020UL,
120         0x80000020UL, 0x80108020UL, 0x80108000UL, 0x80000000UL,
121         0x80008000UL, 0x00100000UL, 0x00000020UL, 0x80100020UL,
122         0x00108000UL, 0x00100020UL, 0x80008020UL, 0x00000000UL,
123         0x80000000UL, 0x00008000UL, 0x00108020UL, 0x80100000UL,
124         0x00100020UL, 0x80000020UL, 0x00000000UL, 0x00108000UL,
125         0x00008020UL, 0x80108000UL, 0x80100000UL, 0x00008020UL,
126         0x00000000UL, 0x00108020UL, 0x80100020UL, 0x00100000UL,
127         0x80008020UL, 0x80100000UL, 0x80108000UL, 0x00008000UL,
128         0x80100000UL, 0x80008000UL, 0x00000020UL, 0x80108020UL,
129         0x00108020UL, 0x00000020UL, 0x00008000UL, 0x80000000UL,
130         0x00008020UL, 0x80108000UL, 0x00100000UL, 0x80000020UL,
131         0x00100020UL, 0x80008020UL, 0x80000020UL, 0x00100020UL,
132         0x00108000UL, 0x00000000UL, 0x80008000UL, 0x00008020UL,
133         0x80000000UL, 0x80100020UL, 0x80108020UL, 0x00108000UL
134 };
135
136 static const u32 SP3[64] =
137 {
138         0x00000208UL, 0x08020200UL, 0x00000000UL, 0x08020008UL,
139         0x08000200UL, 0x00000000UL, 0x00020208UL, 0x08000200UL,
140         0x00020008UL, 0x08000008UL, 0x08000008UL, 0x00020000UL,
141         0x08020208UL, 0x00020008UL, 0x08020000UL, 0x00000208UL,
142         0x08000000UL, 0x00000008UL, 0x08020200UL, 0x00000200UL,
143         0x00020200UL, 0x08020000UL, 0x08020008UL, 0x00020208UL,
144         0x08000208UL, 0x00020200UL, 0x00020000UL, 0x08000208UL,
145         0x00000008UL, 0x08020208UL, 0x00000200UL, 0x08000000UL,
146         0x08020200UL, 0x08000000UL, 0x00020008UL, 0x00000208UL,
147         0x00020000UL, 0x08020200UL, 0x08000200UL, 0x00000000UL,
148         0x00000200UL, 0x00020008UL, 0x08020208UL, 0x08000200UL,
149         0x08000008UL, 0x00000200UL, 0x00000000UL, 0x08020008UL,
150         0x08000208UL, 0x00020000UL, 0x08000000UL, 0x08020208UL,
151         0x00000008UL, 0x00020208UL, 0x00020200UL, 0x08000008UL,
152         0x08020000UL, 0x08000208UL, 0x00000208UL, 0x08020000UL,
153         0x00020208UL, 0x00000008UL, 0x08020008UL, 0x00020200UL
154 };
155
156 static const u32 SP4[64] =
157 {
158         0x00802001UL, 0x00002081UL, 0x00002081UL, 0x00000080UL,
159         0x00802080UL, 0x00800081UL, 0x00800001UL, 0x00002001UL,
160         0x00000000UL, 0x00802000UL, 0x00802000UL, 0x00802081UL,
161         0x00000081UL, 0x00000000UL, 0x00800080UL, 0x00800001UL,
162         0x00000001UL, 0x00002000UL, 0x00800000UL, 0x00802001UL,
163         0x00000080UL, 0x00800000UL, 0x00002001UL, 0x00002080UL,
164         0x00800081UL, 0x00000001UL, 0x00002080UL, 0x00800080UL,
165         0x00002000UL, 0x00802080UL, 0x00802081UL, 0x00000081UL,
166         0x00800080UL, 0x00800001UL, 0x00802000UL, 0x00802081UL,
167         0x00000081UL, 0x00000000UL, 0x00000000UL, 0x00802000UL,
168         0x00002080UL, 0x00800080UL, 0x00800081UL, 0x00000001UL,
169         0x00802001UL, 0x00002081UL, 0x00002081UL, 0x00000080UL,
170         0x00802081UL, 0x00000081UL, 0x00000001UL, 0x00002000UL,
171         0x00800001UL, 0x00002001UL, 0x00802080UL, 0x00800081UL,
172         0x00002001UL, 0x00002080UL, 0x00800000UL, 0x00802001UL,
173         0x00000080UL, 0x00800000UL, 0x00002000UL, 0x00802080UL
174 };
175
176 static const u32 SP5[64] =
177 {
178         0x00000100UL, 0x02080100UL, 0x02080000UL, 0x42000100UL,
179         0x00080000UL, 0x00000100UL, 0x40000000UL, 0x02080000UL,
180         0x40080100UL, 0x00080000UL, 0x02000100UL, 0x40080100UL,
181         0x42000100UL, 0x42080000UL, 0x00080100UL, 0x40000000UL,
182         0x02000000UL, 0x40080000UL, 0x40080000UL, 0x00000000UL,
183         0x40000100UL, 0x42080100UL, 0x42080100UL, 0x02000100UL,
184         0x42080000UL, 0x40000100UL, 0x00000000UL, 0x42000000UL,
185         0x02080100UL, 0x02000000UL, 0x42000000UL, 0x00080100UL,
186         0x00080000UL, 0x42000100UL, 0x00000100UL, 0x02000000UL,
187         0x40000000UL, 0x02080000UL, 0x42000100UL, 0x40080100UL,
188         0x02000100UL, 0x40000000UL, 0x42080000UL, 0x02080100UL,
189         0x40080100UL, 0x00000100UL, 0x02000000UL, 0x42080000UL,
190         0x42080100UL, 0x00080100UL, 0x42000000UL, 0x42080100UL,
191         0x02080000UL, 0x00000000UL, 0x40080000UL, 0x42000000UL,
192         0x00080100UL, 0x02000100UL, 0x40000100UL, 0x00080000UL,
193         0x00000000UL, 0x40080000UL, 0x02080100UL, 0x40000100UL
194 };
195
196 static const u32 SP6[64] =
197 {
198         0x20000010UL, 0x20400000UL, 0x00004000UL, 0x20404010UL,
199         0x20400000UL, 0x00000010UL, 0x20404010UL, 0x00400000UL,
200         0x20004000UL, 0x00404010UL, 0x00400000UL, 0x20000010UL,
201         0x00400010UL, 0x20004000UL, 0x20000000UL, 0x00004010UL,
202         0x00000000UL, 0x00400010UL, 0x20004010UL, 0x00004000UL,
203         0x00404000UL, 0x20004010UL, 0x00000010UL, 0x20400010UL,
204         0x20400010UL, 0x00000000UL, 0x00404010UL, 0x20404000UL,
205         0x00004010UL, 0x00404000UL, 0x20404000UL, 0x20000000UL,
206         0x20004000UL, 0x00000010UL, 0x20400010UL, 0x00404000UL,
207         0x20404010UL, 0x00400000UL, 0x00004010UL, 0x20000010UL,
208         0x00400000UL, 0x20004000UL, 0x20000000UL, 0x00004010UL,
209         0x20000010UL, 0x20404010UL, 0x00404000UL, 0x20400000UL,
210         0x00404010UL, 0x20404000UL, 0x00000000UL, 0x20400010UL,
211         0x00000010UL, 0x00004000UL, 0x20400000UL, 0x00404010UL,
212         0x00004000UL, 0x00400010UL, 0x20004010UL, 0x00000000UL,
213         0x20404000UL, 0x20000000UL, 0x00400010UL, 0x20004010UL
214 };
215
216 static const u32 SP7[64] =
217 {
218         0x00200000UL, 0x04200002UL, 0x04000802UL, 0x00000000UL,
219         0x00000800UL, 0x04000802UL, 0x00200802UL, 0x04200800UL,
220         0x04200802UL, 0x00200000UL, 0x00000000UL, 0x04000002UL,
221         0x00000002UL, 0x04000000UL, 0x04200002UL, 0x00000802UL,
222         0x04000800UL, 0x00200802UL, 0x00200002UL, 0x04000800UL,
223         0x04000002UL, 0x04200000UL, 0x04200800UL, 0x00200002UL,
224         0x04200000UL, 0x00000800UL, 0x00000802UL, 0x04200802UL,
225         0x00200800UL, 0x00000002UL, 0x04000000UL, 0x00200800UL,
226         0x04000000UL, 0x00200800UL, 0x00200000UL, 0x04000802UL,
227         0x04000802UL, 0x04200002UL, 0x04200002UL, 0x00000002UL,
228         0x00200002UL, 0x04000000UL, 0x04000800UL, 0x00200000UL,
229         0x04200800UL, 0x00000802UL, 0x00200802UL, 0x04200800UL,
230         0x00000802UL, 0x04000002UL, 0x04200802UL, 0x04200000UL,
231         0x00200800UL, 0x00000000UL, 0x00000002UL, 0x04200802UL,
232         0x00000000UL, 0x00200802UL, 0x04200000UL, 0x00000800UL,
233         0x04000002UL, 0x04000800UL, 0x00000800UL, 0x00200002UL
234 };
235
236 static const u32 SP8[64] =
237 {
238         0x10001040UL, 0x00001000UL, 0x00040000UL, 0x10041040UL,
239         0x10000000UL, 0x10001040UL, 0x00000040UL, 0x10000000UL,
240         0x00040040UL, 0x10040000UL, 0x10041040UL, 0x00041000UL,
241         0x10041000UL, 0x00041040UL, 0x00001000UL, 0x00000040UL,
242         0x10040000UL, 0x10000040UL, 0x10001000UL, 0x00001040UL,
243         0x00041000UL, 0x00040040UL, 0x10040040UL, 0x10041000UL,
244         0x00001040UL, 0x00000000UL, 0x00000000UL, 0x10040040UL,
245         0x10000040UL, 0x10001000UL, 0x00041040UL, 0x00040000UL,
246         0x00041040UL, 0x00040000UL, 0x10041000UL, 0x00001000UL,
247         0x00000040UL, 0x10040040UL, 0x00001000UL, 0x00041040UL,
248         0x10001000UL, 0x00000040UL, 0x10000040UL, 0x10040000UL,
249         0x10040040UL, 0x10000000UL, 0x00040000UL, 0x10001040UL,
250         0x00000000UL, 0x10041040UL, 0x00040040UL, 0x10000040UL,
251         0x10040000UL, 0x10001000UL, 0x10001040UL, 0x00000000UL,
252         0x10041040UL, 0x00041000UL, 0x00041000UL, 0x00001040UL,
253         0x00001040UL, 0x00040040UL, 0x10000000UL, 0x10041000UL
254 };
255
256
257 static void cookey(const u32 *raw1, u32 *keyout)
258 {
259         u32 *cook;
260         const u32 *raw0;
261         u32 dough[32];
262         int i;
263
264         cook = dough;
265         for (i = 0; i < 16; i++, raw1++) {
266                 raw0 = raw1++;
267                 *cook    = (*raw0 & 0x00fc0000L) << 6;
268                 *cook   |= (*raw0 & 0x00000fc0L) << 10;
269                 *cook   |= (*raw1 & 0x00fc0000L) >> 10;
270                 *cook++ |= (*raw1 & 0x00000fc0L) >> 6;
271                 *cook    = (*raw0 & 0x0003f000L) << 12;
272                 *cook   |= (*raw0 & 0x0000003fL) << 16;
273                 *cook   |= (*raw1 & 0x0003f000L) >> 4;
274                 *cook++ |= (*raw1 & 0x0000003fL);
275         }
276
277         os_memcpy(keyout, dough, sizeof(dough));
278 }
279
280
281 static void deskey(const u8 *key, int decrypt, u32 *keyout)
282 {
283         u32 i, j, l, m, n, kn[32];
284         u8 pc1m[56], pcr[56];
285
286         for (j = 0; j < 56; j++) {
287                 l = (u32) pc1[j];
288                 m = l & 7;
289                 pc1m[j] = (u8)
290                         ((key[l >> 3U] & bytebit[m]) == bytebit[m] ? 1 : 0);
291         }
292
293         for (i = 0; i < 16; i++) {
294                 if (decrypt)
295                         m = (15 - i) << 1;
296                 else
297                         m = i << 1;
298                 n = m + 1;
299                 kn[m] = kn[n] = 0L;
300                 for (j = 0; j < 28; j++) {
301                         l = j + (u32) totrot[i];
302                         if (l < 28)
303                                 pcr[j] = pc1m[l];
304                         else
305                                 pcr[j] = pc1m[l - 28];
306                 }
307                 for (/* j = 28 */; j < 56; j++) {
308                         l = j + (u32) totrot[i];
309                         if (l < 56)
310                                 pcr[j] = pc1m[l];
311                         else
312                                 pcr[j] = pc1m[l - 28];
313                 }
314                 for (j = 0; j < 24; j++) {
315                         if ((int) pcr[(int) pc2[j]] != 0)
316                                 kn[m] |= bigbyte[j];
317                         if ((int) pcr[(int) pc2[j + 24]] != 0)
318                                 kn[n] |= bigbyte[j];
319                 }
320         }
321
322         cookey(kn, keyout);
323 }
324
325
326 static void desfunc(u32 *block, const u32 *keys)
327 {
328         u32 work, right, leftt;
329         int cur_round;
330
331         leftt = block[0];
332         right = block[1];
333
334         work = ((leftt >> 4)  ^ right) & 0x0f0f0f0fL;
335         right ^= work;
336         leftt ^= (work << 4);
337
338         work = ((leftt >> 16) ^ right) & 0x0000ffffL;
339         right ^= work;
340         leftt ^= (work << 16);
341
342         work = ((right >> 2)  ^ leftt) & 0x33333333L;
343         leftt ^= work;
344         right ^= (work << 2);
345
346         work = ((right >> 8)  ^ leftt) & 0x00ff00ffL;
347         leftt ^= work;
348         right ^= (work << 8);
349
350         right = ROLc(right, 1);
351         work = (leftt ^ right) & 0xaaaaaaaaL;
352
353         leftt ^= work;
354         right ^= work;
355         leftt = ROLc(leftt, 1);
356
357         for (cur_round = 0; cur_round < 8; cur_round++) {
358                 work  = RORc(right, 4) ^ *keys++;
359                 leftt ^= SP7[work        & 0x3fL]
360                         ^ SP5[(work >>  8) & 0x3fL]
361                         ^ SP3[(work >> 16) & 0x3fL]
362                         ^ SP1[(work >> 24) & 0x3fL];
363                 work  = right ^ *keys++;
364                 leftt ^= SP8[ work        & 0x3fL]
365                         ^  SP6[(work >>  8) & 0x3fL]
366                         ^  SP4[(work >> 16) & 0x3fL]
367                         ^  SP2[(work >> 24) & 0x3fL];
368
369                 work = RORc(leftt, 4) ^ *keys++;
370                 right ^= SP7[ work        & 0x3fL]
371                         ^  SP5[(work >>  8) & 0x3fL]
372                         ^  SP3[(work >> 16) & 0x3fL]
373                         ^  SP1[(work >> 24) & 0x3fL];
374                 work  = leftt ^ *keys++;
375                 right ^= SP8[ work        & 0x3fL]
376                         ^  SP6[(work >>  8) & 0x3fL]
377                         ^  SP4[(work >> 16) & 0x3fL]
378                         ^  SP2[(work >> 24) & 0x3fL];
379         }
380
381         right = RORc(right, 1);
382         work = (leftt ^ right) & 0xaaaaaaaaL;
383         leftt ^= work;
384         right ^= work;
385         leftt = RORc(leftt, 1);
386         work = ((leftt >> 8) ^ right) & 0x00ff00ffL;
387         right ^= work;
388         leftt ^= (work << 8);
389         /* -- */
390         work = ((leftt >> 2) ^ right) & 0x33333333L;
391         right ^= work;
392         leftt ^= (work << 2);
393         work = ((right >> 16) ^ leftt) & 0x0000ffffL;
394         leftt ^= work;
395         right ^= (work << 16);
396         work = ((right >> 4) ^ leftt) & 0x0f0f0f0fL;
397         leftt ^= work;
398         right ^= (work << 4);
399
400         block[0] = right;
401         block[1] = leftt;
402 }
403
404
405 /* wpa_supplicant/hostapd specific wrapper */
406
407 void des_encrypt(const u8 *clear, const u8 *key, u8 *cypher)
408 {
409         u8 pkey[8], next, tmp;
410         int i;
411         u32 ek[32], work[2];
412
413         /* Add parity bits to the key */
414         next = 0;
415         for (i = 0; i < 7; i++) {
416                 tmp = key[i];
417                 pkey[i] = (tmp >> i) | next | 1;
418                 next = tmp << (7 - i);
419         }
420         pkey[i] = next | 1;
421
422         deskey(pkey, 0, ek);
423
424         work[0] = WPA_GET_BE32(clear);
425         work[1] = WPA_GET_BE32(clear + 4);
426         desfunc(work, ek);
427         WPA_PUT_BE32(cypher, work[0]);
428         WPA_PUT_BE32(cypher + 4, work[1]);
429 }
430
431
432 struct des3_key_s {
433         u32 ek[3][32];
434         u32 dk[3][32];
435 };
436
437 void des3_key_setup(const u8 *key, struct des3_key_s *dkey)
438 {
439         deskey(key, 0, dkey->ek[0]);
440         deskey(key + 8, 1, dkey->ek[1]);
441         deskey(key + 16, 0, dkey->ek[2]);
442
443         deskey(key, 1, dkey->dk[2]);
444         deskey(key + 8, 0, dkey->dk[1]);
445         deskey(key + 16, 1, dkey->dk[0]);
446 }
447
448
449 void des3_encrypt(const u8 *plain, const struct des3_key_s *key, u8 *crypt)
450 {
451         u32 work[2];
452
453         work[0] = WPA_GET_BE32(plain);
454         work[1] = WPA_GET_BE32(plain + 4);
455         desfunc(work, key->ek[0]);
456         desfunc(work, key->ek[1]);
457         desfunc(work, key->ek[2]);
458         WPA_PUT_BE32(crypt, work[0]);
459         WPA_PUT_BE32(crypt + 4, work[1]);
460 }
461
462
463 void des3_decrypt(const u8 *crypt, const struct des3_key_s *key, u8 *plain)
464 {
465         u32 work[2];
466
467         work[0] = WPA_GET_BE32(crypt);
468         work[1] = WPA_GET_BE32(crypt + 4);
469         desfunc(work, key->dk[0]);
470         desfunc(work, key->dk[1]);
471         desfunc(work, key->dk[2]);
472         WPA_PUT_BE32(plain, work[0]);
473         WPA_PUT_BE32(plain + 4, work[1]);
474 }
475
476 #endif /* INTERNAL_DES */