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"
27 typedef struct AVDES AVDES
;
29 #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
30 static const uint8_t IP_shuffle
[] = {
31 T(58, 50, 42, 34, 26, 18, 10, 2),
32 T(60, 52, 44, 36, 28, 20, 12, 4),
33 T(62, 54, 46, 38, 30, 22, 14, 6),
34 T(64, 56, 48, 40, 32, 24, 16, 8),
35 T(57, 49, 41, 33, 25, 17, 9, 1),
36 T(59, 51, 43, 35, 27, 19, 11, 3),
37 T(61, 53, 45, 37, 29, 21, 13, 5),
38 T(63, 55, 47, 39, 31, 23, 15, 7)
42 #define T(a, b, c, d) 32-a,32-b,32-c,32-d
43 static const uint8_t P_shuffle
[] = {
55 #define T(a, b, c, d, e, f, g) 64-a,64-b,64-c,64-d,64-e,64-f,64-g
56 static const uint8_t PC1_shuffle
[] = {
57 T(57, 49, 41, 33, 25, 17, 9),
58 T( 1, 58, 50, 42, 34, 26, 18),
59 T(10, 2, 59, 51, 43, 35, 27),
60 T(19, 11, 3, 60, 52, 44, 36),
61 T(63, 55, 47, 39, 31, 23, 15),
62 T( 7, 62, 54, 46, 38, 30, 22),
63 T(14, 6, 61, 53, 45, 37, 29),
64 T(21, 13, 5, 28, 20, 12, 4)
68 #define T(a, b, c, d, e, f) 56-a,56-b,56-c,56-d,56-e,56-f
69 static const uint8_t PC2_shuffle
[] = {
70 T(14, 17, 11, 24, 1, 5),
71 T( 3, 28, 15, 6, 21, 10),
72 T(23, 19, 12, 4, 26, 8),
73 T(16, 7, 27, 20, 13, 2),
74 T(41, 52, 31, 37, 47, 55),
75 T(30, 40, 51, 45, 33, 48),
76 T(44, 49, 39, 56, 34, 53),
77 T(46, 42, 50, 36, 29, 32)
82 static const uint8_t S_boxes
[8][32] = {
84 0x0e, 0xf4, 0x7d, 0x41, 0xe2, 0x2f, 0xdb, 0x18, 0xa3, 0x6a, 0xc6, 0xbc, 0x95, 0x59, 0x30, 0x87,
85 0xf4, 0xc1, 0x8e, 0x28, 0x4d, 0x96, 0x12, 0x7b, 0x5f, 0xbc, 0x39, 0xe7, 0xa3, 0x0a, 0x65, 0xd0,
87 0x3f, 0xd1, 0x48, 0x7e, 0xf6, 0x2b, 0x83, 0xe4, 0xc9, 0x07, 0x12, 0xad, 0x6c, 0x90, 0xb5, 0x5a,
88 0xd0, 0x8e, 0xa7, 0x1b, 0x3a, 0xf4, 0x4d, 0x21, 0xb5, 0x68, 0x7c, 0xc6, 0x09, 0x53, 0xe2, 0x9f,
90 0xda, 0x70, 0x09, 0x9e, 0x36, 0x43, 0x6f, 0xa5, 0x21, 0x8d, 0x5c, 0xe7, 0xcb, 0xb4, 0xf2, 0x18,
91 0x1d, 0xa6, 0xd4, 0x09, 0x68, 0x9f, 0x83, 0x70, 0x4b, 0xf1, 0xe2, 0x3c, 0xb5, 0x5a, 0x2e, 0xc7,
93 0xd7, 0x8d, 0xbe, 0x53, 0x60, 0xf6, 0x09, 0x3a, 0x41, 0x72, 0x28, 0xc5, 0x1b, 0xac, 0xe4, 0x9f,
94 0x3a, 0xf6, 0x09, 0x60, 0xac, 0x1b, 0xd7, 0x8d, 0x9f, 0x41, 0x53, 0xbe, 0xc5, 0x72, 0x28, 0xe4,
96 0xe2, 0xbc, 0x24, 0xc1, 0x47, 0x7a, 0xdb, 0x16, 0x58, 0x05, 0xf3, 0xaf, 0x3d, 0x90, 0x8e, 0x69,
97 0xb4, 0x82, 0xc1, 0x7b, 0x1a, 0xed, 0x27, 0xd8, 0x6f, 0xf9, 0x0c, 0x95, 0xa6, 0x43, 0x50, 0x3e,
99 0xac, 0xf1, 0x4a, 0x2f, 0x79, 0xc2, 0x96, 0x58, 0x60, 0x1d, 0xd3, 0xe4, 0x0e, 0xb7, 0x35, 0x8b,
100 0x49, 0x3e, 0x2f, 0xc5, 0x92, 0x58, 0xfc, 0xa3, 0xb7, 0xe0, 0x14, 0x7a, 0x61, 0x0d, 0x8b, 0xd6,
102 0xd4, 0x0b, 0xb2, 0x7e, 0x4f, 0x90, 0x18, 0xad, 0xe3, 0x3c, 0x59, 0xc7, 0x25, 0xfa, 0x86, 0x61,
103 0x61, 0xb4, 0xdb, 0x8d, 0x1c, 0x43, 0xa7, 0x7e, 0x9a, 0x5f, 0x06, 0xf8, 0xe0, 0x25, 0x39, 0xc2,
105 0x1d, 0xf2, 0xd8, 0x84, 0xa6, 0x3f, 0x7b, 0x41, 0xca, 0x59, 0x63, 0xbe, 0x05, 0xe0, 0x9c, 0x27,
106 0x27, 0x1b, 0xe4, 0x71, 0x49, 0xac, 0x8e, 0xd2, 0xf0, 0xc6, 0x9a, 0x0d, 0x3f, 0x53, 0x65, 0xb8,
111 * This table contains the results of applying both the S-box and P-shuffle.
112 * It can be regenerated by compiling this file with -DCONFIG_SMALL -DTEST -DGENTABLES
114 static const uint32_t S_boxes_P_shuffle
[8][64] = {
116 0x00808200, 0x00000000, 0x00008000, 0x00808202, 0x00808002, 0x00008202, 0x00000002, 0x00008000,
117 0x00000200, 0x00808200, 0x00808202, 0x00000200, 0x00800202, 0x00808002, 0x00800000, 0x00000002,
118 0x00000202, 0x00800200, 0x00800200, 0x00008200, 0x00008200, 0x00808000, 0x00808000, 0x00800202,
119 0x00008002, 0x00800002, 0x00800002, 0x00008002, 0x00000000, 0x00000202, 0x00008202, 0x00800000,
120 0x00008000, 0x00808202, 0x00000002, 0x00808000, 0x00808200, 0x00800000, 0x00800000, 0x00000200,
121 0x00808002, 0x00008000, 0x00008200, 0x00800002, 0x00000200, 0x00000002, 0x00800202, 0x00008202,
122 0x00808202, 0x00008002, 0x00808000, 0x00800202, 0x00800002, 0x00000202, 0x00008202, 0x00808200,
123 0x00000202, 0x00800200, 0x00800200, 0x00000000, 0x00008002, 0x00008200, 0x00000000, 0x00808002,
126 0x40084010, 0x40004000, 0x00004000, 0x00084010, 0x00080000, 0x00000010, 0x40080010, 0x40004010,
127 0x40000010, 0x40084010, 0x40084000, 0x40000000, 0x40004000, 0x00080000, 0x00000010, 0x40080010,
128 0x00084000, 0x00080010, 0x40004010, 0x00000000, 0x40000000, 0x00004000, 0x00084010, 0x40080000,
129 0x00080010, 0x40000010, 0x00000000, 0x00084000, 0x00004010, 0x40084000, 0x40080000, 0x00004010,
130 0x00000000, 0x00084010, 0x40080010, 0x00080000, 0x40004010, 0x40080000, 0x40084000, 0x00004000,
131 0x40080000, 0x40004000, 0x00000010, 0x40084010, 0x00084010, 0x00000010, 0x00004000, 0x40000000,
132 0x00004010, 0x40084000, 0x00080000, 0x40000010, 0x00080010, 0x40004010, 0x40000010, 0x00080010,
133 0x00084000, 0x00000000, 0x40004000, 0x00004010, 0x40000000, 0x40080010, 0x40084010, 0x00084000,
136 0x00000104, 0x04010100, 0x00000000, 0x04010004, 0x04000100, 0x00000000, 0x00010104, 0x04000100,
137 0x00010004, 0x04000004, 0x04000004, 0x00010000, 0x04010104, 0x00010004, 0x04010000, 0x00000104,
138 0x04000000, 0x00000004, 0x04010100, 0x00000100, 0x00010100, 0x04010000, 0x04010004, 0x00010104,
139 0x04000104, 0x00010100, 0x00010000, 0x04000104, 0x00000004, 0x04010104, 0x00000100, 0x04000000,
140 0x04010100, 0x04000000, 0x00010004, 0x00000104, 0x00010000, 0x04010100, 0x04000100, 0x00000000,
141 0x00000100, 0x00010004, 0x04010104, 0x04000100, 0x04000004, 0x00000100, 0x00000000, 0x04010004,
142 0x04000104, 0x00010000, 0x04000000, 0x04010104, 0x00000004, 0x00010104, 0x00010100, 0x04000004,
143 0x04010000, 0x04000104, 0x00000104, 0x04010000, 0x00010104, 0x00000004, 0x04010004, 0x00010100,
146 0x80401000, 0x80001040, 0x80001040, 0x00000040, 0x00401040, 0x80400040, 0x80400000, 0x80001000,
147 0x00000000, 0x00401000, 0x00401000, 0x80401040, 0x80000040, 0x00000000, 0x00400040, 0x80400000,
148 0x80000000, 0x00001000, 0x00400000, 0x80401000, 0x00000040, 0x00400000, 0x80001000, 0x00001040,
149 0x80400040, 0x80000000, 0x00001040, 0x00400040, 0x00001000, 0x00401040, 0x80401040, 0x80000040,
150 0x00400040, 0x80400000, 0x00401000, 0x80401040, 0x80000040, 0x00000000, 0x00000000, 0x00401000,
151 0x00001040, 0x00400040, 0x80400040, 0x80000000, 0x80401000, 0x80001040, 0x80001040, 0x00000040,
152 0x80401040, 0x80000040, 0x80000000, 0x00001000, 0x80400000, 0x80001000, 0x00401040, 0x80400040,
153 0x80001000, 0x00001040, 0x00400000, 0x80401000, 0x00000040, 0x00400000, 0x00001000, 0x00401040,
156 0x00000080, 0x01040080, 0x01040000, 0x21000080, 0x00040000, 0x00000080, 0x20000000, 0x01040000,
157 0x20040080, 0x00040000, 0x01000080, 0x20040080, 0x21000080, 0x21040000, 0x00040080, 0x20000000,
158 0x01000000, 0x20040000, 0x20040000, 0x00000000, 0x20000080, 0x21040080, 0x21040080, 0x01000080,
159 0x21040000, 0x20000080, 0x00000000, 0x21000000, 0x01040080, 0x01000000, 0x21000000, 0x00040080,
160 0x00040000, 0x21000080, 0x00000080, 0x01000000, 0x20000000, 0x01040000, 0x21000080, 0x20040080,
161 0x01000080, 0x20000000, 0x21040000, 0x01040080, 0x20040080, 0x00000080, 0x01000000, 0x21040000,
162 0x21040080, 0x00040080, 0x21000000, 0x21040080, 0x01040000, 0x00000000, 0x20040000, 0x21000000,
163 0x00040080, 0x01000080, 0x20000080, 0x00040000, 0x00000000, 0x20040000, 0x01040080, 0x20000080,
166 0x10000008, 0x10200000, 0x00002000, 0x10202008, 0x10200000, 0x00000008, 0x10202008, 0x00200000,
167 0x10002000, 0x00202008, 0x00200000, 0x10000008, 0x00200008, 0x10002000, 0x10000000, 0x00002008,
168 0x00000000, 0x00200008, 0x10002008, 0x00002000, 0x00202000, 0x10002008, 0x00000008, 0x10200008,
169 0x10200008, 0x00000000, 0x00202008, 0x10202000, 0x00002008, 0x00202000, 0x10202000, 0x10000000,
170 0x10002000, 0x00000008, 0x10200008, 0x00202000, 0x10202008, 0x00200000, 0x00002008, 0x10000008,
171 0x00200000, 0x10002000, 0x10000000, 0x00002008, 0x10000008, 0x10202008, 0x00202000, 0x10200000,
172 0x00202008, 0x10202000, 0x00000000, 0x10200008, 0x00000008, 0x00002000, 0x10200000, 0x00202008,
173 0x00002000, 0x00200008, 0x10002008, 0x00000000, 0x10202000, 0x10000000, 0x00200008, 0x10002008,
176 0x00100000, 0x02100001, 0x02000401, 0x00000000, 0x00000400, 0x02000401, 0x00100401, 0x02100400,
177 0x02100401, 0x00100000, 0x00000000, 0x02000001, 0x00000001, 0x02000000, 0x02100001, 0x00000401,
178 0x02000400, 0x00100401, 0x00100001, 0x02000400, 0x02000001, 0x02100000, 0x02100400, 0x00100001,
179 0x02100000, 0x00000400, 0x00000401, 0x02100401, 0x00100400, 0x00000001, 0x02000000, 0x00100400,
180 0x02000000, 0x00100400, 0x00100000, 0x02000401, 0x02000401, 0x02100001, 0x02100001, 0x00000001,
181 0x00100001, 0x02000000, 0x02000400, 0x00100000, 0x02100400, 0x00000401, 0x00100401, 0x02100400,
182 0x00000401, 0x02000001, 0x02100401, 0x02100000, 0x00100400, 0x00000000, 0x00000001, 0x02100401,
183 0x00000000, 0x00100401, 0x02100000, 0x00000400, 0x02000001, 0x02000400, 0x00000400, 0x00100001,
186 0x08000820, 0x00000800, 0x00020000, 0x08020820, 0x08000000, 0x08000820, 0x00000020, 0x08000000,
187 0x00020020, 0x08020000, 0x08020820, 0x00020800, 0x08020800, 0x00020820, 0x00000800, 0x00000020,
188 0x08020000, 0x08000020, 0x08000800, 0x00000820, 0x00020800, 0x00020020, 0x08020020, 0x08020800,
189 0x00000820, 0x00000000, 0x00000000, 0x08020020, 0x08000020, 0x08000800, 0x00020820, 0x00020000,
190 0x00020820, 0x00020000, 0x08020800, 0x00000800, 0x00000020, 0x08020020, 0x00000800, 0x00020820,
191 0x08000800, 0x00000020, 0x08000020, 0x08020000, 0x08020020, 0x08000000, 0x00020000, 0x08000820,
192 0x00000000, 0x08020820, 0x00020020, 0x08000020, 0x08020000, 0x08000800, 0x08000820, 0x00000000,
193 0x08020820, 0x00020800, 0x00020800, 0x00000820, 0x00000820, 0x00020020, 0x08000000, 0x08020800,
198 static uint64_t shuffle(uint64_t in
, const uint8_t *shuffle
, int shuffle_len
) {
201 for (i
= 0; i
< shuffle_len
; i
++)
202 res
+= res
+ ((in
>> *shuffle
++) & 1);
206 static uint64_t shuffle_inv(uint64_t in
, const uint8_t *shuffle
, int shuffle_len
) {
209 shuffle
+= shuffle_len
- 1;
210 for (i
= 0; i
< shuffle_len
; i
++) {
211 res
|= (in
& 1) << *shuffle
--;
217 static uint32_t f_func(uint32_t r
, uint64_t k
) {
220 // rotate to get first part of E-shuffle in the lowest 6 bits
221 r
= (r
<< 1) | (r
>> 31);
222 // apply S-boxes, those compress the data again from 8 * 6 to 8 * 4 bits
223 for (i
= 7; i
>= 0; i
--) {
224 uint8_t tmp
= (r
^ k
) & 0x3f;
226 uint8_t v
= S_boxes
[i
][tmp
>> 1];
227 if (tmp
& 1) v
>>= 4;
228 out
= (out
>> 4) | (v
<< 28);
230 out
|= S_boxes_P_shuffle
[i
][tmp
];
232 // get next 6 bits of E-shuffle and round key k into the lowest bits
233 r
= (r
>> 4) | (r
<< 28);
237 out
= shuffle(out
, P_shuffle
, sizeof(P_shuffle
));
243 * \brief rotate the two halves of the expanded 56 bit key each 1 bit left
245 * Note: the specification calls this "shift", so I kept it although
248 static uint64_t key_shift_left(uint64_t CDn
) {
249 uint64_t carries
= (CDn
>> 27) & 0x10000001;
256 static void gen_roundkeys(uint64_t K
[16], uint64_t key
) {
258 // discard parity bits from key and shuffle it into C and D parts
259 uint64_t CDn
= shuffle(key
, PC1_shuffle
, sizeof(PC1_shuffle
));
260 // generate round keys
261 for (i
= 0; i
< 16; i
++) {
262 CDn
= key_shift_left(CDn
);
263 if (i
> 1 && i
!= 8 && i
!= 15)
264 CDn
= key_shift_left(CDn
);
265 K
[i
] = shuffle(CDn
, PC2_shuffle
, sizeof(PC2_shuffle
));
269 static uint64_t des_encdec(uint64_t in
, uint64_t K
[16], int decrypt
) {
271 // used to apply round keys in reverse order for decryption
272 decrypt
= decrypt
? 15 : 0;
273 // shuffle irrelevant to security but to ease hardware implementations
274 in
= shuffle(in
, IP_shuffle
, sizeof(IP_shuffle
));
275 for (i
= 0; i
< 16; i
++) {
277 f_res
= f_func(in
, K
[decrypt
^ i
]);
278 in
= (in
<< 32) | (in
>> 32);
281 in
= (in
<< 32) | (in
>> 32);
282 // reverse shuffle used to ease hardware implementations
283 in
= shuffle_inv(in
, IP_shuffle
, sizeof(IP_shuffle
));
287 int av_des_init(AVDES
*d
, const uint8_t *key
, int key_bits
, int decrypt
) {
288 if (key_bits
!= 64 && key_bits
!= 192)
290 d
->triple_des
= key_bits
> 64;
291 gen_roundkeys(d
->round_keys
[0], AV_RB64(key
));
293 gen_roundkeys(d
->round_keys
[1], AV_RB64(key
+ 8));
294 gen_roundkeys(d
->round_keys
[2], AV_RB64(key
+ 16));
299 void av_des_crypt(AVDES
*d
, uint8_t *dst
, const uint8_t *src
, int count
, uint8_t *iv
, int decrypt
) {
300 uint64_t iv_val
= iv
? be2me_64(*(uint64_t *)iv
) : 0;
301 while (count
-- > 0) {
303 uint64_t src_val
= src
? be2me_64(*(const uint64_t *)src
) : 0;
305 uint64_t tmp
= src_val
;
307 src_val
= des_encdec(src_val
, d
->round_keys
[2], 1);
308 src_val
= des_encdec(src_val
, d
->round_keys
[1], 0);
310 dst_val
= des_encdec(src_val
, d
->round_keys
[0], 1) ^ iv_val
;
311 iv_val
= iv
? tmp
: 0;
313 dst_val
= des_encdec(src_val
^ iv_val
, d
->round_keys
[0], 0);
315 dst_val
= des_encdec(dst_val
, d
->round_keys
[1], 1);
316 dst_val
= des_encdec(dst_val
, d
->round_keys
[2], 0);
318 iv_val
= iv
? dst_val
: 0;
320 *(uint64_t *)dst
= be2me_64(dst_val
);
325 *(uint64_t *)iv
= be2me_64(iv_val
);
334 #include <sys/time.h>
335 static uint64_t rand64(void) {
337 r
= (r
<< 32) | rand();
341 static const uint8_t test_key
[] = {0x12, 0x34, 0x56, 0x78, 0x9a, 0xbc, 0xde, 0xf0};
342 static const DECLARE_ALIGNED(8, uint8_t, plain
[]) = {0xfe, 0xdc, 0xba, 0x98, 0x76, 0x54, 0x32, 0x10};
343 static const DECLARE_ALIGNED(8, uint8_t, crypt
[]) = {0x4a, 0xb6, 0x5b, 0x3d, 0x4b, 0x06, 0x15, 0x18};
344 static DECLARE_ALIGNED(8, uint8_t, tmp
[8]);
345 static DECLARE_ALIGNED(8, uint8_t, large_buffer
[10002][8]);
346 static const uint8_t cbc_key
[] = {
347 0x01, 0x23, 0x45, 0x67, 0x89, 0xab, 0xcd, 0xef,
348 0x23, 0x45, 0x67, 0x89, 0xab, 0xcd, 0xef, 0x01,
349 0x45, 0x67, 0x89, 0xab, 0xcd, 0xef, 0x01, 0x23
352 static int run_test(int cbc
, int decrypt
) {
354 int delay
= cbc
&& !decrypt
? 2 : 1;
356 AV_WB64(large_buffer
[0], 0x4e6f772069732074ULL
);
357 AV_WB64(large_buffer
[1], 0x1234567890abcdefULL
);
358 AV_WB64(tmp
, 0x1234567890abcdefULL
);
359 av_des_init(&d
, cbc_key
, 192, decrypt
);
360 av_des_crypt(&d
, large_buffer
[delay
], large_buffer
[0], 10000, cbc
? tmp
: NULL
, decrypt
);
361 res
= AV_RB64(large_buffer
[9999 + delay
]);
364 return res
== 0xc5cecf63ecec514cULL
;
366 return res
== 0xcb191f85d1ed8439ULL
;
369 return res
== 0x8325397644091a0aULL
;
371 return res
== 0xdd17e8b8b437d232ULL
;
385 uint64_t roundkeys
[16];
386 gettimeofday(&tv
, NULL
);
387 srand(tv
.tv_sec
* 1000 * 1000 + tv
.tv_usec
);
388 key
[0] = AV_RB64(test_key
);
389 data
= AV_RB64(plain
);
390 gen_roundkeys(roundkeys
, key
[0]);
391 if (des_encdec(data
, roundkeys
, 0) != AV_RB64(crypt
)) {
392 printf("Test 1 failed\n");
395 av_des_init(&d
, test_key
, 64, 0);
396 av_des_crypt(&d
, tmp
, plain
, 1, NULL
, 0);
397 if (memcmp(tmp
, crypt
, sizeof(crypt
))) {
398 printf("Public API decryption failed\n");
401 if (!run_test(0, 0) || !run_test(0, 1) || !run_test(1, 0) || !run_test(1, 1)) {
402 printf("Partial Monte-Carlo test failed\n");
405 for (i
= 0; i
< 1000000; i
++) {
406 key
[0] = rand64(); key
[1] = rand64(); key
[2] = rand64();
408 av_des_init(&d
, key
, 192, 0);
409 av_des_crypt(&d
, &ct
, &data
, 1, NULL
, 0);
410 av_des_init(&d
, key
, 192, 1);
411 av_des_crypt(&d
, &ct
, &ct
, 1, NULL
, 1);
413 printf("Test 2 failed\n");
418 printf("static const uint32_t S_boxes_P_shuffle[8][64] = {\n");
419 for (i
= 0; i
< 8; i
++) {
421 for (j
= 0; j
< 64; j
++) {
422 uint32_t v
= S_boxes
[i
][j
>> 1];
423 v
= j
& 1 ? v
>> 4 : v
& 0xf;
425 v
= shuffle(v
, P_shuffle
, sizeof(P_shuffle
));
426 printf((j
& 7) == 0 ? "\n " : " ");
427 printf("0x%08X,", v
);