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