Subversion Repositories twofish

TWOFISH MANUAL

(c) 2006 Spyros Ninos

This document is under the GPL. See file COPYING for licence details.

1. Introduction

2. Crypto primitives usage

3. Testbenches

4. Misc + Tips

1. INTRODUCTION

===============

        Twofish is a 128bit-block symmetric cipher, finalist candidate for the AES contest.

It supports keys of 128, 192, 256 and all the sizes below 256 bits (with padding). This

implementation accepts keys of 128, 192 and 256 bits. If you want a different size then

you'll have to create the padder yourself. The implementation was written in a VHDL 87

and 93 mixed versions. Just to be sure, use the 93 version in compilation. The naming

convention for the components is kept as simple but self-explanatory as I could. I had

in mind that it would be possible to use two or three ciphers in the same design, so

names are such that there would be no name-conflict (I hope...). For every key-depended

component the respective key size was used in the name to indicate the component's

target (i.e twofish_S128 is for 128 bit key). The cipher components are pure

combinational circuits. This decision was based upon the assumption of portability.

Since no memory is used, it can be implemented in any programmable device. Also, maximum

flexibility was intended by dividing the cipher in key-parts. By doing this, you

have the choice to implement the cipher as a rolled out, iterative, pipelined or any

other architecture you may like to build.

2. CRYPTO PRIMITIVES USAGE

==========================

        The twofish.vhd file is divided in four parts. Firstly, there's the part where all

the key-independent components are found. The next three parts concern the components

that depend on the key - 128, 192 and 256 bits respectively.

In the file you'll find the below main components:

        1) twofish_data_input

        2) twofish_data_output

        3) twofish_S128

        4) twofish_keysched128

        5) twofish_whit_keysched128

        6) twofish_encryption_round128

        7) twofish_decryption_round128

        8) twofish_S192

        9) twofish_keysched192

        10) twofish_whit_keysched192

        11) twofish_encryption_round192

        12) twofish_decryption_round192

        13) twofish_S256

        14) twofish_keysched256

        15) twofish_whit_keysched256

        16) twofish_encryption_round256

        17) twofish_decryption_round256

You'll also find all the other components that the above depend on, but they are not

important in building the cipher - except perhaps if you want to study the structure

of this implementation and/or modify it. A short description of them follows:

1) The first component is the TWOFISH_DATA_INPUT, which is a simple tranformation of the

input data from the way we provide it (which is big endian) to little endian convention,

as required by the twofish specification. It must be used as an interface between the

input data provided to the circuit and the rest of the cipher. An alternative would be

to extract the code from it and integrate it to another component. Note that since the

data block size of the cipher is always 128 bits, this component is supposed to be used

with the components of all the key-sizes. The interface of the component is as follows:

        entity twofish_data_input is

        port    (

                        in_tdi  : in std_logic_vector(127 downto 0);

                        out_tdi : out std_logic_vector(127 downto 0)

                        );

        end twofish_data_input;

It is quite simple; in_tdi is the data input as we provide it and out_tdi is the

transformed input data. (tdi comes from the Twofish Data Input)

2) The component TWOFISH_DATA_OUTPUT makes the reverse procedure of the twofish_data_input.

It takes the little endian convention cipher result and transforms it to the big endian

one, as the specification requires. This component too is supposed to be used with the

components of all the key-sizes. The interface is as follows:

        entity twofish_data_output is

        port    (

                        in_tdo  : in std_logic_vector(127 downto 0);

                        out_tdo : out std_logic_vector(127 downto 0)

                        );

        end twofish_data_output;

in_tdo accepts the ciphertext as we take it from the last round and out_tdo is the

tranformed ciphertext. (tdo comes from the Twofish Data Output)

3) The TWOFISH_S128 is a component that takes the key of 128 bits and produces the S0

and S1 for the f function. The interface is as follows:

        entity twofish_S128 is

        port    (

                        in_key_ts128            : in std_logic_vector(127 downto 0);

                        out_Sfirst_ts128,

                        out_Ssecond_ts128       : out std_logic_vector(31 downto 0)

                        );

        end twofish_S128;

Here, in_key_ts128 is the key that we provide. Note that there is no component that

transforms the key to the form that the twofish specification requires; rather the

tranformation takes place within the twofish_S128 component. Here, there is the

assumption/association that Sfirst refers to S0 and Ssecond refers to S1. There is

no need to remember the association, since throughout the design, the same rule

is followed, so the only thing you have to do it to connect the pins with the

same name. This component can be used only when you implement a 128 bit key size

design. (ts128 comes from Twofish_S128)

4) The TWOFISH_KEYSCHED128 component is the key scheduler of the twofish cipher,

for 128 bit keys. It's interface is as follows:

        entity twofish_keysched128 is

        port    (

                        odd_in_tk128,

                        even_in_tk128           : in std_logic_vector(7 downto 0);

                        in_key_tk128            : in std_logic_vector(127 downto 0);

                        out_key_up_tk128,

                        out_key_down_tk128                      : out std_logic_vector(31 downto 0)

                        );

        end twofish_keysched128;

odd_in_tk128 and even_in_tk128 are the numbers of the round 2i and 2i+1, as described

in the specification. Clearly, 2i relates to the even_in_tk128 and 2i+1 relates to

the odd_in_tk128. in_key_tk128 is where the key goes. The key must be supplied to the

components without any endian-transformation; the tranformation takes place in the

component, as in twofish_S128. out_key_up_tk128 and out_key_down_tk128 are the two

keys produced from the scheduler. The association is that as we look the twofish

diagram provided in the specification page 11 (figure 3), the upper key is what we

get from out_key_up_tk128 and the down key is what we get from out_key_down_tk128.

As before, you don't have to remember the association, names are used the same throughout

the whole design. This component too, can be used only when you implement a 128 bit key

size design. (tk128 comes from Twofish_Keysched128).

IMPORTANT NOTICE: This component can be used in two ways: in combination with

twofish_whit_keysched128 (see below) or as a standalone component. In the first

case, whitening keys are produced by twofish_whit_keysched128; so even_in_tk128 and

odd_in_tk128 must start from 8,9 respectively and above. Or if you use it standalone

then you can start from 0 and above.

5) The TWOFISH_WHIT_KEYSCHED128 produces the whitening keys K0..K7. The interface

is as follows:

        entity twofish_whit_keysched128 is

        port    (

                        in_key_twk128           : in std_logic_vector(127 downto 0);

                        out_K0_twk128,

                        out_K1_twk128,

                        out_K2_twk128,

                        out_K3_twk128,

                        out_K4_twk128,

                        out_K5_twk128,

                        out_K6_twk128,

                        out_K7_twk128                   : out std_logic_vector(31 downto 0)

                        );

        end twofish_whit_keysched128;

in_key_twk128 is where the key is connected. As above, no big-little endian tranformation

must take place. It is performed within the component. The eight outputs produce the

keys. This component too can be used only when you implement a 128 bit key size design.

(twk128 comes from Twofish_Whit_Keysched128).

IMPORTANT NOTICE: If this component is to be used as a combination with twofish_keysched128

care should be taken when supplying numbers to the latter. Read the notice of the

twofish_keysched128.

6) The TWOFISH_ENCRYPTION_ROUND128 is the component that implements one round of encryption.

The interface is as follows:

        entity twofish_encryption_round128 is

        port    (

                        in1_ter128,

                        in2_ter128,

                        in3_ter128,

                        in4_ter128,

                        in_Sfirst_ter128,

                        in_Ssecond_ter128,

                        in_key_up_ter128,

                        in_key_down_ter128              : in std_logic_vector(31 downto 0);

                        out1_ter128,

                        out2_ter128,

                        out3_ter128,

                        out4_ter128                     : out std_logic_vector(31 downto 0)

                        );

        end twofish_encryption_round128;

in1_ter128, in1_ter128, in1_ter128, in1_ter128 are the four 32 bit inputs to the cipher

round. in_Sfirst_ter128, in_Ssecond_ter128 are the two S needed for the g functions,

in_key_up_ter128 and in_key_down_ter128 are the two round keys. Note that up and down

names are given to keys according to the diagram given in Twofish spec. You don't need

to worry about it, keys follow the same naming convention throughout the whole design.

Finally, out1_ter128, out1_ter228, out3_ter128 and out4_ter128 are the 32 bit outputs

of the encryption round (ter128 comes from Twofish_Encryption_Round128).

IMPORTANT NOTICE: the output swapping is taking place IN the component. YOU HAVE TO undo

the last swap after the 16th round.

7) The TWOFISH_DECRYPTION_ROUND128 is the component tha implements one round of decryption.

The interface is as follows:

        entity twofish_decryption_round128 is

        port    (

                        in1_tdr128,

                        in2_tdr128,

                        in3_tdr128,

                        in4_tdr128,

                        in_Sfirst_tdr128,

                        in_Ssecond_tdr128,

                        in_key_up_tdr128,

                        in_key_down_tdr128      : in std_logic_vector(31 downto 0);

                        out1_tdr128,

                        out2_tdr128,

                        out3_tdr128,

                        out4_tdr128                     : out std_logic_vector(31 downto 0)

                        );

        end twofish_decryption_round128;

As in twofish_encryption_round128 component, the ports are quite self-explanatory.

(tdr128 comes from Twofish_Decryption_Round128).

IMPORTANT NOTICE: as in twofish_encryption_round128, inside the component the output

swapping is taking place. YOU HAVE TO undo the last swap after the 16th round.

Components

        8) twofish_S192

        9) twofish_keysched192

        10) twofish_whit_keysched192

        11) twofish_encryption_round192

        12) twofish_decryption_round192

        13) twofish_S256

        14) twofish_keysched256

        15) twofish_whit_keysched256

        16) twofish_encryption_round256

        17) twofish_decryption_round256

work exactly as their 128 bit counterparts. The only difference is the third S that

is provided by twofish_S192 and needed by some of the rest of them, and the fourth

S that is provided by twofish_S256. I.e:

        entity twofish_S192 is

        port    (

                        in_key_ts192            : in std_logic_vector(191 downto 0);

                        out_Sfirst_ts192,

                        out_Ssecond_ts192,

                        out_Sthird_ts192                        : out std_logic_vector(31 downto 0)

                        );

        end twofish_S192;

which provide a third S that is used in twofish encryption and decryption rounds for

192 bits and the fourth S that is provided from the twofish_S256 is used by the

twofish encryption and decryption rounds for 256 bits.

Every IMPORTANT NOTICE that exist for the 128 bit components, are valid for

these components too.

3. TESTBENCHES

==============

Testbenches for the cipher are provided for Tables, Variable key, Variable text,

ECB/CBC Monte Carlo encryption and decryption tests. Every testbench comes with

it's respective testvector file. The testvector file is transformed into a form

that it's easier to be manipulated, than in the original form supplied by the

cipher designer(s).

Every testbench produces a file with the results, that can be cross-checked

with the testvector file of input - just to be certain that results are as

expected (usually with "diff").

Along with the transformed testvector files, the orignal testvector files - which

are provided by the cipher designer(s) - are given. That way, you can check the

originality of the transformed testvector files if you want to.

Finally, some secondary circuits are provided for the testbenches to work. These

are a 128 bit register, a mux and demux for 128 bit input(s)/output(s).

4. MISC + TIPS

==============

You must pay attention in the whitening steps. None of the components actually

implements the input or output whitening steps. You only have the component

that produces the whitening keys.

Each cipher implementation was designed so as to demand as few components as

possible. That way, there would be no difficulty in using them and designing

the algo in its total. The problem is that the Reed Solomon used to produce

the S keys is in a rolled-out form, because I chose not to use any form of

memory. So, if you want to implement more that one key size cipher in the

same circuit/FPGA, the design size grows very much, and I doubt if it will

fit in a signle FPGA. If you decide that you need more that one cipher

instantiation, then you'll have to tweak the design of the Reed Solomon.

One example follows:

Current implementaion is that the reed solomon components are specifically

designed for the key size of the cipher, i.e for 128 bits key:

        entity reed_solomon128 is

        port    (

                        in_rs128                        : in std_logic_vector(127 downto 0);

                        out_Sfirst_rs128,

                        out_Ssecond_rs128               : out std_logic_vector(31 downto 0)

                        );

        end reed_solomon128;

and for 192 bits key:

        entity reed_solomon192 is

        port    (

                        in_rs192                        : in std_logic_vector(191 downto 0);

                        out_Sfirst_rs192,

                        out_Ssecond_rs192,

                        out_Sthird_rs192                : out std_logic_vector(31 downto 0)

                        );

        end reed_solomon192;

What is happening, is that each component takes the input key, and performs the

multiplications in rolled-out form of every 64 bit input. In other terms, in_rs128

is split up in two 64 bit chunks, and each one is driven in it's respective

multipliers. The result of the first multipliers is driven to out_Sfirst, the result

of the second to out_Ssecond. Respectively for reed_solomon192 the result of the

third multiplier is driven to out_Sthird and for reed_solomon256 the result of the

fourth multiplier is driven to out_Sfourth. Every multiplication needs it's

multipliers (note that it is not a single mul, but a group of them because its

a matrix multiplication) so in the first component we need two groups of muls,

in the second component three groups of them and in the third we need four.

If you had to implement cipher with 128 and 192 sizes for example, you'd have to

implement both reed solomon components which total in 5 groups of multipliers.

One solution would be to create a reed solomon that would take a single 64 bit

input and procude a single 32 bit output. For example:

        entity reed_solomon is

        port    (

                        in_rs                   : in std_logic_vector(63 downto 0);

                        out_S_rs                : out std_logic_vector(31 downto 0)

                        );

        end reed_solomon;

Then you would divide the key into 64 bit chunks (128 bit in 2 chunks, 192 bit

in 3 chunks and 256 bits in 4 chunks) and provide them to the component

sequentially. The results of the reed_solomon could be stored in a sort of RAM.

That way you may slow down the process but you get to implement only one group

of multipliers and you gain a lot in space.

The same goes for the whitening keys components. In the whitening components

the function h is impemented 8 times (2 h functions for each pair of keys,

for the first 8 keys - K0..7). You could follow the above example and implement

a component that accepts a 64 bit input (key chunk, every M is 32 bit, you need

2 Ms for every h function) and produce a single 32 bit key. Thus,  you can

produce every key sequentially and store it in a RAM for example.

If you want some implementation examples, you'll have to read the testbenches.

The cipher is implemented in iterated mode, but you'll get a clear picture of how

to connect the components.