git.sesse.net Git - ffmpeg/blob - libavutil/des.c

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