1
/* serpent.c - Implementation of the Serpent encryption algorithm.
2
* Copyright (C) 2003, 2004, 2005 Free Software Foundation, Inc.
4
* This file is part of Libgcrypt.
6
* Libgcrypt is free software; you can redistribute it and/or modify
7
* it under the terms of the GNU Lesser general Public License as
8
* published by the Free Software Foundation; either version 2.1 of
9
* the License, or (at your option) any later version.
11
* Libgcrypt is distributed in the hope that it will be useful,
12
* but WITHOUT ANY WARRANTY; without even the implied warranty of
13
* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
14
* GNU Lesser General Public License for more details.
16
* You should have received a copy of the GNU Lesser General Public
17
* License along with this program; if not, write to the Free Software
18
* Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA
32
/* Number of rounds per Serpent encrypt/decrypt operation. */
35
/* Magic number, used during generating of the subkeys. */
36
#define PHI 0x9E3779B9
38
/* Serpent works on 128 bit blocks. */
39
typedef u32 serpent_block_t[4];
41
/* Serpent key, provided by the user. If the original key is shorter
42
than 256 bits, it is padded. */
43
typedef u32 serpent_key_t[8];
45
/* The key schedule consists of 33 128 bit subkeys. */
46
typedef u32 serpent_subkeys_t[ROUNDS + 1][4];
48
/* A Serpent context. */
49
typedef struct serpent_context
51
serpent_subkeys_t keys; /* Generated subkeys. */
56
static const char *serpent_test (void);
59
#define byte_swap_32(x) \
61
| (((x) & 0xff000000) >> 24) | (((x) & 0x00ff0000) >> 8) \
62
| (((x) & 0x0000ff00) << 8) | (((x) & 0x000000ff) << 24))
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:
68
Copyright (C) 1998 Ross Anderson, Eli Biham, Lars Knudsen.
70
To quote the Serpent homepage
71
(http://www.cl.cam.ac.uk/~rja14/serpent.html):
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." */
80
#define SBOX0(a, b, c, d, w, x, y, z) \
82
u32 t02, t03, t05, t06, t07, t08, t09; \
83
u32 t11, t12, t13, t14, t15, t17, t01; \
104
#define SBOX0_INVERSE(a, b, c, d, w, x, y, z) \
106
u32 t02, t03, t04, t05, t06, t08, t09, t10; \
107
u32 t12, t13, t14, t15, t17, t18, t01; \
129
#define SBOX1(a, b, c, d, w, x, y, z) \
131
u32 t02, t03, t04, t05, t06, t07, t08; \
132
u32 t10, t11, t12, t13, t16, t17, t01; \
153
#define SBOX1_INVERSE(a, b, c, d, w, x, y, z) \
155
u32 t02, t03, t04, t05, t06, t07, t08; \
156
u32 t09, t10, t11, t14, t15, t17, t01; \
177
#define SBOX2(a, b, c, d, w, x, y, z) \
179
u32 t02, t03, t05, t06, t07, t08; \
180
u32 t09, t10, t12, t13, t14, t01; \
199
#define SBOX2_INVERSE(a, b, c, d, w, x, y, z) \
201
u32 t02, t03, t04, t06, t07, t08, t09; \
202
u32 t10, t11, t12, t15, t16, t17, t01; \
223
#define SBOX3(a, b, c, d, w, x, y, z) \
225
u32 t02, t03, t04, t05, t06, t07, t08; \
226
u32 t09, t10, t11, t13, t14, t15, t01; \
247
#define SBOX3_INVERSE(a, b, c, d, w, x, y, z) \
249
u32 t02, t03, t04, t05, t06, t07, t09; \
250
u32 t11, t12, t13, t14, t16, t01; \
270
#define SBOX4(a, b, c, d, w, x, y, z) \
272
u32 t02, t03, t04, t05, t06, t08, t09; \
273
u32 t10, t11, t12, t13, t14, t15, t16, t01; \
295
#define SBOX4_INVERSE(a, b, c, d, w, x, y, z) \
297
u32 t02, t03, t04, t05, t06, t07, t09; \
298
u32 t10, t11, t12, t13, t15, t01; \
318
#define SBOX5(a, b, c, d, w, x, y, z) \
320
u32 t02, t03, t04, t05, t07, t08, t09; \
321
u32 t10, t11, t12, t13, t14, t01; \
341
#define SBOX5_INVERSE(a, b, c, d, w, x, y, z) \
343
u32 t02, t03, t04, t05, t07, t08, t09; \
344
u32 t10, t12, t13, t15, t16, t01; \
364
#define SBOX6(a, b, c, d, w, x, y, z) \
366
u32 t02, t03, t04, t05, t07, t08, t09, t10; \
367
u32 t11, t12, t13, t15, t17, t18, t01; \
389
#define SBOX6_INVERSE(a, b, c, d, w, x, y, z) \
391
u32 t02, t03, t04, t05, t06, t07, t08, t09; \
392
u32 t12, t13, t14, t15, t16, t17, t01; \
414
#define SBOX7(a, b, c, d, w, x, y, z) \
416
u32 t02, t03, t04, t05, t06, t08, t09, t10; \
417
u32 t11, t13, t14, t15, t16, t17, t01; \
439
#define SBOX7_INVERSE(a, b, c, d, w, x, y, z) \
441
u32 t02, t03, t04, t06, t07, t08, t09; \
442
u32 t10, t11, t13, t14, t15, t16, t01; \
463
/* XOR BLOCK1 into BLOCK0. */
464
#define BLOCK_XOR(block0, block1) \
466
block0[0] ^= block1[0]; \
467
block0[1] ^= block1[1]; \
468
block0[2] ^= block1[2]; \
469
block0[3] ^= block1[3]; \
472
/* Copy BLOCK_SRC to BLOCK_DST. */
473
#define BLOCK_COPY(block_dst, block_src) \
475
block_dst[0] = block_src[0]; \
476
block_dst[1] = block_src[1]; \
477
block_dst[2] = block_src[2]; \
478
block_dst[3] = block_src[3]; \
481
/* Apply SBOX number WHICH to to the block found in ARRAY0 at index
482
INDEX, writing the output to the block found in ARRAY1 at index
484
#define SBOX(which, array0, array1, index) \
485
SBOX##which (array0[index + 0], array0[index + 1], \
486
array0[index + 2], array0[index + 3], \
487
array1[index + 0], array1[index + 1], \
488
array1[index + 2], array1[index + 3]);
490
/* Apply inverse SBOX number WHICH to to the block found in ARRAY0 at
491
index INDEX, writing the output to the block found in ARRAY1 at
493
#define SBOX_INVERSE(which, array0, array1, index) \
494
SBOX##which##_INVERSE (array0[index + 0], array0[index + 1], \
495
array0[index + 2], array0[index + 3], \
496
array1[index + 0], array1[index + 1], \
497
array1[index + 2], array1[index + 3]);
499
/* Apply the linear transformation to BLOCK. */
500
#define LINEAR_TRANSFORMATION(block) \
502
block[0] = rol (block[0], 13); \
503
block[2] = rol (block[2], 3); \
504
block[1] = block[1] ^ block[0] ^ block[2]; \
505
block[3] = block[3] ^ block[2] ^ (block[0] << 3); \
506
block[1] = rol (block[1], 1); \
507
block[3] = rol (block[3], 7); \
508
block[0] = block[0] ^ block[1] ^ block[3]; \
509
block[2] = block[2] ^ block[3] ^ (block[1] << 7); \
510
block[0] = rol (block[0], 5); \
511
block[2] = rol (block[2], 22); \
514
/* Apply the inverse linear transformation to BLOCK. */
515
#define LINEAR_TRANSFORMATION_INVERSE(block) \
517
block[2] = ror (block[2], 22); \
518
block[0] = ror (block[0] , 5); \
519
block[2] = block[2] ^ block[3] ^ (block[1] << 7); \
520
block[0] = block[0] ^ block[1] ^ block[3]; \
521
block[3] = ror (block[3], 7); \
522
block[1] = ror (block[1], 1); \
523
block[3] = block[3] ^ block[2] ^ (block[0] << 3); \
524
block[1] = block[1] ^ block[0] ^ block[2]; \
525
block[2] = ror (block[2], 3); \
526
block[0] = ror (block[0], 13); \
529
/* Apply a Serpent round to BLOCK, using the SBOX number WHICH and the
530
subkeys contained in SUBKEYS. Use BLOCK_TMP as temporary storage.
531
This macro increments `round'. */
532
#define ROUND(which, subkeys, block, block_tmp) \
534
BLOCK_XOR (block, subkeys[round]); \
536
SBOX (which, block, block_tmp, 0); \
537
LINEAR_TRANSFORMATION (block_tmp); \
538
BLOCK_COPY (block, block_tmp); \
541
/* Apply the last Serpent round to BLOCK, using the SBOX number WHICH
542
and the subkeys contained in SUBKEYS. Use BLOCK_TMP as temporary
543
storage. The result will be stored in BLOCK_TMP. This macro
544
increments `round'. */
545
#define ROUND_LAST(which, subkeys, block, block_tmp) \
547
BLOCK_XOR (block, subkeys[round]); \
549
SBOX (which, block, block_tmp, 0); \
550
BLOCK_XOR (block_tmp, subkeys[round]); \
554
/* Apply an inverse Serpent round to BLOCK, using the SBOX number
555
WHICH and the subkeys contained in SUBKEYS. Use BLOCK_TMP as
556
temporary storage. This macro increments `round'. */
557
#define ROUND_INVERSE(which, subkey, block, block_tmp) \
559
LINEAR_TRANSFORMATION_INVERSE (block); \
560
SBOX_INVERSE (which, block, block_tmp, 0); \
561
BLOCK_XOR (block_tmp, subkey[round]); \
563
BLOCK_COPY (block, block_tmp); \
566
/* Apply the first Serpent round to BLOCK, using the SBOX number WHICH
567
and the subkeys contained in SUBKEYS. Use BLOCK_TMP as temporary
568
storage. The result will be stored in BLOCK_TMP. This macro
569
increments `round'. */
570
#define ROUND_FIRST_INVERSE(which, subkeys, block, block_tmp) \
572
BLOCK_XOR (block, subkeys[round]); \
574
SBOX_INVERSE (which, block, block_tmp, 0); \
575
BLOCK_XOR (block_tmp, subkeys[round]); \
579
/* Convert the user provided key KEY of KEY_LENGTH bytes into the
580
internally used format. */
582
serpent_key_prepare (const byte *key, unsigned int key_length,
583
serpent_key_t key_prepared)
588
for (i = 0; i < key_length / 4; i++)
590
#ifdef WORDS_BIGENDIAN
591
key_prepared[i] = byte_swap_32 (((u32 *) key)[i]);
593
key_prepared[i] = ((u32 *) key)[i];
599
/* Key must be padded according to the Serpent
601
key_prepared[i] = 0x00000001;
603
for (i++; i < 8; i++)
608
/* Derive the 33 subkeys from KEY and store them in SUBKEYS. */
610
serpent_subkeys_generate (serpent_key_t key, serpent_subkeys_t subkeys)
612
u32 w_real[140]; /* The `prekey'. */
617
/* Initialize with key values. */
618
for (i = 0; i < 8; i++)
621
/* Expand to intermediate key using the affine recurrence. */
622
for (i = 0; i < 132; i++)
623
w[i] = rol (w[i - 8] ^ w[i - 5] ^ w[i - 3] ^ w[i - 1] ^ PHI ^ i, 11);
625
/* Calculate subkeys via S-Boxes, in bitslice mode. */
660
/* Renumber subkeys. */
661
for (i = 0; i < ROUNDS + 1; i++)
662
for (j = 0; j < 4; j++)
663
subkeys[i][j] = k[4 * i + j];
666
/* Initialize CONTEXT with the key KEY of KEY_LENGTH bits. */
668
serpent_setkey_internal (serpent_context_t *context,
669
const byte *key, unsigned int key_length)
671
serpent_key_t key_prepared;
673
serpent_key_prepare (key, key_length, key_prepared);
674
serpent_subkeys_generate (key_prepared, context->keys);
675
_gcry_burn_stack (272 * sizeof (u32));
678
/* Initialize CTX with the key KEY of KEY_LENGTH bytes. */
679
static gcry_err_code_t
680
serpent_setkey (void *ctx,
681
const byte *key, unsigned int key_length)
683
serpent_context_t *context = ctx;
684
static const char *serpent_test_ret;
685
static int serpent_init_done;
686
gcry_err_code_t ret = GPG_ERR_NO_ERROR;
688
if (! serpent_init_done)
690
/* Execute a self-test the first time, Serpent is used. */
691
serpent_test_ret = serpent_test ();
692
if (serpent_test_ret)
693
log_error ("Serpent test failure: %s\n", serpent_test_ret);
694
serpent_init_done = 1;
697
if (serpent_test_ret)
698
ret = GPG_ERR_SELFTEST_FAILED;
701
serpent_setkey_internal (context, key, key_length);
702
_gcry_burn_stack (sizeof (serpent_key_t));
709
serpent_encrypt_internal (serpent_context_t *context,
710
const serpent_block_t input, serpent_block_t output)
712
serpent_block_t b, b_next;
715
#ifdef WORDS_BIGENDIAN
716
b[0] = byte_swap_32 (input[0]);
717
b[1] = byte_swap_32 (input[1]);
718
b[2] = byte_swap_32 (input[2]);
719
b[3] = byte_swap_32 (input[3]);
727
ROUND (0, context->keys, b, b_next);
728
ROUND (1, context->keys, b, b_next);
729
ROUND (2, context->keys, b, b_next);
730
ROUND (3, context->keys, b, b_next);
731
ROUND (4, context->keys, b, b_next);
732
ROUND (5, context->keys, b, b_next);
733
ROUND (6, context->keys, b, b_next);
734
ROUND (7, context->keys, b, b_next);
735
ROUND (0, context->keys, b, b_next);
736
ROUND (1, context->keys, b, b_next);
737
ROUND (2, context->keys, b, b_next);
738
ROUND (3, context->keys, b, b_next);
739
ROUND (4, context->keys, b, b_next);
740
ROUND (5, context->keys, b, b_next);
741
ROUND (6, context->keys, b, b_next);
742
ROUND (7, context->keys, b, b_next);
743
ROUND (0, context->keys, b, b_next);
744
ROUND (1, context->keys, b, b_next);
745
ROUND (2, context->keys, b, b_next);
746
ROUND (3, context->keys, b, b_next);
747
ROUND (4, context->keys, b, b_next);
748
ROUND (5, context->keys, b, b_next);
749
ROUND (6, context->keys, b, b_next);
750
ROUND (7, context->keys, b, b_next);
751
ROUND (0, context->keys, b, b_next);
752
ROUND (1, context->keys, b, b_next);
753
ROUND (2, context->keys, b, b_next);
754
ROUND (3, context->keys, b, b_next);
755
ROUND (4, context->keys, b, b_next);
756
ROUND (5, context->keys, b, b_next);
757
ROUND (6, context->keys, b, b_next);
759
ROUND_LAST (7, context->keys, b, b_next);
761
#ifdef WORDS_BIGENDIAN
762
output[0] = byte_swap_32 (b_next[0]);
763
output[1] = byte_swap_32 (b_next[1]);
764
output[2] = byte_swap_32 (b_next[2]);
765
output[3] = byte_swap_32 (b_next[3]);
767
output[0] = b_next[0];
768
output[1] = b_next[1];
769
output[2] = b_next[2];
770
output[3] = b_next[3];
775
serpent_decrypt_internal (serpent_context_t *context,
776
const serpent_block_t input, serpent_block_t output)
778
serpent_block_t b, b_next;
781
#ifdef WORDS_BIGENDIAN
782
b_next[0] = byte_swap_32 (input[0]);
783
b_next[1] = byte_swap_32 (input[1]);
784
b_next[2] = byte_swap_32 (input[2]);
785
b_next[3] = byte_swap_32 (input[3]);
787
b_next[0] = input[0];
788
b_next[1] = input[1];
789
b_next[2] = input[2];
790
b_next[3] = input[3];
793
ROUND_FIRST_INVERSE (7, context->keys, b_next, b);
795
ROUND_INVERSE (6, context->keys, b, b_next);
796
ROUND_INVERSE (5, context->keys, b, b_next);
797
ROUND_INVERSE (4, context->keys, b, b_next);
798
ROUND_INVERSE (3, context->keys, b, b_next);
799
ROUND_INVERSE (2, context->keys, b, b_next);
800
ROUND_INVERSE (1, context->keys, b, b_next);
801
ROUND_INVERSE (0, context->keys, b, b_next);
802
ROUND_INVERSE (7, context->keys, b, b_next);
803
ROUND_INVERSE (6, context->keys, b, b_next);
804
ROUND_INVERSE (5, context->keys, b, b_next);
805
ROUND_INVERSE (4, context->keys, b, b_next);
806
ROUND_INVERSE (3, context->keys, b, b_next);
807
ROUND_INVERSE (2, context->keys, b, b_next);
808
ROUND_INVERSE (1, context->keys, b, b_next);
809
ROUND_INVERSE (0, context->keys, b, b_next);
810
ROUND_INVERSE (7, context->keys, b, b_next);
811
ROUND_INVERSE (6, context->keys, b, b_next);
812
ROUND_INVERSE (5, context->keys, b, b_next);
813
ROUND_INVERSE (4, context->keys, b, b_next);
814
ROUND_INVERSE (3, context->keys, b, b_next);
815
ROUND_INVERSE (2, context->keys, b, b_next);
816
ROUND_INVERSE (1, context->keys, b, b_next);
817
ROUND_INVERSE (0, context->keys, b, b_next);
818
ROUND_INVERSE (7, context->keys, b, b_next);
819
ROUND_INVERSE (6, context->keys, b, b_next);
820
ROUND_INVERSE (5, context->keys, b, b_next);
821
ROUND_INVERSE (4, context->keys, b, b_next);
822
ROUND_INVERSE (3, context->keys, b, b_next);
823
ROUND_INVERSE (2, context->keys, b, b_next);
824
ROUND_INVERSE (1, context->keys, b, b_next);
825
ROUND_INVERSE (0, context->keys, b, b_next);
828
#ifdef WORDS_BIGENDIAN
829
output[0] = byte_swap_32 (b_next[0]);
830
output[1] = byte_swap_32 (b_next[1]);
831
output[2] = byte_swap_32 (b_next[2]);
832
output[3] = byte_swap_32 (b_next[3]);
834
output[0] = b_next[0];
835
output[1] = b_next[1];
836
output[2] = b_next[2];
837
output[3] = b_next[3];
842
serpent_encrypt (void *ctx, byte *buffer_out, const byte *buffer_in)
844
serpent_context_t *context = ctx;
846
serpent_encrypt_internal (context,
847
(const u32 *) buffer_in, (u32 *) buffer_out);
848
_gcry_burn_stack (2 * sizeof (serpent_block_t));
852
serpent_decrypt (void *ctx, byte *buffer_out, const byte *buffer_in)
854
serpent_context_t *context = ctx;
856
serpent_decrypt_internal (context,
857
(const u32 *) buffer_in,
859
_gcry_burn_stack (2 * sizeof (serpent_block_t));
869
serpent_context_t context;
870
unsigned char scratch[16];
876
unsigned char key[32];
877
unsigned char text_plain[16];
878
unsigned char text_cipher[16];
883
"\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00",
884
"\xD2\x9D\x57\x6F\xCE\xA3\xA3\xA7\xED\x90\x99\xF2\x92\x73\xD7\x8E",
885
"\xB2\x28\x8B\x96\x8A\xE8\xB0\x86\x48\xD1\xCE\x96\x06\xFD\x99\x2D"
889
"\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00"
890
"\x00\x00\x00\x00\x00\x00\x00\x00",
891
"\xD2\x9D\x57\x6F\xCE\xAB\xA3\xA7\xED\x98\x99\xF2\x92\x7B\xD7\x8E",
892
"\x13\x0E\x35\x3E\x10\x37\xC2\x24\x05\xE8\xFA\xEF\xB2\xC3\xC3\xE9"
896
"\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00"
897
"\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00",
898
"\xD0\x95\x57\x6F\xCE\xA3\xE3\xA7\xED\x98\xD9\xF2\x90\x73\xD7\x8E",
899
"\xB9\x0E\xE5\x86\x2D\xE6\x91\x68\xF2\xBD\xD5\x12\x5B\x45\x47\x2B"
903
"\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00"
904
"\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00",
905
"\x00\x00\x00\x00\x01\x00\x00\x00\x02\x00\x00\x00\x03\x00\x00\x00",
906
"\x20\x61\xA4\x27\x82\xBD\x52\xEC\x69\x1E\xC3\x83\xB0\x3B\xA7\x7C"
913
for (i = 0; test_data[i].key_length; i++)
915
serpent_setkey_internal (&context, test_data[i].key,
916
test_data[i].key_length);
917
serpent_encrypt_internal (&context,
918
(const u32 *) test_data[i].text_plain,
921
if (memcmp (scratch, test_data[i].text_cipher, sizeof (serpent_block_t)))
922
switch (test_data[i].key_length)
925
return "Serpent-128 test encryption failed.";
927
return "Serpent-192 test encryption failed.";
929
return "Serpent-256 test encryption failed.";
932
serpent_decrypt_internal (&context,
933
(const u32 *) test_data[i].text_cipher,
935
if (memcmp (scratch, test_data[i].text_plain, sizeof (serpent_block_t)))
936
switch (test_data[i].key_length)
939
return "Serpent-128 test decryption failed.";
941
return "Serpent-192 test decryption failed.";
943
return "Serpent-256 test decryption failed.";
952
/* "SERPENT" is an alias for "SERPENT128". */
953
static const char *cipher_spec_serpent128_aliases[] =
959
gcry_cipher_spec_t _gcry_cipher_spec_serpent128 =
961
"SERPENT128", cipher_spec_serpent128_aliases, NULL, 16, 128,
962
sizeof (serpent_context_t),
963
serpent_setkey, serpent_encrypt, serpent_decrypt
966
gcry_cipher_spec_t _gcry_cipher_spec_serpent192 =
968
"SERPENT192", NULL, NULL, 16, 192,
969
sizeof (serpent_context_t),
970
serpent_setkey, serpent_encrypt, serpent_decrypt
973
gcry_cipher_spec_t _gcry_cipher_spec_serpent256 =
975
"SERPENT256", NULL, NULL, 16, 256,
976
sizeof (serpent_context_t),
977
serpent_setkey, serpent_encrypt, serpent_decrypt