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