Cryptography-Digest Digest #920, Volume #8 Sun, 17 Jan 99 13:13:01 EST
Contents:
Re: read and pass please!!! ("Jay")
Re: Too simple to be safe ("Kazak, Boris")
Trying to find simple, yet effective implementation of crypto... ("Tim Mavers")
Feistel network ([EMAIL PROTECTED])
----------------------------------------------------------------------------
From: "Jay" <[EMAIL PROTECTED]>
Subject: Re: read and pass please!!!
Date: Sun, 17 Jan 1999 08:35:56 -0500
PLEASE DO NOT DO THIS! IT IS A HOAX
This message has periodically been sent again and again by well meaning
people, but it just clutters up mail boxes. The doctor mentioned had to
change his phone number. The American Cancer Society is NOT involved in any
such program.
There are others like this. Before you forward anything like this please
check:
http://www.hoaxkill.com/
http://kumite.com/myths/
http://www.urbanlegends.com
http://www.snopes.com/
Jay
Angel wrote in message <[EMAIL PROTECTED]>...
>
>Dear All,
>
>I just received this mail from a friend of mine in my college. Please
>respond to it. It will just mean employing a little bit of time and
>won't cost you a penny. All it needs is the heart for you to send
>this mail.
>
>PLEASE pass this mail on to everybody you know. It is the request
>of a little girl who will soon leave this world as she has been a
>victim of the terrible disease called CANCER.
[...]
>this to as many people as possible, you can give her and her family a
>little hope, because with every name that this is sent to, The
>American Cancer Society will donate 3 cents per name to her treatment
>and recovery plan. One guy sent this to 500
>people
------------------------------
From: "Kazak, Boris" <[EMAIL PROTECTED]>
Subject: Re: Too simple to be safe
Date: Sun, 17 Jan 1999 10:53:54 -0500
Reply-To: [EMAIL PROTECTED]
Paul Rubin wrote:
> (snip)
> How did you generate
> the 150 kbyte file? For example if it came from a 16-bit rand()
> generator, it has almost no real entropy and so it is useless.
> There are a lot of opportunities to mess up.
==================
My randomizing procedure is inspired by the convolution
algorithm, which is very common in digital filtering studies.
Essentially the convolution is described by the following
formula, sorry, it is not easy to reproduce it in the ASCII text file.
If K[n] is some random byte sequence and G[i] is some file
( of unknown origin, it can be any .BMP or .WAV file):
*********************************************************
n=N
CONV[m] = SUM {G[n+m]*K[n]} ;
n=1
where N is the number of points in K[n]
*********************************************************
Obviously, the number of points in G[i] must be big enough to
allow this procedure. The random sequence K[n] can be, for example,
the first 64 bytes of PI, multiplication is unsigned Mod 255, all
eventual carries and overflows are disregarded (anyway, this is meant
to be a one-way procedure).
>
> >I was not going for "fancy", this is just practical.
> >And this scheme seems to work with any block cipher, regardless...
> >Additionally, we use KOI-8 encoding for Russian plaintext, this
> >hopefully will make the attacks a little more difficult, if they
> >will use the English-plaintext stereotype :)
>
> I still don't see the need for the 150 kbyte file. It creates a
> vulnerability since if the file is seized, the game is over.
=================
In this you are absolutely correct, but this applies to any key seizure.
=================
> It might even be better to just keep re-using the same key.
> If you don't want to do that, use a single permanent memorized
> key (passphrase) to encrypt a temporary key which is different
> for each message.
>
> Best would be to use a public key method like Diffie-Hellman key
> exchange for every message to create a new secret key, and destroy
> each new secret key after using it once.
========================
Yes, I am thinking on going ahead with this, especially since NSA
declassified its KeyExchangeAlgorithm (along with Skipjack). This
KEA is simple, all the constants are provided in the document, so
one must only install an appropriate BigNumber math package.
Still my 150 Kb random file may serve as a source even in this case.
------------------------------
From: "Tim Mavers" <[EMAIL PROTECTED]>
Subject: Trying to find simple, yet effective implementation of crypto...
Date: Sun, 17 Jan 1999 10:15:35 -0600
I am trying to implement a system where my program can send messages to a
server (also written by me) who then can reply (or send messages) to another
client (my program as well). The messages have to be encrypted. The
messages basically contain a meta-protocol that the programs use to
communicate with each other (the server parses the messages and determines
what to do). Since I don't want anyone knowing my protocol (it's a very
basic one, but if known by all, malicious acts can be done).
Is there a basic crypto principle I can use for this? I have read through
the sci.crypt FAQ and the first couple chapters of Bruce Scheiners book
(very eye-opening), but am still confused about what the best method to
take.
The server must decrypt the packets on-the-fly (very quickly) and then
re-encrypt them to go to someone else.
Each client program doesn't need to have it's own "public" key as everything
can be encrypted the same (is this a flaw?)
Can anyone help?
------------------------------
From: [EMAIL PROTECTED]
Subject: Feistel network
Date: Sun, 17 Jan 1999 17:32:31 GMT
/*********** 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..
.
Encrypting 100000002
SF starting to encrypt 100000002
SF ENCR Round=0 1 2
SF ENCR Round=1 3 1
SF ENCR Round=2 2 3
SF ENCR Round=3 1 2
Dout = 100000003 at 127
.Decrypting 100000003
SF starting to decrypt 100000003
SF DECR Round=3 1 3
SF DECR Round=2 2 1
SF DECR Round=1 3 2
SF DECR Round=0 1 3
Dout = 100000002 at 227
Setting key to real key..
.
Encrypting 100000002
SF starting to encrypt 100000002
SF ENCR Round=0 1 2
SF ENCR Round=1 deadbef2 1
SF ENCR Round=2 a9acb9c1 deadbef2
SF ENCR Round=3 746241da a9acb9c1
Dout = 746241da57a2b608 at 347
.Decrypting 746241da57a2b608
SF starting to decrypt 746241da57a2b608
SF DECR Round=3 746241da 57a2b608
SF DECR Round=2 a9acb9c1 746241da
SF DECR Round=1 deadbef2 a9acb9c1
SF DECR Round=0 1 deadbef2
Dout = 100000002 at 447
.......................................................Sim timed out at 1000
Exiting VeriWell for Win32 at time 1000
0 Errors, 2 Warnings, Memory Used: 67594
Analogies
Design : Fabrication :: Author : Publisher
Design : Fabrication :: Programmer : Disk duplicator
Read Toffler.
"When everything is programming, programmers will do everything"
*/
module SimpleFeistel ( Clk, Reset_n, // system signals
Din, // data and key appear here
Dout, // output here
Encrypt, // control signals
Decrypt,
Loadkey
);
input Clk, Reset_n;
input [63:0] Din;
output [63:0] Dout;
input Encrypt, Decrypt;
input Loadkey;
// These are Major states of the circuit
parameter IDLE=0; // must be 0 since reset to 0
parameter BUSY_KEY=1;
parameter BUSY_ENC=2;
parameter BUSY_DEC=3;
// internal state registers
reg [3:0] State;
reg Phase;
reg [1:0] Round;
reg [31:0] Left, Right, Temp; // working registers
reg [63:0] Dout; // stores output
reg [31:0] Key [0:3];
integer i; // not synthesized
wire [31:0] Fval;
assign Fval = Key[ Round ] + Left ; // this is a continuous assignment
// ie, continuously evaluated
// this defines a standard clocked design..
always @(posedge Clk or negedge Reset_n) begin
if (!Reset_n) begin: resetting
{ Dout, State, Phase, Round } <= 0;
{Temp, Left, Right } <= 0;
for (i=0; i<4; i=i+1) begin Key[i] =0; end
$display("Resetting");
end // resetting
else begin
case (State)
IDLE: begin
case ( { Encrypt, Decrypt, Loadkey } )
3'b 100: begin: start_encr
State <=
BUSY_ENC;
{Left,Right} <=
Din;
Round <=0;
Phase <=0;
$display("\t SF
starting to encrypt %0x", Din);
end
3'b 010: begin: start_decr
State <=
BUSY_DEC;
{Left,Right} <=
Din;
Round <=3;
Phase <=0;
$display("\t SF
starting to decrypt %0x", Din);
end
3'b 001: begin: start_loading_key
State <=
BUSY_KEY;
Key[0] <= Din
[63:32];
Key[1] <= Din
[31:0];
end
default: begin: idling
$write(".");
end
endcase // start command
end // idle
BUSY_KEY: begin
State <= IDLE; // return to IDLING
{ Key[2], Key[3] } <= Din; // save
rest of key
end
BUSY_ENC: begin
Phase <= Phase +1;
case (Phase)
0: begin Temp <= Left;
Left <= Fval ^
Right;
$display("\t SF
ENCR Round=%0d %0x %0x", Round, Left, Right);
end
1: begin
if ( Round == 3 ) begin
Dout <=
{Temp , Left}; // note swap
State
<= IDLE;
//
$strobe("done encr %0d %0x", $time, Dout);
end
else begin
Round <= Round
+1;
Right <= Temp;
end
end
endcase // Phase
end
BUSY_DEC: begin
Phase <= Phase +1;
case (Phase)
0: begin Temp <= Left;
Left <= Fval ^
Right;
$display("\t SF
DECR Round=%0d %0x %0x", Round, Left, Right);
end
1: begin
if (Round== 0) begin
Dout <=
{Temp , Left}; // note swap
State
<= IDLE;
//
$strobe("done decr %0d %0x", $time, Dout);
end
else begin
Round <= Round -
1;
Right <= Temp;
end
end
endcase // Phase
end
endcase // State
end // else
end // always
endmodule
/*********** START OF TEST BENCH FOR SIMPLEFEISTEL.v .... cut here....
STARTBLOCKCOMMENT
test_sfeistel.v
This is a testbench for the SimpleFeistel module.
The first part was generated from the SF module spec,
driving its "input"s with registers, and connecting
wires to its "output"s.
This testbench also generates a period=10 clock, and drives signal
lines with test vectors.
Note that since this testbench is not synthesized, we can
use # delays to wait a clock, and we can use tasks to
structure the testbench for convenience.
Timing:
Loadkey occupies 2 clocks.
Encrypt and decrypt occupy 10 clocks.
Sample output:
Resetting
Resetting
Setting key to all zero key..
.
Encrypting 100000002
Dout = 100000003 at 127
.Decrypting 100000003
Dout = 100000002 at 227
Setting key to all zero key..
.
Encrypting 100000002
Dout = 746241da57a2b608 at 347
.Decrypting 746241da57a2b608
Dout = 100000002 at 447
.......................................................Sim timed out at 1000
ENDBLOCKCOMMENT
module test_SimpleFeistel;
reg Clk, Reset_n;
reg [63:0] Din;
wire [63:0] Dout;
reg Encrypt, Decrypt;
reg Loadkey;
SimpleFeistel dut( Clk, Reset_n, // system signals
Din, // data and key appear here
Dout, // output here
Encrypt, // control signals
Decrypt,
Loadkey
);
initial begin
$vw_dumpvars(); // Veriwell dump of variables
#1000 $display("Sim timed out at %0d",$time);
$finish;
end
always @(Clk) #5 Clk <= !Clk; // generate a period 10 clock
initial begin
{ Clk, Din, Encrypt, Decrypt, Loadkey} <= 0;
#1 Reset_n <=1;
#1 Reset_n <=0;
#5 Reset_n <=1;
$display("Setting key to all zero key..");
#10 Loadkey <= 1;
Din <= 64'h 0; // set first part of key
#10 Loadkey <=0; // shut off Loadkey signal
Din <= 64'h 0; // set rest of key
LOOPBACKTEST;
$display("Setting key to real key..");
#10 Loadkey <= 1;
Din <= 64'h DEADBEEFCAFEFACE; // set part of key
#10 Loadkey <=0;
Din <= 64'h 0123456789ABCDEF;
// set rest of key
LOOPBACKTEST;
end // init
task LOOPBACKTEST;
begin
$display("\n");
#10 Din <= 64'h 0000000100000002;
Encrypt <=1;
$strobe("Encrypting %0x", Din);
#10 Encrypt <=0;
#80 $display("Dout = %0x at %0d",Dout, $time);
#10 Din <= Dout; // 64'h 0000000100000002;
Decrypt <=1;
$strobe("Decrypting %0x", Din);
#10 Decrypt <=0;
#80 $display("Dout = %0x at %0d",Dout, $time);
end
endtask
endmodule
**************** END OF TEST_SFEISTEL.V .... cut here.... ********/
/*********** FEISTC.C FOLLOWS .... cut here....
STARTBLOCKCOMMENT
This program implements a lame 64-bit block cipher of
the Feistel type. The cipher has 4 iterations (two full
rounds) and uses addition mod 2^32 as its F() function.
No pre- or post- whitening, round-dependent permutations,
large S-boxes, etc. found in serious ciphers are absent.
This exists to provide Known Good vectors for a Verilog
port of the same algorithm. This is written in
"HDL-friendly C", where the coding style makes explicit
certain hardware-friendly ways of doing things that
regular C has better ways of doing.
This was developed with the free lcc-win32 compiler.
ENDBLOCKCOMMENT
#define NROUNDS 2 // two F() calls per "round"
unsigned int F( unsigned int K, unsigned int Left )
{return K+Left; // not particularly secure..
}
// inputs: ptr to array of int32 Key data
// 64 bit input block as 2 int32s
// encryption/decryption command, encr=1 decr=0
// outputs: input block is overwritten
crypt(unsigned int * Key, unsigned int *Datahi, unsigned int *Datalo,
int Encr)
{
unsigned int Temp, Newval, 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
Newval= F(Key[round], Left);
Left=Newval ^ Right;
Right=Temp;
}
*Datahi = Right;
*Datalo = Left; // note swap
}
int Key[NROUNDS<<1];
int Upper, Lower;
void loopbacktest()
{
printf("Encrypt..\n");
printf("Input: %0x %0x\n", Upper, Lower);
crypt(Key, &Upper, &Lower, 1);
printf("Output: %0x %0x\n", Upper, Lower);
printf("\nNow decrypt..\n");
crypt(Key, &Upper, &Lower, 0);
printf("Output: %0x %0x\n\n", Upper, Lower);
}
// TEST MAIN()
main()
{
int i;
printf("feistc Nrounds=%d\n", NROUNDS);
Upper=1; Lower=2; // plaintext
printf("Setting all zeroes key\n");
for (i=0; i<NROUNDS<<1; i++) {Key[i]=0;} // set key
loopbacktest();
printf("\nSetting real key\n");
Key[0]= 0xDEADBEEF;
Key[1]= 0xCAFEFACE;
Key[2]= 0x01234567;
Key[3]= 0x89ABCDEF;
loopbacktest();
printf("Done.\n");
}
************ END OF FEISTC.C ********/
/*
Colophon
PC Tools
LCC-Win32 C Compiler
by C Fraser, D Hanson
Veriwell 2.1 Verilog Simulator & Waveform Viewer
www.wellspring.com
Developed from scratch on personal equiptment, time.
Refs
Feistel patents
Schneier, Applied Crypto; www.counterpane.com
Thomas & Moorby, Verilog
K & R, C
Hubbell Verilog Tutorial
Rand, Fountainhead
Phil Zimmerman, PGP 262 User's Manual
*/
============= Posted via Deja News, The Discussion Network ============
http://www.dejanews.com/ Search, Read, Discuss, or Start Your Own
------------------------------
** FOR YOUR REFERENCE **
The service address, to which questions about the list itself and requests
to be added to or deleted from it should be directed, is:
Internet: [EMAIL PROTECTED]
You can send mail to the entire list (and sci.crypt) via:
Internet: [EMAIL PROTECTED]
End of Cryptography-Digest Digest
******************************
