[107604] in Cypherpunks
No subject found in mail header
daemon@ATHENA.MIT.EDU (Mixmaster)
Tue Jan 19 13:14:31 1999
Date: Tue, 19 Jan 1999 09:16:12 -0800 (PST)
From: Mixmaster <mixmaster@remail.obscura.com>
To: cypherpunks@toad.com
Reply-To: Mixmaster <mixmaster@remail.obscura.com>
/*********** INTRO
Feistel Education/Research Module
Topics: cryptography, block cipher,
digital design, verilog, logic synthesis,
CSEE education
16 Jan 99
Here are several tools for the investigator to
learn about block ciphers. Included is full source code
for a synthesiable Verilog model of a Feistel cipher
and the equivalent in C. We provide pointers to the
free C compiler and Verilog simulator used to develop the tools.
Playing with runnable source is a very efficient way of learning.
Verilog
We provide SimpleFeistel.v and test_SimpleFeistel.v,
which are Verilog models of a simple Feistel block cipher
and its testbench.
Using the Veriwell simulator, load the Project "SimpleF.PRJ"
Then run the project. Statements in the code display text documenting
the progress of the computation. You can also load a "Waveform"
file generated by the simulation and view simulated multitrace
oscilloscope ("logic analyzer") waveforms.
C
We provide Feistc.c, which is a C implementation of the
simple Feistel cipher used in our example. This is used
as a reference to check the Verilog. For instance, the
values used in each round are printed.
......
Appendix:
Encryption using a block cipher in the style of Horst Feistel:
DataIn = Left, Right
for ( round = 0; round < NROUNDS * 2; round++ ) {
Temp=Left;
Left = F(Left) ^ Right;
Right = Left;
}
DataOut = Right, Left;
This has the nice properties that:
1. the data is used to encrypt the data (one half hides the other each half-round)
2. the function F need not be invertible (e.g., random-like substitutions of Blowfish)
3. the function F is typically key-dependent
4. additional key-dependent operations may be introduced (e.g., round-dependent
permutation of Right half when P-table entry is xored)
5. this can be strengthened with the DESX construction,
where two extra 64-bit keys are xored with the input and output
(e.g., the pre- and post- "whitening" steps of Blowfish
6. decryption is performed in the same software or hardware used for encryption
by stepping through the rounds in reverse order
.......
Note: this file contains a verilog testbench for itself and an equivalent
program in C, included as comments.
.......
Enjoy.
*****************/
/************* SPLITTING THIS FILE
This distribution-file contains:
sfeistel.v simple Feistel cipher in Verilog
test_sfeistel.v testbench for sfeistel.v
feistc.c self-contained C program to implement, test algorithm
The last two files are included as *comments* inside this .v file.
Inside the last two files, there are block comments delimited with
STARTBLOCKCOMMENT and ENDBLOCKCOMMENT. After you cut test_sfeistel.v and
feistc.c and paste them into files of those names, you replace those
delimiters with the slash-asterisks you see delimiting this comment.
(The verilog simulator complains about nested block comments..)
**************/
/*
SimpleFeistel 16 Jan 99
This is a synthesizable Verilog implementation of
a two-full-round (4 iteration) 64-bit Feistel block cipher.
The round function F() is addition (mod 2^32) with the raw key words.
The algorithm in C:
unsigned int F( unsigned int K, unsigned int Left )
{return K+Left;
}
crypt(unsigned int * Key, unsigned int *Datahi, unsigned int *Datalo,
int Encr)
{
unsigned int Temp, Fval, Left, Right;
int first, last, delta, round;
Left = *Datahi; Right = *Datalo;
if (Encr) {first=0; last=NROUNDS<<1; delta= 1; }
else {first=(NROUNDS<<1) -1; last= -1; delta= -1; }
for (round=first; round != last ; round=round+ delta) {
printf("\tround %d key %x %x %x\n", round, Key[round], Left, Right);
Temp = Left; // Feistel construction in RTL-friendly C
Fval = F( Key[round], Left );
Left = Fval ^ Right;
Right = Temp;
}
*Datahi = Right;
*Datalo = Left; // note swap
}
A complete implementation in C of this algorithm including a testbench is given at the
end of this file.
Translating for Synthesizable Verilog
"In Verilog, everything happens all at once, all the time, unless you stop it."
"Verilog is like microcoding and building something at the same time"
Some choices. First, we assign the leftmost bit as the most significant.
We use the positive edge of a clock and we include an asynchronous reset.
All outputs are driven by registers. We use a 10 unit clock period.
Instead of using pointers to the input and output variables, we provide a 64 bit
input port and a 64 bit output port. We also provide individual
"Encr", "Decr" control inputs, which are active high.
We also provide a "Loadkey" control input which specifies that the first half of the
keying information is available on the 64 bit input, and the second half will
be available on the next clock. While we could have provided a 128 lines for this,
we choose in this design to time-multiplex the Din path. This would let us
use a smaller (cheaper) pin-count package.
Permutations (such as the final swap) are cheap since they are implemented by crossing wires.
We can perform various operations in parallel. For instance, we copy Left
into Temp at the same time as we compute the Fval from Left. Note that in Verilog,
<= is parallel assignment: A <= B; C <= A; means that C gets A's original value,
not B's. On the next clock edge, A will store a copy of B.
When Encr is asserted, the 64 bit plaintext must be present on Din.
N clocks later the ciphertext is present on Dout. Decryption works
similarly. (Handily, for a Feistel cipher like this, you decrypt by
simply reversing the subkey ordering.)
Security Notes
This cipher is not secure. There is no pre or post whitening; no substitution boxes;
no key expansion; too few rounds; and a very lame F(). For research purposes only.
Not for human or diagnostic use. Consult your local cryptographer if symptoms persist.
Implementation Notes
This implementation is too register hungry, which simplifies and speeds the design
but is expensive to scale. Using RAM blocks is preferable. Also not demonstrated:
using ROMs to simplify and speed computations. Handshaking. Preventing use before
loading a key.
What Next
Feed the Verilog source to an FPGA synthesis tool. Feed the resulting netlist
to your FPGA-specific place-and-route tool. Configure your FPGA, debug, verify.
Win32 Tools
This model and its testbench are small enough to run under Wellspring's "Veriwell"
Verilog simulator demo license. Ie, you can run this Verilog model, learn about Feistel
algorithms and their implementations, for free.
There is an accompanying C implementation, "SFeistelc.c" which was used to
check this verilog. That (trivial) C code compiles as a console app under the
lcc-win32 C compiler, which is free, and lightweight. Good for education. Think
of the children.
The <Hubbell?> online tutorial is great for learning Verilog.
Exercises
Study the C source. Diagram the dataflow during one computation.
Work an example by hand. Decrypt it. The first key you try can be
the all-zeroes key.
Study the Verilog tutorial, then study the Verilog source. Try
modifying the algorithm. Unless you are a mathematician with experience
finding weaknesses in others' codes, you shouldn't think of publishing
your own. See the PGP manual for this.
Major project: add a "key schedule", ie, expand the 128-bit user-supplied
key into more key material, e.g., to permit more iterations. Blowfish
is excellent in having a large key setup time.
Study Questions
Implementation:
How can this circuit be sped up? At what cost?
How could you embed a back door?
How could you make the circuit resistant to probing, power analysis, etc?
How would you make it (or a system containing them) more reliable,
e.g., tolerant to soft failures in a high radiation environment?
How many of these could you fit on the head of a pin?
Algorithm
Try to attack the cipher. How can the algorithm be made more resistant to this attack?
Compare this to real Feistel ciphers, e.g., Blowfish, DES, etc. How do they differ?
What was the author trying to do with each step? Why?
Note that practical cipher design is a matter of efficiency (in some specified implementation
technology) as well as security. Err on the side you feel comfortable on.
Sample Verilog Simulator Output:
Highest level modules:
test_SimpleFeistel
Resetting
Resetting
Setting key to all zero key..
