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