_ Git - BearSSL/blob - src/symcipher/des_tab.c

   1 /*
   2  * Copyright (c) 2016 Thomas Pornin <pornin@bolet.org>
   3  *
   4  * Permission is hereby granted, free of charge, to any person obtaining
   5  * a copy of this software and associated documentation files (the
   6  * "Software"), to deal in the Software without restriction, including
   7  * without limitation the rights to use, copy, modify, merge, publish,
   8  * distribute, sublicense, and/or sell copies of the Software, and to
   9  * permit persons to whom the Software is furnished to do so, subject to
  10  * the following conditions:
  11  *
  12  * The above copyright notice and this permission notice shall be
  13  * included in all copies or substantial portions of the Software.
  14  *
  15  * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
  16  * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
  17  * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
  18  * NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS
  19  * BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN
  20  * ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN
  21  * CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE
  22  * SOFTWARE.
  23  */
  24
  25 #include "inner.h"
  26
  27 /*
  28  * PC2left[x] tells where bit x goes when applying PC-2. 'x' is a bit
  29  * position in the left rotated key word. Both position are in normal
  30  * order (rightmost bit is 0).
  31  */
  32 static const unsigned char PC2left[] = {
  33         16,  3,  7, 24, 20, 11, 24,
  34         13,  2, 10, 24, 22,  5, 15,
  35         23,  1,  9, 21, 12, 24,  6,
  36          4, 14, 18,  8, 17,  0, 19
  37 };
  38
  39 /*
  40  * Similar to PC2left[x], for the right rotated key word.
  41  */
  42 static const unsigned char PC2right[] = {
  43          8, 18, 24,  6, 22, 15,  3,
  44         10, 12, 19,  5, 14, 11, 24,
  45          4, 23, 16,  9, 24, 20,  2,
  46         24,  7, 13,  0, 21, 17,  1
  47 };
  48
  49 /*
  50  * S-boxes and PC-1 merged.
  51  */
  52 static const uint32_t S1[] = {
  53         0x00808200, 0x00000000, 0x00008000, 0x00808202,
  54         0x00808002, 0x00008202, 0x00000002, 0x00008000,
  55         0x00000200, 0x00808200, 0x00808202, 0x00000200,
  56         0x00800202, 0x00808002, 0x00800000, 0x00000002,
  57         0x00000202, 0x00800200, 0x00800200, 0x00008200,
  58         0x00008200, 0x00808000, 0x00808000, 0x00800202,
  59         0x00008002, 0x00800002, 0x00800002, 0x00008002,
  60         0x00000000, 0x00000202, 0x00008202, 0x00800000,
  61         0x00008000, 0x00808202, 0x00000002, 0x00808000,
  62         0x00808200, 0x00800000, 0x00800000, 0x00000200,
  63         0x00808002, 0x00008000, 0x00008200, 0x00800002,
  64         0x00000200, 0x00000002, 0x00800202, 0x00008202,
  65         0x00808202, 0x00008002, 0x00808000, 0x00800202,
  66         0x00800002, 0x00000202, 0x00008202, 0x00808200,
  67         0x00000202, 0x00800200, 0x00800200, 0x00000000,
  68         0x00008002, 0x00008200, 0x00000000, 0x00808002
  69 };
  70
  71 static const uint32_t S2[] = {
  72         0x40084010, 0x40004000, 0x00004000, 0x00084010,
  73         0x00080000, 0x00000010, 0x40080010, 0x40004010,
  74         0x40000010, 0x40084010, 0x40084000, 0x40000000,
  75         0x40004000, 0x00080000, 0x00000010, 0x40080010,
  76         0x00084000, 0x00080010, 0x40004010, 0x00000000,
  77         0x40000000, 0x00004000, 0x00084010, 0x40080000,
  78         0x00080010, 0x40000010, 0x00000000, 0x00084000,
  79         0x00004010, 0x40084000, 0x40080000, 0x00004010,
  80         0x00000000, 0x00084010, 0x40080010, 0x00080000,
  81         0x40004010, 0x40080000, 0x40084000, 0x00004000,
  82         0x40080000, 0x40004000, 0x00000010, 0x40084010,
  83         0x00084010, 0x00000010, 0x00004000, 0x40000000,
  84         0x00004010, 0x40084000, 0x00080000, 0x40000010,
  85         0x00080010, 0x40004010, 0x40000010, 0x00080010,
  86         0x00084000, 0x00000000, 0x40004000, 0x00004010,
  87         0x40000000, 0x40080010, 0x40084010, 0x00084000
  88 };
  89
  90 static const uint32_t S3[] = {
  91         0x00000104, 0x04010100, 0x00000000, 0x04010004,
  92         0x04000100, 0x00000000, 0x00010104, 0x04000100,
  93         0x00010004, 0x04000004, 0x04000004, 0x00010000,
  94         0x04010104, 0x00010004, 0x04010000, 0x00000104,
  95         0x04000000, 0x00000004, 0x04010100, 0x00000100,
  96         0x00010100, 0x04010000, 0x04010004, 0x00010104,
  97         0x04000104, 0x00010100, 0x00010000, 0x04000104,
  98         0x00000004, 0x04010104, 0x00000100, 0x04000000,
  99         0x04010100, 0x04000000, 0x00010004, 0x00000104,
 100         0x00010000, 0x04010100, 0x04000100, 0x00000000,
 101         0x00000100, 0x00010004, 0x04010104, 0x04000100,
 102         0x04000004, 0x00000100, 0x00000000, 0x04010004,
 103         0x04000104, 0x00010000, 0x04000000, 0x04010104,
 104         0x00000004, 0x00010104, 0x00010100, 0x04000004,
 105         0x04010000, 0x04000104, 0x00000104, 0x04010000,
 106         0x00010104, 0x00000004, 0x04010004, 0x00010100
 107 };
 108
 109 static const uint32_t S4[] = {
 110         0x80401000, 0x80001040, 0x80001040, 0x00000040,
 111         0x00401040, 0x80400040, 0x80400000, 0x80001000,
 112         0x00000000, 0x00401000, 0x00401000, 0x80401040,
 113         0x80000040, 0x00000000, 0x00400040, 0x80400000,
 114         0x80000000, 0x00001000, 0x00400000, 0x80401000,
 115         0x00000040, 0x00400000, 0x80001000, 0x00001040,
 116         0x80400040, 0x80000000, 0x00001040, 0x00400040,
 117         0x00001000, 0x00401040, 0x80401040, 0x80000040,
 118         0x00400040, 0x80400000, 0x00401000, 0x80401040,
 119         0x80000040, 0x00000000, 0x00000000, 0x00401000,
 120         0x00001040, 0x00400040, 0x80400040, 0x80000000,
 121         0x80401000, 0x80001040, 0x80001040, 0x00000040,
 122         0x80401040, 0x80000040, 0x80000000, 0x00001000,
 123         0x80400000, 0x80001000, 0x00401040, 0x80400040,
 124         0x80001000, 0x00001040, 0x00400000, 0x80401000,
 125         0x00000040, 0x00400000, 0x00001000, 0x00401040
 126 };
 127
 128 static const uint32_t S5[] = {
 129         0x00000080, 0x01040080, 0x01040000, 0x21000080,
 130         0x00040000, 0x00000080, 0x20000000, 0x01040000,
 131         0x20040080, 0x00040000, 0x01000080, 0x20040080,
 132         0x21000080, 0x21040000, 0x00040080, 0x20000000,
 133         0x01000000, 0x20040000, 0x20040000, 0x00000000,
 134         0x20000080, 0x21040080, 0x21040080, 0x01000080,
 135         0x21040000, 0x20000080, 0x00000000, 0x21000000,
 136         0x01040080, 0x01000000, 0x21000000, 0x00040080,
 137         0x00040000, 0x21000080, 0x00000080, 0x01000000,
 138         0x20000000, 0x01040000, 0x21000080, 0x20040080,
 139         0x01000080, 0x20000000, 0x21040000, 0x01040080,
 140         0x20040080, 0x00000080, 0x01000000, 0x21040000,
 141         0x21040080, 0x00040080, 0x21000000, 0x21040080,
 142         0x01040000, 0x00000000, 0x20040000, 0x21000000,
 143         0x00040080, 0x01000080, 0x20000080, 0x00040000,
 144         0x00000000, 0x20040000, 0x01040080, 0x20000080
 145 };
 146
 147 static const uint32_t S6[] = {
 148         0x10000008, 0x10200000, 0x00002000, 0x10202008,
 149         0x10200000, 0x00000008, 0x10202008, 0x00200000,
 150         0x10002000, 0x00202008, 0x00200000, 0x10000008,
 151         0x00200008, 0x10002000, 0x10000000, 0x00002008,
 152         0x00000000, 0x00200008, 0x10002008, 0x00002000,
 153         0x00202000, 0x10002008, 0x00000008, 0x10200008,
 154         0x10200008, 0x00000000, 0x00202008, 0x10202000,
 155         0x00002008, 0x00202000, 0x10202000, 0x10000000,
 156         0x10002000, 0x00000008, 0x10200008, 0x00202000,
 157         0x10202008, 0x00200000, 0x00002008, 0x10000008,
 158         0x00200000, 0x10002000, 0x10000000, 0x00002008,
 159         0x10000008, 0x10202008, 0x00202000, 0x10200000,
 160         0x00202008, 0x10202000, 0x00000000, 0x10200008,
 161         0x00000008, 0x00002000, 0x10200000, 0x00202008,
 162         0x00002000, 0x00200008, 0x10002008, 0x00000000,
 163         0x10202000, 0x10000000, 0x00200008, 0x10002008
 164 };
 165
 166 static const uint32_t S7[] = {
 167         0x00100000, 0x02100001, 0x02000401, 0x00000000,
 168         0x00000400, 0x02000401, 0x00100401, 0x02100400,
 169         0x02100401, 0x00100000, 0x00000000, 0x02000001,
 170         0x00000001, 0x02000000, 0x02100001, 0x00000401,
 171         0x02000400, 0x00100401, 0x00100001, 0x02000400,
 172         0x02000001, 0x02100000, 0x02100400, 0x00100001,
 173         0x02100000, 0x00000400, 0x00000401, 0x02100401,
 174         0x00100400, 0x00000001, 0x02000000, 0x00100400,
 175         0x02000000, 0x00100400, 0x00100000, 0x02000401,
 176         0x02000401, 0x02100001, 0x02100001, 0x00000001,
 177         0x00100001, 0x02000000, 0x02000400, 0x00100000,
 178         0x02100400, 0x00000401, 0x00100401, 0x02100400,
 179         0x00000401, 0x02000001, 0x02100401, 0x02100000,
 180         0x00100400, 0x00000000, 0x00000001, 0x02100401,
 181         0x00000000, 0x00100401, 0x02100000, 0x00000400,
 182         0x02000001, 0x02000400, 0x00000400, 0x00100001
 183 };
 184
 185 static const uint32_t S8[] = {
 186         0x08000820, 0x00000800, 0x00020000, 0x08020820,
 187         0x08000000, 0x08000820, 0x00000020, 0x08000000,
 188         0x00020020, 0x08020000, 0x08020820, 0x00020800,
 189         0x08020800, 0x00020820, 0x00000800, 0x00000020,
 190         0x08020000, 0x08000020, 0x08000800, 0x00000820,
 191         0x00020800, 0x00020020, 0x08020020, 0x08020800,
 192         0x00000820, 0x00000000, 0x00000000, 0x08020020,
 193         0x08000020, 0x08000800, 0x00020820, 0x00020000,
 194         0x00020820, 0x00020000, 0x08020800, 0x00000800,
 195         0x00000020, 0x08020020, 0x00000800, 0x00020820,
 196         0x08000800, 0x00000020, 0x08000020, 0x08020000,
 197         0x08020020, 0x08000000, 0x00020000, 0x08000820,
 198         0x00000000, 0x08020820, 0x00020020, 0x08000020,
 199         0x08020000, 0x08000800, 0x08000820, 0x00000000,
 200         0x08020820, 0x00020800, 0x00020800, 0x00000820,
 201         0x00000820, 0x00020020, 0x08000000, 0x08020800
 202 };
 203
 204 static inline uint32_t
 205 Fconf(uint32_t r0, uint32_t skl, uint32_t skr)
 206 {
 207         uint32_t r1;
 208
 209         r1 = (r0 << 16) | (r0 >> 16);
 210         return
 211                   S1[((r1 >> 11) ^ (skl >> 18)) & 0x3F]
 212                 | S2[((r0 >> 23) ^ (skl >> 12)) & 0x3F]
 213                 | S3[((r0 >> 19) ^ (skl >>  6)) & 0x3F]
 214                 | S4[((r0 >> 15) ^ (skl      )) & 0x3F]
 215                 | S5[((r0 >> 11) ^ (skr >> 18)) & 0x3F]
 216                 | S6[((r0 >>  7) ^ (skr >> 12)) & 0x3F]
 217                 | S7[((r0 >>  3) ^ (skr >>  6)) & 0x3F]
 218                 | S8[((r1 >> 15) ^ (skr      )) & 0x3F];
 219 }
 220
 221 static void
 222 process_block_unit(uint32_t *pl, uint32_t *pr, const uint32_t *skey)
 223 {
 224         int i;
 225         uint32_t l, r;
 226
 227         l = *pl;
 228         r = *pr;
 229         for (i = 0; i < 16; i ++) {
 230                 uint32_t t;
 231
 232                 t = l ^ Fconf(r, skey[(i << 1) + 0], skey[(i << 1) + 1]);
 233                 l = r;
 234                 r = t;
 235         }
 236         *pl = r;
 237         *pr = l;
 238 }
 239
 240 /* see inner.h */
 241 void
 242 br_des_tab_process_block(unsigned num_rounds, const uint32_t *skey, void *block)
 243 {
 244         unsigned char *buf;
 245         uint32_t l, r;
 246
 247         buf = block;
 248         l = br_dec32be(buf);
 249         r = br_dec32be(buf + 4);
 250         br_des_do_IP(&l, &r);
 251         while (num_rounds -- > 0) {
 252                 process_block_unit(&l, &r, skey);
 253                 skey += 32;
 254         }
 255         br_des_do_invIP(&l, &r);
 256         br_enc32be(buf, l);
 257         br_enc32be(buf + 4, r);
 258 }
 259
 260 static void
 261 keysched_unit(uint32_t *skey, const void *key)
 262 {
 263         int i;
 264
 265         br_des_keysched_unit(skey, key);
 266
 267         /*
 268          * Apply PC-2 to get the 48-bit subkeys.
 269          */
 270         for (i = 0; i < 16; i ++) {
 271                 uint32_t xl, xr, ul, ur;
 272                 int j;
 273
 274                 xl = skey[(i << 1) + 0];
 275                 xr = skey[(i << 1) + 1];
 276                 ul = 0;
 277                 ur = 0;
 278                 for (j = 0; j < 28; j ++) {
 279                         ul |= (xl & 1) << PC2left[j];
 280                         ur |= (xr & 1) << PC2right[j];
 281                         xl >>= 1;
 282                         xr >>= 1;
 283                 }
 284                 skey[(i << 1) + 0] = ul;
 285                 skey[(i << 1) + 1] = ur;
 286         }
 287 }
 288
 289 /* see inner.h */
 290 unsigned
 291 br_des_tab_keysched(uint32_t *skey, const void *key, size_t key_len)
 292 {
 293         switch (key_len) {
 294         case 8:
 295                 keysched_unit(skey, key);
 296                 return 1;
 297         case 16:
 298                 keysched_unit(skey, key);
 299                 keysched_unit(skey + 32, (const unsigned char *)key + 8);
 300                 br_des_rev_skey(skey + 32);
 301                 memcpy(skey + 64, skey, 32 * sizeof *skey);
 302                 return 3;
 303         default:
 304                 keysched_unit(skey, key);
 305                 keysched_unit(skey + 32, (const unsigned char *)key + 8);
 306                 br_des_rev_skey(skey + 32);
 307                 keysched_unit(skey + 64, (const unsigned char *)key + 16);
 308                 return 3;
 309         }
 310 }