36f90ffaae99d83ee54330726bfa64c64dc5e9a4
[libav.git] / libavutil / des.c
1 /*
2 * DES encryption/decryption
3 * Copyright (c) 2007 Reimar Doeffinger
4 *
5 * This file is part of FFmpeg.
6 *
7 * FFmpeg is free software; you can redistribute it and/or
8 * modify it under the terms of the GNU Lesser General Public
9 * License as published by the Free Software Foundation; either
10 * version 2.1 of the License, or (at your option) any later version.
11 *
12 * FFmpeg is distributed in the hope that it will be useful,
13 * but WITHOUT ANY WARRANTY; without even the implied warranty of
14 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
15 * Lesser General Public License for more details.
16 *
17 * You should have received a copy of the GNU Lesser General Public
18 * License along with FFmpeg; if not, write to the Free Software
19 * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA
20 */
21 #include <inttypes.h>
22 #include "des.h"
23
24 #define T(a, b, c, d, e, f, g, h) 64-a,64-b,64-c,64-d,64-e,64-f,64-g,64-h
25 static const uint8_t IP_shuffle[] = {
26 T(58, 50, 42, 34, 26, 18, 10, 2),
27 T(60, 52, 44, 36, 28, 20, 12, 4),
28 T(62, 54, 46, 38, 30, 22, 14, 6),
29 T(64, 56, 48, 40, 32, 24, 16, 8),
30 T(57, 49, 41, 33, 25, 17, 9, 1),
31 T(59, 51, 43, 35, 27, 19, 11, 3),
32 T(61, 53, 45, 37, 29, 21, 13, 5),
33 T(63, 55, 47, 39, 31, 23, 15, 7)
34 };
35 #undef T
36
37 #define T(a, b, c, d) 32-a,32-b,32-c,32-d
38 static const uint8_t P_shuffle[] = {
39 T(16, 7, 20, 21),
40 T(29, 12, 28, 17),
41 T( 1, 15, 23, 26),
42 T( 5, 18, 31, 10),
43 T( 2, 8, 24, 14),
44 T(32, 27, 3, 9),
45 T(19, 13, 30, 6),
46 T(22, 11, 4, 25)
47 };
48 #undef T
49
50 #define T(a, b, c, d, e, f, g) 64-a,64-b,64-c,64-d,64-e,64-f,64-g
51 static const uint8_t PC1_shuffle[] = {
52 T(57, 49, 41, 33, 25, 17, 9),
53 T( 1, 58, 50, 42, 34, 26, 18),
54 T(10, 2, 59, 51, 43, 35, 27),
55 T(19, 11, 3, 60, 52, 44, 36),
56 T(63, 55, 47, 39, 31, 23, 15),
57 T( 7, 62, 54, 46, 38, 30, 22),
58 T(14, 6, 61, 53, 45, 37, 29),
59 T(21, 13, 5, 28, 20, 12, 4)
60 };
61 #undef T
62
63 #define T(a, b, c, d, e, f) 56-a,56-b,56-c,56-d,56-e,56-f
64 static const uint8_t PC2_shuffle[] = {
65 T(14, 17, 11, 24, 1, 5),
66 T( 3, 28, 15, 6, 21, 10),
67 T(23, 19, 12, 4, 26, 8),
68 T(16, 7, 27, 20, 13, 2),
69 T(41, 52, 31, 37, 47, 55),
70 T(30, 40, 51, 45, 33, 48),
71 T(44, 49, 39, 56, 34, 53),
72 T(46, 42, 50, 36, 29, 32)
73 };
74 #undef T
75
76 #ifdef CONFIG_SMALL
77 static const uint8_t S_boxes[8][32] = {
78 {
79 0x0e, 0xf4, 0x7d, 0x41, 0xe2, 0x2f, 0xdb, 0x18, 0xa3, 0x6a, 0xc6, 0xbc, 0x95, 0x59, 0x30, 0x87,
80 0xf4, 0xc1, 0x8e, 0x28, 0x4d, 0x96, 0x12, 0x7b, 0x5f, 0xbc, 0x39, 0xe7, 0xa3, 0x0a, 0x65, 0xd0,
81 }, {
82 0x3f, 0xd1, 0x48, 0x7e, 0xf6, 0x2b, 0x83, 0xe4, 0xc9, 0x07, 0x12, 0xad, 0x6c, 0x90, 0xb5, 0x5a,
83 0xd0, 0x8e, 0xa7, 0x1b, 0x3a, 0xf4, 0x4d, 0x21, 0xb5, 0x68, 0x7c, 0xc6, 0x09, 0x53, 0xe2, 0x9f,
84 }, {
85 0xda, 0x70, 0x09, 0x9e, 0x36, 0x43, 0x6f, 0xa5, 0x21, 0x8d, 0x5c, 0xe7, 0xcb, 0xb4, 0xf2, 0x18,
86 0x1d, 0xa6, 0xd4, 0x09, 0x68, 0x9f, 0x83, 0x70, 0x4b, 0xf1, 0xe2, 0x3c, 0xb5, 0x5a, 0x2e, 0xc7,
87 }, {
88 0xd7, 0x8d, 0xbe, 0x53, 0x60, 0xf6, 0x09, 0x3a, 0x41, 0x72, 0x28, 0xc5, 0x1b, 0xac, 0xe4, 0x9f,
89 0x3a, 0xf6, 0x09, 0x60, 0xac, 0x1b, 0xd7, 0x8d, 0x9f, 0x41, 0x53, 0xbe, 0xc5, 0x72, 0x28, 0xe4,
90 }, {
91 0xe2, 0xbc, 0x24, 0xc1, 0x47, 0x7a, 0xdb, 0x16, 0x58, 0x05, 0xf3, 0xaf, 0x3d, 0x90, 0x8e, 0x69,
92 0xb4, 0x82, 0xc1, 0x7b, 0x1a, 0xed, 0x27, 0xd8, 0x6f, 0xf9, 0x0c, 0x95, 0xa6, 0x43, 0x50, 0x3e,
93 }, {
94 0xac, 0xf1, 0x4a, 0x2f, 0x79, 0xc2, 0x96, 0x58, 0x60, 0x1d, 0xd3, 0xe4, 0x0e, 0xb7, 0x35, 0x8b,
95 0x49, 0x3e, 0x2f, 0xc5, 0x92, 0x58, 0xfc, 0xa3, 0xb7, 0xe0, 0x14, 0x7a, 0x61, 0x0d, 0x8b, 0xd6,
96 }, {
97 0xd4, 0x0b, 0xb2, 0x7e, 0x4f, 0x90, 0x18, 0xad, 0xe3, 0x3c, 0x59, 0xc7, 0x25, 0xfa, 0x86, 0x61,
98 0x61, 0xb4, 0xdb, 0x8d, 0x1c, 0x43, 0xa7, 0x7e, 0x9a, 0x5f, 0x06, 0xf8, 0xe0, 0x25, 0x39, 0xc2,
99 }, {
100 0x1d, 0xf2, 0xd8, 0x84, 0xa6, 0x3f, 0x7b, 0x41, 0xca, 0x59, 0x63, 0xbe, 0x05, 0xe0, 0x9c, 0x27,
101 0x27, 0x1b, 0xe4, 0x71, 0x49, 0xac, 0x8e, 0xd2, 0xf0, 0xc6, 0x9a, 0x0d, 0x3f, 0x53, 0x65, 0xb8,
102 }
103 };
104 #else
105 /**
106 * This table contains the results of applying both the S-box and P-shuffle.
107 * It can be regenerated by compiling this file with -DCONFIG_SMALL -DTEST -DGENTABLES
108 */
109 static const uint32_t S_boxes_P_shuffle[8][64] = {
110 {
111 0x00808200, 0x00000000, 0x00008000, 0x00808202, 0x00808002, 0x00008202, 0x00000002, 0x00008000,
112 0x00000200, 0x00808200, 0x00808202, 0x00000200, 0x00800202, 0x00808002, 0x00800000, 0x00000002,
113 0x00000202, 0x00800200, 0x00800200, 0x00008200, 0x00008200, 0x00808000, 0x00808000, 0x00800202,
114 0x00008002, 0x00800002, 0x00800002, 0x00008002, 0x00000000, 0x00000202, 0x00008202, 0x00800000,
115 0x00008000, 0x00808202, 0x00000002, 0x00808000, 0x00808200, 0x00800000, 0x00800000, 0x00000200,
116 0x00808002, 0x00008000, 0x00008200, 0x00800002, 0x00000200, 0x00000002, 0x00800202, 0x00008202,
117 0x00808202, 0x00008002, 0x00808000, 0x00800202, 0x00800002, 0x00000202, 0x00008202, 0x00808200,
118 0x00000202, 0x00800200, 0x00800200, 0x00000000, 0x00008002, 0x00008200, 0x00000000, 0x00808002,
119 },
120 {
121 0x40084010, 0x40004000, 0x00004000, 0x00084010, 0x00080000, 0x00000010, 0x40080010, 0x40004010,
122 0x40000010, 0x40084010, 0x40084000, 0x40000000, 0x40004000, 0x00080000, 0x00000010, 0x40080010,
123 0x00084000, 0x00080010, 0x40004010, 0x00000000, 0x40000000, 0x00004000, 0x00084010, 0x40080000,
124 0x00080010, 0x40000010, 0x00000000, 0x00084000, 0x00004010, 0x40084000, 0x40080000, 0x00004010,
125 0x00000000, 0x00084010, 0x40080010, 0x00080000, 0x40004010, 0x40080000, 0x40084000, 0x00004000,
126 0x40080000, 0x40004000, 0x00000010, 0x40084010, 0x00084010, 0x00000010, 0x00004000, 0x40000000,
127 0x00004010, 0x40084000, 0x00080000, 0x40000010, 0x00080010, 0x40004010, 0x40000010, 0x00080010,
128 0x00084000, 0x00000000, 0x40004000, 0x00004010, 0x40000000, 0x40080010, 0x40084010, 0x00084000,
129 },
130 {
131 0x00000104, 0x04010100, 0x00000000, 0x04010004, 0x04000100, 0x00000000, 0x00010104, 0x04000100,
132 0x00010004, 0x04000004, 0x04000004, 0x00010000, 0x04010104, 0x00010004, 0x04010000, 0x00000104,
133 0x04000000, 0x00000004, 0x04010100, 0x00000100, 0x00010100, 0x04010000, 0x04010004, 0x00010104,
134 0x04000104, 0x00010100, 0x00010000, 0x04000104, 0x00000004, 0x04010104, 0x00000100, 0x04000000,
135 0x04010100, 0x04000000, 0x00010004, 0x00000104, 0x00010000, 0x04010100, 0x04000100, 0x00000000,
136 0x00000100, 0x00010004, 0x04010104, 0x04000100, 0x04000004, 0x00000100, 0x00000000, 0x04010004,
137 0x04000104, 0x00010000, 0x04000000, 0x04010104, 0x00000004, 0x00010104, 0x00010100, 0x04000004,
138 0x04010000, 0x04000104, 0x00000104, 0x04010000, 0x00010104, 0x00000004, 0x04010004, 0x00010100,
139 },
140 {
141 0x80401000, 0x80001040, 0x80001040, 0x00000040, 0x00401040, 0x80400040, 0x80400000, 0x80001000,
142 0x00000000, 0x00401000, 0x00401000, 0x80401040, 0x80000040, 0x00000000, 0x00400040, 0x80400000,
143 0x80000000, 0x00001000, 0x00400000, 0x80401000, 0x00000040, 0x00400000, 0x80001000, 0x00001040,
144 0x80400040, 0x80000000, 0x00001040, 0x00400040, 0x00001000, 0x00401040, 0x80401040, 0x80000040,
145 0x00400040, 0x80400000, 0x00401000, 0x80401040, 0x80000040, 0x00000000, 0x00000000, 0x00401000,
146 0x00001040, 0x00400040, 0x80400040, 0x80000000, 0x80401000, 0x80001040, 0x80001040, 0x00000040,
147 0x80401040, 0x80000040, 0x80000000, 0x00001000, 0x80400000, 0x80001000, 0x00401040, 0x80400040,
148 0x80001000, 0x00001040, 0x00400000, 0x80401000, 0x00000040, 0x00400000, 0x00001000, 0x00401040,
149 },
150 {
151 0x00000080, 0x01040080, 0x01040000, 0x21000080, 0x00040000, 0x00000080, 0x20000000, 0x01040000,
152 0x20040080, 0x00040000, 0x01000080, 0x20040080, 0x21000080, 0x21040000, 0x00040080, 0x20000000,
153 0x01000000, 0x20040000, 0x20040000, 0x00000000, 0x20000080, 0x21040080, 0x21040080, 0x01000080,
154 0x21040000, 0x20000080, 0x00000000, 0x21000000, 0x01040080, 0x01000000, 0x21000000, 0x00040080,
155 0x00040000, 0x21000080, 0x00000080, 0x01000000, 0x20000000, 0x01040000, 0x21000080, 0x20040080,
156 0x01000080, 0x20000000, 0x21040000, 0x01040080, 0x20040080, 0x00000080, 0x01000000, 0x21040000,
157 0x21040080, 0x00040080, 0x21000000, 0x21040080, 0x01040000, 0x00000000, 0x20040000, 0x21000000,
158 0x00040080, 0x01000080, 0x20000080, 0x00040000, 0x00000000, 0x20040000, 0x01040080, 0x20000080,
159 },
160 {
161 0x10000008, 0x10200000, 0x00002000, 0x10202008, 0x10200000, 0x00000008, 0x10202008, 0x00200000,
162 0x10002000, 0x00202008, 0x00200000, 0x10000008, 0x00200008, 0x10002000, 0x10000000, 0x00002008,
163 0x00000000, 0x00200008, 0x10002008, 0x00002000, 0x00202000, 0x10002008, 0x00000008, 0x10200008,
164 0x10200008, 0x00000000, 0x00202008, 0x10202000, 0x00002008, 0x00202000, 0x10202000, 0x10000000,
165 0x10002000, 0x00000008, 0x10200008, 0x00202000, 0x10202008, 0x00200000, 0x00002008, 0x10000008,
166 0x00200000, 0x10002000, 0x10000000, 0x00002008, 0x10000008, 0x10202008, 0x00202000, 0x10200000,
167 0x00202008, 0x10202000, 0x00000000, 0x10200008, 0x00000008, 0x00002000, 0x10200000, 0x00202008,
168 0x00002000, 0x00200008, 0x10002008, 0x00000000, 0x10202000, 0x10000000, 0x00200008, 0x10002008,
169 },
170 {
171 0x00100000, 0x02100001, 0x02000401, 0x00000000, 0x00000400, 0x02000401, 0x00100401, 0x02100400,
172 0x02100401, 0x00100000, 0x00000000, 0x02000001, 0x00000001, 0x02000000, 0x02100001, 0x00000401,
173 0x02000400, 0x00100401, 0x00100001, 0x02000400, 0x02000001, 0x02100000, 0x02100400, 0x00100001,
174 0x02100000, 0x00000400, 0x00000401, 0x02100401, 0x00100400, 0x00000001, 0x02000000, 0x00100400,
175 0x02000000, 0x00100400, 0x00100000, 0x02000401, 0x02000401, 0x02100001, 0x02100001, 0x00000001,
176 0x00100001, 0x02000000, 0x02000400, 0x00100000, 0x02100400, 0x00000401, 0x00100401, 0x02100400,
177 0x00000401, 0x02000001, 0x02100401, 0x02100000, 0x00100400, 0x00000000, 0x00000001, 0x02100401,
178 0x00000000, 0x00100401, 0x02100000, 0x00000400, 0x02000001, 0x02000400, 0x00000400, 0x00100001,
179 },
180 {
181 0x08000820, 0x00000800, 0x00020000, 0x08020820, 0x08000000, 0x08000820, 0x00000020, 0x08000000,
182 0x00020020, 0x08020000, 0x08020820, 0x00020800, 0x08020800, 0x00020820, 0x00000800, 0x00000020,
183 0x08020000, 0x08000020, 0x08000800, 0x00000820, 0x00020800, 0x00020020, 0x08020020, 0x08020800,
184 0x00000820, 0x00000000, 0x00000000, 0x08020020, 0x08000020, 0x08000800, 0x00020820, 0x00020000,
185 0x00020820, 0x00020000, 0x08020800, 0x00000800, 0x00000020, 0x08020020, 0x00000800, 0x00020820,
186 0x08000800, 0x00000020, 0x08000020, 0x08020000, 0x08020020, 0x08000000, 0x00020000, 0x08000820,
187 0x00000000, 0x08020820, 0x00020020, 0x08000020, 0x08020000, 0x08000800, 0x08000820, 0x00000000,
188 0x08020820, 0x00020800, 0x00020800, 0x00000820, 0x00000820, 0x00020020, 0x08000000, 0x08020800,
189 },
190 };
191 #endif
192
193 static uint64_t shuffle(uint64_t in, const uint8_t *shuffle, int shuffle_len) {
194 int i;
195 uint64_t res = 0;
196 for (i = 0; i < shuffle_len; i++)
197 res += res + ((in >> *shuffle++) & 1);
198 return res;
199 }
200
201 static uint64_t shuffle_inv(uint64_t in, const uint8_t *shuffle, int shuffle_len) {
202 int i;
203 uint64_t res = 0;
204 shuffle += shuffle_len - 1;
205 for (i = 0; i < shuffle_len; i++) {
206 res |= (in & 1) << *shuffle--;
207 in >>= 1;
208 }
209 return res;
210 }
211
212 static uint32_t f_func(uint32_t r, uint64_t k) {
213 int i;
214 uint32_t out = 0;
215 // rotate to get first part of E-shuffle in the lowest 6 bits
216 r = (r << 1) | (r >> 31);
217 // apply S-boxes, those compress the data again from 8 * 6 to 8 * 4 bits
218 for (i = 7; i >= 0; i--) {
219 uint8_t tmp = (r ^ k) & 0x3f;
220 #ifdef CONFIG_SMALL
221 uint8_t v = S_boxes[i][tmp >> 1];
222 if (tmp & 1) v >>= 4;
223 out = (out >> 4) | (v << 28);
224 #else
225 out |= S_boxes_P_shuffle[i][tmp];
226 #endif
227 // get next 6 bits of E-shuffle and round key k into the lowest bits
228 r = (r >> 4) | (r << 28);
229 k >>= 6;
230 }
231 #ifdef CONFIG_SMALL
232 out = shuffle(out, P_shuffle, sizeof(P_shuffle));
233 #endif
234 return out;
235 }
236
237 /**
238 * \brief rotate the two halves of the expanded 56 bit key each 1 bit left
239 *
240 * Note: the specification calls this "shift", so I kept it although
241 * it is confusing.
242 */
243 static uint64_t key_shift_left(uint64_t CDn) {
244 uint64_t carries = (CDn >> 27) & 0x10000001;
245 CDn <<= 1;
246 CDn &= ~0x10000001;
247 CDn |= carries;
248 return CDn;
249 }
250
251 uint64_t ff_des_encdec(uint64_t in, uint64_t key, int decrypt) {
252 int i;
253 uint64_t K[16];
254 // discard parity bits from key and shuffle it into C and D parts
255 uint64_t CDn = shuffle(key, PC1_shuffle, sizeof(PC1_shuffle));
256 // generate round keys
257 for (i = 0; i < 16; i++) {
258 CDn = key_shift_left(CDn);
259 if (i > 1 && i != 8 && i != 15)
260 CDn = key_shift_left(CDn);
261 K[i] = shuffle(CDn, PC2_shuffle, sizeof(PC2_shuffle));
262 }
263 // used to apply round keys in reverse order for decryption
264 decrypt = decrypt ? 15 : 0;
265 // shuffle irrelevant to security but to ease hardware implementations
266 in = shuffle(in, IP_shuffle, sizeof(IP_shuffle));
267 for (i = 0; i < 16; i++) {
268 uint32_t f_res;
269 f_res = f_func(in, K[decrypt ^ i]);
270 in = (in << 32) | (in >> 32);
271 in ^= f_res;
272 }
273 in = (in << 32) | (in >> 32);
274 // reverse shuffle used to ease hardware implementations
275 in = shuffle_inv(in, IP_shuffle, sizeof(IP_shuffle));
276 return in;
277 }
278
279 #ifdef TEST
280 #include <stdlib.h>
281 #include <stdio.h>
282 #include <sys/time.h>
283 static uint64_t rand64(void) {
284 uint64_t r = rand();
285 r = (r << 32) | rand();
286 return r;
287 }
288
289 int main(void) {
290 int i, j;
291 struct timeval tv;
292 uint64_t key;
293 uint64_t data;
294 uint64_t ct;
295 gettimeofday(&tv, NULL);
296 srand(tv.tv_sec * 1000 * 1000 + tv.tv_usec);
297 key = 0x123456789abcdef0ULL;
298 data = 0xfedcba9876543210ULL;
299 if (ff_des_encdec(data, key, 0) != 0x4ab65b3d4b061518ULL) {
300 printf("Test 1 failed\n");
301 return 1;
302 }
303 for (i = 0; i < 1000000; i++) {
304 key = rand64();
305 data = rand64();
306 ct = ff_des_encdec(data, key, 0);
307 if (ff_des_encdec(ct, key, 1) != data) {
308 printf("Test 2 failed\n");
309 return 1;
310 }
311 }
312 #ifdef GENTABLES
313 printf("static const uint32_t S_boxes_P_shuffle[8][64] = {\n");
314 for (i = 0; i < 8; i++) {
315 printf(" {");
316 for (j = 0; j < 64; j++) {
317 uint32_t v = S_boxes[i][j >> 1];
318 v = j & 1 ? v >> 4 : v & 0xf;
319 v <<= 28 - 4 * i;
320 v = shuffle(v, P_shuffle, sizeof(P_shuffle));
321 printf((j & 7) == 0 ? "\n " : " ");
322 printf("0x%08X,", v);
323 }
324 printf("\n },\n");
325 }
326 printf("};\n");
327 #endif
328 return 0;
329 }
330 #endif