Why is Serpent faster than AES in this benchmark? I have a laptop without the AES-NI CPU instructions but with SSE4.1.

I'm using Linux and tried the (in-memory) cryptsetup benchmark to get the rough tendency which returned:

#  Algorithm | Key |  Encryption |  Decryption
     aes-cbc   128b   101,4 MiB/s   159,6 MiB/s
 serpent-cbc   128b    52,7 MiB/s   203,4 MiB/s
 twofish-cbc   128b   126,4 MiB/s   176,1 MiB/s
     aes-cbc   256b   107,8 MiB/s   120,4 MiB/s
 serpent-cbc   256b    52,9 MiB/s   203,3 MiB/s
 twofish-cbc   256b   135,2 MiB/s   177,0 MiB/s
     aes-xts   256b   160,6 MiB/s   160,2 MiB/s
 serpent-xts   256b   181,2 MiB/s   188,6 MiB/s
 twofish-xts   256b   164,4 MiB/s   166,2 MiB/s
     aes-xts   512b   121,4 MiB/s   121,0 MiB/s
 serpent-xts   512b   181,4 MiB/s   188,6 MiB/s
 twofish-xts   512b   164,7 MiB/s   165,4 MiB/s


I'm very surprised:


AES has fewer rounds than Serpent so AES should be faster.
AES usage is much higher than Serpent so one could expect the Linux AES crypto module to be much more optimized than Serpent's.
There is no speed decrease with bigger key size in Serpent while there is in AES.
The tests I made 1 year ago on the same computer gave the same speed for AES but all Serpent entries were averaging at 50 MiB/s.
To my knowledge, there has been no huge enhancement of Serpent kernel module in the past year.


Would you trust this "benchmark"? If not, how would you explain the great results for Serpent?
AES has fewer rounds than Serpent so AES should be faster.


The number of rounds by itself is meaningless. Some ciphers have a few complex rounds and others have many simple rounds. See my answer to Why does SHA-1 have 80 rounds? for a related explanation.


  There is no speed decrease with bigger key size in Serpent while there is in AES.


The performance is determined by the number of rounds, and not directly influenced by the key-size.

The AES designers decided that 14 rounds are required for a 256 bit security level and 10 rounds for a 128 bit security level. So AES-256 is about 1.4 times as expensive as AES-128. If you add overhead the relative difference becomes a bit smaller.

The Serpent designers decided to use 32 rounds for all key sizes, so performance is the same for larger keys.


  How would you explain the great results for Serpent?


When operating on a single block Serpent is more expensive than AES. This was one of the reasons why Rijndael was chosen over Serpent to become AES.

When operating on multiple blocks in parallel, Serpent profits from an implementation technique called bit-slicing. So Serpent is faster in modes that allow parallelization.

CBC encryption is sequential (You need the previous block of ciphertext to start encrypting a block), so Serpent is slow here. CBC decryption supports parallelism, since you already know the previous ciphertext block at the start, so Serpent is fast here.

XTS always allows parallelism since the encryption/decryption of different blocks is independent. So Serpent is fast in XTS mode.

It's also possible to implement AES using bit-slicing, but it doesn't profit as much as Serpent since it's possible to use lookup tables to produce an implementation of AES that's fast even for a single block. Some people prefer bit-sliced AES implementations since they avoid timing attacks associated with lookup tables.