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