# Serpent 256bit Non bit sliced version (Table Sbox/IP/FP/LT/ILT) (Non-bitslice notation rules)

Good afternoon! I got some mismatches while counting Round Keys at non bitsliced version of Serpent. I have used official AES submission outputs (file ecb_iv.txt).

AES submission package test vector:

Key: 0000000000000000000000000000000100112233445566778899aabbccddeeff

First K0{w0,w1,w2,w3}

Rewriting key to ordinary format (as according to specifications, the word0 is LSB and word7 is MSB and converting to Little Endian, to ensure that all ongoing results will be only in Little Endian format)

Rewrote key:
ffeeddcc/bbaa9988/77665544/33221100/01000000/00000000/00000000/00000000

Converting to Little Endian
0xffeeddcc

ff 255 cc
ee 238 dd
dd 221 ee
cc 204 ff
0xccddeeff

0xbbaa9988

bb 187 88
aa 170 99
99 153 aa
88 136 bb
0x8899aabb

0x77665544

77 119 44
66 102 55
55 85 66
44 68 77
0x44556677

0x33221100

33 51 00
22 34 11
11 17 22
00 00 33
0x00112233

0x01000000

01 1 00
00 0 00
00 0 00
00 0 01
0x00000001


Final key:0xccddeeff/0x8899aabb/0x44556677/0x00112233/0x00000001/0x00000000/0x00000000/0x00000000

Enumerate it from word-8,word-7,word-6,word-5,word-4,word-3,word-2,word-1 ccddeeff/8899aabb/44556677/00112233/00000001/00000000/00000000/00000000

word-8 word-7 word-6 word-5 word-4 word-3 word-2 word-1

Setting them to words 0,7 with out changes

ccddeeff/8899aabb/44556677/00112233/00000001/00000000/00000000/00000000 word0 word1 word2 word3 word4 word5 word6 word7

counting words8-15:
wi=(wi−8⊕wi−5⊕wi−3⊕wi−1⊕ϕ⊕(i−8))⋘11

word8

word0^word3^word5^word7^9e3779b9^0<<<11
ccddeeff ^ 00112233 ^9e3779b9 <<<11=DDABAA97

word9
word1^word4^word6^word8^9e3779b9^1<<<11
8899aabb^00000001^DDABAA97^9e3779b9^1 <<<11=2BCCAE58

word10
word2^word5^word7^word9^9e3779b9^2<<<11
44556677^2BCCAE58^9e3779b9^2<<<11=758CA78D

word11
word3^word6^word8^word10^9e3779b9^3<<<11
00112233^DDABAA97^758CA78D^9e3779b9^3<<<11=AB499B0

word8-11 is enough to get firs pair of key k0{word0,word1,word2,word3}

after word8-15 are setted back to words0-7
word8-131 than calculated by
wi=(wi−8⊕wi−5⊕wi−3⊕wi−1⊕ϕ⊕i)⋘11

DDABAA97 2BCCAE58 758CA78D AB499B0

Next Step Apply IP to all keys, first is k0{word0,word1,word2,word3}
11011101101010111010101010010111 (bits 96-127) DDABAA97
00101011110011001010111001011000 (bits 64-95)  2BCCAE58
01110101100011001010011110001101 (bits 32-63)  758CA78D
00001010101101001001100110110000 (bits 0-31)   AB499B0

Values from IP (0,32,64,96) (1,33,65,97) (2,34,66,98) (3,35,67,99)
(4,36,68,100) (5,37,69,101) (6,38,70,102) (7,39,71,103)
Moving bits from IP table to a new one each 2 rows gives a 32bits outputs (16bits*2=32bits)

00010101011001011011010110100111
1565B5A7 output1

after IP to k0 it is

1565b5a7
f2987e11
f078b67c
d28b6515

and it needs to proceed them through Sboxes
HEX:1565b5a7

Split on 4 bytes:0001|0101|0110|0101|1011|0101|1010|0111

S3(1)->15->1111
S3(5)->9->1001
S3(6)->6->0110
S3(5)->9->1001
S3(11)->4->0100
S3(5)->9->1001
S3(10)->2->0010
S3(7)->3->0011

Concating back:11111001011010010100100100100011
result:F9694923


and it matches with K0{word0}

in non bitsliced outputs for Round Keys SK^[0]=f9694923eb1d35ffe03d463a7bd469f9 I also applied same steps at remaining keys and it fully matched with AES submission outputs:

SK^[0]=f9694923eb1d35ffe03d463a7bd469f9
SK^[1]=81c9c543ebb17d93f72ddb7b1246c0fe
SK^[2]=d9cb9d294f75a21f76e516e9a0220149
SK^[3]=7810c931c1bf1344206b34edd58336ff
SK^[4]=770284b55f8f901d9984c9272d0a6c00
SK^[5]=8eeee9aa40ca17afa469e088d93a4678
SK^[6]=c60a71e5965ffe06dfe17e797b99180a
SK^[8]=f6798765f7f43680d8ccddb8ef8b045f
SK^[9]=afff59cb69d8690629b64c9c710a28d2
SK^[10]=7b24db75b1a4533f99f134c0c9343b8d
SK^[11]=0f3ea4410b6d5c38253b77af36cd0a3d
SK^[12]=ebeeb9cb6aa8a2cd4a9ff4ac9667b0c5
SK^[13]=0a648b0792de2d289c71b056aa3caa07
SK^[14]=3ee97c748dec6703d8119331173f1cf7
SK^[15]=d7ce765e2f54e7602654d1376e3f24c2
SK^[16]=b42146cc14611092459a14e95c1ef9fe
SK^[17]=643789ef955c87b60300059087118823
SK^[19]=4d562aa98150415396f15f4eb971782d
SK^[20]=044c9af1f8d10e0d93cb8ef5305947c7
SK^[21]=57de9e2f931e62bc80bda30917982a90
SK^[22]=778aaa18c01266eb626f4c43bc23db00
SK^[24]=d73930a36a61b688bb689b9cd6b1fc4e
SK^[25]=9bd25f02b282121e5e1f656d66fd08a6
SK^[26]=0bbd2fd2455b39a89f578781f5248db0
SK^[28]=eff1ffd0659046d9b510c70d4400261d
SK^[29]=dd39136e08c886fae38e0977243a5668
SK^[30]=d2d744c1bd9306671555fd3c4a0cf068
SK^[31]=852c9e30bde39b76be7035830ba430e1
SK^[32]=60c9994505ceea6aba133490d6cf2a1a


But the problem occures when I tested second test vector which is:

Key: 000000000000000100112233445566778899aabbccddeeffffeeddccbbaa9988

I also rewrote it from LSB to MSB as above and converted to Little Endian

8899aabb|ccddeeff|ffeeddcc|bbaa9988|77665544|33221100|01000000|00000000

8899aabb
88-136
99-153
aa-170
bb-187
0x8899aabb

ccddeeff
cc-204
dd-221
ee-238
ff-255
0xccddeeff

ffeeddcc
ff-255
ee-238
dd-221
cc-204
0xccddeeff

bbaa9988
bb-187
aa-170
99-153
88-136
0x8899aabb

77665544
77-119
66-102
55-85
44-68
0x44556677

33221100
33-51
22-34
11-17
00-00
0x00112233

01000000
01-1
00-0
00-0
00-0
0x00000001

00000000
00-0
00-0
00-0
00-0
0x00000000

8899aabb|ccddeeff|ccddeeff|8899aabb|44556677|00112233|00000001|00000000
word0   word1    word2      word3   word4   word5   word6  word7

counting words8-15:
wi=(wi−8⊕wi−5⊕wi−3⊕wi−1⊕ϕ⊕(i−8))⋘11

word8

word0^word3^word5^word7^9e3779b9^0<<<11
8899aabb^8899aabb^00112233^9e3779b9<<<11=32DC54F1

word9
word1^word4^word6^word8^9e3779b9^1<<<11
ccddeeff^44556677^00000001^32DC54F1^9e3779b9^1<<<11=1D2E0123

word10
word2^word5^word7^word9^9e3779b9^2<<<11

word11
word3^word6^word8^word10^9e3779b9^3<<<11

word8-11 is enough to get firs pair of key k0{word0,word1,word2,word3}

after word8-15 are setted back to words0-7
word8-131 than calculated by
wi=(wi−8⊕wi−5⊕wi−3⊕wi−1⊕ϕ⊕i)⋘11

32DC54F1 1D2E0123 ADA2A27E 812C7C4E

Applying IP to K0
c053661e
51e1bb60
49c98942
1d75cce3

Applying Sbox

HEX:c053661e

Split on 4 bytes:1100|0000|0101|0011|0110|0110|0001|1110

S3(12)->10->1010
S3(0)->0->0000
S3(5)->9->1001
S3(3)->8->1000
S3(6)->6->0110
S3(6)->6->0110
S3(1)->15->1111
S3(14)->5->0101

Concating back:10100000100110000110011011110101
result:A09866F5


But the K0 is SK^[0]=fbfd4c99|d82261b4|14db9401|ae85f52d according to AES Submission. Very strange that on first test vector all calculations of round keys was correct, but on 2nd test vectors not.

Maybe the problem is in bit counting, so that:

11011101101010111010101010010111 (bits 96-127) DDABAA97
00101011110011001010111001011000 (bits 64-95)  2BCCAE58
01110101100011001010011110001101 (bits 32-63)  758CA78D
00001010101101001001100110110000 (bits 0-31)   AB499B0


and it needs to count bits from righ to left instead of left to right. Now I counting bits in a following way:

from left to right bit0=0 bit1=0 bit2=0 bit3=0 bit4=1 bit5=0 bit6=1 bit7=0 bit8=1

but it must be from right to left bit0=0 bit1=0 bit2=0 bit3=0 bit4=1 bit5=1 bit6=0 bit7=1 bit8=1

And during all estimations of Sbox/IP/FP/LT/ILT calculations must be from right to left?

Thanks!

Addition: Seems that counting bits from right to left is incorrect, left to right as I did in calculations is correctly. But it's still uncertain why 2nd test vecotr did not matched with submission package.

Also is enumeration is going right to left order while performing table linear      transform?
input0 input1 input2 input3
DDABAA97 2BCCAE58 758CA78D AB499B0

110111011/0/1010111010101010010111 (bits 96-127) DDABAA97
001010/1/111001100101/0/1110010110/0/0 (bits 64-95) 2BCCAE58
01110101100011001010/0/111/1/0001101 (bits 32-63) 758CA78D
0000101010110100/1/001100110110000 (bits 0-31) AB499B0

bit 0 of output will be XORING of bits {16 52 56 70 83 94 105}
bit 0 of output=1 xor 0 xor 1 xor 1 xor 0 xor 0 xor xor 0=1.


Maybe the problem with the second test vector occured because of incorrect key schedule? In official document there is written 'As with the description of the cipher, we can describe the key schedule in either standard or bitslice mode. We will give the substantive description for the latter case' which means that the description is given for bitslice mode, but not for the general(non-bitsliced mode)?

Addition3: I found that in this document there is a notice, http://csrc.nist.gov/archive/aes/round2/conf3/papers/31-tkohno.pdf that the main difference between non-bitslice and bitslice version is the bite order. But there is no much difference if you start to proceed key as a 128bit or by parts of 32bits each, In the second test vector above the word0,1,2,3 after IP is c053661e51e1bb6049c989421d75cce3, if to convert it to binary it will be same 32bits blocks

1100 0000 0101 0011 0110 0110 0001 1110
0101 0001 1110 0001 1011 1011 0110 0000
0100 1001 1100 1001 1000 1001 0100 0010
0001 1101 0111 0101 1100 1100 1110 0011


So the result will be same as if I sliced a key on 4 32bits, rather than proceeding as in size of 128bits

Applying Sbox

HEX:c053661e

Split on 4 bytes:1100|0000|0101|0011|0110|0110|0001|1110

S3(12)->10->1010
S3(0)->0->0000
S3(5)->9->1001
S3(3)->8->1000
S3(6)->6->0110
S3(6)->6->0110
S3(1)->15->1111
S3(14)->5->0101

Concating back:10100000100110000110011011110101
result:A09866F5


Can anyone say how non bitslice format should be looked like as I already tried to do IP in that way

  32DC54F1 1D2E0123 ADA2A27E 812C7C4E

0011 0010 1101 1100 0101 0100 1111 0001  (bits 96-127) 32DC54F1
0001 1101 0010 1110 0000 0001 0010 0011  (bits 64-95)  1D2E0123
1010 1101 1010 0010 1010 0010 0111 1110  (bits 32-63)  ADA2A27E
1000 0001 0010 1100 0111 1100 0100 1110  (bits 0-31)   812C7C4E
Now I count bits from left to right, so that bits 0,1,2,3 are 1(bit 0),0(bit 1),0(bit 2),0(bit 3). I aslo tried to count right to left, so that bits 0,1,2,3 are 0(bit 0),1(bit 1),1(bit 2),1(bit 3)


But it still did not matched with the second test vector of AES submission, Key: 000000000000000100112233445566778899aabbccddeeffffeeddccbbaa9988

Addition 4: Also tried to use 'flipped sboxes' but same keys are not matching with AES submission vector. Flipped sboxes:

{12, 7, 5, 14, 15, 2, 10, 9, 1, 11, 6, 0, 8, 4, 13, 3},
{15, 8, 9, 6, 4, 7, 10, 12, 3, 13, 0, 11, 14, 1, 5, 2},
{1, 11, 12, 0, 14, 7, 5, 10, 6, 8, 3, 13, 9, 2, 15, 4},
{0, 11, 3, 5, 13, 4, 6, 10, 15, 8, 9, 14, 1, 2, 12, 7},
{8, 4, 3, 9, 1, 2, 13, 14, 15, 10, 0, 7, 12, 5, 6, 11},
{15, 0, 2, 11, 4, 7, 9, 14, 10, 12, 5, 6, 13, 1, 3, 8},
{14, 7, 1, 11, 3, 8, 6, 5, 4, 9, 2, 12, 10, 15, 13, 0},
{8, 14, 7, 9, 15, 3, 4, 10, 11, 2, 1, 12, 0, 5, 13, 6}


But I think that flipped sboxes are not taking difference since I stored all values(key/plaintext) in little endian format, so calculations will be still in little endian. I guess something wrong with sboxes when I put keys through them. But there is no difference if to take 4bit of key and pass it thorugh 32 sboxes. Or to take single 32bit value and pass it through sbox, as I did above. Answers will be same. Can anyone explain what is the real difference in non-bitslice version in exclusion that table linear transform is used. And what is wrong with calculations since I checked them I think that non-bitslice notation use different rules, but I don't see where error is. Thanks!

• Are you sure you didn't use some old version of Serpent with DES S-Box? – LightBit Oct 30 '14 at 16:03
• I have used this constant Sboxes: S0: 3 8 15 1 10 6 5 11 14 13 4 2 7 0 9 12 S1: 15 12 2 7 9 0 5 10 1 11 14 8 6 13 3 4 S2: 8 6 7 9 3 12 10 15 13 1 14 4 0 11 5 2 S3: 0 15 11 8 12 9 6 3 13 1 2 4 10 7 5 14 S4: 1 15 8 3 12 0 11 6 2 5 4 10 9 14 7 13 S5: 15 5 2 11 4 10 9 12 0 3 14 8 13 6 7 1 S6: 7 2 12 5 8 4 6 11 14 9 1 15 13 3 10 0 S7: 1 13 15 0 14 8 2 11 7 4 12 10 9 3 5 6 It is from official submission pdf – nmZ Oct 31 '14 at 0:55
• Maybe a bit order should be like this 11011101101010111010101010010111 (bits 0-31) DDABAA97 00101011110011001010111001011000 (bits 32-63) 2BCCAE58 01110101100011001010011110001101 (bits 64-95) 758CA78D 00001010101101001001100110110000 (bits 96-127) AB499B0 Or all above calculations is correct? – nmZ Oct 31 '14 at 1:41