serpent-set-key.c

   1 /* serpent-set-key.c
   2
   3    The serpent block cipher.
   4
   5    For more details on this algorithm, see the Serpent website at
   6    http://www.cl.cam.ac.uk/~rja14/serpent.html
   7
   8    Copyright (C) 2011, 2014  Niels Möller
   9    Copyright (C) 2010, 2011  Simon Josefsson
  10    Copyright (C) 2003, 2004, 2005 Free Software Foundation, Inc.
  11
  12    This file is part of GNU Nettle.
  13
  14    GNU Nettle is free software: you can redistribute it and/or
  15    modify it under the terms of either:
  16
  17      * the GNU Lesser General Public License as published by the Free
  18        Software Foundation; either version 3 of the License, or (at your
  19        option) any later version.
  20
  21    or
  22
  23      * the GNU General Public License as published by the Free
  24        Software Foundation; either version 2 of the License, or (at your
  25        option) any later version.
  26
  27    or both in parallel, as here.
  28
  29    GNU Nettle is distributed in the hope that it will be useful,
  30    but WITHOUT ANY WARRANTY; without even the implied warranty of
  31    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  32    General Public License for more details.
  33
  34    You should have received copies of the GNU General Public License and
  35    the GNU Lesser General Public License along with this program.  If
  36    not, see http://www.gnu.org/licenses/.
  37 */
  38
  39 /* This file is derived from cipher/serpent.c in Libgcrypt v1.4.6.
  40    The adaption to Nettle was made by Simon Josefsson on 2010-12-07
  41    with final touches on 2011-05-30.  Changes include replacing
  42    libgcrypt with nettle in the license template, renaming
  43    serpent_context to serpent_ctx, renaming u32 to uint32_t, removing
  44    libgcrypt stubs and selftests, modifying entry function prototypes,
  45    using FOR_BLOCKS to iterate through data in encrypt/decrypt, using
  46    LE_READ_UINT32 and LE_WRITE_UINT32 to access data in
  47    encrypt/decrypt, and running indent on the code. */
  48
  49 #if HAVE_CONFIG_H
  50 #include "config.h"
  51 #endif
  52
  53 #include <assert.h>
  54 #include <limits.h>
  55
  56 #include "serpent.h"
  57
  58 #include "macros.h"
  59 #include "serpent-internal.h"
  60
  61 /* Magic number, used during generating of the subkeys.  */
  62 #define PHI 0x9E3779B9
  63
  64 /* These are the S-Boxes of Serpent.  They are copied from Serpents
  65    reference implementation (the optimized one, contained in
  66    `floppy2') and are therefore:
  67
  68      Copyright (C) 1998 Ross Anderson, Eli Biham, Lars Knudsen.
  69
  70   To quote the Serpent homepage
  71   (http://www.cl.cam.ac.uk/~rja14/serpent.html):
  72
  73   "Serpent is now completely in the public domain, and we impose no
  74    restrictions on its use.  This was announced on the 21st August at
  75    the First AES Candidate Conference. The optimised implementations
  76    in the submission package are now under the GNU PUBLIC LICENSE
  77    (GPL), although some comments in the code still say otherwise. You
  78    are welcome to use Serpent for any application."  */
  79
  80 /* FIXME: Except when used within the key schedule, the inputs are not
  81    used after the substitution, and hence we could allow them to be
  82    destroyed. Can this freedom be used to optimize the sboxes? */
  83 #define SBOX0(type, a, b, c, d, w, x, y, z)     \
  84   do { \
  85     type t02, t03, t05, t06, t07, t08, t09; \
  86     type t11, t12, t13, t14, t15, t17, t01; \
  87     t01 = b   ^ c  ; \
  88     t02 = a   | d  ; \
  89     t03 = a   ^ b  ; \
  90     z   = t02 ^ t01; \
  91     t05 = c   | z  ; \
  92     t06 = a   ^ d  ; \
  93     t07 = b   | c  ; \
  94     t08 = d   & t05; \
  95     t09 = t03 & t07; \
  96     y   = t09 ^ t08; \
  97     t11 = t09 & y  ; \
  98     t12 = c   ^ d  ; \
  99     t13 = t07 ^ t11; \
 100     t14 = b   & t06; \
 101     t15 = t06 ^ t13; \
 102     w   =     ~ t15; \
 103     t17 = w   ^ t14; \
 104     x   = t12 ^ t17; \
 105   } while (0)
 106
 107 #define SBOX1(type, a, b, c, d, w, x, y, z)     \
 108   do { \
 109     type t02, t03, t04, t05, t06, t07, t08; \
 110     type t10, t11, t12, t13, t16, t17, t01; \
 111     t01 = a   | d  ; \
 112     t02 = c   ^ d  ; \
 113     t03 =     ~ b  ; \
 114     t04 = a   ^ c  ; \
 115     t05 = a   | t03; \
 116     t06 = d   & t04; \
 117     t07 = t01 & t02; \
 118     t08 = b   | t06; \
 119     y   = t02 ^ t05; \
 120     t10 = t07 ^ t08; \
 121     t11 = t01 ^ t10; \
 122     t12 = y   ^ t11; \
 123     t13 = b   & d  ; \
 124     z   =     ~ t10; \
 125     x   = t13 ^ t12; \
 126     t16 = t10 | x  ; \
 127     t17 = t05 & t16; \
 128     w   = c   ^ t17; \
 129   } while (0)
 130
 131 #define SBOX2(type, a, b, c, d, w, x, y, z) \
 132   do {                                     \
 133     type t02, t03, t05, t06, t07, t08; \
 134     type t09, t10, t12, t13, t14, t01; \
 135     t01 = a   | c  ; \
 136     t02 = a   ^ b  ; \
 137     t03 = d   ^ t01; \
 138     w   = t02 ^ t03; \
 139     t05 = c   ^ w  ; \
 140     t06 = b   ^ t05; \
 141     t07 = b   | t05; \
 142     t08 = t01 & t06; \
 143     t09 = t03 ^ t07; \
 144     t10 = t02 | t09; \
 145     x   = t10 ^ t08; \
 146     t12 = a   | d  ; \
 147     t13 = t09 ^ x  ; \
 148     t14 = b   ^ t13; \
 149     z   =     ~ t09; \
 150     y   = t12 ^ t14; \
 151   } while (0)
 152
 153 #define SBOX3(type, a, b, c, d, w, x, y, z) \
 154   do {                                          \
 155     type t02, t03, t04, t05, t06, t07, t08; \
 156     type t09, t10, t11, t13, t14, t15, t01; \
 157     t01 = a   ^ c  ; \
 158     t02 = a   | d  ; \
 159     t03 = a   & d  ; \
 160     t04 = t01 & t02; \
 161     t05 = b   | t03; \
 162     t06 = a   & b  ; \
 163     t07 = d   ^ t04; \
 164     t08 = c   | t06; \
 165     t09 = b   ^ t07; \
 166     t10 = d   & t05; \
 167     t11 = t02 ^ t10; \
 168     z   = t08 ^ t09; \
 169     t13 = d   | z  ; \
 170     t14 = a   | t07; \
 171     t15 = b   & t13; \
 172     y   = t08 ^ t11; \
 173     w   = t14 ^ t15; \
 174     x   = t05 ^ t04; \
 175   } while (0)
 176
 177 #define SBOX4(type, a, b, c, d, w, x, y, z) \
 178   do { \
 179     type t02, t03, t04, t05, t06, t08, t09; \
 180     type t10, t11, t12, t13, t14, t15, t16, t01; \
 181     t01 = a   | b  ; \
 182     t02 = b   | c  ; \
 183     t03 = a   ^ t02; \
 184     t04 = b   ^ d  ; \
 185     t05 = d   | t03; \
 186     t06 = d   & t01; \
 187     z   = t03 ^ t06; \
 188     t08 = z   & t04; \
 189     t09 = t04 & t05; \
 190     t10 = c   ^ t06; \
 191     t11 = b   & c  ; \
 192     t12 = t04 ^ t08; \
 193     t13 = t11 | t03; \
 194     t14 = t10 ^ t09; \
 195     t15 = a   & t05; \
 196     t16 = t11 | t12; \
 197     y   = t13 ^ t08; \
 198     x   = t15 ^ t16; \
 199     w   =     ~ t14; \
 200   } while (0)
 201
 202 #define SBOX5(type, a, b, c, d, w, x, y, z) \
 203   do { \
 204     type t02, t03, t04, t05, t07, t08, t09; \
 205     type t10, t11, t12, t13, t14, t01; \
 206     t01 = b   ^ d  ; \
 207     t02 = b   | d  ; \
 208     t03 = a   & t01; \
 209     t04 = c   ^ t02; \
 210     t05 = t03 ^ t04; \
 211     w   =     ~ t05; \
 212     t07 = a   ^ t01; \
 213     t08 = d   | w  ; \
 214     t09 = b   | t05; \
 215     t10 = d   ^ t08; \
 216     t11 = b   | t07; \
 217     t12 = t03 | w  ; \
 218     t13 = t07 | t10; \
 219     t14 = t01 ^ t11; \
 220     y   = t09 ^ t13; \
 221     x   = t07 ^ t08; \
 222     z   = t12 ^ t14; \
 223   } while (0)
 224
 225 #define SBOX6(type, a, b, c, d, w, x, y, z) \
 226   do { \
 227     type t02, t03, t04, t05, t07, t08, t09, t10;        \
 228     type t11, t12, t13, t15, t17, t18, t01; \
 229     t01 = a   & d  ; \
 230     t02 = b   ^ c  ; \
 231     t03 = a   ^ d  ; \
 232     t04 = t01 ^ t02; \
 233     t05 = b   | c  ; \
 234     x   =     ~ t04; \
 235     t07 = t03 & t05; \
 236     t08 = b   & x  ; \
 237     t09 = a   | c  ; \
 238     t10 = t07 ^ t08; \
 239     t11 = b   | d  ; \
 240     t12 = c   ^ t11; \
 241     t13 = t09 ^ t10; \
 242     y   =     ~ t13; \
 243     t15 = x   & t03; \
 244     z   = t12 ^ t07; \
 245     t17 = a   ^ b  ; \
 246     t18 = y   ^ t15; \
 247     w   = t17 ^ t18; \
 248   } while (0)
 249
 250 #define SBOX7(type, a, b, c, d, w, x, y, z) \
 251   do { \
 252     type t02, t03, t04, t05, t06, t08, t09, t10;        \
 253     type t11, t13, t14, t15, t16, t17, t01; \
 254     t01 = a   & c  ; \
 255     t02 =     ~ d  ; \
 256     t03 = a   & t02; \
 257     t04 = b   | t01; \
 258     t05 = a   & b  ; \
 259     t06 = c   ^ t04; \
 260     z   = t03 ^ t06; \
 261     t08 = c   | z  ; \
 262     t09 = d   | t05; \
 263     t10 = a   ^ t08; \
 264     t11 = t04 & z  ; \
 265     x   = t09 ^ t10; \
 266     t13 = b   ^ x  ; \
 267     t14 = t01 ^ x  ; \
 268     t15 = c   ^ t05; \
 269     t16 = t11 | t13; \
 270     t17 = t02 | t14; \
 271     w   = t15 ^ t17; \
 272     y   = a   ^ t16; \
 273   } while (0)
 274
 275 /* Key schedule */
 276 /* Note: Increments k */
 277 #define KS_RECURRENCE(w, i, k)                                          \
 278   do {                                                                  \
 279     uint32_t _wn = (w)[(i)] ^ (w)[((i)+3)&7] ^ w[((i)+5)&7]             \
 280       ^ w[((i)+7)&7] ^ PHI ^ (k)++;                                     \
 281     ((w)[(i)] = ROTL32(11, _wn));                                       \
 282   } while (0)
 283
 284 /* Note: Increments k four times and keys once */
 285 #define KS(keys, s, w, i, k)                                    \
 286   do {                                                          \
 287     KS_RECURRENCE(w, (i), (k));                                 \
 288     KS_RECURRENCE(w, (i)+1, (k));                               \
 289     KS_RECURRENCE(w, (i)+2, (k));                               \
 290     KS_RECURRENCE(w, (i)+3, (k));                               \
 291     SBOX##s(uint32_t, w[(i)],w[(i)+1],w[(i)+2],w[(i)+3],                \
 292             (*keys)[0],(*keys)[1],(*keys)[2],(*keys)[3]);       \
 293     (keys)++;                                                   \
 294   } while (0)
 295
 296 /* Pad user key and convert to an array of 8 uint32_t. */
 297 static void
 298 serpent_key_pad (const uint8_t *key, unsigned int key_length,
 299                  uint32_t *w)
 300 {
 301   unsigned int i;
 302
 303   assert (key_length <= SERPENT_MAX_KEY_SIZE);
 304
 305   for (i = 0; key_length >= 4; key_length -=4, key += 4)
 306     w[i++] = LE_READ_UINT32(key);
 307
 308   if (i < 8)
 309     {
 310       /* Key must be padded according to the Serpent specification.
 311          "aabbcc" -> "aabbcc0100...00" -> 0x01ccbbaa. */
 312       uint32_t pad = 0x01;
 313
 314       while (key_length > 0)
 315         pad = pad << 8 | key[--key_length];
 316
 317       w[i++] = pad;
 318
 319       while (i < 8)
 320         w[i++] = 0;
 321     }
 322 }
 323
 324 /* Initialize CONTEXT with the key KEY of LENGTH bytes.  */
 325 void
 326 serpent_set_key (struct serpent_ctx *ctx,
 327                  size_t length, const uint8_t * key)
 328 {
 329   uint32_t w[8];
 330   uint32_t (*keys)[4];
 331   unsigned k;
 332
 333   serpent_key_pad (key, length, w);
 334
 335   /* Derive the 33 subkeys from KEY and store them in SUBKEYS. We do
 336      the recurrence in the key schedule using W as a circular buffer
 337      of just 8 uint32_t. */
 338
 339   /* FIXME: Would be better to invoke SBOX with scalar variables as
 340      arguments, no arrays. To do that, unpack w into separate
 341      variables, use temporary variables as the SBOX destination. */
 342
 343   keys = ctx->keys;
 344   k = 0;
 345   for (;;)
 346     {
 347       KS(keys, 3, w, 0, k);
 348       if (k == 132)
 349         break;
 350       KS(keys, 2, w, 4, k);
 351       KS(keys, 1, w, 0, k);
 352       KS(keys, 0, w, 4, k);
 353       KS(keys, 7, w, 0, k);
 354       KS(keys, 6, w, 4, k);
 355       KS(keys, 5, w, 0, k);
 356       KS(keys, 4, w, 4, k);
 357     }
 358   assert (keys == ctx->keys + 33);
 359 }
 360
 361 void
 362 serpent128_set_key (struct serpent_ctx *ctx, const uint8_t *key)
 363 {
 364   serpent_set_key (ctx, SERPENT128_KEY_SIZE, key);
 365 }
 366
 367 void
 368 serpent192_set_key (struct serpent_ctx *ctx, const uint8_t *key)
 369 {
 370   serpent_set_key (ctx, SERPENT192_KEY_SIZE, key);
 371 }
 372
 373 void
 374 serpent256_set_key (struct serpent_ctx *ctx, const uint8_t *key)
 375 {
 376   serpent_set_key (ctx, SERPENT256_KEY_SIZE, key);
 377 }