Лабораторная работа №21 / serpent.tar / serpent-as-submitted / floppy5 / serpent

{ 13	15	32}	{50	61	89	93	108}	{62	73	103}	{50 61	77	79	91	96	119}
{ 17	19	36}	{54	65	93	97	112}	{66	77	107}	{54 65	81	83	95	100	123}
{ 21	23	40}	{58	69	97	101	116}	{70	81	111}	{58 69	85	87	99	104	127}
{ 25	27	44} {62 73 101 105 120} {74							85	115} { 3 62 73			89	91	103	108}
{ 29	31	48} {66 77 105 109 124} {78							89	119} { 7 66 77			93	95	107	112}
{ 33	35	52} { 0 70 81 109 113} {82							93	123} {11 70 81			97	99	111	116}
{ 37	39	56} { 4 74 85 113 117} {86							97	127} {15 74 85 101 103 115 120}
{ 41	43	60} { 8 78 89 117 121} {							3	90} {19 78 89 105 107 119 124}
{ 45	47	64} {12 82			93	121	125} {		7	94} { 0 23 82 93 109 111 123}
{ 49	51	68} { 1		16	86	97	125} {		11	98} { 4 27		86	97	113	115	127}

A.5 S-Boxes

Here are the S-boxes S0 through S7:

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

Here are the inverse S-boxes for use in decryption:

InvS0:	13	3	11	0	10	6	5	12	1	14	4	7	15	9	8	2
InvS1:	5	8	2	14	15	6	12	3	11	4	7	9	1	13	10	0
InvS2:	12	9	15	4	11	14	1	2	0	3	6	13	5	8	10	7
InvS3:	0	9	10	7	11	14	6	13	3	5	12	2	4	8	15	1
InvS4:	5	0	8	3	10	9	7	14	2	12	11	6	4	15	13	1
InvS5:	8	15	2	9	4	1	13	14	11	6	5	3	7	12	10	0
InvS6:	15	10	1	13	5	3	6	0	4	9	14	7	2	12	8	11
InvS7:	3	0	6	13	9	14	15	8	5	12	11	7	10	1	4	2

A.6 Lists of Relevant Instructions on Various Processors

The relevant instructions on the following processors are:

Pentium:	AND, OR, XOR, NOT, rotate
MMX:	AND, OR, XOR, NOT, ANDN, only shifts
Alpha:	AND, OR, XOR, NOT, ANDN, ORN, XORN, only shifts

where the ANDN operation on x and y is x^(:y), the ORN operation is x_(:y), and the XORN operation is x (:y) (or equivalently :(x y)).

On MMX a rotate takes four instructions, while on an Alpha it takes three. On Pentium and MMX it might be necessary to copy some of the registers before

21

use, as instructions have only two arguments; but some instructions can refer directly to memory. The Alpha instructions have 3 arguments (src1, src2 and destination), but cannot refer directly to memory.

A.7 Historical Remarks

Here we describe some design history. In our rst design, the linear transformations were just bit permutations, which were applied as rotations of the 32-bit words in the bitslice implementation. In order to ensure maximal avalanche, the idea was to choose these rotations in a way that ensured maximal avalanche in the fewest number of rounds. Thus, we chose three rotations at each round: we used (0, 1, 3, 7) for the even rounds and (0, 5, 13, 22) for the odd rounds. The reason for this was that (a) rotating all four words is useless (b) a single set of rotations did not su ce for full avalanche (c) these sets of rotations have the property that no di erence of pairs in either of them coincides with a di erence either in the same set or the other set.

However, we felt that the avalanche was still slow, as each bit a ected only one bit in the next round, and thus one active S-box a ected only 2{4 out of the 32 S-boxes in the next round. As a result, we had to use 64 rounds, and the cipher was only slightly faster than triple-DES. So we moved to a more complex linear transformation; this improved the avalanche, and analysis showed that we could now reduce the number of rounds to 32. We believe that the nal result is a faster and yet more secure cipher.

We also considered replacing the XOR operations by seemingly more complex operations, such as additions. We did not do this for two major reasons: (1) Our analysis takes advantage of the independence of the bits in the XOR operation, as it allows us to describe the cipher in a standard way, and use the known kinds of analysis. This would not hold if the XOR operations were replaced; (2) in some other ciphers the replacement of XORs by additions (or other operations) has turned out to weaken the cipher, rather than strengthening it.

As noted above, the rst published version of Serpent reused the S-boxes from DES. After this was presented at Fast Software Encryption 98 [10], we studied a number of other linear transformations and S-boxes. We found that it was easy to construct S-boxes that gave much greater security. We were aware that any improvement might come at the expense of the public con dence generated by reusing the DES S-boxes. However, the possible improvement in security was simply too great to forego. We therefore decided to counter the fear of trapdoors by generating the new S-boxes in a simple deterministic way.

Having decided not to use the full set of DES S-boxes, we were also free to change from 32 S-boxes to 8, which greatly reduces the complexity of hardware and microcontroller rmware implementations.

After the rst version of Serpent was published, some people commented that the key schedule seemed overdesigned. On reflection we agreed; it was particularly heavy for hardware implementation. Much of the complexity came from using the S-boxes to operate on distant rather than consecutive words of the prekey, in order to `minimize the key leakage in the event of a di erential attack

22

on the last few rounds of the cipher', as we put it in [10]. But given the enormous safety margins against di erential attack provided by the new S-boxes, we decided that it was safe to discard this feature. Using consecutive inputs to the key schedule S-boxes means that round keys can be computed `on the fly' in hardware without any signi cant memory overhead. This further reduces the gate complexity of hardware implementations.

Finally, we considered making available cognate algorithms with the same structure as Serpent but with block sizes of (say) 64, 256 and 512 bits. In the end we decided not include these in our submission for a number of reasons, of which by far the most important was that we used the available time to concentrate on the main algorithm. We did not have the resources to test variants with other block lengths with the thoroughness that would have been appropriate. We do not however foresee any great di culty in developing such variants should they be required at a later date.

23