# Assembly Language Programming

## July 19, 2013

### FASM – Serpent-1 Encryption

The Serpent-1 Encryption Algorithm was a candidate for the AES and came second to the eventual winner Rijndael.

The homepage for Serpent is here:

Serpent uses a 256 bit key to encrypt 128 bit blocks. The 128 bit input block is encrypted in 32 rounds.

## Related Post

The Javascript version can be found here: Serpent-1 Encryption Algorithm

## The Key Schedule

The 256 bit input key is used to generate 33 x 128 bit sub-keys. The first 32 sub-keys are used in the 32 rounds of the encryption process. The 33rd sub-key is used in the final round.

The following pseudo-code shows the sub-key generation process. An array of 140 32-bit words is created. The first 8 elements are filled with the original 256 bit input key. Then the remaining 132 words are generated as follows:

 for(i = 8 ; i < 140 ; i++) { Key[i] = Key[i-8] xor Key[i-5] xor Key[i-3] xor Key[i-1] xor 0x9e3779b9 xor i; Key[i] = ROTL(Key[i],11); }

The 33 sub-keys (of 128 bits each) are then put through the s-boxes as follows:

 s_index = 3; for(i = 8; i < 136 ; i += 4) { Key[i],Key[i+1],Key[i+2],Key[i+3] = S-Box[s_index](Key[i],Key[i+1],Key[i+2],Key[i+3]); s_index--; if(s_index < 0) s_index = 7; } Key[i],Key[i+1],Key[i+2],Key[i+3] = S-Box[s_index](Key[i],Key[i+1],Key[i+2],Key[i+3]);

## Encryption

The 128 bit input block is encrypted in 32 rounds as follows:

 C = input block; for(round = 0 ; round < 32 ; round++) { C = C xor SubKey[round]; C = S-Box[round mod 8](C); if(round==31) break; C = LT(C); } C = C xor SubKey[32];

C is the 128 bit cipher text. SubKey[round] is one of the 33 x 128 bit sub-keys, indexed from 0 to 32. LT is the linear transform as described below.

## Decryption

Decryption is the exact reverse of the encryption process:

 C = C xor SubKey[32]; for(round = 31 ; round >= 0 ; round--) { if(round == 31) goto .sub C = InvLT(C); .sub: C = InvS-Box[round mod 8](C); C = C xor SubKey[round]; }

## The Linear Transform

The linear transform is applied to a 128 bit block. The block is divided into 4 x 32 bit words as follows: |w0|w1|w2|w3|

 w0 = RotLeft(w0,13); w2 = RotLeft(w2,3); w1 = w1 xor w0 xor w2; w3 = w3 xor w2 xor ShiftLeft(w0,3); w1 = RotLeft(w1,1); w3 = RotLeft(w3,7); w0 = w0 xor w1 xor w3; w2 = w2 xor w3 xor ShiftLeft(w1,7); w0 = RotLeft(w0,5); w2 = RotLeft(w2,22);

## The Inverse Linear Transform

The inverse linear transform is just the linear transform operations in reverse order, but with ROTR instead of ROTL:

 w2 = RotRight(w2,22); w0 = RotRight(w0,5); w2 = w2 xor w3 xor ShiftLeft(w1,7); w0 = w0 xor w1 xor w3; w3 = RotRight(w3,7); w1 = RotRight(w1,1); w3 = w3 xor w2 xor ShiftLeft(w0,3); w1 = w1 xor w0 xor w2; w2 = RotRight(w2,3); w0 = RotRight(w0,13);

## The S-Boxes

Serpent uses 8 s-boxes. Each s-box contains 16 elements. The input and output to a s-box is a 4 bit value, as follows:

n’ = s-box[n], (n = 0-15)

My program implements the bitslice mode of the serpent cipher algorithm. The diagram below shows how the s-boxes are implemented in bitslice mode. The 128 bit input block is divided up into 4 x 32 bit words: |w0|w1|w2|w3|. These are then arranged as shown in the diagram. The substitution is then applied by taking 32 slices of 4 bits each and putting then through 32 copies of the s-box in parallel. Bit 0 is the lsb in the 4 bit value.

## Input Byte Ordering

The input/output is represented as a hexadecimal number, with each pair of hex digits corresponding directly to a byte in an internal byte array. Let the internal array be called input_array[]. Then the first 2 digits in the input correspond to the byte at input_array[0], the next 2 digits correspond to the byte at input_array[1], and so on. The input bytes are organised internally into 32 bit words, with input_array[0] – input_array[3] being the first word, input_array[4] – input_array[7] being the second word, and so on.

For example:

 Byte array (NESSIE) input/output: 16 byte input = 11223344 55667788 9900aabb ccddeeff Stored as: input_array[16] = [11,22,33,44,55,66,77,88,99,00,aa,bb,cc,dd,ee,ff];

Test vectors for Serpent-1 with 256 bit keys are specified in byte array (NESSIE) format here:

## The FASM x86 Source Code

To use the program enter a 256 bit key (64 hex digits) and press [Set Key]. This will display the key schedule. Note that the program expects a full 256 bit key, it will not pad keys shorter than this in the way specified by the algorithm.

Then enter the 128 bit input text (32 hex digits) and press [Encrypt] or [Decrypt]. The program will display the result from each round of the 32 rounds of encryption or decryption, with the final round being the result.