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 #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