EuCrypt Chapter 11: Serpent



February 22nd, 2018 by Diana Coman

~ This is part of the EuCrypt series. Start with Introducing EuCrypt. ~

This chapter adds to EuCrypt's generous endowment in the bit and byte diddling1 department: a byte-ready Serpent joins the bit-level Keccak and byte-level Keccak from previous chapters!

As I previously reviewed the functioning and testing of this implementation of Serpent, I won't repeat that part here. I'll go instead straight to the code, which is found in eucrypt/smg_serpent. There is first the smg_serpent.gpr file, for compiling (using gprbuild)2 the smg_serpent as a static library by itself:

-- S.MG, 2018

project SMG_Serpent is
  for Languages use ("Ada");
  for Library_Name use "SMG_Serpent";
  for Library_Kind use "static";

  for Source_Dirs use ("src");
  for Object_Dir use "obj";
  for Library_Dir use "lib";

end SMG_Serpent;

As you might guess from the .gpr file above, the actual sources of Serpent itself are found in eucrypt/smg_serpent/src. The smg_serpent.ads is minimal, simply defining a few types that Serpent uses (Bytes as array of Unsigned_8 aka array of octets aka array of groups of 8 bits; Words as array of Unsigned_32; Block as an array of 16 octets; Key as an array of 32 octets and Key_Schedule as an array of 140 32-bit words indexed for Serpent's purposes from -8 to 13), the three main procedures for Serpent use (making the key schedule out of a given Serpent key; encrypting a given plaintext with a given key schedule; decrypting a given encrypted text with a given key schedule) and one additional procedure that provides one single self-test of Serpent's functioning:

-------------------------------------------------------------------------------
-- S.MG, 2018; with added automated tests
--
-- Serpent Blockcipher
--
-- Copyright (c) 1998 Markus G. Kuhn . All rights reserved.
--
-- $Id: serpent.ads,v 1.2 1998-06-10 14:22:16+00 mgk25 Exp $
--
-------------------------------------------------------------------------------
--
-- This is the Ada95 reference implementation of the Serpent cipher
-- submitted by Ross Anderson, Eli Biham and Lars Knudson in June 1998 to
-- the NIST Advanced Encryption Standard (AES) contest. Please note that
-- this is a revised algorithm that is not identical to the old version
-- presented at the 1998 Fast Software Encryption Workshop.
-- 
--
-- Compiled with GNAT 3.10p under Linux, this implementation encrypts and
-- decrypts with 20.8 Mbit/s on a 300 MHz Pentium II.
--
-------------------------------------------------------------------------------

with Interfaces; use Interfaces;

package SMG_Serpent is

  pragma Pure(SMG_Serpent);

  type Bytes is array (Integer range <>) of Unsigned_8;
  type Words is array (Integer range <>) of Unsigned_32;
  subtype Block is Bytes (0 .. 15);
  subtype Key   is Bytes (0 .. 31);
  subtype Key_Schedule is Words (-8 .. 131);

  procedure Prepare_Key (K : in Key; W : out Key_Schedule);

  procedure Encrypt (W : in Key_Schedule; Plaintext  :  in Block;
					   Ciphertext : out Block);

  procedure Decrypt (W : in Key_Schedule; Ciphertext :  in Block;
					   Plaintext  : out Block);

  procedure Selftest;

  Implementation_Error : exception;  -- raised if Selftest failed

end SMG_Serpent;

The actual implementation of the above is quite straightforward but relatively verbose due to loops being unrolled for faster execution. There is also handling of big endian / little endian iron through octet flipping, as required:

 -------------------------------------------------------------------------------
 --
 -- Serpent Blockcipher
 --
 -- Copyright (c) 1998 Markus G. Kuhn . All rights reserved.
 --
 -- Modified by S.MG, 2018
 --
 -------------------------------------------------------------------------------
 --
 -- This implementation is optimized for best execution time by use of
 -- function inlining and loop unrolling. It is not intended to be used in
 -- applications (such as smartcards) where machine code size matters. Best
 -- compiled with highest optimization level activated and all run-time
 -- checks supressed.
 --
 -------------------------------------------------------------------------------

with System, Ada.Unchecked_Conversion;
use System;

package body SMG_Serpent is

  pragma Optimize( Time );

  -- Auxiliary functions for byte array to word array conversion with
  -- Bigendian/Littleendian handling.
  --
  -- The convention followed here is that the input byte array
  --
  --   00 01 02 03 04 05 06 07 08 09 0a 0b 0c 0d 0e 0f
  --
  -- is converted into the register values
  --
  --   X0 = 03020100,  X1 = 07060504,  X2 = 0b0a0908,  X3 = 0f0e0d0c

  subtype Bytes_4 is Bytes (0 .. 3);
  function Cast is new Ada.Unchecked_Conversion (Bytes_4, Unsigned_32);
  function Cast is new Ada.Unchecked_Conversion (Unsigned_32, Bytes_4);

  function Bytes_To_Word (X : Bytes_4) return Unsigned_32 is
  begin
    if Default_Bit_Order = Low_Order_First then
      -- we have a Littleendian processor
      return Cast(X);
    else
      -- word sex change
      return Cast((X(3), X(2), X(1), X(0)));
    end if;
  end Bytes_To_Word;

  function Word_To_Bytes (X : Unsigned_32) return Bytes_4 is
  begin
    if Default_Bit_Order = Low_Order_First then
      -- we have a Littleendian processor
      return Cast(X);
    else
      -- word sex change
      return (Cast(X)(3), Cast(X)(2), Cast(X)(1), Cast(X)(0));
    end if;
  end Word_To_Bytes;

  pragma Inline(Bytes_To_Word, Word_To_Bytes);
  -- inline functions for the Encryption and Decryption procedures

  -- Sbox function
  procedure S (R : Integer; X0, X1, X2, X3 : in out Unsigned_32) is
      T01, T02, T03, T04, T05, T06, T07, T08, T09,
      T10, T11, T12, T13, T14, T15, T16, T17, T18 : Unsigned_32;
      W, X, Y, Z : Unsigned_32;
  begin
    if R = 0 then
      -- S0:   3  8 15  1 10  6  5 11 14 13  4  2  7  0  9 12
      -- depth = 5,7,4,2, Total gates=18
      T01 := X1  xor X2;
      T02 := X0  or X3;
      T03 := X0  xor X1;
      Z   := T02 xor T01;
      T05 := X2  or z;
      T06 := X0  xor X3;
      T07 := X1  or X2;
      T08 := X3  and T05;
      T09 := T03 and T07;
      Y   := T09 xor T08;
      T11 := T09 and y;
      T12 := X2  xor X3;
      T13 := T07 xor T11;
      T14 := X1  and T06;
      T15 := T06 xor T13;
      W   :=     not T15;
      T17 := W   xor T14;
      X   := T12 xor T17;
    elsif R = 1 then
      -- S1:  15 12  2  7  9  0  5 10  1 11 14  8  6 13  3  4
      -- depth = 10,7,3,5, Total gates=18
      T01 := X0  or X3;
      T02 := X2  xor X3;
      T03 :=     not X1;
      T04 := X0  xor X2;
      T05 := X0  or T03;
      T06 := X3  and T04;
      T07 := T01 and T02;
      T08 := X1  or T06;
      Y   := T02 xor T05;
      T10 := T07 xor T08;
      T11 := T01 xor T10;
      T12 := Y   xor T11;
      T13 := X1  and X3;
      Z   :=     not T10;
      X   := T13 xor T12;
      T16 := T10 or x;
      T17 := T05 and T16;
      W   := X2  xor T17;
    elsif R = 2 then
      -- S2:   8  6  7  9  3 12 10 15 13  1 14  4  0 11  5  2
      -- depth = 3,8,11,7, Total gates=16
      T01 := X0  or X2;
      T02 := X0  xor X1;
      T03 := X3  xor T01;
      W   := T02 xor T03;
      T05 := X2  xor w;
      T06 := X1  xor T05;
      T07 := X1  or T05;
      T08 := T01 and T06;
      T09 := T03 xor T07;
      T10 := T02 or T09;
      X   := T10 xor T08;
      T12 := X0  or X3;
      T13 := T09 xor x;
      T14 := X1  xor T13;
      Z   :=     not T09;
      Y   := T12 xor T14;
    elsif R = 3 then
      -- S3:   0 15 11  8 12  9  6  3 13  1  2  4 10  7  5 14
      -- depth = 8,3,5,5, Total gates=18
      T01 := X0  xor X2;
      T02 := X0  or X3;
      T03 := X0  and X3;
      T04 := T01 and T02;
      T05 := X1  or T03;
      T06 := X0  and X1;
      T07 := X3  xor T04;
      T08 := X2  or T06;
      T09 := X1  xor T07;
      T10 := X3  and T05;
      T11 := T02 xor T10;
      Z   := T08 xor T09;
      T13 := X3  or z;
      T14 := X0  or T07;
      T15 := X1  and T13;
      Y   := T08 xor T11;
      W   := T14 xor T15;
      X   := T05 xor T04;
    elsif R = 4 then
      -- S4:   1 15  8  3 12  0 11  6  2  5  4 10  9 14  7 13
      -- depth = 6,7,5,3, Total gates=19
      T01 := X0  or X1;
      T02 := X1  or X2;
      T03 := X0  xor T02;
      T04 := X1  xor X3;
      T05 := X3  or T03;
      T06 := X3  and T01;
      Z   := T03 xor T06;
      T08 := Z   and T04;
      T09 := T04 and T05;
      T10 := X2  xor T06;
      T11 := X1  and X2;
      T12 := T04 xor T08;
      T13 := T11 or T03;
      T14 := T10 xor T09;
      T15 := X0  and T05;
      T16 := T11 or T12;
      Y   := T13 xor T08;
      X   := T15 xor T16;
      W   :=     not T14;
    elsif R = 5 then
      -- S5:  15  5  2 11  4 10  9 12  0  3 14  8 13  6  7  1
      -- depth = 4,6,8,6, Total gates=17
      T01 := X1  xor X3;
      T02 := X1  or X3;
      T03 := X0  and T01;
      T04 := X2  xor T02;
      T05 := T03 xor T04;
      W   :=     not T05;
      T07 := X0  xor T01;
      T08 := X3  or w;
      T09 := X1  or T05;
      T10 := X3  xor T08;
      T11 := X1  or T07;
      T12 := T03 or w;
      T13 := T07 or T10;
      T14 := T01 xor T11;
      Y   := T09 xor T13;
      X   := T07 xor T08;
      Z   := T12 xor T14;
    elsif R = 6 then
      -- S6:   7  2 12  5  8  4  6 11 14  9  1 15 13  3 10  0
      -- depth = 8,3,6,3, Total gates=19
      T01 := X0  and X3;
      T02 := X1  xor X2;
      T03 := X0  xor X3;
      T04 := T01 xor T02;
      T05 := X1  or X2;
      X   :=     not T04;
      T07 := T03 and T05;
      T08 := X1  and x;
      T09 := X0  or X2;
      T10 := T07 xor T08;
      T11 := X1  or X3;
      T12 := X2  xor T11;
      T13 := T09 xor T10;
      Y   :=     not T13;
      T15 := X   and T03;
      Z   := T12 xor T07;
      T17 := X0  xor X1;
      T18 := Y   xor T15;
      W   := T17 xor T18;
    elsif R = 7 then
      -- S7:   1 13 15  0 14  8  2 11  7  4 12 10  9  3  5  6
      -- depth = 10,7,10,4, Total gates=19
      T01 := X0  and X2;
      T02 :=     not X3;
      T03 := X0  and T02;
      T04 := X1  or T01;
      T05 := X0  and X1;
      T06 := X2  xor T04;
      Z   := T03 xor T06;
      T08 := X2  or z;
      T09 := X3  or T05;
      T10 := X0  xor T08;
      T11 := T04 and z;
      X   := T09 xor T10;
      T13 := X1  xor x;
      T14 := T01 xor x;
      T15 := X2  xor T05;
      T16 := T11 or T13;
      T17 := T02 or T14;
      W   := T15 xor T17;
      Y   := X0  xor T16;
    end if;
    X0 := W;
    X1 := X;
    X2 := Y;
    X3 := Z;
  end S;

  -- Inverse Sbox function

  procedure SI (R : Integer; X0, X1, X2, X3 : in out Unsigned_32) is
      T01, T02, T03, T04, T05, T06, T07, T08, T09,
      T10, T11, T12, T13, T14, T15, T16, T17, T18 : Unsigned_32;
      W, X, Y, Z : Unsigned_32;
  begin
    if R = 0 then
      -- InvS0:  13  3 11  0 10  6  5 12  1 14  4  7 15  9  8  2
      -- depth = 8,4,3,6, Total gates=19
      T01 := X2  xor X3;
      T02 := X0  or X1;
      T03 := X1  or X2;
      T04 := X2  and T01;
      T05 := T02 xor T01;
      T06 := X0  or T04;
      Y   :=     not T05;
      T08 := X1  xor X3;
      T09 := T03 and T08;
      T10 := X3  or y;
      X   := T09 xor T06;
      T12 := X0  or T05;
      T13 := X   xor T12;
      T14 := T03 xor T10;
      T15 := X0  xor X2;
      Z   := T14 xor T13;
      T17 := T05 and T13;
      T18 := T14 or T17;
      W   := T15 xor T18;
    elsif R = 1 then
      -- InvS1:   5  8  2 14 15  6 12  3 11  4  7  9  1 13 10  0
      -- depth = 7,4,5,3, Total gates=18
      T01 := X0  xor X1;
      T02 := X1  or X3;
      T03 := X0  and X2;
      T04 := X2  xor T02;
      T05 := X0  or T04;
      T06 := T01 and T05;
      T07 := X3  or T03;
      T08 := X1  xor T06;
      T09 := T07 xor T06;
      T10 := T04 or T03;
      T11 := X3  and T08;
      Y   :=     not T09;
      X   := T10 xor T11;
      T14 := X0  or y;
      T15 := T06 xor x;
      Z   := T01 xor T04;
      T17 := X2  xor T15;
      W   := T14 xor T17;
    elsif R = 2 then
      -- InvS2:  12  9 15  4 11 14  1  2  0  3  6 13  5  8 10  7
      -- depth = 3,6,8,3, Total gates=18
      T01 := X0  xor X3;
      T02 := X2  xor X3;
      T03 := X0  and X2;
      T04 := X1  or T02;
      W   := T01 xor T04;
      T06 := X0  or X2;
      T07 := X3  or w;
      T08 :=     not X3;
      T09 := X1  and T06;
      T10 := T08 or T03;
      T11 := X1  and T07;
      T12 := T06 and T02;
      Z   := T09 xor T10;
      X   := T12 xor T11;
      T15 := X2  and z;
      T16 := W   xor x;
      T17 := T10 xor T15;
      Y   := T16 xor T17;
    elsif R = 3 then
      -- InvS3:   0  9 10  7 11 14  6 13  3  5 12  2  4  8 15  1
      -- depth = 3,6,4,4, Total gates=17
      T01 := X2  or X3;
      T02 := X0  or X3;
      T03 := X2  xor T02;
      T04 := X1  xor T02;
      T05 := X0  xor X3;
      T06 := T04 and T03;
      T07 := X1  and T01;
      Y   := T05 xor T06;
      T09 := X0  xor T03;
      W   := T07 xor T03;
      T11 := W   or T05;
      T12 := T09 and T11;
      T13 := X0  and y;
      T14 := T01 xor T05;
      X   := X1  xor T12;
      T16 := X1  or T13;
      Z   := T14 xor T16;
    elsif R = 4 then
      -- InvS4:   5  0  8  3 10  9  7 14  2 12 11  6  4 15 13  1
      -- depth = 6,4,7,3, Total gates=17
      T01 := X1  or X3;
      T02 := X2  or X3;
      T03 := X0  and T01;
      T04 := X1  xor T02;
      T05 := X2  xor X3;
      T06 :=     not T03;
      T07 := X0  and T04;
      X   := T05 xor T07;
      T09 := X   or T06;
      T10 := X0  xor T07;
      T11 := T01 xor T09;
      T12 := X3  xor T04;
      T13 := X2  or T10;
      Z   := T03 xor T12;
      T15 := X0  xor T04;
      Y   := T11 xor T13;
      W   := T15 xor T09;
    elsif R = 5 then
      -- InvS5:   8 15  2  9  4  1 13 14 11  6  5  3  7 12 10  0
      -- depth = 4,6,9,7, Total gates=17
      T01 := X0  and X3;
      T02 := X2  xor T01;
      T03 := X0  xor X3;
      T04 := X1  and T02;
      T05 := X0  and X2;
      W   := T03 xor T04;
      T07 := X0  and w;
      T08 := T01 xor w;
      T09 := X1  or T05;
      T10 :=     not X1;
      X   := T08 xor T09;
      T12 := T10 or T07;
      T13 := W   or x;
      Z   := T02 xor T12;
      T15 := T02 xor T13;
      T16 := X1  xor X3;
      Y   := T16 xor T15;
    elsif R = 6 then
      -- InvS6:  15 10  1 13  5  3  6  0  4  9 14  7  2 12  8 11
      -- depth = 5,3,8,6, Total gates=19
      T01 := X0  xor X2;
      T02 :=     not X2;
      T03 := X1  and T01;
      T04 := X1  or T02;
      T05 := X3  or T03;
      T06 := X1  xor X3;
      T07 := X0  and T04;
      T08 := X0  or T02;
      T09 := T07 xor T05;
      X   := T06 xor T08;
      W   :=     not T09;
      T12 := X1  and w;
      T13 := T01 and T05;
      T14 := T01 xor T12;
      T15 := T07 xor T13;
      T16 := X3  or T02;
      T17 := X0  xor x;
      Z   := T17 xor T15;
      Y   := T16 xor T14;
    elsif R = 7 then
      -- InvS7:   3  0  6 13  9 14 15  8  5 12 11  7 10  1  4  2
      -- depth := 9,7,3,3, Total gates:=18
      T01 := X0  and X1;
      T02 := X0  or X1;
      T03 := X2  or T01;
      T04 := X3  and T02;
      Z   := T03 xor T04;
      T06 := X1  xor T04;
      T07 := X3  xor z;
      T08 :=     not T07;
      T09 := T06 or T08;
      T10 := X1  xor X3;
      T11 := X0  or X3;
      X   := X0  xor T09;
      T13 := X2  xor T06;
      T14 := X2  and T11;
      T15 := X3  or x;
      T16 := T01 or T10;
      W   := T13 xor T15;
      Y   := T14 xor T16;
    end if;
    X0 := W;
    X1 := X;
    X2 := Y;
    X3 := Z;
  end SI;

  -- Linear Transform

  procedure Tr (X0, X1, X2, X3 : in out Unsigned_32) is
  begin
    X0 := Rotate_Left(X0, 13);
    X2 := Rotate_Left(X2, 3);
    X1 := X1 xor X0 xor X2;
    X3 := X3 xor X2 xor Shift_Left(X0, 3);
    X1 := Rotate_Left(X1, 1);
    X3 := Rotate_Left(X3, 7);
    X0 := X0 xor X1 xor X3;
    X2 := X2 xor X3 xor Shift_Left(X1, 7);
    X0 := Rotate_Left(X0, 5);
    X2 := Rotate_Left(X2, 22);
  end Tr;

  -- Inverse Linear Transform

  procedure TrI (X0, X1, X2, X3 : in out Unsigned_32) is
  begin
    X2 := Rotate_Right(X2, 22);
    X0 := Rotate_Right(X0, 5);
    X2 := X2 xor X3 xor Shift_Left(X1, 7);
    X0 := X0 xor X1 xor X3;
    X3 := Rotate_Right(X3, 7);
    X1 := Rotate_Right(X1, 1);
    X3 := X3 xor X2 xor Shift_Left(X0, 3);
    X1 := X1 xor X0 xor X2;
    X2 := Rotate_Right(X2, 3);
    X0 := Rotate_Right(X0, 13);
  end TrI;

  procedure Keying (W : Key_Schedule;
                    R : Integer;
       X0, X1, X2, X3 : in out Unsigned_32) is
  begin
    X0 := X0 xor W(4*R);
    X1 := X1 xor W(4*R+1);
    X2 := X2 xor W(4*R+2);
    X3 := X3 xor W(4*R+3);
  end Keying;

  pragma Inline(S, SI, Tr, TrI, Keying);

  procedure Prepare_Key (K : in Key; W : out Key_Schedule) is
  begin
    for I in 0..7 loop
      W(-8+I) := Bytes_To_Word(K(4*I .. 4*I+3));
    end loop;
    for I in 0..131 loop
      W(I) := Rotate_Left(W(I-8) xor W(I-5) xor W(I-3) xor W(I-1) xor
              16#9e3779b9# xor Unsigned_32(I), 11);
    end loop;
    S(3, W(  0), W(  1), W(  2), W(  3));
    S(2, W(  4), W(  5), W(  6), W(  7));
    S(1, W(  8), W(  9), W( 10), W( 11));
    S(0, W( 12), W( 13), W( 14), W( 15));
    S(7, W( 16), W( 17), W( 18), W( 19));
    S(6, W( 20), W( 21), W( 22), W( 23));
    S(5, W( 24), W( 25), W( 26), W( 27));
    S(4, W( 28), W( 29), W( 30), W( 31));
    S(3, W( 32), W( 33), W( 34), W( 35));
    S(2, W( 36), W( 37), W( 38), W( 39));
    S(1, W( 40), W( 41), W( 42), W( 43));
    S(0, W( 44), W( 45), W( 46), W( 47));
    S(7, W( 48), W( 49), W( 50), W( 51));
    S(6, W( 52), W( 53), W( 54), W( 55));
    S(5, W( 56), W( 57), W( 58), W( 59));
    S(4, W( 60), W( 61), W( 62), W( 63));
    S(3, W( 64), W( 65), W( 66), W( 67));
    S(2, W( 68), W( 69), W( 70), W( 71));
    S(1, W( 72), W( 73), W( 74), W( 75));
    S(0, W( 76), W( 77), W( 78), W( 79));
    S(7, W( 80), W( 81), W( 82), W( 83));
    S(6, W( 84), W( 85), W( 86), W( 87));
    S(5, W( 88), W( 89), W( 90), W( 91));
    S(4, W( 92), W( 93), W( 94), W( 95));
    S(3, W( 96), W( 97), W( 98), W( 99));
    S(2, W(100), W(101), W(102), W(103));
    S(1, W(104), W(105), W(106), W(107));
    S(0, W(108), W(109), W(110), W(111));
    S(7, W(112), W(113), W(114), W(115));
    S(6, W(116), W(117), W(118), W(119));
    S(5, W(120), W(121), W(122), W(123));
    S(4, W(124), W(125), W(126), W(127));
    S(3, W(128), W(129), W(130), W(131));
  end Prepare_Key;

  procedure Encrypt (W : in Key_Schedule; Plaintext  :  in Block;
            Ciphertext : out Block) is
    X0, X1, X2, X3 : Unsigned_32;
  begin
    X0 := Bytes_To_Word(Plaintext( 0 ..  3));
    X1 := Bytes_To_Word(Plaintext( 4 ..  7));
    X2 := Bytes_To_Word(Plaintext( 8 .. 11));
    X3 := Bytes_To_Word(Plaintext(12 .. 15));

    Keying(W,  0, X0, X1, X2, X3); S(0, X0, X1, X2, X3); Tr(X0, X1, X2, X3);
    Keying(W,  1, X0, X1, X2, X3); S(1, X0, X1, X2, X3); Tr(X0, X1, X2, X3);
    Keying(W,  2, X0, X1, X2, X3); S(2, X0, X1, X2, X3); Tr(X0, X1, X2, X3);
    Keying(W,  3, X0, X1, X2, X3); S(3, X0, X1, X2, X3); Tr(X0, X1, X2, X3);
    Keying(W,  4, X0, X1, X2, X3); S(4, X0, X1, X2, X3); Tr(X0, X1, X2, X3);
    Keying(W,  5, X0, X1, X2, X3); S(5, X0, X1, X2, X3); Tr(X0, X1, X2, X3);
    Keying(W,  6, X0, X1, X2, X3); S(6, X0, X1, X2, X3); Tr(X0, X1, X2, X3);
    Keying(W,  7, X0, X1, X2, X3); S(7, X0, X1, X2, X3); Tr(X0, X1, X2, X3);
    Keying(W,  8, X0, X1, X2, X3); S(0, X0, X1, X2, X3); Tr(X0, X1, X2, X3);
    Keying(W,  9, X0, X1, X2, X3); S(1, X0, X1, X2, X3); Tr(X0, X1, X2, X3);
    Keying(W, 10, X0, X1, X2, X3); S(2, X0, X1, X2, X3); Tr(X0, X1, X2, X3);
    Keying(W, 11, X0, X1, X2, X3); S(3, X0, X1, X2, X3); Tr(X0, X1, X2, X3);
    Keying(W, 12, X0, X1, X2, X3); S(4, X0, X1, X2, X3); Tr(X0, X1, X2, X3);
    Keying(W, 13, X0, X1, X2, X3); S(5, X0, X1, X2, X3); Tr(X0, X1, X2, X3);
    Keying(W, 14, X0, X1, X2, X3); S(6, X0, X1, X2, X3); Tr(X0, X1, X2, X3);
    Keying(W, 15, X0, X1, X2, X3); S(7, X0, X1, X2, X3); Tr(X0, X1, X2, X3);
    Keying(W, 16, X0, X1, X2, X3); S(0, X0, X1, X2, X3); Tr(X0, X1, X2, X3);
    Keying(W, 17, X0, X1, X2, X3); S(1, X0, X1, X2, X3); Tr(X0, X1, X2, X3);
    Keying(W, 18, X0, X1, X2, X3); S(2, X0, X1, X2, X3); Tr(X0, X1, X2, X3);
    Keying(W, 19, X0, X1, X2, X3); S(3, X0, X1, X2, X3); Tr(X0, X1, X2, X3);
    Keying(W, 20, X0, X1, X2, X3); S(4, X0, X1, X2, X3); Tr(X0, X1, X2, X3);
    Keying(W, 21, X0, X1, X2, X3); S(5, X0, X1, X2, X3); Tr(X0, X1, X2, X3);
    Keying(W, 22, X0, X1, X2, X3); S(6, X0, X1, X2, X3); Tr(X0, X1, X2, X3);
    Keying(W, 23, X0, X1, X2, X3); S(7, X0, X1, X2, X3); Tr(X0, X1, X2, X3);
    Keying(W, 24, X0, X1, X2, X3); S(0, X0, X1, X2, X3); Tr(X0, X1, X2, X3);
    Keying(W, 25, X0, X1, X2, X3); S(1, X0, X1, X2, X3); Tr(X0, X1, X2, X3);
    Keying(W, 26, X0, X1, X2, X3); S(2, X0, X1, X2, X3); Tr(X0, X1, X2, X3);
    Keying(W, 27, X0, X1, X2, X3); S(3, X0, X1, X2, X3); Tr(X0, X1, X2, X3);
    Keying(W, 28, X0, X1, X2, X3); S(4, X0, X1, X2, X3); Tr(X0, X1, X2, X3);
    Keying(W, 29, X0, X1, X2, X3); S(5, X0, X1, X2, X3); Tr(X0, X1, X2, X3);
    Keying(W, 30, X0, X1, X2, X3); S(6, X0, X1, X2, X3); Tr(X0, X1, X2, X3);
    Keying(W, 31, X0, X1, X2, X3);
    S(7, X0, X1, X2, X3);
    Keying(W, 32, X0, X1, X2, X3);

    Ciphertext( 0 ..  3) := Word_To_Bytes(X0);
    Ciphertext( 4 ..  7) := Word_To_Bytes(X1);
    Ciphertext( 8 .. 11) := Word_To_Bytes(X2);
    Ciphertext(12 .. 15) := Word_To_Bytes(X3);
  end Encrypt;

  procedure Decrypt (W : in Key_Schedule; Ciphertext :  in Block;
            Plaintext  : out Block) is
    X0, X1, X2, X3 : Unsigned_32;
  begin
    X0 := Bytes_To_Word(Ciphertext( 0 ..  3));
    X1 := Bytes_To_Word(Ciphertext( 4 ..  7));
    X2 := Bytes_To_Word(Ciphertext( 8 .. 11));
    X3 := Bytes_To_Word(Ciphertext(12 .. 15));

    Keying(W, 32, X0, X1, X2, X3);
    SI(7, X0, X1, X2, X3);
    Keying(W, 31, X0, X1, X2, X3);
    TrI(X0, X1, X2, X3); SI(6, X0, X1, X2, X3); Keying(W,30, X0, X1, X2, X3);
    TrI(X0, X1, X2, X3); SI(5, X0, X1, X2, X3); Keying(W,29, X0, X1, X2, X3);
    TrI(X0, X1, X2, X3); SI(4, X0, X1, X2, X3); Keying(W,28, X0, X1, X2, X3);
    TrI(X0, X1, X2, X3); SI(3, X0, X1, X2, X3); Keying(W,27, X0, X1, X2, X3);
    TrI(X0, X1, X2, X3); SI(2, X0, X1, X2, X3); Keying(W,26, X0, X1, X2, X3);
    TrI(X0, X1, X2, X3); SI(1, X0, X1, X2, X3); Keying(W,25, X0, X1, X2, X3);
    TrI(X0, X1, X2, X3); SI(0, X0, X1, X2, X3); Keying(W,24, X0, X1, X2, X3);
    TrI(X0, X1, X2, X3); SI(7, X0, X1, X2, X3); Keying(W,23, X0, X1, X2, X3);
    TrI(X0, X1, X2, X3); SI(6, X0, X1, X2, X3); Keying(W,22, X0, X1, X2, X3);
    TrI(X0, X1, X2, X3); SI(5, X0, X1, X2, X3); Keying(W,21, X0, X1, X2, X3);
    TrI(X0, X1, X2, X3); SI(4, X0, X1, X2, X3); Keying(W,20, X0, X1, X2, X3);
    TrI(X0, X1, X2, X3); SI(3, X0, X1, X2, X3); Keying(W,19, X0, X1, X2, X3);
    TrI(X0, X1, X2, X3); SI(2, X0, X1, X2, X3); Keying(W,18, X0, X1, X2, X3);
    TrI(X0, X1, X2, X3); SI(1, X0, X1, X2, X3); Keying(W,17, X0, X1, X2, X3);
    TrI(X0, X1, X2, X3); SI(0, X0, X1, X2, X3); Keying(W,16, X0, X1, X2, X3);
    TrI(X0, X1, X2, X3); SI(7, X0, X1, X2, X3); Keying(W,15, X0, X1, X2, X3);
    TrI(X0, X1, X2, X3); SI(6, X0, X1, X2, X3); Keying(W,14, X0, X1, X2, X3);
    TrI(X0, X1, X2, X3); SI(5, X0, X1, X2, X3); Keying(W,13, X0, X1, X2, X3);
    TrI(X0, X1, X2, X3); SI(4, X0, X1, X2, X3); Keying(W,12, X0, X1, X2, X3);
    TrI(X0, X1, X2, X3); SI(3, X0, X1, X2, X3); Keying(W,11, X0, X1, X2, X3);
    TrI(X0, X1, X2, X3); SI(2, X0, X1, X2, X3); Keying(W,10, X0, X1, X2, X3);
    TrI(X0, X1, X2, X3); SI(1, X0, X1, X2, X3); Keying(W, 9, X0, X1, X2, X3);
    TrI(X0, X1, X2, X3); SI(0, X0, X1, X2, X3); Keying(W, 8, X0, X1, X2, X3);
    TrI(X0, X1, X2, X3); SI(7, X0, X1, X2, X3); Keying(W, 7, X0, X1, X2, X3);
    TrI(X0, X1, X2, X3); SI(6, X0, X1, X2, X3); Keying(W, 6, X0, X1, X2, X3);
    TrI(X0, X1, X2, X3); SI(5, X0, X1, X2, X3); Keying(W, 5, X0, X1, X2, X3);
    TrI(X0, X1, X2, X3); SI(4, X0, X1, X2, X3); Keying(W, 4, X0, X1, X2, X3);
    TrI(X0, X1, X2, X3); SI(3, X0, X1, X2, X3); Keying(W, 3, X0, X1, X2, X3);
    TrI(X0, X1, X2, X3); SI(2, X0, X1, X2, X3); Keying(W, 2, X0, X1, X2, X3);
    TrI(X0, X1, X2, X3); SI(1, X0, X1, X2, X3); Keying(W, 1, X0, X1, X2, X3);
    TrI(X0, X1, X2, X3); SI(0, X0, X1, X2, X3); Keying(W, 0, X0, X1, X2, X3);

    Plaintext( 0 ..  3) := Word_To_Bytes(X0);
    Plaintext( 4 ..  7) := Word_To_Bytes(X1);
    Plaintext( 8 .. 11) := Word_To_Bytes(X2);
    Plaintext(12 .. 15) := Word_To_Bytes(X3);
  end Decrypt;

  procedure Selftest is
    K     : Key    := (others => 0);
    P     : Block  := (others => 0);
    P2, C : Block;
    W     : Key_Schedule;
  begin
    for I in 1 .. 128 loop
      Prepare_Key(K, W);
      Encrypt(W, P, C);
      Decrypt(W, C, P2);
      if (P2 /= P) then
        raise Implementation_Error;
      end if;
      P           := K( 0 .. 15);
      K( 0 .. 15) := K(16 .. 31);
      K(16 .. 31) := C;
    end loop;
    if C /= (16#A2#, 16#46#, 16#AB#, 16#69#, 16#0A#, 16#E6#, 16#8D#, 16#FB#,
             16#02#, 16#04#, 16#CB#, 16#E2#, 16#8E#, 16#D8#, 16#EB#, 16#7A#)
      then
      raise Implementation_Error;
    end if;
  end Selftest;

end SMG_Serpent;

The Selftest procedure above runs one single test for Serpent encrypt/decrypt, failing with an "Implementation_Error" if the result is not as expected. I added a bigger set of tests on all the test vectors and cases publicly available as part of the NESSIE project. The eucrypt/smg_serpent/tests/smg_serpent_tests.gpr can be used with gprbuild to compile the code for the automated tests:

 -- Tests for SMG_Serpent (part of EuCrypt)
 -- S.MG, 2018

project SMG_Serpent_Tests is
  for Source_Dirs use (".", "../src");
  for Object_Dir use "obj";
  for Exec_Dir use ".";

  for Main use ("testall.adb");
end SMG_Serpent_Tests;

EuCrypt/smg_serpent/tests/test_serpent.ads defines a package Test_Serpent that includes a procedure for running one single hard-coded test (similar to Selftest in Serpent's own code) and another procedure for running all tests on all test vectors and cases from a given file:

-- S.MG, 2018

with Ada.Strings.Fixed;
use Ada.Strings.Fixed;

package Test_Serpent is
	procedure test_from_file(filename: String);
	procedure test_one;
end Test_Serpent;

The implementation of those two testing procedures is in eucrypt/smg_serpent/tests/test_serpent.adb, where a lot of space is taken mainly by reading and interpreting the plain-text NESSIE format of the test vectors:

 -- S.MG, 2018
 -- Testing of Serpent implementation using Nessie-format test vectors

with SMG_Serpent; use SMG_Serpent;

with Ada.Text_IO; use Ada.Text_IO;
with Ada.Command_Line; use Ada.Command_Line; -- set exit status on fail
with Interfaces; use Interfaces; -- unsigned_8

package body Test_Serpent is
  Test_Fail : exception;  -- raised if a test fails

  procedure test_from_file (filename: String) is
    file     : FILE_TYPE;
    keylen   : constant := 256;
    blocklen : constant := 128;
    octets   : constant := 16;
    K        : Key;
    P, P2    : Block;	--plain text
    C, C2    : Block;	--cipher (encrypted) text
    times100 : Block;	--value after 100 iterations
    times1k  : Block;	--value after 1000 iterations
    W        : Key_Schedule;
    Test_No  : Positive := 1;
  begin
    begin
      open(file, In_File, filename);
      exception
      when others =>
        Put_Line(Standard_Error, "Can not open the file '" & filename &
                                 "'. Does it exist?");
        Set_Exit_Status(Failure);
        return;
    end;

    loop
      declare
        Line1      : String := Get_Line(file);
        Line2      : String := Line1;
        key1, key2 : String( 1..octets*2 );
        len        : Natural := 0;
      begin
        --check if this is test data of any known kind
        if index( Line1, "key=", 1 ) > 0 then
          Line2 := Get_Line( file );
          key1  := Tail( Line1, octets*2  );
          key2  := Tail( Line2, octets*2 );
          for jj in 1..octets loop
            K(jj-1) := Unsigned_8'Value("16#" &
                                        key1( ( jj - 1 ) * 2 + 1 .. jj * 2 ) &
                                        "#");
            K( jj + octets - 1 ) :=
                       Unsigned_8'Value("16#" &
                                        key2( ( jj - 1 ) * 2 + 1 .. jj * 2 ) &
                                        "#");
          end loop;

        elsif index( Line1, "plain=", 1 ) > 0 then
          key1 := Tail( Line1, octets * 2 );
          for jj in 1..octets loop
            P(jj-1) := Unsigned_8'Value("16#" &
                                        key1( ( jj - 1 ) * 2 + 1 .. jj * 2 ) &
                                        "#");
          end loop;
        elsif index( Line1, "cipher=", 1 ) > 0 then
          key1 := Tail( Line1, octets * 2 );
          for jj in 1..octets loop
            C(jj-1) := Unsigned_8'Value("16#" &
                                        key1( ( jj - 1 ) * 2 + 1 .. jj * 2) &
                                        "#");
          end loop;
        elsif index( Line1, "100 times=", 1 ) > 0 then
          key1 := Tail( Line1, octets * 2 );
          for jj in 1..octets loop
            times100(jj-1) :=
                       Unsigned_8'Value("16#" &
                                        key1( ( jj - 1 ) * 2 + 1 .. jj * 2 ) &
                                        "#");
          end loop;
        elsif index( Line1, "1000 times=", 1 ) > 0 then
          key1 := Tail( Line1, octets * 2 );
          for jj in 1..octets loop
            times1k(jj-1) :=
                       Unsigned_8'value("16#" &
                                        key1( ( jj - 1 ) * 2 + 1 .. jj * 2 ) &
                                        "#");
          end loop;
          --at this stage we should have ALL needed, so run test
          Put("-----Test " & Positive'Image(Test_No) & ": encryption...");
          Prepare_Key(K, W);
          Encrypt(W, P, C2);
          if C2 /= C then
            raise Test_Fail;
          else
            Put_Line("Passed-----");
          end if;
          Put("-----Test " & Positive'Image(Test_No) & ": decryption...");
          Decrypt(W, C2, P2);
          if P /= P2 then
            raise Test_Fail;
          else
            Put_Line("Passed-----");
          end if;

          Put("-----Test " & Positive'Image(Test_No) & ": 100 iterations...");
          for jj in 1 .. 100 loop
            Encrypt(W, P, C2);
            Decrypt(W, C2, P2);
            if (P2 /= P) then
              raise Test_Fail;
            end if;
            P := C2;
          end loop;
          Put_Line("Passed-----");

          Put("-----Test " & Positive'Image(Test_No) & ": 1000 iterations...");

          for jj in 1 .. 900 loop
            Encrypt(W, P, C2);
            Decrypt(W, C2, P2);
            if (P2 /= P) then
              raise Test_Fail;
            end if;
            P := C2;
          end loop;
          Put_Line("Passed-----");
          Test_No := Test_No + 1;
        end if;
        exit when End_Of_File(file);
      end;
    end loop;
    Close(file);
  end test_from_file;

  procedure test_one is
    K: Key;
    P, P2: Block;
    C: Block;
    W: Key_Schedule;
  begin
    K := (16#80#, 16#00#, 16#00#, 16#00#, 16#00#, 16#00#, 16#00#, 16#00#,
          16#00#, 16#00#, 16#00#, 16#00#, 16#00#, 16#00#, 16#00#, 16#00#,
          16#00#, 16#00#, 16#00#, 16#00#, 16#00#, 16#00#, 16#00#, 16#00#,
          16#00#, 16#00#, 16#00#, 16#00#, 16#00#, 16#00#, 16#00#, 16#00#);

    P := (16#00#, 16#00#, 16#00#, 16#00#, 16#00#, 16#00#, 16#00#, 16#00#,
          16#00#, 16#00#, 16#00#, 16#00#, 16#00#, 16#00#, 16#00#, 16#00#);

    SMG_Serpent.Prepare_Key(K, W);
    Encrypt(W, P, C);
    if C /= (16#A2#, 16#23#, 16#AA#, 16#12#, 16#88#, 16#46#, 16#3C#, 16#0E#,
             16#2B#, 16#E3#, 16#8E#, 16#BD#, 16#82#, 16#56#, 16#16#, 16#C0#)
      then
      raise Test_Fail;
    end if;

    for I in 1 .. 100 loop
      Encrypt(W, P, C);
      Decrypt(W, C, P2);
      if (P2 /= P) then
        raise Test_Fail;
      end if;
      P := C;
    end loop;

    if C /= (16#73#, 16#9E#, 16#01#, 16#48#, 16#97#, 16#1F#, 16#D9#, 16#75#,
             16#B5#, 16#85#, 16#EA#, 16#FD#, 16#BD#, 16#65#, 16#9E#, 16#2C#)
      then
      raise Test_Fail;
    end if;

    for I in 1 .. 900 loop
      Encrypt(W, P, C);
      Decrypt(W, C, P2);
      if (P2 /= P) then
        raise Test_Fail;
      end if;
      P := C;
    end loop;

    if C /= (16#BE#, 16#FD#, 16#00#, 16#E0#, 16#D6#, 16#E2#, 16#7E#, 16#56#,
             16#95#, 16#1D#, 16#C6#, 16#61#, 16#44#, 16#40#, 16#D2#, 16#86#)
      then
      raise Test_Fail;
    else
      Put_Line("PASSED: test single case.");
    end if;

  end test_one;

end Test_Serpent;

To put everything together, the calls to the two testing procedures are in eucrypt/smg_serpent/tests/test_serpent.ads:

-- S.MG, 2018

with Ada.Strings.Fixed;
use Ada.Strings.Fixed;

package Test_Serpent is
	procedure test_from_file(filename: String);
	procedure test_one;
end Test_Serpent;

The test vectors from the NESSIE project are also provided in eucrypt/smg_serpent/tests/nessie_vectors.txt but I won't paste them here directly seeing how the file has 10309 lines.

For the actual .vpatch this time I even had a choice of vdiff tools to use, since phf conveniently just published the first part of his work on vtools. I can therefore happily report that his patches press fine and his resulting vdiff worked on this chapter's files all right as far as I can see. A comparison of the .vpatch obtained with the old vdiff vs the .vpatch obtained with phf's vdiff reveals (as phf has already noted) that there a differences only with respect to the order in which the files are considered. For the curious reader, here is the diff of the two vpatches, obtained with "diff eucrypt_ch11_serpent.vpatch test.vpatch" where test.vpatch is the result of running phf's vdiff while eucrypt_ch11_serpent.vpatch is the result of running the old vdiff: diff_order.txt. In the interest of consistency, I'll publish this .vpatch as obtained with the same .vdiff as all other EuCrypt vpatches, but as EuCrypt will soon end, I'll gladly move on to using phf's vdiff for future projects.

As usual, the .vpatch for this chapter, together with my signature for it can be found on my Reference Code Shelf as well as by following the direct links copied here for your convenience:

In the next chapter I'll finally bring everything together through a .vpatch that should (among other things) provide a way to compile the whole EuCrypt as one single aggregate library.


  1. You might call this "hashing" or "encryption/decryption" or even voodoo. After all this work on EuCrypt, I am increasingly drawn towards calling it bit byte diddling - fits better both the actual happenings and the level of proof as to what exactly is achieved. 

  2. I strongly recommend using Adacore's gprbuild as opposed to the gnu/gcc gprbuild.  

Comments feed: RSS 2.0

One Response to “EuCrypt Chapter 11: Serpent”

  1. […] RSA with Keccak-based OAEP (via EuCrypt) for initial communication of OTPs (Serpent keys). 2.2. Serpent (via EuCrypt) for general […]

Leave a Reply