41c768894297faaa3663635b8d5f2b94b102dadf
[gnupg.git] / cipher / des.c
1 /* des.c - DES and Triple-DES encryption/decryption Algorithm
2  *      Copyright (C) 1998 Free Software Foundation, Inc.
3  *
4  * Please see below for more legal information!
5  *
6  * According to the definition of DES in FIPS PUB 46-2 from December 1993.
7  * For a description of triple encryption, see:
8  *   Bruce Schneier: Applied Cryptography. Second Edition.
9  *   John Wiley & Sons, 1996. ISBN 0-471-12845-7. Pages 358 ff.
10  *
11  * This file is part of GnuPG.
12  *
13  * GnuPG is free software; you can redistribute it and/or modify
14  * it under the terms of the GNU General Public License as published by
15  * the Free Software Foundation; either version 2 of the License, or
16  * (at your option) any later version.
17  *
18  * GnuPG is distributed in the hope that it will be useful,
19  * but WITHOUT ANY WARRANTY; without even the implied warranty of
20  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
21  * GNU General Public License for more details.
22  *
23  * You should have received a copy of the GNU General Public License
24  * along with this program; if not, write to the Free Software
25  * Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA
26  */
27
28
29 /*
30  * Written by Michael Roth <mroth@nessie.de>, September 1998
31  */
32
33
34 /*
35  *  U S A G E
36  * ===========
37  *
38  * For DES or Triple-DES encryption/decryption you must initialize a proper
39  * encryption context with a key.
40  *
41  * A DES key is 64bit wide but only 56bits of the key are used. The remaining
42  * bits are parity bits and they will _not_ checked in this implementation, but
43  * simply ignored.
44  *
45  * For Tripple-DES you could use either two 64bit keys or three 64bit keys.
46  * The parity bits will _not_ checked, too.
47  *
48  * After initializing a context with a key you could use this context to
49  * encrypt or decrypt data in 64bit blocks in Electronic Codebook Mode.
50  *
51  * (In the examples below the slashes at the beginning and ending of comments
52  * are omited.)
53  *
54  * DES Example
55  * -----------
56  *     unsigned char key[8];
57  *     unsigned char plaintext[8];
58  *     unsigned char ciphertext[8];
59  *     unsigned char recoverd[8];
60  *     des_ctx context;
61  *
62  *     * Fill 'key' and 'plaintext' with some data *
63  *     ....
64  *
65  *     * Set up the DES encryption context *
66  *     des_setkey(context, key);
67  *
68  *     * Encrypt the plaintext *
69  *     des_ecb_encrypt(context, plaintext, ciphertext);
70  *
71  *     * To recover the orginal plaintext from ciphertext use: *
72  *     des_ecb_decrypt(context, ciphertext, recoverd);
73  *
74  *
75  * Triple-DES Example
76  * ------------------
77  *     unsigned char key1[8];
78  *     unsigned char key2[8];
79  *     unsigned char key3[8];
80  *     unsigned char plaintext[8];
81  *     unsigned char ciphertext[8];
82  *     unsigned char recoverd[8];
83  *     tripledes_ctx context;
84  *
85  *     * If you would like to use two 64bit keys, fill 'key1' and'key2'
86  *       then setup the encryption context: *
87  *     tripledes_set2keys(context, key1, key2);
88  *
89  *     * To use three 64bit keys with Triple-DES use: *
90  *     tripledes_set3keys(context, key1, key2, key3);
91  *
92  *     * Encrypting plaintext with Triple-DES *
93  *     tripledes_ecb_encrypt(context, plaintext, ciphertext);
94  *
95  *     * Decrypting ciphertext to recover the plaintext with Triple-DES *
96  *     tripledes_ecb_decrypt(context, ciphertext, recoverd);
97  *
98  *
99  * Selftest
100  * --------
101  *     char *error_msg;
102  *
103  *     * To perform a selftest of this DES/Triple-DES implementation use the
104  *       function selftest(). It will return an error string if their are
105  *       some problems with this library. *
106  *
107  *     if ( (error_msg = selftest()) )
108  *     {
109  *         fprintf(stderr, "An error in the DES/Tripple-DES implementation occured: %s\n", error_msg);
110  *         abort();
111  *     }
112  */
113
114
115 #include <config.h>
116 #include <string.h>            /* memcpy, memcmp */
117 #include <assert.h>
118 #include "types.h"             /* for byte and u32 typedefs */
119 #include "util.h"              /* for log_fatal() */
120 #include "des.h"
121
122
123 /* Some defines/checks to support standalone modules */
124
125 #ifndef CIPHER_ALGO_3DES
126   #define CIPHER_ALGO_3DES 2
127 #elif CIPHER_ALGO_3DES != 2
128   #error CIPHER_ALGO_3DES is defined to a wrong value.
129 #endif
130
131 #ifndef G10ERR_WEAK_KEY
132   #define G10ERR_WEAK_KEY 43
133 #elif G10ERR_WEAK_KEY != 43
134   #error G10ERR_WEAK_KEY is defined to a wrong value.
135 #endif
136
137 #ifndef G10ERR_WRONG_KEYLEN
138   #define G10ERR_WRONG_KEYLEN 44
139 #elif G10ERR_WRONG_KEYLEN != 44
140   #error G10ERR_WRONG_KEYLEN is defined to a wrong value.
141 #endif
142
143
144
145 /* Macros used by the info function. */
146 #define FNCCAST_SETKEY(f)  ((int(*)(void*, byte*, unsigned))(f))
147 #define FNCCAST_CRYPT(f)   ((void(*)(void*, byte*, byte*))(f))
148
149
150 /*
151  * Encryption/Decryption context of DES
152  */
153 typedef struct _des_ctx
154   {
155     u32 encrypt_subkeys[32];
156     u32 decrypt_subkeys[32];
157   }
158 des_ctx[1];
159
160 /*
161  * Encryption/Decryption context of Triple-DES
162  */
163 typedef struct _tripledes_ctx
164   {
165     u32 encrypt_subkeys[96];
166     u32 decrypt_subkeys[96];
167   }
168 tripledes_ctx[1];
169
170
171 static void des_key_schedule (const byte *, u32 *);
172 static int des_setkey (struct _des_ctx *, const byte *);
173 static int des_ecb_crypt (struct _des_ctx *, const byte *, byte *, int);
174 static int tripledes_set2keys (struct _tripledes_ctx *, const byte *, const byte *);
175 static int tripledes_set3keys (struct _tripledes_ctx *, const byte *, const byte *, const byte *);
176 static int tripledes_ecb_crypt (struct _tripledes_ctx *, const byte *, byte *, int);
177 static int is_weak_key ( const byte *key );
178 static const char *selftest (void);
179
180
181
182
183
184
185 /*
186  * The s-box values are permuted according to the 'primitive function P'
187  */
188 static u32 sbox1[64] =
189 {
190   0x00808200, 0x00000000, 0x00008000, 0x00808202, 0x00808002, 0x00008202, 0x00000002, 0x00008000,
191   0x00000200, 0x00808200, 0x00808202, 0x00000200, 0x00800202, 0x00808002, 0x00800000, 0x00000002,
192   0x00000202, 0x00800200, 0x00800200, 0x00008200, 0x00008200, 0x00808000, 0x00808000, 0x00800202,
193   0x00008002, 0x00800002, 0x00800002, 0x00008002, 0x00000000, 0x00000202, 0x00008202, 0x00800000,
194   0x00008000, 0x00808202, 0x00000002, 0x00808000, 0x00808200, 0x00800000, 0x00800000, 0x00000200,
195   0x00808002, 0x00008000, 0x00008200, 0x00800002, 0x00000200, 0x00000002, 0x00800202, 0x00008202,
196   0x00808202, 0x00008002, 0x00808000, 0x00800202, 0x00800002, 0x00000202, 0x00008202, 0x00808200,
197   0x00000202, 0x00800200, 0x00800200, 0x00000000, 0x00008002, 0x00008200, 0x00000000, 0x00808002
198 };
199
200 static u32 sbox2[64] =
201 {
202   0x40084010, 0x40004000, 0x00004000, 0x00084010, 0x00080000, 0x00000010, 0x40080010, 0x40004010,
203   0x40000010, 0x40084010, 0x40084000, 0x40000000, 0x40004000, 0x00080000, 0x00000010, 0x40080010,
204   0x00084000, 0x00080010, 0x40004010, 0x00000000, 0x40000000, 0x00004000, 0x00084010, 0x40080000,
205   0x00080010, 0x40000010, 0x00000000, 0x00084000, 0x00004010, 0x40084000, 0x40080000, 0x00004010,
206   0x00000000, 0x00084010, 0x40080010, 0x00080000, 0x40004010, 0x40080000, 0x40084000, 0x00004000,
207   0x40080000, 0x40004000, 0x00000010, 0x40084010, 0x00084010, 0x00000010, 0x00004000, 0x40000000,
208   0x00004010, 0x40084000, 0x00080000, 0x40000010, 0x00080010, 0x40004010, 0x40000010, 0x00080010,
209   0x00084000, 0x00000000, 0x40004000, 0x00004010, 0x40000000, 0x40080010, 0x40084010, 0x00084000
210 };
211
212 static u32 sbox3[64] =
213 {
214   0x00000104, 0x04010100, 0x00000000, 0x04010004, 0x04000100, 0x00000000, 0x00010104, 0x04000100,
215   0x00010004, 0x04000004, 0x04000004, 0x00010000, 0x04010104, 0x00010004, 0x04010000, 0x00000104,
216   0x04000000, 0x00000004, 0x04010100, 0x00000100, 0x00010100, 0x04010000, 0x04010004, 0x00010104,
217   0x04000104, 0x00010100, 0x00010000, 0x04000104, 0x00000004, 0x04010104, 0x00000100, 0x04000000,
218   0x04010100, 0x04000000, 0x00010004, 0x00000104, 0x00010000, 0x04010100, 0x04000100, 0x00000000,
219   0x00000100, 0x00010004, 0x04010104, 0x04000100, 0x04000004, 0x00000100, 0x00000000, 0x04010004,
220   0x04000104, 0x00010000, 0x04000000, 0x04010104, 0x00000004, 0x00010104, 0x00010100, 0x04000004,
221   0x04010000, 0x04000104, 0x00000104, 0x04010000, 0x00010104, 0x00000004, 0x04010004, 0x00010100
222 };
223
224 static u32 sbox4[64] =
225 {
226   0x80401000, 0x80001040, 0x80001040, 0x00000040, 0x00401040, 0x80400040, 0x80400000, 0x80001000,
227   0x00000000, 0x00401000, 0x00401000, 0x80401040, 0x80000040, 0x00000000, 0x00400040, 0x80400000,
228   0x80000000, 0x00001000, 0x00400000, 0x80401000, 0x00000040, 0x00400000, 0x80001000, 0x00001040,
229   0x80400040, 0x80000000, 0x00001040, 0x00400040, 0x00001000, 0x00401040, 0x80401040, 0x80000040,
230   0x00400040, 0x80400000, 0x00401000, 0x80401040, 0x80000040, 0x00000000, 0x00000000, 0x00401000,
231   0x00001040, 0x00400040, 0x80400040, 0x80000000, 0x80401000, 0x80001040, 0x80001040, 0x00000040,
232   0x80401040, 0x80000040, 0x80000000, 0x00001000, 0x80400000, 0x80001000, 0x00401040, 0x80400040,
233   0x80001000, 0x00001040, 0x00400000, 0x80401000, 0x00000040, 0x00400000, 0x00001000, 0x00401040
234 };
235
236 static u32 sbox5[64] =
237 {
238   0x00000080, 0x01040080, 0x01040000, 0x21000080, 0x00040000, 0x00000080, 0x20000000, 0x01040000,
239   0x20040080, 0x00040000, 0x01000080, 0x20040080, 0x21000080, 0x21040000, 0x00040080, 0x20000000,
240   0x01000000, 0x20040000, 0x20040000, 0x00000000, 0x20000080, 0x21040080, 0x21040080, 0x01000080,
241   0x21040000, 0x20000080, 0x00000000, 0x21000000, 0x01040080, 0x01000000, 0x21000000, 0x00040080,
242   0x00040000, 0x21000080, 0x00000080, 0x01000000, 0x20000000, 0x01040000, 0x21000080, 0x20040080,
243   0x01000080, 0x20000000, 0x21040000, 0x01040080, 0x20040080, 0x00000080, 0x01000000, 0x21040000,
244   0x21040080, 0x00040080, 0x21000000, 0x21040080, 0x01040000, 0x00000000, 0x20040000, 0x21000000,
245   0x00040080, 0x01000080, 0x20000080, 0x00040000, 0x00000000, 0x20040000, 0x01040080, 0x20000080
246 };
247
248 static u32 sbox6[64] =
249 {
250   0x10000008, 0x10200000, 0x00002000, 0x10202008, 0x10200000, 0x00000008, 0x10202008, 0x00200000,
251   0x10002000, 0x00202008, 0x00200000, 0x10000008, 0x00200008, 0x10002000, 0x10000000, 0x00002008,
252   0x00000000, 0x00200008, 0x10002008, 0x00002000, 0x00202000, 0x10002008, 0x00000008, 0x10200008,
253   0x10200008, 0x00000000, 0x00202008, 0x10202000, 0x00002008, 0x00202000, 0x10202000, 0x10000000,
254   0x10002000, 0x00000008, 0x10200008, 0x00202000, 0x10202008, 0x00200000, 0x00002008, 0x10000008,
255   0x00200000, 0x10002000, 0x10000000, 0x00002008, 0x10000008, 0x10202008, 0x00202000, 0x10200000,
256   0x00202008, 0x10202000, 0x00000000, 0x10200008, 0x00000008, 0x00002000, 0x10200000, 0x00202008,
257   0x00002000, 0x00200008, 0x10002008, 0x00000000, 0x10202000, 0x10000000, 0x00200008, 0x10002008
258 };
259
260 static u32 sbox7[64] =
261 {
262   0x00100000, 0x02100001, 0x02000401, 0x00000000, 0x00000400, 0x02000401, 0x00100401, 0x02100400,
263   0x02100401, 0x00100000, 0x00000000, 0x02000001, 0x00000001, 0x02000000, 0x02100001, 0x00000401,
264   0x02000400, 0x00100401, 0x00100001, 0x02000400, 0x02000001, 0x02100000, 0x02100400, 0x00100001,
265   0x02100000, 0x00000400, 0x00000401, 0x02100401, 0x00100400, 0x00000001, 0x02000000, 0x00100400,
266   0x02000000, 0x00100400, 0x00100000, 0x02000401, 0x02000401, 0x02100001, 0x02100001, 0x00000001,
267   0x00100001, 0x02000000, 0x02000400, 0x00100000, 0x02100400, 0x00000401, 0x00100401, 0x02100400,
268   0x00000401, 0x02000001, 0x02100401, 0x02100000, 0x00100400, 0x00000000, 0x00000001, 0x02100401,
269   0x00000000, 0x00100401, 0x02100000, 0x00000400, 0x02000001, 0x02000400, 0x00000400, 0x00100001
270 };
271
272 static u32 sbox8[64] =
273 {
274   0x08000820, 0x00000800, 0x00020000, 0x08020820, 0x08000000, 0x08000820, 0x00000020, 0x08000000,
275   0x00020020, 0x08020000, 0x08020820, 0x00020800, 0x08020800, 0x00020820, 0x00000800, 0x00000020,
276   0x08020000, 0x08000020, 0x08000800, 0x00000820, 0x00020800, 0x00020020, 0x08020020, 0x08020800,
277   0x00000820, 0x00000000, 0x00000000, 0x08020020, 0x08000020, 0x08000800, 0x00020820, 0x00020000,
278   0x00020820, 0x00020000, 0x08020800, 0x00000800, 0x00000020, 0x08020020, 0x00000800, 0x00020820,
279   0x08000800, 0x00000020, 0x08000020, 0x08020000, 0x08020020, 0x08000000, 0x00020000, 0x08000820,
280   0x00000000, 0x08020820, 0x00020020, 0x08000020, 0x08020000, 0x08000800, 0x08000820, 0x00000000,
281   0x08020820, 0x00020800, 0x00020800, 0x00000820, 0x00000820, 0x00020020, 0x08000000, 0x08020800
282 };
283
284
285
286 /*
287  * These two tables are part of the 'permuted choice 1' function.
288  * In this implementation several speed improvements are done.
289  */
290 u32 leftkey_swap[16] =
291 {
292   0x00000000, 0x00000001, 0x00000100, 0x00000101,
293   0x00010000, 0x00010001, 0x00010100, 0x00010101,
294   0x01000000, 0x01000001, 0x01000100, 0x01000101,
295   0x01010000, 0x01010001, 0x01010100, 0x01010101
296 };
297
298 u32 rightkey_swap[16] =
299 {
300   0x00000000, 0x01000000, 0x00010000, 0x01010000,
301   0x00000100, 0x01000100, 0x00010100, 0x01010100,
302   0x00000001, 0x01000001, 0x00010001, 0x01010001,
303   0x00000101, 0x01000101, 0x00010101, 0x01010101,
304 };
305
306
307
308 /*
309  * Numbers of left shifts per round for encryption subkey schedule
310  * To calculate the decryption key scheduling we just reverse the
311  * ordering of the subkeys so we can omit the table for decryption
312  * subkey schedule.
313  */
314 static byte encrypt_rotate_tab[16] =
315 {
316   1, 1, 2, 2, 2, 2, 2, 2, 1, 2, 2, 2, 2, 2, 2, 1
317 };
318
319
320
321 /*
322  * Table with weak DES keys sorted in ascending order.
323  * In DES their are 64 known keys wich are weak. They are weak
324  * because they produce only one, two or four different
325  * subkeys in the subkey scheduling process.
326  * The keys in this table have all their parity bits cleared.
327  */
328 static byte weak_keys[64][8] =
329 {
330   { 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00 },  { 0x00, 0x00, 0x1e, 0x1e, 0x00, 0x00, 0x0e, 0x0e },
331   { 0x00, 0x00, 0xe0, 0xe0, 0x00, 0x00, 0xf0, 0xf0 },  { 0x00, 0x00, 0xfe, 0xfe, 0x00, 0x00, 0xfe, 0xfe },
332   { 0x00, 0x1e, 0x00, 0x1e, 0x00, 0x0e, 0x00, 0x0e },  { 0x00, 0x1e, 0x1e, 0x00, 0x00, 0x0e, 0x0e, 0x00 },
333   { 0x00, 0x1e, 0xe0, 0xfe, 0x00, 0x0e, 0xf0, 0xfe },  { 0x00, 0x1e, 0xfe, 0xe0, 0x00, 0x0e, 0xfe, 0xf0 },
334   { 0x00, 0xe0, 0x00, 0xe0, 0x00, 0xf0, 0x00, 0xf0 },  { 0x00, 0xe0, 0x1e, 0xfe, 0x00, 0xf0, 0x0e, 0xfe },
335   { 0x00, 0xe0, 0xe0, 0x00, 0x00, 0xf0, 0xf0, 0x00 },  { 0x00, 0xe0, 0xfe, 0x1e, 0x00, 0xf0, 0xfe, 0x0e },
336   { 0x00, 0xfe, 0x00, 0xfe, 0x00, 0xfe, 0x00, 0xfe },  { 0x00, 0xfe, 0x1e, 0xe0, 0x00, 0xfe, 0x0e, 0xf0 },
337   { 0x00, 0xfe, 0xe0, 0x1e, 0x00, 0xfe, 0xf0, 0x0e },  { 0x00, 0xfe, 0xfe, 0x00, 0x00, 0xfe, 0xfe, 0x00 },
338   { 0x0e, 0x0e, 0x0e, 0x0e, 0xf0, 0xf0, 0xf0, 0xf0 },  { 0x1e, 0x00, 0x00, 0x1e, 0x0e, 0x00, 0x00, 0x0e },
339   { 0x1e, 0x00, 0x1e, 0x00, 0x0e, 0x00, 0x0e, 0x00 },  { 0x1e, 0x00, 0xe0, 0xfe, 0x0e, 0x00, 0xf0, 0xfe },
340   { 0x1e, 0x00, 0xfe, 0xe0, 0x0e, 0x00, 0xfe, 0xf0 },  { 0x1e, 0x1e, 0x00, 0x00, 0x0e, 0x0e, 0x00, 0x00 },
341   { 0x1e, 0x1e, 0x1e, 0x1e, 0x0e, 0x0e, 0x0e, 0x0e },  { 0x1e, 0x1e, 0xe0, 0xe0, 0x0e, 0x0e, 0xf0, 0xf0 },
342   { 0x1e, 0x1e, 0xfe, 0xfe, 0x0e, 0x0e, 0xfe, 0xfe },  { 0x1e, 0xe0, 0x00, 0xfe, 0x0e, 0xf0, 0x00, 0xfe },
343   { 0x1e, 0xe0, 0x1e, 0xe0, 0x0e, 0xf0, 0x0e, 0xf0 },  { 0x1e, 0xe0, 0xe0, 0x1e, 0x0e, 0xf0, 0xf0, 0x0e },
344   { 0x1e, 0xe0, 0xfe, 0x00, 0x0e, 0xf0, 0xfe, 0x00 },  { 0x1e, 0xfe, 0x00, 0xe0, 0x0e, 0xfe, 0x00, 0xf0 },
345   { 0x1e, 0xfe, 0x1e, 0xfe, 0x0e, 0xfe, 0x0e, 0xfe },  { 0x1e, 0xfe, 0xe0, 0x00, 0x0e, 0xfe, 0xf0, 0x00 },
346   { 0x1e, 0xfe, 0xfe, 0x1e, 0x0e, 0xfe, 0xfe, 0x0e },  { 0xe0, 0x00, 0x00, 0xe0, 0xf0, 0x00, 0x00, 0xf0 },
347   { 0xe0, 0x00, 0x1e, 0xfe, 0xf0, 0x00, 0x0e, 0xfe },  { 0xe0, 0x00, 0xe0, 0x00, 0xf0, 0x00, 0xf0, 0x00 },
348   { 0xe0, 0x00, 0xfe, 0x1e, 0xf0, 0x00, 0xfe, 0x0e },  { 0xe0, 0x1e, 0x00, 0xfe, 0xf0, 0x0e, 0x00, 0xfe },
349   { 0xe0, 0x1e, 0x1e, 0xe0, 0xf0, 0x0e, 0x0e, 0xf0 },  { 0xe0, 0x1e, 0xe0, 0x1e, 0xf0, 0x0e, 0xf0, 0x0e },
350   { 0xe0, 0x1e, 0xfe, 0x00, 0xf0, 0x0e, 0xfe, 0x00 },  { 0xe0, 0xe0, 0x00, 0x00, 0xf0, 0xf0, 0x00, 0x00 },
351   { 0xe0, 0xe0, 0x1e, 0x1e, 0xf0, 0xf0, 0x0e, 0x0e },  { 0xe0, 0xe0, 0xfe, 0xfe, 0xf0, 0xf0, 0xfe, 0xfe },
352   { 0xe0, 0xfe, 0x00, 0x1e, 0xf0, 0xfe, 0x00, 0x0e },  { 0xe0, 0xfe, 0x1e, 0x00, 0xf0, 0xfe, 0x0e, 0x00 },
353   { 0xe0, 0xfe, 0xe0, 0xfe, 0xf0, 0xfe, 0xf0, 0xfe },  { 0xe0, 0xfe, 0xfe, 0xe0, 0xf0, 0xfe, 0xfe, 0xf0 },
354   { 0xfe, 0x00, 0x00, 0xfe, 0xfe, 0x00, 0x00, 0xfe },  { 0xfe, 0x00, 0x1e, 0xe0, 0xfe, 0x00, 0x0e, 0xf0 },
355   { 0xfe, 0x00, 0xe0, 0x1e, 0xfe, 0x00, 0xf0, 0x0e },  { 0xfe, 0x00, 0xfe, 0x00, 0xfe, 0x00, 0xfe, 0x00 },
356   { 0xfe, 0x1e, 0x00, 0xe0, 0xfe, 0x0e, 0x00, 0xf0 },  { 0xfe, 0x1e, 0x1e, 0xfe, 0xfe, 0x0e, 0x0e, 0xfe },
357   { 0xfe, 0x1e, 0xe0, 0x00, 0xfe, 0x0e, 0xf0, 0x00 },  { 0xfe, 0x1e, 0xfe, 0x1e, 0xfe, 0x0e, 0xfe, 0x0e },
358   { 0xfe, 0xe0, 0x00, 0x1e, 0xfe, 0xf0, 0x00, 0x0e },  { 0xfe, 0xe0, 0x1e, 0x00, 0xfe, 0xf0, 0x0e, 0x00 },
359   { 0xfe, 0xe0, 0xe0, 0xfe, 0xfe, 0xf0, 0xf0, 0xfe },  { 0xfe, 0xe0, 0xfe, 0xe0, 0xfe, 0xf0, 0xfe, 0xf0 },
360   { 0xfe, 0xfe, 0x00, 0x00, 0xfe, 0xfe, 0x00, 0x00 },  { 0xfe, 0xfe, 0x1e, 0x1e, 0xfe, 0xfe, 0x0e, 0x0e },
361   { 0xfe, 0xfe, 0xe0, 0xe0, 0xfe, 0xfe, 0xf0, 0xf0 },  { 0xfe, 0xfe, 0xfe, 0xfe, 0xfe, 0xfe, 0xfe, 0xfe }
362 };
363
364
365
366
367
368
369 /*
370  * Macro to swap bits across two words
371  */
372 #define DO_PERMUTATION(a, temp, b, offset, mask)        \
373     temp = ((a>>offset) ^ b) & mask;                    \
374     b ^= temp;                                          \
375     a ^= temp<<offset;
376
377
378 /*
379  * This performs the 'initial permutation' for the data to be encrypted or decrypted
380  */
381 #define INITIAL_PERMUTATION(left, temp, right)          \
382     DO_PERMUTATION(left, temp, right, 4, 0x0f0f0f0f)    \
383     DO_PERMUTATION(left, temp, right, 16, 0x0000ffff)   \
384     DO_PERMUTATION(right, temp, left, 2, 0x33333333)    \
385     DO_PERMUTATION(right, temp, left, 8, 0x00ff00ff)    \
386     DO_PERMUTATION(left, temp, right, 1, 0x55555555)
387
388
389 /*
390  * The 'inverse initial permutation'
391  */
392 #define FINAL_PERMUTATION(left, temp, right)            \
393     DO_PERMUTATION(left, temp, right, 1, 0x55555555)    \
394     DO_PERMUTATION(right, temp, left, 8, 0x00ff00ff)    \
395     DO_PERMUTATION(right, temp, left, 2, 0x33333333)    \
396     DO_PERMUTATION(left, temp, right, 16, 0x0000ffff)   \
397     DO_PERMUTATION(left, temp, right, 4, 0x0f0f0f0f)
398
399
400 /*
401  * A full DES round including 'expansion function', 'sbox substitution'
402  * and 'primitive function P' but without swapping the left and right word.
403  */
404 #define DES_ROUND(from, to, work, subkey)               \
405     work = ((from<<1) | (from>>31)) ^ *subkey++;        \
406     to ^= sbox8[  work      & 0x3f ];                   \
407     to ^= sbox6[ (work>>8)  & 0x3f ];                   \
408     to ^= sbox4[ (work>>16) & 0x3f ];                   \
409     to ^= sbox2[ (work>>24) & 0x3f ];                   \
410     work = ((from>>3) | (from<<29)) ^ *subkey++;        \
411     to ^= sbox7[  work      & 0x3f ];                   \
412     to ^= sbox5[ (work>>8)  & 0x3f ];                   \
413     to ^= sbox3[ (work>>16) & 0x3f ];                   \
414     to ^= sbox1[ (work>>24) & 0x3f ];
415
416
417 /*
418  * Macros to convert 8 bytes from/to 32bit words
419  */
420 #define READ_64BIT_DATA(data, left, right)                                      \
421     left  = (data[0] << 24) | (data[1] << 16) | (data[2] << 8) | data[3];       \
422     right = (data[4] << 24) | (data[5] << 16) | (data[6] << 8) | data[7];
423
424 #define WRITE_64BIT_DATA(data, left, right)                                     \
425     data[0] = (left >> 24) &0xff; data[1] = (left >> 16) &0xff;                 \
426     data[2] = (left >> 8) &0xff; data[3] = left &0xff;                          \
427     data[4] = (right >> 24) &0xff; data[5] = (right >> 16) &0xff;               \
428     data[6] = (right >> 8) &0xff; data[7] = right &0xff;
429
430
431 /*
432  * Handy macros for encryption and decryption of data
433  */
434 #define des_ecb_encrypt(ctx, from, to)          des_ecb_crypt(ctx, from, to, 0)
435 #define des_ecb_decrypt(ctx, from, to)          des_ecb_crypt(ctx, from, to, 1)
436 #define tripledes_ecb_encrypt(ctx, from, to)    tripledes_ecb_crypt(ctx, from, to, 0)
437 #define tripledes_ecb_decrypt(ctx, from, to)    tripledes_ecb_crypt(ctx, from, to, 1)
438
439
440
441
442
443
444 /*
445  * des_key_schedule():    Calculate 16 subkeys pairs (even/odd) for
446  *                        16 encryption rounds.
447  *                        To calculate subkeys for decryption the caller
448  *                        have to reorder the generated subkeys.
449  *
450  *    rawkey:       8 Bytes of key data
451  *    subkey:       Array of at least 32 u32s. Will be filled
452  *                  with calculated subkeys.
453  *
454  */
455 static void
456 des_key_schedule (const byte * rawkey, u32 * subkey)
457 {
458   u32 left, right, work;
459   int round;
460
461   READ_64BIT_DATA (rawkey, left, right)
462
463   DO_PERMUTATION (right, work, left, 4, 0x0f0f0f0f)
464   DO_PERMUTATION (right, work, left, 0, 0x10101010)
465
466   left = (leftkey_swap[(left >> 0) & 0xf] << 3) | (leftkey_swap[(left >> 8) & 0xf] << 2)
467     | (leftkey_swap[(left >> 16) & 0xf] << 1) | (leftkey_swap[(left >> 24) & 0xf])
468     | (leftkey_swap[(left >> 5) & 0xf] << 7) | (leftkey_swap[(left >> 13) & 0xf] << 6)
469     | (leftkey_swap[(left >> 21) & 0xf] << 5) | (leftkey_swap[(left >> 29) & 0xf] << 4);
470
471   left &= 0x0fffffff;
472
473   right = (rightkey_swap[(right >> 1) & 0xf] << 3) | (rightkey_swap[(right >> 9) & 0xf] << 2)
474     | (rightkey_swap[(right >> 17) & 0xf] << 1) | (rightkey_swap[(right >> 25) & 0xf])
475     | (rightkey_swap[(right >> 4) & 0xf] << 7) | (rightkey_swap[(right >> 12) & 0xf] << 6)
476     | (rightkey_swap[(right >> 20) & 0xf] << 5) | (rightkey_swap[(right >> 28) & 0xf] << 4);
477
478   right &= 0x0fffffff;
479
480   for (round = 0; round < 16; ++round)
481     {
482       left = ((left << encrypt_rotate_tab[round]) | (left >> (28 - encrypt_rotate_tab[round]))) & 0x0fffffff;
483       right = ((right << encrypt_rotate_tab[round]) | (right >> (28 - encrypt_rotate_tab[round]))) & 0x0fffffff;
484
485       *subkey++ = ((left << 4) & 0x24000000)
486         | ((left << 28) & 0x10000000)
487         | ((left << 14) & 0x08000000)
488         | ((left << 18) & 0x02080000)
489         | ((left << 6) & 0x01000000)
490         | ((left << 9) & 0x00200000)
491         | ((left >> 1) & 0x00100000)
492         | ((left << 10) & 0x00040000)
493         | ((left << 2) & 0x00020000)
494         | ((left >> 10) & 0x00010000)
495         | ((right >> 13) & 0x00002000)
496         | ((right >> 4) & 0x00001000)
497         | ((right << 6) & 0x00000800)
498         | ((right >> 1) & 0x00000400)
499         | ((right >> 14) & 0x00000200)
500         | (right & 0x00000100)
501         | ((right >> 5) & 0x00000020)
502         | ((right >> 10) & 0x00000010)
503         | ((right >> 3) & 0x00000008)
504         | ((right >> 18) & 0x00000004)
505         | ((right >> 26) & 0x00000002)
506         | ((right >> 24) & 0x00000001);
507
508       *subkey++ = ((left << 15) & 0x20000000)
509         | ((left << 17) & 0x10000000)
510         | ((left << 10) & 0x08000000)
511         | ((left << 22) & 0x04000000)
512         | ((left >> 2) & 0x02000000)
513         | ((left << 1) & 0x01000000)
514         | ((left << 16) & 0x00200000)
515         | ((left << 11) & 0x00100000)
516         | ((left << 3) & 0x00080000)
517         | ((left >> 6) & 0x00040000)
518         | ((left << 15) & 0x00020000)
519         | ((left >> 4) & 0x00010000)
520         | ((right >> 2) & 0x00002000)
521         | ((right << 8) & 0x00001000)
522         | ((right >> 14) & 0x00000808)
523         | ((right >> 9) & 0x00000400)
524         | ((right) & 0x00000200)
525         | ((right << 7) & 0x00000100)
526         | ((right >> 7) & 0x00000020)
527         | ((right >> 3) & 0x00000011)
528         | ((right << 2) & 0x00000004)
529         | ((right >> 21) & 0x00000002);
530     }
531 }
532
533
534
535 /*
536  * Fill a DES context with subkeys calculated from a 64bit key.
537  * Does not check parity bits, but simply ignore them.
538  * Does not check for weak keys.
539  */
540 static int
541 des_setkey (struct _des_ctx *ctx, const byte * key)
542 {
543   int i;
544
545   des_key_schedule (key, ctx->encrypt_subkeys);
546
547   for(i=0; i<32; i+=2)
548     {
549       ctx->decrypt_subkeys[i]   = ctx->encrypt_subkeys[30-i];
550       ctx->decrypt_subkeys[i+1] = ctx->encrypt_subkeys[31-i];
551     }
552
553   return 0;
554 }
555
556
557
558 /*
559  * Electronic Codebook Mode DES encryption/decryption of data according
560  * to 'mode'.
561  */
562 static int
563 des_ecb_crypt (struct _des_ctx *ctx, const byte * from, byte * to, int mode)
564 {
565   u32 left, right, work;
566   u32 *keys;
567
568   keys = mode ? ctx->decrypt_subkeys : ctx->encrypt_subkeys;
569
570   READ_64BIT_DATA (from, left, right)
571   INITIAL_PERMUTATION (left, work, right)
572
573   DES_ROUND (right, left, work, keys) DES_ROUND (left, right, work, keys)
574   DES_ROUND (right, left, work, keys) DES_ROUND (left, right, work, keys)
575   DES_ROUND (right, left, work, keys) DES_ROUND (left, right, work, keys)
576   DES_ROUND (right, left, work, keys) DES_ROUND (left, right, work, keys)
577   DES_ROUND (right, left, work, keys) DES_ROUND (left, right, work, keys)
578   DES_ROUND (right, left, work, keys) DES_ROUND (left, right, work, keys)
579   DES_ROUND (right, left, work, keys) DES_ROUND (left, right, work, keys)
580   DES_ROUND (right, left, work, keys) DES_ROUND (left, right, work, keys)
581
582   FINAL_PERMUTATION (right, work, left)
583   WRITE_64BIT_DATA (to, right, left)
584
585   return 0;
586 }
587
588
589
590 /*
591  * Fill a Triple-DES context with subkeys calculated from two 64bit keys.
592  * Does not check the parity bits of the keys, but simply ignore them.
593  * Does not check for weak keys.
594  */
595 static int
596 tripledes_set2keys (struct _tripledes_ctx *ctx,
597                     const byte * key1,
598                     const byte * key2)
599 {
600   int i;
601
602   des_key_schedule (key1, ctx->encrypt_subkeys);
603   des_key_schedule (key2, &(ctx->decrypt_subkeys[32]));
604
605   for(i=0; i<32; i+=2)
606     {
607       ctx->decrypt_subkeys[i]    = ctx->encrypt_subkeys[30-i];
608       ctx->decrypt_subkeys[i+1]  = ctx->encrypt_subkeys[31-i];
609
610       ctx->encrypt_subkeys[i+32] = ctx->decrypt_subkeys[62-i];
611       ctx->encrypt_subkeys[i+33] = ctx->decrypt_subkeys[63-i];
612
613       ctx->encrypt_subkeys[i+64] = ctx->encrypt_subkeys[i];
614       ctx->encrypt_subkeys[i+65] = ctx->encrypt_subkeys[i+1];
615
616       ctx->decrypt_subkeys[i+64] = ctx->decrypt_subkeys[i];
617       ctx->decrypt_subkeys[i+65] = ctx->decrypt_subkeys[i+1];
618     }
619
620   return 0;
621 }
622
623
624
625 /*
626  * Fill a Triple-DES context with subkeys calculated from three 64bit keys.
627  * Does not check the parity bits of the keys, but simply ignore them.
628  * Does not check for weak keys.
629  */
630 static int
631 tripledes_set3keys (struct _tripledes_ctx *ctx,
632                     const byte * key1,
633                     const byte * key2,
634                     const byte * key3)
635 {
636   int i;
637
638   des_key_schedule (key1, ctx->encrypt_subkeys);
639   des_key_schedule (key2, &(ctx->decrypt_subkeys[32]));
640   des_key_schedule (key3, &(ctx->encrypt_subkeys[64]));
641
642   for(i=0; i<32; i+=2)
643     {
644       ctx->decrypt_subkeys[i]    = ctx->encrypt_subkeys[94-i];
645       ctx->decrypt_subkeys[i+1]  = ctx->encrypt_subkeys[95-i];
646
647       ctx->encrypt_subkeys[i+32] = ctx->decrypt_subkeys[62-i];
648       ctx->encrypt_subkeys[i+33] = ctx->decrypt_subkeys[63-i];
649
650       ctx->decrypt_subkeys[i+64] = ctx->encrypt_subkeys[30-i];
651       ctx->decrypt_subkeys[i+65] = ctx->encrypt_subkeys[31-i];
652     }
653
654   return 0;
655 }
656
657
658
659 /*
660  * Electronic Codebook Mode Triple-DES encryption/decryption of data according to 'mode'.
661  * Sometimes this mode is named 'EDE' mode (Encryption-Decryption-Encryption).
662  */
663 static int
664 tripledes_ecb_crypt (struct _tripledes_ctx *ctx, const byte * from, byte * to, int mode)
665 {
666   u32 left, right, work;
667   u32 *keys;
668
669   keys = mode ? ctx->decrypt_subkeys : ctx->encrypt_subkeys;
670
671   READ_64BIT_DATA (from, left, right)
672   INITIAL_PERMUTATION (left, work, right)
673
674   DES_ROUND (right, left, work, keys) DES_ROUND (left, right, work, keys)
675   DES_ROUND (right, left, work, keys) DES_ROUND (left, right, work, keys)
676   DES_ROUND (right, left, work, keys) DES_ROUND (left, right, work, keys)
677   DES_ROUND (right, left, work, keys) DES_ROUND (left, right, work, keys)
678   DES_ROUND (right, left, work, keys) DES_ROUND (left, right, work, keys)
679   DES_ROUND (right, left, work, keys) DES_ROUND (left, right, work, keys)
680   DES_ROUND (right, left, work, keys) DES_ROUND (left, right, work, keys)
681   DES_ROUND (right, left, work, keys) DES_ROUND (left, right, work, keys)
682
683   DES_ROUND (left, right, work, keys) DES_ROUND (right, left, work, keys)
684   DES_ROUND (left, right, work, keys) DES_ROUND (right, left, work, keys)
685   DES_ROUND (left, right, work, keys) DES_ROUND (right, left, work, keys)
686   DES_ROUND (left, right, work, keys) DES_ROUND (right, left, work, keys)
687   DES_ROUND (left, right, work, keys) DES_ROUND (right, left, work, keys)
688   DES_ROUND (left, right, work, keys) DES_ROUND (right, left, work, keys)
689   DES_ROUND (left, right, work, keys) DES_ROUND (right, left, work, keys)
690   DES_ROUND (left, right, work, keys) DES_ROUND (right, left, work, keys)
691
692   DES_ROUND (right, left, work, keys) DES_ROUND (left, right, work, keys)
693   DES_ROUND (right, left, work, keys) DES_ROUND (left, right, work, keys)
694   DES_ROUND (right, left, work, keys) DES_ROUND (left, right, work, keys)
695   DES_ROUND (right, left, work, keys) DES_ROUND (left, right, work, keys)
696   DES_ROUND (right, left, work, keys) DES_ROUND (left, right, work, keys)
697   DES_ROUND (right, left, work, keys) DES_ROUND (left, right, work, keys)
698   DES_ROUND (right, left, work, keys) DES_ROUND (left, right, work, keys)
699   DES_ROUND (right, left, work, keys) DES_ROUND (left, right, work, keys)
700
701   FINAL_PERMUTATION (right, work, left)
702   WRITE_64BIT_DATA (to, right, left)
703
704   return 0;
705 }
706
707
708
709 /*
710  * Check whether the 8 byte key is weak.
711  * Dose not check the parity bits of the key but simple ignore them.
712  */
713 static int
714 is_weak_key ( const byte *key )
715 {
716   byte work[8];
717   int i, left, right, middle, cmp_result;
718
719   /* clear parity bits */
720   for(i=0; i<8; ++i)
721      work[i] = key[i] & 0xfe;
722
723   /* binary search in the weak key table */
724   left = 0;
725   right = 63;
726   while(left <= right)
727     {
728       middle = (left + right) / 2;
729
730       if ( !(cmp_result=memcmp(work, weak_keys[middle], 8)) )
731           return -1;
732
733       if ( cmp_result > 0 )
734           left = middle + 1;
735       else
736           right = middle - 1;
737     }
738
739   return 0;
740 }
741
742
743
744 /*
745  * Performs a selftest of this DES/Triple-DES implementation.
746  * Returns an string with the error text on failure.
747  * Returns NULL if all is ok.
748  */
749 static const char *
750 selftest (void)
751 {
752   /*
753    * Check if 'u32' is really 32 bits wide. This DES / 3DES implementation
754    * need this.
755    */
756   if (sizeof (u32) != 4)
757        return "Wrong word size for DES configured.";
758
759   /*
760    * DES Maintenance Test
761    */
762   {
763     int i;
764     byte key[8] =
765     {0x55, 0x55, 0x55, 0x55, 0x55, 0x55, 0x55, 0x55};
766     byte input[8] =
767     {0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff};
768     byte result[8] =
769     {0x24, 0x6e, 0x9d, 0xb9, 0xc5, 0x50, 0x38, 0x1a};
770     byte temp1[8], temp2[8], temp3[8];
771     des_ctx des;
772
773     for (i = 0; i < 64; ++i)
774       {
775         des_setkey (des, key);
776         des_ecb_encrypt (des, input, temp1);
777         des_ecb_encrypt (des, temp1, temp2);
778         des_setkey (des, temp2);
779         des_ecb_decrypt (des, temp1, temp3);
780         memcpy (key, temp3, 8);
781         memcpy (input, temp1, 8);
782       }
783     if (memcmp (temp3, result, 8))
784       return "DES maintenance test failed.";
785   }
786
787
788   /*
789    * Triple-DES test  (Do somebody known on official test?)
790    *
791    * FIXME: This test doesn't use tripledes_set3keys() !
792    */
793   {
794     int i;
795     byte input[8] =
796     {0xfe, 0xdc, 0xba, 0x98, 0x76, 0x54, 0x32, 0x10};
797     byte key1[8] =
798     {0x12, 0x34, 0x56, 0x78, 0x9a, 0xbc, 0xde, 0xf0};
799     byte key2[8] =
800     {0x11, 0x22, 0x33, 0x44, 0xff, 0xaa, 0xcc, 0xdd};
801     byte result[8] =
802     {0x7b, 0x38, 0x3b, 0x23, 0xa2, 0x7d, 0x26, 0xd3};
803
804     tripledes_ctx des3;
805
806     for (i = 0; i < 16; ++i)
807       {
808         tripledes_set2keys (des3, key1, key2);
809         tripledes_ecb_encrypt (des3, input, key1);
810         tripledes_ecb_decrypt (des3, input, key2);
811         tripledes_set3keys (des3, key1, input, key2);
812         tripledes_ecb_encrypt (des3, input, input);
813       }
814     if (memcmp (input, result, 8))
815       return "TRIPLE-DES test failed.";
816   }
817
818
819   /*
820    * Check the weak key detection. We simply assume the table with
821    * weak keys is ok and check every key in the table if it is
822    * detected... (This test is a little bit stupid)
823    */
824   {
825     int i;
826
827     for (i = 0; i < 64; ++i)
828         if (!is_weak_key(weak_keys[i]))
829             return "DES weak key detection failed";
830   }
831
832   return 0;
833 }
834
835
836 static int
837 do_tripledes_setkey ( struct _tripledes_ctx *ctx, byte *key, unsigned keylen )
838 {
839     if( keylen != 24 )
840         return G10ERR_WRONG_KEYLEN;
841
842     tripledes_set3keys ( ctx, key, key+8, key+16);
843
844     if( is_weak_key( key ) || is_weak_key( key+8 ) || is_weak_key( key+16 ) )
845         return G10ERR_WEAK_KEY;
846
847     return 0;
848 }
849
850
851 static void
852 do_tripledes_encrypt( struct _tripledes_ctx *ctx, byte *outbuf, byte *inbuf )
853 {
854     tripledes_ecb_encrypt ( ctx, inbuf, outbuf );
855 }
856
857 static void
858 do_tripledes_decrypt( struct _tripledes_ctx *ctx, byte *outbuf, byte *inbuf )
859 {
860     tripledes_ecb_decrypt ( ctx, inbuf, outbuf );
861 }
862
863
864 /****************
865  * Return some information about the algorithm.  We need algo here to
866  * distinguish different flavors of the algorithm.
867  * Returns: A pointer to string describing the algorithm or NULL if
868  *          the ALGO is invalid.
869  */
870 const char *
871 des_get_info( int algo, size_t *keylen,
872                    size_t *blocksize, size_t *contextsize,
873                    int  (**r_setkey)( void *c, byte *key, unsigned keylen ),
874                    void (**r_encrypt)( void *c, byte *outbuf, byte *inbuf ),
875                    void (**r_decrypt)( void *c, byte *outbuf, byte *inbuf )
876                  )
877 {
878     static int did_selftest = 0;
879
880     if( !did_selftest ) {
881         const char *s = selftest();
882         if( s )
883             log_fatal("selftest failed: %s\n", s );
884         did_selftest = 1;
885     }
886
887
888     if( algo == CIPHER_ALGO_3DES ) {
889         *keylen = 192;
890         *blocksize = 8;
891         *contextsize = sizeof(struct _tripledes_ctx);
892         *r_setkey = FNCCAST_SETKEY(do_tripledes_setkey);
893         *r_encrypt= FNCCAST_CRYPT(do_tripledes_encrypt);
894         *r_decrypt= FNCCAST_CRYPT(do_tripledes_decrypt);
895         return "3DES";
896     }
897     return NULL;
898 }
899