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