2 * DES encryption/decryption
3 * Copyright (c) 2007 Reimar Doeffinger
5 * This file is part of FFmpeg.
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.
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.
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
24 #include "intreadwrite.h"
28 #if !FF_API_CRYPTO_CONTEXT
30 uint64_t round_keys[3][16];
35 #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
36 static const uint8_t IP_shuffle[] = {
37 T(58, 50, 42, 34, 26, 18, 10, 2),
38 T(60, 52, 44, 36, 28, 20, 12, 4),
39 T(62, 54, 46, 38, 30, 22, 14, 6),
40 T(64, 56, 48, 40, 32, 24, 16, 8),
41 T(57, 49, 41, 33, 25, 17, 9, 1),
42 T(59, 51, 43, 35, 27, 19, 11, 3),
43 T(61, 53, 45, 37, 29, 21, 13, 5),
44 T(63, 55, 47, 39, 31, 23, 15, 7)
48 #if CONFIG_SMALL || defined(GENTABLES)
49 #define T(a, b, c, d) 32-a,32-b,32-c,32-d
50 static const uint8_t P_shuffle[] = {
63 #define T(a, b, c, d, e, f, g) 64-a,64-b,64-c,64-d,64-e,64-f,64-g
64 static const uint8_t PC1_shuffle[] = {
65 T(57, 49, 41, 33, 25, 17, 9),
66 T( 1, 58, 50, 42, 34, 26, 18),
67 T(10, 2, 59, 51, 43, 35, 27),
68 T(19, 11, 3, 60, 52, 44, 36),
69 T(63, 55, 47, 39, 31, 23, 15),
70 T( 7, 62, 54, 46, 38, 30, 22),
71 T(14, 6, 61, 53, 45, 37, 29),
72 T(21, 13, 5, 28, 20, 12, 4)
76 #define T(a, b, c, d, e, f) 56-a,56-b,56-c,56-d,56-e,56-f
77 static const uint8_t PC2_shuffle[] = {
78 T(14, 17, 11, 24, 1, 5),
79 T( 3, 28, 15, 6, 21, 10),
80 T(23, 19, 12, 4, 26, 8),
81 T(16, 7, 27, 20, 13, 2),
82 T(41, 52, 31, 37, 47, 55),
83 T(30, 40, 51, 45, 33, 48),
84 T(44, 49, 39, 56, 34, 53),
85 T(46, 42, 50, 36, 29, 32)
90 static const uint8_t S_boxes[8][32] = {
92 0x0e, 0xf4, 0x7d, 0x41, 0xe2, 0x2f, 0xdb, 0x18, 0xa3, 0x6a, 0xc6, 0xbc, 0x95, 0x59, 0x30, 0x87,
93 0xf4, 0xc1, 0x8e, 0x28, 0x4d, 0x96, 0x12, 0x7b, 0x5f, 0xbc, 0x39, 0xe7, 0xa3, 0x0a, 0x65, 0xd0,
95 0x3f, 0xd1, 0x48, 0x7e, 0xf6, 0x2b, 0x83, 0xe4, 0xc9, 0x07, 0x12, 0xad, 0x6c, 0x90, 0xb5, 0x5a,
96 0xd0, 0x8e, 0xa7, 0x1b, 0x3a, 0xf4, 0x4d, 0x21, 0xb5, 0x68, 0x7c, 0xc6, 0x09, 0x53, 0xe2, 0x9f,
98 0xda, 0x70, 0x09, 0x9e, 0x36, 0x43, 0x6f, 0xa5, 0x21, 0x8d, 0x5c, 0xe7, 0xcb, 0xb4, 0xf2, 0x18,
99 0x1d, 0xa6, 0xd4, 0x09, 0x68, 0x9f, 0x83, 0x70, 0x4b, 0xf1, 0xe2, 0x3c, 0xb5, 0x5a, 0x2e, 0xc7,
101 0xd7, 0x8d, 0xbe, 0x53, 0x60, 0xf6, 0x09, 0x3a, 0x41, 0x72, 0x28, 0xc5, 0x1b, 0xac, 0xe4, 0x9f,
102 0x3a, 0xf6, 0x09, 0x60, 0xac, 0x1b, 0xd7, 0x8d, 0x9f, 0x41, 0x53, 0xbe, 0xc5, 0x72, 0x28, 0xe4,
104 0xe2, 0xbc, 0x24, 0xc1, 0x47, 0x7a, 0xdb, 0x16, 0x58, 0x05, 0xf3, 0xaf, 0x3d, 0x90, 0x8e, 0x69,
105 0xb4, 0x82, 0xc1, 0x7b, 0x1a, 0xed, 0x27, 0xd8, 0x6f, 0xf9, 0x0c, 0x95, 0xa6, 0x43, 0x50, 0x3e,
107 0xac, 0xf1, 0x4a, 0x2f, 0x79, 0xc2, 0x96, 0x58, 0x60, 0x1d, 0xd3, 0xe4, 0x0e, 0xb7, 0x35, 0x8b,
108 0x49, 0x3e, 0x2f, 0xc5, 0x92, 0x58, 0xfc, 0xa3, 0xb7, 0xe0, 0x14, 0x7a, 0x61, 0x0d, 0x8b, 0xd6,
110 0xd4, 0x0b, 0xb2, 0x7e, 0x4f, 0x90, 0x18, 0xad, 0xe3, 0x3c, 0x59, 0xc7, 0x25, 0xfa, 0x86, 0x61,
111 0x61, 0xb4, 0xdb, 0x8d, 0x1c, 0x43, 0xa7, 0x7e, 0x9a, 0x5f, 0x06, 0xf8, 0xe0, 0x25, 0x39, 0xc2,
113 0x1d, 0xf2, 0xd8, 0x84, 0xa6, 0x3f, 0x7b, 0x41, 0xca, 0x59, 0x63, 0xbe, 0x05, 0xe0, 0x9c, 0x27,
114 0x27, 0x1b, 0xe4, 0x71, 0x49, 0xac, 0x8e, 0xd2, 0xf0, 0xc6, 0x9a, 0x0d, 0x3f, 0x53, 0x65, 0xb8,
119 * This table contains the results of applying both the S-box and P-shuffle.
120 * It can be regenerated by compiling this file with -DCONFIG_SMALL -DTEST -DGENTABLES
122 static const uint32_t S_boxes_P_shuffle[8][64] = {
124 0x00808200, 0x00000000, 0x00008000, 0x00808202, 0x00808002, 0x00008202, 0x00000002, 0x00008000,
125 0x00000200, 0x00808200, 0x00808202, 0x00000200, 0x00800202, 0x00808002, 0x00800000, 0x00000002,
126 0x00000202, 0x00800200, 0x00800200, 0x00008200, 0x00008200, 0x00808000, 0x00808000, 0x00800202,
127 0x00008002, 0x00800002, 0x00800002, 0x00008002, 0x00000000, 0x00000202, 0x00008202, 0x00800000,
128 0x00008000, 0x00808202, 0x00000002, 0x00808000, 0x00808200, 0x00800000, 0x00800000, 0x00000200,
129 0x00808002, 0x00008000, 0x00008200, 0x00800002, 0x00000200, 0x00000002, 0x00800202, 0x00008202,
130 0x00808202, 0x00008002, 0x00808000, 0x00800202, 0x00800002, 0x00000202, 0x00008202, 0x00808200,
131 0x00000202, 0x00800200, 0x00800200, 0x00000000, 0x00008002, 0x00008200, 0x00000000, 0x00808002,
134 0x40084010, 0x40004000, 0x00004000, 0x00084010, 0x00080000, 0x00000010, 0x40080010, 0x40004010,
135 0x40000010, 0x40084010, 0x40084000, 0x40000000, 0x40004000, 0x00080000, 0x00000010, 0x40080010,
136 0x00084000, 0x00080010, 0x40004010, 0x00000000, 0x40000000, 0x00004000, 0x00084010, 0x40080000,
137 0x00080010, 0x40000010, 0x00000000, 0x00084000, 0x00004010, 0x40084000, 0x40080000, 0x00004010,
138 0x00000000, 0x00084010, 0x40080010, 0x00080000, 0x40004010, 0x40080000, 0x40084000, 0x00004000,
139 0x40080000, 0x40004000, 0x00000010, 0x40084010, 0x00084010, 0x00000010, 0x00004000, 0x40000000,
140 0x00004010, 0x40084000, 0x00080000, 0x40000010, 0x00080010, 0x40004010, 0x40000010, 0x00080010,
141 0x00084000, 0x00000000, 0x40004000, 0x00004010, 0x40000000, 0x40080010, 0x40084010, 0x00084000,
144 0x00000104, 0x04010100, 0x00000000, 0x04010004, 0x04000100, 0x00000000, 0x00010104, 0x04000100,
145 0x00010004, 0x04000004, 0x04000004, 0x00010000, 0x04010104, 0x00010004, 0x04010000, 0x00000104,
146 0x04000000, 0x00000004, 0x04010100, 0x00000100, 0x00010100, 0x04010000, 0x04010004, 0x00010104,
147 0x04000104, 0x00010100, 0x00010000, 0x04000104, 0x00000004, 0x04010104, 0x00000100, 0x04000000,
148 0x04010100, 0x04000000, 0x00010004, 0x00000104, 0x00010000, 0x04010100, 0x04000100, 0x00000000,
149 0x00000100, 0x00010004, 0x04010104, 0x04000100, 0x04000004, 0x00000100, 0x00000000, 0x04010004,
150 0x04000104, 0x00010000, 0x04000000, 0x04010104, 0x00000004, 0x00010104, 0x00010100, 0x04000004,
151 0x04010000, 0x04000104, 0x00000104, 0x04010000, 0x00010104, 0x00000004, 0x04010004, 0x00010100,
154 0x80401000, 0x80001040, 0x80001040, 0x00000040, 0x00401040, 0x80400040, 0x80400000, 0x80001000,
155 0x00000000, 0x00401000, 0x00401000, 0x80401040, 0x80000040, 0x00000000, 0x00400040, 0x80400000,
156 0x80000000, 0x00001000, 0x00400000, 0x80401000, 0x00000040, 0x00400000, 0x80001000, 0x00001040,
157 0x80400040, 0x80000000, 0x00001040, 0x00400040, 0x00001000, 0x00401040, 0x80401040, 0x80000040,
158 0x00400040, 0x80400000, 0x00401000, 0x80401040, 0x80000040, 0x00000000, 0x00000000, 0x00401000,
159 0x00001040, 0x00400040, 0x80400040, 0x80000000, 0x80401000, 0x80001040, 0x80001040, 0x00000040,
160 0x80401040, 0x80000040, 0x80000000, 0x00001000, 0x80400000, 0x80001000, 0x00401040, 0x80400040,
161 0x80001000, 0x00001040, 0x00400000, 0x80401000, 0x00000040, 0x00400000, 0x00001000, 0x00401040,
164 0x00000080, 0x01040080, 0x01040000, 0x21000080, 0x00040000, 0x00000080, 0x20000000, 0x01040000,
165 0x20040080, 0x00040000, 0x01000080, 0x20040080, 0x21000080, 0x21040000, 0x00040080, 0x20000000,
166 0x01000000, 0x20040000, 0x20040000, 0x00000000, 0x20000080, 0x21040080, 0x21040080, 0x01000080,
167 0x21040000, 0x20000080, 0x00000000, 0x21000000, 0x01040080, 0x01000000, 0x21000000, 0x00040080,
168 0x00040000, 0x21000080, 0x00000080, 0x01000000, 0x20000000, 0x01040000, 0x21000080, 0x20040080,
169 0x01000080, 0x20000000, 0x21040000, 0x01040080, 0x20040080, 0x00000080, 0x01000000, 0x21040000,
170 0x21040080, 0x00040080, 0x21000000, 0x21040080, 0x01040000, 0x00000000, 0x20040000, 0x21000000,
171 0x00040080, 0x01000080, 0x20000080, 0x00040000, 0x00000000, 0x20040000, 0x01040080, 0x20000080,
174 0x10000008, 0x10200000, 0x00002000, 0x10202008, 0x10200000, 0x00000008, 0x10202008, 0x00200000,
175 0x10002000, 0x00202008, 0x00200000, 0x10000008, 0x00200008, 0x10002000, 0x10000000, 0x00002008,
176 0x00000000, 0x00200008, 0x10002008, 0x00002000, 0x00202000, 0x10002008, 0x00000008, 0x10200008,
177 0x10200008, 0x00000000, 0x00202008, 0x10202000, 0x00002008, 0x00202000, 0x10202000, 0x10000000,
178 0x10002000, 0x00000008, 0x10200008, 0x00202000, 0x10202008, 0x00200000, 0x00002008, 0x10000008,
179 0x00200000, 0x10002000, 0x10000000, 0x00002008, 0x10000008, 0x10202008, 0x00202000, 0x10200000,
180 0x00202008, 0x10202000, 0x00000000, 0x10200008, 0x00000008, 0x00002000, 0x10200000, 0x00202008,
181 0x00002000, 0x00200008, 0x10002008, 0x00000000, 0x10202000, 0x10000000, 0x00200008, 0x10002008,
184 0x00100000, 0x02100001, 0x02000401, 0x00000000, 0x00000400, 0x02000401, 0x00100401, 0x02100400,
185 0x02100401, 0x00100000, 0x00000000, 0x02000001, 0x00000001, 0x02000000, 0x02100001, 0x00000401,
186 0x02000400, 0x00100401, 0x00100001, 0x02000400, 0x02000001, 0x02100000, 0x02100400, 0x00100001,
187 0x02100000, 0x00000400, 0x00000401, 0x02100401, 0x00100400, 0x00000001, 0x02000000, 0x00100400,
188 0x02000000, 0x00100400, 0x00100000, 0x02000401, 0x02000401, 0x02100001, 0x02100001, 0x00000001,
189 0x00100001, 0x02000000, 0x02000400, 0x00100000, 0x02100400, 0x00000401, 0x00100401, 0x02100400,
190 0x00000401, 0x02000001, 0x02100401, 0x02100000, 0x00100400, 0x00000000, 0x00000001, 0x02100401,
191 0x00000000, 0x00100401, 0x02100000, 0x00000400, 0x02000001, 0x02000400, 0x00000400, 0x00100001,
194 0x08000820, 0x00000800, 0x00020000, 0x08020820, 0x08000000, 0x08000820, 0x00000020, 0x08000000,
195 0x00020020, 0x08020000, 0x08020820, 0x00020800, 0x08020800, 0x00020820, 0x00000800, 0x00000020,
196 0x08020000, 0x08000020, 0x08000800, 0x00000820, 0x00020800, 0x00020020, 0x08020020, 0x08020800,
197 0x00000820, 0x00000000, 0x00000000, 0x08020020, 0x08000020, 0x08000800, 0x00020820, 0x00020000,
198 0x00020820, 0x00020000, 0x08020800, 0x00000800, 0x00000020, 0x08020020, 0x00000800, 0x00020820,
199 0x08000800, 0x00000020, 0x08000020, 0x08020000, 0x08020020, 0x08000000, 0x00020000, 0x08000820,
200 0x00000000, 0x08020820, 0x00020020, 0x08000020, 0x08020000, 0x08000800, 0x08000820, 0x00000000,
201 0x08020820, 0x00020800, 0x00020800, 0x00000820, 0x00000820, 0x00020020, 0x08000000, 0x08020800,
206 static uint64_t shuffle(uint64_t in, const uint8_t *shuffle, int shuffle_len) {
209 for (i = 0; i < shuffle_len; i++)
210 res += res + ((in >> *shuffle++) & 1);
214 static uint64_t shuffle_inv(uint64_t in, const uint8_t *shuffle, int shuffle_len) {
217 shuffle += shuffle_len - 1;
218 for (i = 0; i < shuffle_len; i++) {
219 res |= (in & 1) << *shuffle--;
225 static uint32_t f_func(uint32_t r, uint64_t k) {
228 // rotate to get first part of E-shuffle in the lowest 6 bits
229 r = (r << 1) | (r >> 31);
230 // apply S-boxes, those compress the data again from 8 * 6 to 8 * 4 bits
231 for (i = 7; i >= 0; i--) {
232 uint8_t tmp = (r ^ k) & 0x3f;
234 uint8_t v = S_boxes[i][tmp >> 1];
235 if (tmp & 1) v >>= 4;
236 out = (out >> 4) | (v << 28);
238 out |= S_boxes_P_shuffle[i][tmp];
240 // get next 6 bits of E-shuffle and round key k into the lowest bits
241 r = (r >> 4) | (r << 28);
245 out = shuffle(out, P_shuffle, sizeof(P_shuffle));
251 * @brief rotate the two halves of the expanded 56 bit key each 1 bit left
253 * Note: the specification calls this "shift", so I kept it although
256 static uint64_t key_shift_left(uint64_t CDn) {
257 uint64_t carries = (CDn >> 27) & 0x10000001;
264 static void gen_roundkeys(uint64_t K[16], uint64_t key) {
266 // discard parity bits from key and shuffle it into C and D parts
267 uint64_t CDn = shuffle(key, PC1_shuffle, sizeof(PC1_shuffle));
268 // generate round keys
269 for (i = 0; i < 16; i++) {
270 CDn = key_shift_left(CDn);
271 if (i > 1 && i != 8 && i != 15)
272 CDn = key_shift_left(CDn);
273 K[i] = shuffle(CDn, PC2_shuffle, sizeof(PC2_shuffle));
277 static uint64_t des_encdec(uint64_t in, uint64_t K[16], int decrypt) {
279 // used to apply round keys in reverse order for decryption
280 decrypt = decrypt ? 15 : 0;
281 // shuffle irrelevant to security but to ease hardware implementations
282 in = shuffle(in, IP_shuffle, sizeof(IP_shuffle));
283 for (i = 0; i < 16; i++) {
285 f_res = f_func(in, K[decrypt ^ i]);
286 in = (in << 32) | (in >> 32);
289 in = (in << 32) | (in >> 32);
290 // reverse shuffle used to ease hardware implementations
291 in = shuffle_inv(in, IP_shuffle, sizeof(IP_shuffle));
295 AVDES *av_des_alloc(void)
297 return av_mallocz(sizeof(struct AVDES));
300 int av_des_init(AVDES *d, const uint8_t *key, int key_bits, av_unused int decrypt) {
301 if (key_bits != 64 && key_bits != 192)
303 d->triple_des = key_bits > 64;
304 gen_roundkeys(d->round_keys[0], AV_RB64(key));
306 gen_roundkeys(d->round_keys[1], AV_RB64(key + 8));
307 gen_roundkeys(d->round_keys[2], AV_RB64(key + 16));
312 static void av_des_crypt_mac(AVDES *d, uint8_t *dst, const uint8_t *src, int count, uint8_t *iv, int decrypt, int mac) {
313 uint64_t iv_val = iv ? AV_RB64(iv) : 0;
314 while (count-- > 0) {
316 uint64_t src_val = src ? AV_RB64(src) : 0;
318 uint64_t tmp = src_val;
320 src_val = des_encdec(src_val, d->round_keys[2], 1);
321 src_val = des_encdec(src_val, d->round_keys[1], 0);
323 dst_val = des_encdec(src_val, d->round_keys[0], 1) ^ iv_val;
324 iv_val = iv ? tmp : 0;
326 dst_val = des_encdec(src_val ^ iv_val, d->round_keys[0], 0);
328 dst_val = des_encdec(dst_val, d->round_keys[1], 1);
329 dst_val = des_encdec(dst_val, d->round_keys[2], 0);
331 iv_val = iv ? dst_val : 0;
333 AV_WB64(dst, dst_val);
342 void av_des_crypt(AVDES *d, uint8_t *dst, const uint8_t *src, int count, uint8_t *iv, int decrypt) {
343 av_des_crypt_mac(d, dst, src, count, iv, decrypt, 0);
346 void av_des_mac(AVDES *d, uint8_t *dst, const uint8_t *src, int count) {
347 av_des_crypt_mac(d, dst, src, count, (uint8_t[8]){0}, 0, 1);
356 static uint64_t rand64(void) {
358 r = (r << 32) | rand();
362 static const uint8_t test_key[] = {0x12, 0x34, 0x56, 0x78, 0x9a, 0xbc, 0xde, 0xf0};
363 static const DECLARE_ALIGNED(8, uint8_t, plain)[] = {0xfe, 0xdc, 0xba, 0x98, 0x76, 0x54, 0x32, 0x10};
364 static const DECLARE_ALIGNED(8, uint8_t, crypt)[] = {0x4a, 0xb6, 0x5b, 0x3d, 0x4b, 0x06, 0x15, 0x18};
365 static DECLARE_ALIGNED(8, uint8_t, tmp)[8];
366 static DECLARE_ALIGNED(8, uint8_t, large_buffer)[10002][8];
367 static const uint8_t cbc_key[] = {
368 0x01, 0x23, 0x45, 0x67, 0x89, 0xab, 0xcd, 0xef,
369 0x23, 0x45, 0x67, 0x89, 0xab, 0xcd, 0xef, 0x01,
370 0x45, 0x67, 0x89, 0xab, 0xcd, 0xef, 0x01, 0x23
373 static int run_test(int cbc, int decrypt) {
375 int delay = cbc && !decrypt ? 2 : 1;
377 AV_WB64(large_buffer[0], 0x4e6f772069732074ULL);
378 AV_WB64(large_buffer[1], 0x1234567890abcdefULL);
379 AV_WB64(tmp, 0x1234567890abcdefULL);
380 av_des_init(&d, cbc_key, 192, decrypt);
381 av_des_crypt(&d, large_buffer[delay], large_buffer[0], 10000, cbc ? tmp : NULL, decrypt);
382 res = AV_RB64(large_buffer[9999 + delay]);
385 return res == 0xc5cecf63ecec514cULL;
387 return res == 0xcb191f85d1ed8439ULL;
390 return res == 0x8325397644091a0aULL;
392 return res == 0xdd17e8b8b437d232ULL;
405 uint64_t roundkeys[16];
407 key[0] = AV_RB64(test_key);
408 data = AV_RB64(plain);
409 gen_roundkeys(roundkeys, key[0]);
410 if (des_encdec(data, roundkeys, 0) != AV_RB64(crypt)) {
411 printf("Test 1 failed\n");
414 av_des_init(&d, test_key, 64, 0);
415 av_des_crypt(&d, tmp, plain, 1, NULL, 0);
416 if (memcmp(tmp, crypt, sizeof(crypt))) {
417 printf("Public API decryption failed\n");
420 if (!run_test(0, 0) || !run_test(0, 1) || !run_test(1, 0) || !run_test(1, 1)) {
421 printf("Partial Monte-Carlo test failed\n");
424 for (i = 0; i < 1000; i++) {
425 key[0] = rand64(); key[1] = rand64(); key[2] = rand64();
427 av_des_init(&d, (uint8_t*)key, 192, 0);
428 av_des_crypt(&d, (uint8_t*)&ct, (uint8_t*)&data, 1, NULL, 0);
429 av_des_init(&d, (uint8_t*)key, 192, 1);
430 av_des_crypt(&d, (uint8_t*)&ct, (uint8_t*)&ct, 1, NULL, 1);
432 printf("Test 2 failed\n");
437 printf("static const uint32_t S_boxes_P_shuffle[8][64] = {\n");
438 for (i = 0; i < 8; i++) {
440 for (j = 0; j < 64; j++) {
441 uint32_t v = S_boxes[i][j >> 1];
442 v = j & 1 ? v >> 4 : v & 0xf;
444 v = shuffle(v, P_shuffle, sizeof(P_shuffle));
445 printf((j & 7) == 0 ? "\n " : " ");
446 printf("0x%08X,", v);