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