Statistics
| Branch: | Revision:

ffmpeg / libavutil / des.c @ 93826f56

History | View | Annotate | Download (14.5 KB)

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 "common.h"
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
26
static 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
39
static 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
52
static 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
65
static 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
78
static 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
 */
110
static 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

    
194
static 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

    
202
static 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

    
213
static 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
 */
244
static 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

    
252
uint64_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
#undef printf
282
#undef rand
283
#undef srand
284
#include <stdlib.h>
285
#include <stdio.h>
286
#include <sys/time.h>
287
static uint64_t rand64(void) {
288
    uint64_t r = rand();
289
    r = (r << 32) | rand();
290
    return r;
291
}
292

    
293
int main(void) {
294
    int i, j;
295
    struct timeval tv;
296
    uint64_t key;
297
    uint64_t data;
298
    uint64_t ct;
299
    gettimeofday(&tv, NULL);
300
    srand(tv.tv_sec * 1000 * 1000 + tv.tv_usec);
301
    key = 0x123456789abcdef0ULL;
302
    data = 0xfedcba9876543210ULL;
303
    if (ff_des_encdec(data, key, 0) != 0x4ab65b3d4b061518ULL) {
304
        printf("Test 1 failed\n");
305
        return 1;
306
    }
307
    for (i = 0; i < 1000000; i++) {
308
        key = rand64();
309
        data = rand64();
310
        ct = ff_des_encdec(data, key, 0);
311
        if (ff_des_encdec(ct, key, 1) != data) {
312
            printf("Test 2 failed\n");
313
            return 1;
314
        }
315
    }
316
#ifdef GENTABLES
317
    printf("static const uint32_t S_boxes_P_shuffle[8][64] = {\n");
318
    for (i = 0; i < 8; i++) {
319
        printf("    {");
320
        for (j = 0; j < 64; j++) {
321
            uint32_t v = S_boxes[i][j >> 1];
322
            v = j & 1 ? v >> 4 : v & 0xf;
323
            v <<= 28 - 4 * i;
324
            v = shuffle(v, P_shuffle, sizeof(P_shuffle));
325
            printf((j & 7) == 0 ? "\n    " : " ");
326
            printf("0x%08X,", v);
327
        }
328
        printf("\n    },\n");
329
    }
330
    printf("};\n");
331
#endif
332
    return 0;
333
}
334
#endif