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