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