# Serpent cipher : Osvik S-Boxes confusion and test vectors

I'm having hard time with the implementation of the S-Boxes by Osvik found in this paper: Speeding up Serpent. At the end of the paper, all the s-boxes are given and then, I just implement them. Here's my implementation of $S_0$ as an example :

UInt32Vector Serpent::S0(const UInt32Vector &Y)
{
UInt32Vector X = Y;
X[3] ^= X[0]; uint32_t X4 = X[1];
X[1] &= X[3]; X4 ^= X[2];
X[1] ^= X[0]; X[0] |= X[3];
X[0] ^= X4;   X4 ^= X[3];
X[3] ^= X[2]; X[2] |= X[1];
X[2] ^= X4;   X4 = ~X4;
X4 |= X[1];   X[1] ^= X[3];
X[1] ^= X4;   X[3] |= X[0];
X[1] ^= X[3]; X4 ^= X[3];

return {X[1], X4, X[2], X[0]};
}


As you can see, this is exactly the $S_0$ from the paper. I have to precise that I checked my s-boxes 3 times to be sure there are the same as the one in the paper. Now, here's how I use $S_i$ for $i=0,\ldots,7$ :

subkeys.push_back(S[k & 7]({W[j], W[j+1], W[j+2], W[j+3]}));


where $k = 3$ and decreasing by 1 as it is mentioned in the algorithm specification.

What's confusing me is the Osvik implementation of his s-boxes compared to the ones described in his paper. This seems to be different. Moreover, in his key schedule, $i = 3$ is increasing instead of decreasing.

Now, here's my questions :

1. Where can I find test vectors to test my s-boxes ? I found one for the key schedule in Floppy 4 (ecb_iv.txt) from the full submission package, but nothing about the s-boxes.

2. Why his s-boxes implementation are different than the ones in his paper ?

3. Are my $S_0$ implementation and usage corrects with what I gave or did I miss something important ?

Thanks a lot for your helps.

-
It should be noted that the endianness in the NIST submission and in all other implementations of Serpent is reversed. For S0 with inputs of all FE25B6A1, I get 01DA495E 01DA495E FE25B6A1 FE25B6A1. This is not the NIST byte order. –  Richie Frame Nov 1 '13 at 18:45
I just tested the values and I got the same results as you. My implementation is done in LittleEndian as it is mentioned in the paper. So am I right ? Sorry, but now, I'm still more confused... which one is right ? –  Gabriel L. Nov 1 '13 at 19:12

## 1 Answer

To answer your questions in order:

1. You won't find test vectors for the s-boxes in the submission - the s-box functions are implementation specific optimisations, especially the bit-sliced s-box functions like the Osvik and Gladman/Simpson, which actually compute multiple s-box lookups in parallel.
If you need to test your s-box implementations, I would take the s-box functions from the implementation you're trying to replicate and generate test vectors yourself in isolation.
2. The difference in the s-boxes between the paper and the C source file is explained on the homepage of those two resources: "...Since then I have made further algorithm improvements, and results optimized for 3-way parallel execution are used in my implementation...".
It looks like Osvik did further searching and testing and came up with better (for x86/x64 architecture probably) s-box functions after publishing the initial functions.
3. I can't see anything obviously wrong with your approach, but I would recommend picking one of the implementations to compare to and generate some test vectors directly from the s-box functions to be certain. This is the approach I was planning to use to integrate the Osvik s-box functions into a library that currently uses the Gladman/Simpson ones - I'm glad you pointed out the inconsistency in the paper/source.
-
Now, I understand why this is different and that makes sense with your explanation. Osvik should write another paper to explain his changes for people who want to understand what's happening, not just copying the code :). Thanks for your explanations (+1). I'm no more confused now. –  Gabriel L. Nov 4 '13 at 19:43