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 #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
29 static const uint8_t IP_shuffle[] = {
30 T(58, 50, 42, 34, 26, 18, 10, 2),
31 T(60, 52, 44, 36, 28, 20, 12, 4),
32 T(62, 54, 46, 38, 30, 22, 14, 6),
33 T(64, 56, 48, 40, 32, 24, 16, 8),
34 T(57, 49, 41, 33, 25, 17, 9, 1),
35 T(59, 51, 43, 35, 27, 19, 11, 3),
36 T(61, 53, 45, 37, 29, 21, 13, 5),
37 T(63, 55, 47, 39, 31, 23, 15, 7)
41 #if CONFIG_SMALL || defined(GENTABLES)
42 #define T(a, b, c, d) 32-a,32-b,32-c,32-d
43 static const uint8_t P_shuffle[] = {
56 #define T(a, b, c, d, e, f, g) 64-a,64-b,64-c,64-d,64-e,64-f,64-g
57 static const uint8_t PC1_shuffle[] = {
58 T(57, 49, 41, 33, 25, 17, 9),
59 T( 1, 58, 50, 42, 34, 26, 18),
60 T(10, 2, 59, 51, 43, 35, 27),
61 T(19, 11, 3, 60, 52, 44, 36),
62 T(63, 55, 47, 39, 31, 23, 15),
63 T( 7, 62, 54, 46, 38, 30, 22),
64 T(14, 6, 61, 53, 45, 37, 29),
65 T(21, 13, 5, 28, 20, 12, 4)
69 #define T(a, b, c, d, e, f) 56-a,56-b,56-c,56-d,56-e,56-f
70 static const uint8_t PC2_shuffle[] = {
71 T(14, 17, 11, 24, 1, 5),
72 T( 3, 28, 15, 6, 21, 10),
73 T(23, 19, 12, 4, 26, 8),
74 T(16, 7, 27, 20, 13, 2),
75 T(41, 52, 31, 37, 47, 55),
76 T(30, 40, 51, 45, 33, 48),
77 T(44, 49, 39, 56, 34, 53),
78 T(46, 42, 50, 36, 29, 32)
83 static const uint8_t S_boxes[8][32] = {
85 0x0e, 0xf4, 0x7d, 0x41, 0xe2, 0x2f, 0xdb, 0x18, 0xa3, 0x6a, 0xc6, 0xbc, 0x95, 0x59, 0x30, 0x87,
86 0xf4, 0xc1, 0x8e, 0x28, 0x4d, 0x96, 0x12, 0x7b, 0x5f, 0xbc, 0x39, 0xe7, 0xa3, 0x0a, 0x65, 0xd0,
88 0x3f, 0xd1, 0x48, 0x7e, 0xf6, 0x2b, 0x83, 0xe4, 0xc9, 0x07, 0x12, 0xad, 0x6c, 0x90, 0xb5, 0x5a,
89 0xd0, 0x8e, 0xa7, 0x1b, 0x3a, 0xf4, 0x4d, 0x21, 0xb5, 0x68, 0x7c, 0xc6, 0x09, 0x53, 0xe2, 0x9f,
91 0xda, 0x70, 0x09, 0x9e, 0x36, 0x43, 0x6f, 0xa5, 0x21, 0x8d, 0x5c, 0xe7, 0xcb, 0xb4, 0xf2, 0x18,
92 0x1d, 0xa6, 0xd4, 0x09, 0x68, 0x9f, 0x83, 0x70, 0x4b, 0xf1, 0xe2, 0x3c, 0xb5, 0x5a, 0x2e, 0xc7,
94 0xd7, 0x8d, 0xbe, 0x53, 0x60, 0xf6, 0x09, 0x3a, 0x41, 0x72, 0x28, 0xc5, 0x1b, 0xac, 0xe4, 0x9f,
95 0x3a, 0xf6, 0x09, 0x60, 0xac, 0x1b, 0xd7, 0x8d, 0x9f, 0x41, 0x53, 0xbe, 0xc5, 0x72, 0x28, 0xe4,
97 0xe2, 0xbc, 0x24, 0xc1, 0x47, 0x7a, 0xdb, 0x16, 0x58, 0x05, 0xf3, 0xaf, 0x3d, 0x90, 0x8e, 0x69,
98 0xb4, 0x82, 0xc1, 0x7b, 0x1a, 0xed, 0x27, 0xd8, 0x6f, 0xf9, 0x0c, 0x95, 0xa6, 0x43, 0x50, 0x3e,
100 0xac, 0xf1, 0x4a, 0x2f, 0x79, 0xc2, 0x96, 0x58, 0x60, 0x1d, 0xd3, 0xe4, 0x0e, 0xb7, 0x35, 0x8b,
101 0x49, 0x3e, 0x2f, 0xc5, 0x92, 0x58, 0xfc, 0xa3, 0xb7, 0xe0, 0x14, 0x7a, 0x61, 0x0d, 0x8b, 0xd6,
103 0xd4, 0x0b, 0xb2, 0x7e, 0x4f, 0x90, 0x18, 0xad, 0xe3, 0x3c, 0x59, 0xc7, 0x25, 0xfa, 0x86, 0x61,
104 0x61, 0xb4, 0xdb, 0x8d, 0x1c, 0x43, 0xa7, 0x7e, 0x9a, 0x5f, 0x06, 0xf8, 0xe0, 0x25, 0x39, 0xc2,
106 0x1d, 0xf2, 0xd8, 0x84, 0xa6, 0x3f, 0x7b, 0x41, 0xca, 0x59, 0x63, 0xbe, 0x05, 0xe0, 0x9c, 0x27,
107 0x27, 0x1b, 0xe4, 0x71, 0x49, 0xac, 0x8e, 0xd2, 0xf0, 0xc6, 0x9a, 0x0d, 0x3f, 0x53, 0x65, 0xb8,
112 * This table contains the results of applying both the S-box and P-shuffle.
113 * It can be regenerated by compiling this file with -DCONFIG_SMALL -DTEST -DGENTABLES
115 static const uint32_t S_boxes_P_shuffle[8][64] = {
117 0x00808200, 0x00000000, 0x00008000, 0x00808202, 0x00808002, 0x00008202, 0x00000002, 0x00008000,
118 0x00000200, 0x00808200, 0x00808202, 0x00000200, 0x00800202, 0x00808002, 0x00800000, 0x00000002,
119 0x00000202, 0x00800200, 0x00800200, 0x00008200, 0x00008200, 0x00808000, 0x00808000, 0x00800202,
120 0x00008002, 0x00800002, 0x00800002, 0x00008002, 0x00000000, 0x00000202, 0x00008202, 0x00800000,
121 0x00008000, 0x00808202, 0x00000002, 0x00808000, 0x00808200, 0x00800000, 0x00800000, 0x00000200,
122 0x00808002, 0x00008000, 0x00008200, 0x00800002, 0x00000200, 0x00000002, 0x00800202, 0x00008202,
123 0x00808202, 0x00008002, 0x00808000, 0x00800202, 0x00800002, 0x00000202, 0x00008202, 0x00808200,
124 0x00000202, 0x00800200, 0x00800200, 0x00000000, 0x00008002, 0x00008200, 0x00000000, 0x00808002,
127 0x40084010, 0x40004000, 0x00004000, 0x00084010, 0x00080000, 0x00000010, 0x40080010, 0x40004010,
128 0x40000010, 0x40084010, 0x40084000, 0x40000000, 0x40004000, 0x00080000, 0x00000010, 0x40080010,
129 0x00084000, 0x00080010, 0x40004010, 0x00000000, 0x40000000, 0x00004000, 0x00084010, 0x40080000,
130 0x00080010, 0x40000010, 0x00000000, 0x00084000, 0x00004010, 0x40084000, 0x40080000, 0x00004010,
131 0x00000000, 0x00084010, 0x40080010, 0x00080000, 0x40004010, 0x40080000, 0x40084000, 0x00004000,
132 0x40080000, 0x40004000, 0x00000010, 0x40084010, 0x00084010, 0x00000010, 0x00004000, 0x40000000,
133 0x00004010, 0x40084000, 0x00080000, 0x40000010, 0x00080010, 0x40004010, 0x40000010, 0x00080010,
134 0x00084000, 0x00000000, 0x40004000, 0x00004010, 0x40000000, 0x40080010, 0x40084010, 0x00084000,
137 0x00000104, 0x04010100, 0x00000000, 0x04010004, 0x04000100, 0x00000000, 0x00010104, 0x04000100,
138 0x00010004, 0x04000004, 0x04000004, 0x00010000, 0x04010104, 0x00010004, 0x04010000, 0x00000104,
139 0x04000000, 0x00000004, 0x04010100, 0x00000100, 0x00010100, 0x04010000, 0x04010004, 0x00010104,
140 0x04000104, 0x00010100, 0x00010000, 0x04000104, 0x00000004, 0x04010104, 0x00000100, 0x04000000,
141 0x04010100, 0x04000000, 0x00010004, 0x00000104, 0x00010000, 0x04010100, 0x04000100, 0x00000000,
142 0x00000100, 0x00010004, 0x04010104, 0x04000100, 0x04000004, 0x00000100, 0x00000000, 0x04010004,
143 0x04000104, 0x00010000, 0x04000000, 0x04010104, 0x00000004, 0x00010104, 0x00010100, 0x04000004,
144 0x04010000, 0x04000104, 0x00000104, 0x04010000, 0x00010104, 0x00000004, 0x04010004, 0x00010100,
147 0x80401000, 0x80001040, 0x80001040, 0x00000040, 0x00401040, 0x80400040, 0x80400000, 0x80001000,
148 0x00000000, 0x00401000, 0x00401000, 0x80401040, 0x80000040, 0x00000000, 0x00400040, 0x80400000,
149 0x80000000, 0x00001000, 0x00400000, 0x80401000, 0x00000040, 0x00400000, 0x80001000, 0x00001040,
150 0x80400040, 0x80000000, 0x00001040, 0x00400040, 0x00001000, 0x00401040, 0x80401040, 0x80000040,
151 0x00400040, 0x80400000, 0x00401000, 0x80401040, 0x80000040, 0x00000000, 0x00000000, 0x00401000,
152 0x00001040, 0x00400040, 0x80400040, 0x80000000, 0x80401000, 0x80001040, 0x80001040, 0x00000040,
153 0x80401040, 0x80000040, 0x80000000, 0x00001000, 0x80400000, 0x80001000, 0x00401040, 0x80400040,
154 0x80001000, 0x00001040, 0x00400000, 0x80401000, 0x00000040, 0x00400000, 0x00001000, 0x00401040,
157 0x00000080, 0x01040080, 0x01040000, 0x21000080, 0x00040000, 0x00000080, 0x20000000, 0x01040000,
158 0x20040080, 0x00040000, 0x01000080, 0x20040080, 0x21000080, 0x21040000, 0x00040080, 0x20000000,
159 0x01000000, 0x20040000, 0x20040000, 0x00000000, 0x20000080, 0x21040080, 0x21040080, 0x01000080,
160 0x21040000, 0x20000080, 0x00000000, 0x21000000, 0x01040080, 0x01000000, 0x21000000, 0x00040080,
161 0x00040000, 0x21000080, 0x00000080, 0x01000000, 0x20000000, 0x01040000, 0x21000080, 0x20040080,
162 0x01000080, 0x20000000, 0x21040000, 0x01040080, 0x20040080, 0x00000080, 0x01000000, 0x21040000,
163 0x21040080, 0x00040080, 0x21000000, 0x21040080, 0x01040000, 0x00000000, 0x20040000, 0x21000000,
164 0x00040080, 0x01000080, 0x20000080, 0x00040000, 0x00000000, 0x20040000, 0x01040080, 0x20000080,
167 0x10000008, 0x10200000, 0x00002000, 0x10202008, 0x10200000, 0x00000008, 0x10202008, 0x00200000,
168 0x10002000, 0x00202008, 0x00200000, 0x10000008, 0x00200008, 0x10002000, 0x10000000, 0x00002008,
169 0x00000000, 0x00200008, 0x10002008, 0x00002000, 0x00202000, 0x10002008, 0x00000008, 0x10200008,
170 0x10200008, 0x00000000, 0x00202008, 0x10202000, 0x00002008, 0x00202000, 0x10202000, 0x10000000,
171 0x10002000, 0x00000008, 0x10200008, 0x00202000, 0x10202008, 0x00200000, 0x00002008, 0x10000008,
172 0x00200000, 0x10002000, 0x10000000, 0x00002008, 0x10000008, 0x10202008, 0x00202000, 0x10200000,
173 0x00202008, 0x10202000, 0x00000000, 0x10200008, 0x00000008, 0x00002000, 0x10200000, 0x00202008,
174 0x00002000, 0x00200008, 0x10002008, 0x00000000, 0x10202000, 0x10000000, 0x00200008, 0x10002008,
177 0x00100000, 0x02100001, 0x02000401, 0x00000000, 0x00000400, 0x02000401, 0x00100401, 0x02100400,
178 0x02100401, 0x00100000, 0x00000000, 0x02000001, 0x00000001, 0x02000000, 0x02100001, 0x00000401,
179 0x02000400, 0x00100401, 0x00100001, 0x02000400, 0x02000001, 0x02100000, 0x02100400, 0x00100001,
180 0x02100000, 0x00000400, 0x00000401, 0x02100401, 0x00100400, 0x00000001, 0x02000000, 0x00100400,
181 0x02000000, 0x00100400, 0x00100000, 0x02000401, 0x02000401, 0x02100001, 0x02100001, 0x00000001,
182 0x00100001, 0x02000000, 0x02000400, 0x00100000, 0x02100400, 0x00000401, 0x00100401, 0x02100400,
183 0x00000401, 0x02000001, 0x02100401, 0x02100000, 0x00100400, 0x00000000, 0x00000001, 0x02100401,
184 0x00000000, 0x00100401, 0x02100000, 0x00000400, 0x02000001, 0x02000400, 0x00000400, 0x00100001,
187 0x08000820, 0x00000800, 0x00020000, 0x08020820, 0x08000000, 0x08000820, 0x00000020, 0x08000000,
188 0x00020020, 0x08020000, 0x08020820, 0x00020800, 0x08020800, 0x00020820, 0x00000800, 0x00000020,
189 0x08020000, 0x08000020, 0x08000800, 0x00000820, 0x00020800, 0x00020020, 0x08020020, 0x08020800,
190 0x00000820, 0x00000000, 0x00000000, 0x08020020, 0x08000020, 0x08000800, 0x00020820, 0x00020000,
191 0x00020820, 0x00020000, 0x08020800, 0x00000800, 0x00000020, 0x08020020, 0x00000800, 0x00020820,
192 0x08000800, 0x00000020, 0x08000020, 0x08020000, 0x08020020, 0x08000000, 0x00020000, 0x08000820,
193 0x00000000, 0x08020820, 0x00020020, 0x08000020, 0x08020000, 0x08000800, 0x08000820, 0x00000000,
194 0x08020820, 0x00020800, 0x00020800, 0x00000820, 0x00000820, 0x00020020, 0x08000000, 0x08020800,
199 static uint64_t shuffle(uint64_t in, const uint8_t *shuffle, int shuffle_len) {
202 for (i = 0; i < shuffle_len; i++)
203 res += res + ((in >> *shuffle++) & 1);
207 static uint64_t shuffle_inv(uint64_t in, const uint8_t *shuffle, int shuffle_len) {
210 shuffle += shuffle_len - 1;
211 for (i = 0; i < shuffle_len; i++) {
212 res |= (in & 1) << *shuffle--;
218 static uint32_t f_func(uint32_t r, uint64_t k) {
221 // rotate to get first part of E-shuffle in the lowest 6 bits
222 r = (r << 1) | (r >> 31);
223 // apply S-boxes, those compress the data again from 8 * 6 to 8 * 4 bits
224 for (i = 7; i >= 0; i--) {
225 uint8_t tmp = (r ^ k) & 0x3f;
227 uint8_t v = S_boxes[i][tmp >> 1];
228 if (tmp & 1) v >>= 4;
229 out = (out >> 4) | (v << 28);
231 out |= S_boxes_P_shuffle[i][tmp];
233 // get next 6 bits of E-shuffle and round key k into the lowest bits
234 r = (r >> 4) | (r << 28);
238 out = shuffle(out, P_shuffle, sizeof(P_shuffle));
244 * @brief rotate the two halves of the expanded 56 bit key each 1 bit left
246 * Note: the specification calls this "shift", so I kept it although
249 static uint64_t key_shift_left(uint64_t CDn) {
250 uint64_t carries = (CDn >> 27) & 0x10000001;
257 static void gen_roundkeys(uint64_t K[16], uint64_t key) {
259 // discard parity bits from key and shuffle it into C and D parts
260 uint64_t CDn = shuffle(key, PC1_shuffle, sizeof(PC1_shuffle));
261 // generate round keys
262 for (i = 0; i < 16; i++) {
263 CDn = key_shift_left(CDn);
264 if (i > 1 && i != 8 && i != 15)
265 CDn = key_shift_left(CDn);
266 K[i] = shuffle(CDn, PC2_shuffle, sizeof(PC2_shuffle));
270 static uint64_t des_encdec(uint64_t in, uint64_t K[16], int decrypt) {
272 // used to apply round keys in reverse order for decryption
273 decrypt = decrypt ? 15 : 0;
274 // shuffle irrelevant to security but to ease hardware implementations
275 in = shuffle(in, IP_shuffle, sizeof(IP_shuffle));
276 for (i = 0; i < 16; i++) {
278 f_res = f_func(in, K[decrypt ^ i]);
279 in = (in << 32) | (in >> 32);
282 in = (in << 32) | (in >> 32);
283 // reverse shuffle used to ease hardware implementations
284 in = shuffle_inv(in, IP_shuffle, sizeof(IP_shuffle));
288 AVDES *av_des_alloc(void)
290 return av_mallocz(sizeof(struct AVDES));
293 int av_des_init(AVDES *d, const uint8_t *key, int key_bits, av_unused int decrypt) {
294 if (key_bits != 64 && key_bits != 192)
295 return AVERROR(EINVAL);
296 d->triple_des = key_bits > 64;
297 gen_roundkeys(d->round_keys[0], AV_RB64(key));
299 gen_roundkeys(d->round_keys[1], AV_RB64(key + 8));
300 gen_roundkeys(d->round_keys[2], AV_RB64(key + 16));
305 static void av_des_crypt_mac(AVDES *d, uint8_t *dst, const uint8_t *src, int count, uint8_t *iv, int decrypt, int mac) {
306 uint64_t iv_val = iv ? AV_RB64(iv) : 0;
307 while (count-- > 0) {
309 uint64_t src_val = src ? AV_RB64(src) : 0;
311 uint64_t tmp = src_val;
313 src_val = des_encdec(src_val, d->round_keys[2], 1);
314 src_val = des_encdec(src_val, d->round_keys[1], 0);
316 dst_val = des_encdec(src_val, d->round_keys[0], 1) ^ iv_val;
317 iv_val = iv ? tmp : 0;
319 dst_val = des_encdec(src_val ^ iv_val, d->round_keys[0], 0);
321 dst_val = des_encdec(dst_val, d->round_keys[1], 1);
322 dst_val = des_encdec(dst_val, d->round_keys[2], 0);
324 iv_val = iv ? dst_val : 0;
326 AV_WB64(dst, dst_val);
335 void av_des_crypt(AVDES *d, uint8_t *dst, const uint8_t *src, int count, uint8_t *iv, int decrypt) {
336 av_des_crypt_mac(d, dst, src, count, iv, decrypt, 0);
339 void av_des_mac(AVDES *d, uint8_t *dst, const uint8_t *src, int count) {
340 av_des_crypt_mac(d, dst, src, count, (uint8_t[8]){0}, 0, 1);
349 static uint64_t rand64(void) {
351 r = (r << 32) | rand();
355 static const uint8_t test_key[] = {0x12, 0x34, 0x56, 0x78, 0x9a, 0xbc, 0xde, 0xf0};
356 static const DECLARE_ALIGNED(8, uint8_t, plain)[] = {0xfe, 0xdc, 0xba, 0x98, 0x76, 0x54, 0x32, 0x10};
357 static const DECLARE_ALIGNED(8, uint8_t, crypt)[] = {0x4a, 0xb6, 0x5b, 0x3d, 0x4b, 0x06, 0x15, 0x18};
358 static DECLARE_ALIGNED(8, uint8_t, tmp)[8];
359 static DECLARE_ALIGNED(8, uint8_t, large_buffer)[10002][8];
360 static const uint8_t cbc_key[] = {
361 0x01, 0x23, 0x45, 0x67, 0x89, 0xab, 0xcd, 0xef,
362 0x23, 0x45, 0x67, 0x89, 0xab, 0xcd, 0xef, 0x01,
363 0x45, 0x67, 0x89, 0xab, 0xcd, 0xef, 0x01, 0x23
366 static int run_test(int cbc, int decrypt) {
368 int delay = cbc && !decrypt ? 2 : 1;
370 AV_WB64(large_buffer[0], 0x4e6f772069732074ULL);
371 AV_WB64(large_buffer[1], 0x1234567890abcdefULL);
372 AV_WB64(tmp, 0x1234567890abcdefULL);
373 av_des_init(&d, cbc_key, 192, decrypt);
374 av_des_crypt(&d, large_buffer[delay], large_buffer[0], 10000, cbc ? tmp : NULL, decrypt);
375 res = AV_RB64(large_buffer[9999 + delay]);
378 return res == 0xc5cecf63ecec514cULL;
380 return res == 0xcb191f85d1ed8439ULL;
383 return res == 0x8325397644091a0aULL;
385 return res == 0xdd17e8b8b437d232ULL;
398 uint64_t roundkeys[16];
400 key[0] = AV_RB64(test_key);
401 data = AV_RB64(plain);
402 gen_roundkeys(roundkeys, key[0]);
403 if (des_encdec(data, roundkeys, 0) != AV_RB64(crypt)) {
404 printf("Test 1 failed\n");
407 av_des_init(&d, test_key, 64, 0);
408 av_des_crypt(&d, tmp, plain, 1, NULL, 0);
409 if (memcmp(tmp, crypt, sizeof(crypt))) {
410 printf("Public API decryption failed\n");
413 if (!run_test(0, 0) || !run_test(0, 1) || !run_test(1, 0) || !run_test(1, 1)) {
414 printf("Partial Monte-Carlo test failed\n");
417 for (i = 0; i < 1000; i++) {
418 key[0] = rand64(); key[1] = rand64(); key[2] = rand64();
420 av_des_init(&d, (uint8_t*)key, 192, 0);
421 av_des_crypt(&d, (uint8_t*)&ct, (uint8_t*)&data, 1, NULL, 0);
422 av_des_init(&d, (uint8_t*)key, 192, 1);
423 av_des_crypt(&d, (uint8_t*)&ct, (uint8_t*)&ct, 1, NULL, 1);
425 printf("Test 2 failed\n");
430 printf("static const uint32_t S_boxes_P_shuffle[8][64] = {\n");
431 for (i = 0; i < 8; i++) {
433 for (j = 0; j < 64; j++) {
434 uint32_t v = S_boxes[i][j >> 1];
435 v = j & 1 ? v >> 4 : v & 0xf;
437 v = shuffle(v, P_shuffle, sizeof(P_shuffle));
438 printf((j & 7) == 0 ? "\n " : " ");
439 printf("0x%08X,", v);