Statistics
| Branch: | Revision:

ffmpeg / libavutil / des.c @ 2e9ad69a

History | View | Annotate | Download (14.4 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 "des.h"
23

    
24
#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
25
static const uint8_t IP_shuffle[] = {
26
    T(58, 50, 42, 34, 26, 18, 10, 2),
27
    T(60, 52, 44, 36, 28, 20, 12, 4),
28
    T(62, 54, 46, 38, 30, 22, 14, 6),
29
    T(64, 56, 48, 40, 32, 24, 16, 8),
30
    T(57, 49, 41, 33, 25, 17,  9, 1),
31
    T(59, 51, 43, 35, 27, 19, 11, 3),
32
    T(61, 53, 45, 37, 29, 21, 13, 5),
33
    T(63, 55, 47, 39, 31, 23, 15, 7)
34
};
35
#undef T
36

    
37
#define T(a, b, c, d) 32-a,32-b,32-c,32-d
38
static const uint8_t P_shuffle[] = {
39
    T(16,  7, 20, 21),
40
    T(29, 12, 28, 17),
41
    T( 1, 15, 23, 26),
42
    T( 5, 18, 31, 10),
43
    T( 2,  8, 24, 14),
44
    T(32, 27,  3,  9),
45
    T(19, 13, 30,  6),
46
    T(22, 11,  4, 25)
47
};
48
#undef T
49

    
50
#define T(a, b, c, d, e, f, g) 64-a,64-b,64-c,64-d,64-e,64-f,64-g
51
static const uint8_t PC1_shuffle[] = {
52
    T(57, 49, 41, 33, 25, 17,  9),
53
    T( 1, 58, 50, 42, 34, 26, 18),
54
    T(10,  2, 59, 51, 43, 35, 27),
55
    T(19, 11,  3, 60, 52, 44, 36),
56
    T(63, 55, 47, 39, 31, 23, 15),
57
    T( 7, 62, 54, 46, 38, 30, 22),
58
    T(14,  6, 61, 53, 45, 37, 29),
59
    T(21, 13,  5, 28, 20, 12,  4)
60
};
61
#undef T
62

    
63
#define T(a, b, c, d, e, f) 56-a,56-b,56-c,56-d,56-e,56-f
64
static const uint8_t PC2_shuffle[] = {
65
    T(14, 17, 11, 24,  1,  5),
66
    T( 3, 28, 15,  6, 21, 10),
67
    T(23, 19, 12,  4, 26,  8),
68
    T(16,  7, 27, 20, 13,  2),
69
    T(41, 52, 31, 37, 47, 55),
70
    T(30, 40, 51, 45, 33, 48),
71
    T(44, 49, 39, 56, 34, 53),
72
    T(46, 42, 50, 36, 29, 32)
73
};
74
#undef T
75

    
76
#ifdef CONFIG_SMALL
77
static const uint8_t S_boxes[8][32] = {
78
    {
79
    0x0e, 0xf4, 0x7d, 0x41, 0xe2, 0x2f, 0xdb, 0x18, 0xa3, 0x6a, 0xc6, 0xbc, 0x95, 0x59, 0x30, 0x87,
80
    0xf4, 0xc1, 0x8e, 0x28, 0x4d, 0x96, 0x12, 0x7b, 0x5f, 0xbc, 0x39, 0xe7, 0xa3, 0x0a, 0x65, 0xd0,
81
    }, {
82
    0x3f, 0xd1, 0x48, 0x7e, 0xf6, 0x2b, 0x83, 0xe4, 0xc9, 0x07, 0x12, 0xad, 0x6c, 0x90, 0xb5, 0x5a,
83
    0xd0, 0x8e, 0xa7, 0x1b, 0x3a, 0xf4, 0x4d, 0x21, 0xb5, 0x68, 0x7c, 0xc6, 0x09, 0x53, 0xe2, 0x9f,
84
    }, {
85
    0xda, 0x70, 0x09, 0x9e, 0x36, 0x43, 0x6f, 0xa5, 0x21, 0x8d, 0x5c, 0xe7, 0xcb, 0xb4, 0xf2, 0x18,
86
    0x1d, 0xa6, 0xd4, 0x09, 0x68, 0x9f, 0x83, 0x70, 0x4b, 0xf1, 0xe2, 0x3c, 0xb5, 0x5a, 0x2e, 0xc7,
87
    }, {
88
    0xd7, 0x8d, 0xbe, 0x53, 0x60, 0xf6, 0x09, 0x3a, 0x41, 0x72, 0x28, 0xc5, 0x1b, 0xac, 0xe4, 0x9f,
89
    0x3a, 0xf6, 0x09, 0x60, 0xac, 0x1b, 0xd7, 0x8d, 0x9f, 0x41, 0x53, 0xbe, 0xc5, 0x72, 0x28, 0xe4,
90
    }, {
91
    0xe2, 0xbc, 0x24, 0xc1, 0x47, 0x7a, 0xdb, 0x16, 0x58, 0x05, 0xf3, 0xaf, 0x3d, 0x90, 0x8e, 0x69,
92
    0xb4, 0x82, 0xc1, 0x7b, 0x1a, 0xed, 0x27, 0xd8, 0x6f, 0xf9, 0x0c, 0x95, 0xa6, 0x43, 0x50, 0x3e,
93
    }, {
94
    0xac, 0xf1, 0x4a, 0x2f, 0x79, 0xc2, 0x96, 0x58, 0x60, 0x1d, 0xd3, 0xe4, 0x0e, 0xb7, 0x35, 0x8b,
95
    0x49, 0x3e, 0x2f, 0xc5, 0x92, 0x58, 0xfc, 0xa3, 0xb7, 0xe0, 0x14, 0x7a, 0x61, 0x0d, 0x8b, 0xd6,
96
    }, {
97
    0xd4, 0x0b, 0xb2, 0x7e, 0x4f, 0x90, 0x18, 0xad, 0xe3, 0x3c, 0x59, 0xc7, 0x25, 0xfa, 0x86, 0x61,
98
    0x61, 0xb4, 0xdb, 0x8d, 0x1c, 0x43, 0xa7, 0x7e, 0x9a, 0x5f, 0x06, 0xf8, 0xe0, 0x25, 0x39, 0xc2,
99
    }, {
100
    0x1d, 0xf2, 0xd8, 0x84, 0xa6, 0x3f, 0x7b, 0x41, 0xca, 0x59, 0x63, 0xbe, 0x05, 0xe0, 0x9c, 0x27,
101
    0x27, 0x1b, 0xe4, 0x71, 0x49, 0xac, 0x8e, 0xd2, 0xf0, 0xc6, 0x9a, 0x0d, 0x3f, 0x53, 0x65, 0xb8,
102
    }
103
};
104
#else
105
/**
106
 * This table contains the results of applying both the S-box and P-shuffle.
107
 * It can be regenerated by compiling this file with -DCONFIG_SMALL -DTEST -DGENTABLES
108
 */
109
static const uint32_t S_boxes_P_shuffle[8][64] = {
110
    {
111
    0x00808200, 0x00000000, 0x00008000, 0x00808202, 0x00808002, 0x00008202, 0x00000002, 0x00008000,
112
    0x00000200, 0x00808200, 0x00808202, 0x00000200, 0x00800202, 0x00808002, 0x00800000, 0x00000002,
113
    0x00000202, 0x00800200, 0x00800200, 0x00008200, 0x00008200, 0x00808000, 0x00808000, 0x00800202,
114
    0x00008002, 0x00800002, 0x00800002, 0x00008002, 0x00000000, 0x00000202, 0x00008202, 0x00800000,
115
    0x00008000, 0x00808202, 0x00000002, 0x00808000, 0x00808200, 0x00800000, 0x00800000, 0x00000200,
116
    0x00808002, 0x00008000, 0x00008200, 0x00800002, 0x00000200, 0x00000002, 0x00800202, 0x00008202,
117
    0x00808202, 0x00008002, 0x00808000, 0x00800202, 0x00800002, 0x00000202, 0x00008202, 0x00808200,
118
    0x00000202, 0x00800200, 0x00800200, 0x00000000, 0x00008002, 0x00008200, 0x00000000, 0x00808002,
119
    },
120
    {
121
    0x40084010, 0x40004000, 0x00004000, 0x00084010, 0x00080000, 0x00000010, 0x40080010, 0x40004010,
122
    0x40000010, 0x40084010, 0x40084000, 0x40000000, 0x40004000, 0x00080000, 0x00000010, 0x40080010,
123
    0x00084000, 0x00080010, 0x40004010, 0x00000000, 0x40000000, 0x00004000, 0x00084010, 0x40080000,
124
    0x00080010, 0x40000010, 0x00000000, 0x00084000, 0x00004010, 0x40084000, 0x40080000, 0x00004010,
125
    0x00000000, 0x00084010, 0x40080010, 0x00080000, 0x40004010, 0x40080000, 0x40084000, 0x00004000,
126
    0x40080000, 0x40004000, 0x00000010, 0x40084010, 0x00084010, 0x00000010, 0x00004000, 0x40000000,
127
    0x00004010, 0x40084000, 0x00080000, 0x40000010, 0x00080010, 0x40004010, 0x40000010, 0x00080010,
128
    0x00084000, 0x00000000, 0x40004000, 0x00004010, 0x40000000, 0x40080010, 0x40084010, 0x00084000,
129
    },
130
    {
131
    0x00000104, 0x04010100, 0x00000000, 0x04010004, 0x04000100, 0x00000000, 0x00010104, 0x04000100,
132
    0x00010004, 0x04000004, 0x04000004, 0x00010000, 0x04010104, 0x00010004, 0x04010000, 0x00000104,
133
    0x04000000, 0x00000004, 0x04010100, 0x00000100, 0x00010100, 0x04010000, 0x04010004, 0x00010104,
134
    0x04000104, 0x00010100, 0x00010000, 0x04000104, 0x00000004, 0x04010104, 0x00000100, 0x04000000,
135
    0x04010100, 0x04000000, 0x00010004, 0x00000104, 0x00010000, 0x04010100, 0x04000100, 0x00000000,
136
    0x00000100, 0x00010004, 0x04010104, 0x04000100, 0x04000004, 0x00000100, 0x00000000, 0x04010004,
137
    0x04000104, 0x00010000, 0x04000000, 0x04010104, 0x00000004, 0x00010104, 0x00010100, 0x04000004,
138
    0x04010000, 0x04000104, 0x00000104, 0x04010000, 0x00010104, 0x00000004, 0x04010004, 0x00010100,
139
    },
140
    {
141
    0x80401000, 0x80001040, 0x80001040, 0x00000040, 0x00401040, 0x80400040, 0x80400000, 0x80001000,
142
    0x00000000, 0x00401000, 0x00401000, 0x80401040, 0x80000040, 0x00000000, 0x00400040, 0x80400000,
143
    0x80000000, 0x00001000, 0x00400000, 0x80401000, 0x00000040, 0x00400000, 0x80001000, 0x00001040,
144
    0x80400040, 0x80000000, 0x00001040, 0x00400040, 0x00001000, 0x00401040, 0x80401040, 0x80000040,
145
    0x00400040, 0x80400000, 0x00401000, 0x80401040, 0x80000040, 0x00000000, 0x00000000, 0x00401000,
146
    0x00001040, 0x00400040, 0x80400040, 0x80000000, 0x80401000, 0x80001040, 0x80001040, 0x00000040,
147
    0x80401040, 0x80000040, 0x80000000, 0x00001000, 0x80400000, 0x80001000, 0x00401040, 0x80400040,
148
    0x80001000, 0x00001040, 0x00400000, 0x80401000, 0x00000040, 0x00400000, 0x00001000, 0x00401040,
149
    },
150
    {
151
    0x00000080, 0x01040080, 0x01040000, 0x21000080, 0x00040000, 0x00000080, 0x20000000, 0x01040000,
152
    0x20040080, 0x00040000, 0x01000080, 0x20040080, 0x21000080, 0x21040000, 0x00040080, 0x20000000,
153
    0x01000000, 0x20040000, 0x20040000, 0x00000000, 0x20000080, 0x21040080, 0x21040080, 0x01000080,
154
    0x21040000, 0x20000080, 0x00000000, 0x21000000, 0x01040080, 0x01000000, 0x21000000, 0x00040080,
155
    0x00040000, 0x21000080, 0x00000080, 0x01000000, 0x20000000, 0x01040000, 0x21000080, 0x20040080,
156
    0x01000080, 0x20000000, 0x21040000, 0x01040080, 0x20040080, 0x00000080, 0x01000000, 0x21040000,
157
    0x21040080, 0x00040080, 0x21000000, 0x21040080, 0x01040000, 0x00000000, 0x20040000, 0x21000000,
158
    0x00040080, 0x01000080, 0x20000080, 0x00040000, 0x00000000, 0x20040000, 0x01040080, 0x20000080,
159
    },
160
    {
161
    0x10000008, 0x10200000, 0x00002000, 0x10202008, 0x10200000, 0x00000008, 0x10202008, 0x00200000,
162
    0x10002000, 0x00202008, 0x00200000, 0x10000008, 0x00200008, 0x10002000, 0x10000000, 0x00002008,
163
    0x00000000, 0x00200008, 0x10002008, 0x00002000, 0x00202000, 0x10002008, 0x00000008, 0x10200008,
164
    0x10200008, 0x00000000, 0x00202008, 0x10202000, 0x00002008, 0x00202000, 0x10202000, 0x10000000,
165
    0x10002000, 0x00000008, 0x10200008, 0x00202000, 0x10202008, 0x00200000, 0x00002008, 0x10000008,
166
    0x00200000, 0x10002000, 0x10000000, 0x00002008, 0x10000008, 0x10202008, 0x00202000, 0x10200000,
167
    0x00202008, 0x10202000, 0x00000000, 0x10200008, 0x00000008, 0x00002000, 0x10200000, 0x00202008,
168
    0x00002000, 0x00200008, 0x10002008, 0x00000000, 0x10202000, 0x10000000, 0x00200008, 0x10002008,
169
    },
170
    {
171
    0x00100000, 0x02100001, 0x02000401, 0x00000000, 0x00000400, 0x02000401, 0x00100401, 0x02100400,
172
    0x02100401, 0x00100000, 0x00000000, 0x02000001, 0x00000001, 0x02000000, 0x02100001, 0x00000401,
173
    0x02000400, 0x00100401, 0x00100001, 0x02000400, 0x02000001, 0x02100000, 0x02100400, 0x00100001,
174
    0x02100000, 0x00000400, 0x00000401, 0x02100401, 0x00100400, 0x00000001, 0x02000000, 0x00100400,
175
    0x02000000, 0x00100400, 0x00100000, 0x02000401, 0x02000401, 0x02100001, 0x02100001, 0x00000001,
176
    0x00100001, 0x02000000, 0x02000400, 0x00100000, 0x02100400, 0x00000401, 0x00100401, 0x02100400,
177
    0x00000401, 0x02000001, 0x02100401, 0x02100000, 0x00100400, 0x00000000, 0x00000001, 0x02100401,
178
    0x00000000, 0x00100401, 0x02100000, 0x00000400, 0x02000001, 0x02000400, 0x00000400, 0x00100001,
179
    },
180
    {
181
    0x08000820, 0x00000800, 0x00020000, 0x08020820, 0x08000000, 0x08000820, 0x00000020, 0x08000000,
182
    0x00020020, 0x08020000, 0x08020820, 0x00020800, 0x08020800, 0x00020820, 0x00000800, 0x00000020,
183
    0x08020000, 0x08000020, 0x08000800, 0x00000820, 0x00020800, 0x00020020, 0x08020020, 0x08020800,
184
    0x00000820, 0x00000000, 0x00000000, 0x08020020, 0x08000020, 0x08000800, 0x00020820, 0x00020000,
185
    0x00020820, 0x00020000, 0x08020800, 0x00000800, 0x00000020, 0x08020020, 0x00000800, 0x00020820,
186
    0x08000800, 0x00000020, 0x08000020, 0x08020000, 0x08020020, 0x08000000, 0x00020000, 0x08000820,
187
    0x00000000, 0x08020820, 0x00020020, 0x08000020, 0x08020000, 0x08000800, 0x08000820, 0x00000000,
188
    0x08020820, 0x00020800, 0x00020800, 0x00000820, 0x00000820, 0x00020020, 0x08000000, 0x08020800,
189
    },
190
};
191
#endif
192

    
193
static uint64_t shuffle(uint64_t in, const uint8_t *shuffle, int shuffle_len) {
194
    int i;
195
    uint64_t res = 0;
196
    for (i = 0; i < shuffle_len; i++)
197
        res += res + ((in >> *shuffle++) & 1);
198
    return res;
199
}
200

    
201
static uint64_t shuffle_inv(uint64_t in, const uint8_t *shuffle, int shuffle_len) {
202
    int i;
203
    uint64_t res = 0;
204
    shuffle += shuffle_len - 1;
205
    for (i = 0; i < shuffle_len; i++) {
206
        res |= (in & 1) << *shuffle--;
207
        in >>= 1;
208
    }
209
    return res;
210
}
211

    
212
static uint32_t f_func(uint32_t r, uint64_t k) {
213
    int i;
214
    uint32_t out = 0;
215
    // rotate to get first part of E-shuffle in the lowest 6 bits
216
    r = (r << 1) | (r >> 31);
217
    // apply S-boxes, those compress the data again from 8 * 6 to 8 * 4 bits
218
    for (i = 7; i >= 0; i--) {
219
        uint8_t tmp = (r ^ k) & 0x3f;
220
#ifdef CONFIG_SMALL
221
        uint8_t v = S_boxes[i][tmp >> 1];
222
        if (tmp & 1) v >>= 4;
223
        out = (out >> 4) | (v << 28);
224
#else
225
        out |= S_boxes_P_shuffle[i][tmp];
226
#endif
227
        // get next 6 bits of E-shuffle and round key k into the lowest bits
228
        r = (r >> 4) | (r << 28);
229
        k >>= 6;
230
    }
231
#ifdef CONFIG_SMALL
232
    out = shuffle(out, P_shuffle, sizeof(P_shuffle));
233
#endif
234
    return out;
235
}
236

    
237
/**
238
 * \brief rotate the two halves of the expanded 56 bit key each 1 bit left
239
 *
240
 * Note: the specification calls this "shift", so I kept it although
241
 * it is confusing.
242
 */
243
static uint64_t key_shift_left(uint64_t CDn) {
244
    uint64_t carries = (CDn >> 27) & 0x10000001;
245
    CDn <<= 1;
246
    CDn &= ~0x10000001;
247
    CDn |= carries;
248
    return CDn;
249
}
250

    
251
uint64_t ff_des_encdec(uint64_t in, uint64_t key, int decrypt) {
252
    int i;
253
    uint64_t K[16];
254
    // discard parity bits from key and shuffle it into C and D parts
255
    uint64_t CDn = shuffle(key, PC1_shuffle, sizeof(PC1_shuffle));
256
    // generate round keys
257
    for (i = 0; i < 16; i++) {
258
        CDn = key_shift_left(CDn);
259
        if (i > 1 && i != 8 && i != 15)
260
            CDn = key_shift_left(CDn);
261
        K[i] = shuffle(CDn, PC2_shuffle, sizeof(PC2_shuffle));
262
    }
263
    // used to apply round keys in reverse order for decryption
264
    decrypt = decrypt ? 15 : 0;
265
    // shuffle irrelevant to security but to ease hardware implementations
266
    in = shuffle(in, IP_shuffle, sizeof(IP_shuffle));
267
    for (i = 0; i < 16; i++) {
268
        uint32_t f_res;
269
        f_res = f_func(in, K[decrypt ^ i]);
270
        in = (in << 32) | (in >> 32);
271
        in ^= f_res;
272
    }
273
    in = (in << 32) | (in >> 32);
274
    // reverse shuffle used to ease hardware implementations
275
    in = shuffle_inv(in, IP_shuffle, sizeof(IP_shuffle));
276
    return in;
277
}
278

    
279
#ifdef TEST
280
#include <stdlib.h>
281
#include <stdio.h>
282
#include <sys/time.h>
283
static uint64_t rand64(void) {
284
    uint64_t r = rand();
285
    r = (r << 32) | rand();
286
    return r;
287
}
288

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