Serpent (encryption)

Serpent
Serpent's linear transformation
developer	Ross Anderson , Eli Biham , Lars Knudsen
Released	August 21, 1998
Derived from	Square
Certification	AES finalist
Key length	128, 192 or 256 bits
Block size	128 bit
structure	Substitution - permutation network
Round	32

Serpent is a symmetric encryption algorithm developed by cryptographers Ross Anderson , Eli Biham and Lars Knudsen . It is a block cipher with a block size of 128 bits and a variable key size of up to 256 bits.

Serpent was a candidate for the Advanced Encryption Standard (AES) and was one of the five finalists in the AES elimination process with Twofish , Rijndael , MARS and RC6 .

Serpent seems to have a safer architecture than Rijndael. MARS, Twofish and Serpent were classified as highly safe, while Rijndael and RC6 were “only” classified as sufficiently safe. Rijndael was mainly criticized for its mathematical structure, which could potentially lead to attacks. In contrast to the other two highly secure candidates in the last round, MARS and Twofish, Serpent was not criticized for its safety and it was assumed that this was the safest of the five finalists.

Serpent also has the fastest speed among the finalists when implemented in hardware that can be pipelined . However, he is the slowest in software implementations, while Rijndael is relatively fast in both hardware and software. Above all, this speed advantage should have been the decisive factor in the decision to declare Rijndael an AES.

functionality

From the key, 33 partial keys up to 128 bits in length each are formed, and the data is divided into blocks of four 32-bit words each. These blocks are then independently encrypted in 32 consecutive rounds. ${\displaystyle K_{\,\!0}}$ ${\displaystyle K_{\,\!32}}$

In each of the rounds to the following operations are performed one after the other: ${\displaystyle i=0}$ ${\displaystyle i=31}$

1. The data block is bit-wise XOR- linked with the partial key. ${\displaystyle K_{\,\!i}}$
2. Four bits that are in the same position in the four data words are always substituted together in an S-Box . There are eight different S-Boxes bis , which are cycled through: in round is used. ${\displaystyle S_{\,\!0}}$ ${\displaystyle S_{\,\!7}}$ ${\displaystyle i}$ ${\displaystyle S_{i\,{\bmod {8}}}}$
3. In round to the data words are subjected to a linear transformation, which is composed of rotations, shifts and XOR operations. It is shown in the picture. Instead, in Runde , the subkey is XORed. ${\displaystyle i=0}$ ${\displaystyle i=30}$ ${\displaystyle i=31}$ ${\displaystyle K_{\,\!32}}$

An alternative implementation of the method works with the substitution of four consecutive bits in a data word. This means that the substitution can be implemented more easily than table access: The four index bits are already together and they only have to be shifted to the right if necessary and the higher bits masked out. Before the first round, the 128 data bits are permuted so that the least significant bits in the four data words come to positions 0 to 3 of the first word, the next most significant to positions 4 to 7, etc. This permutation is reversed after the last round made. The 33 partial keys must also be permuted accordingly. The linear transformation becomes more complicated with this implementation, because here too the different arrangement of the bits must be taken into account.

The first implementation (so-called bitslice technique) has the advantage that all 32 substitutions can be carried out in parallel in one round using bit-by-bit operations . With a correspondingly optimized software implementation, the substitution is faster than with table access. In addition, the developers of the method were able to present a linear transformation that is both simple and effective. B. rotates a data word, all 32 substitution blocks are divided and reassembled.

License

Serpent is not patented and was released as public domain software . It is thus freely available for everyone to use. Optimized versions of the code have been licensed under the GNU General Public License .

Sample applications

The Serpent algorithm is implemented, among others, by the following open source software packages :

• DiskCryptor - full disk encryption, encryption of partitions
• VeraCrypt - full disk encryption, encryption of partitions and of container files
• dm-crypt - hard disk encryption

attack

In 2002, Courtois and Pieprzyk published a paper presenting a potential attack against Serpent (and Rijndael) called XSL. The attack is only theoretical and cannot actually be tried due to its complexity. It is unknown whether the attack could be carried out in practice.

The cryptographers T. Moh and Don Coppersmith believe that the attack on Serpent cannot currently be carried out.

Individual evidence

1. ↑ Ross Anderson, Eli Biham, Lars Knudsen: The Case for Serpent ( English , PDF; 66.8 kB) April 24, 2000. Retrieved May 24, 2012.
2. ↑ Nicolas Courtois, Josef Pieprzyk: Cryptanalysis of Block Ciphers with Overdefined Systems of Equations ( English ) November 9, 2002. Accessed May 24, 2012.
3. ↑ Elisabeth Oswald, Vincent Rijmen, Joan Daemen: AES - An analysis of the security of the Rijndael algorithm (PDF; 130 kB) October 30, 2002. Archived from the original on October 27, 2007. Info: The archive link was automatically inserted and not yet checked. Please check the original and archive link according to the instructions and then remove this notice. Retrieved May 24, 2012. 

Web links

• Serpent (English)
• Description by Markus Repges
• Standard Cryptographic Algorithm Naming to Serpent (English)
• NIST, Report on the Development of the Advanced Encryption Standard (AES), October 2, 2000 (PDF; 392.6 kB)