Chaffing and Winnowing

New Message Reply About this list Date view Thread view Subject view Author view

Mark Rosen (mrosen@peganet.com)
Thu, 7 May 1998 21:23:34 -0400

    I decided to implement Rivest's chaffing and winnowing algorithm in my
commerical encryption software, Kremlin. Only the chaffing and winnowing
algorithm is used, so this version of Kremlin should be freely exportable
from the United States. I am hoping that the actual implementation of the
chaffing and winnowing algorithm in commercial encryption software will
force the government to make a decision one way or the other: either
completely outlaw encryption (including hash functions), or do away with the
export limitations.
    First and foremost, the executable file:
n. Kremlin uses only
symmetric key crypto, and is geared toward file encryption on a single PC,
but it includes an encrypted word processor that encrypts documents and
UUencodes the output (you can e-mail from it also). Let's get some
encrypted, cross-border communication going!
    Of course, the chaffing and winnowing algorithm (and my implementation
of it) are horribly inefficient. A 100 byte text file encrypts to about 65k!
Kremlin does aggressive compression on the data before encryption, but the
messages are still very large.
    There are also many security improvements that can be made. I have
pasted the appropriate source code below, but here are my observations: The
main point of attack is the RNG. I use a simple LFSR. The first thing to do
is to make a better RNG. The message is divided up into 1 byte packets. As
per Rivest's document, an authentication key is computed using the hash
(SHA1) of the packet and an authentication key. I don't use a serial number
because the packets are stored in order (the architecture of my encryption
library prevents me from storing the packets in random order, though this is
certainly a possible improvement). For each wheat packet, there are 20 chaff
packets generated, with the wheat inserted randomly in the chaff. One
possible attack on the chaffing and winnowing algorithm is a simple "look at
the data attack". For example, if you are transmitting a text file, then you
can eliminate messages with non-alphanumeric (and punctuation) characters.
You could probably get a pretty good idea of the contents of the message
this way. Because of the pre-encryption compression, this "attack" is not
possible. Although the compression functions like a package transform (a
poor and not cryptographic package transform, though), I am planning on
implementing the package transform tomorrow (just wanted to get some code
out).
    Kremlin is a commerical product. However, I am not releasing this
version of Kremlin in order to obtain money (the registration stuff is
gone). As I said before, if we can optimize and secure the chaffing and
winnowing algorithm to the point that it would be more difficult to recover
a chaffed encrypted transmission than a 40-bit or 56-bit RC4 transmission
(brute force), then perhaps the Administration will realize that something
will have to be done.
    Unfortunately, for some reason, I ignored the chaffing and winnowing
thing when it first came out, and therefore missed all of the discussion on
CodherPlunks about c&w. And I couldn't find a CodherPlunks archive. So I am
sorry if this message causes some repeats in technical discussion(let me say
that I think the political side of this -- that the export regs. are dumb --
is pretty clear).
    I just read Rivest's paper yesterday. I could find no indication that
the Chaffing and Winnowing algorithms were patented or otherwise protected
in any way (same with the package transform). If I am violating some rule of
academia or something like that by using the chaffing and winnowing
algorithms (and soon the packaging transform), then it is out of ignorance
that I do this, not out of malice.
    Can code that uses the packaging transform be exported from the United
States? The packaging transform does not encrypt, but uses a cryptographic
algorithm. This is starting to push the limits, I think.

    Enough talk. Here's the code. I plan on incorporating your comments (and
my own ideas as far as the packaging transform go) in the program and
releasing updates regularly. Like I said, my goal is to create a workable
method of secure communication that is more secure than the 40-56 bits
currently allowed to be exported by the Administration.

- Mark Rosen
Mach5 Software
http://www.mach5.com/

/* This is my chaffing and winnowing code. It uses the Kremlin SDK, which
encapsulates, buffer and file encryption, and includes support for encrypted
archives. You can see that the functions call SHA1 functions -- these are
part of the SDK too. If you would like to examine the entire SDK, e-mail me
back and I can give you the code */

//Chaff per wheat
#define CHAFF_WHEAT 20

#define CHAFF_SOURCE_SIZE 1
#define CHAFF_PACKAGED_SIZE (CHAFF_SOURCE_SIZE + 20)

unsigned char *Chaff_passkey;
int Chaff_nLength;
static unsigned char Chaff_hash[20];

void Chaff_Init(const unsigned char *cPasskey,int nLength) {
Chaff_passkey = smalloc(nLength);
Chaff_nLength = nLength;
memcpy(Chaff_passkey,cPasskey,nLength);
}

void Chaff_make_packet(const unsigned char c[CHAFF_SOURCE_SIZE], unsigned
char output[CHAFF_PACKAGED_SIZE], int bad) {
unsigned char r[8];
memcpy(output,c,CHAFF_SOURCE_SIZE);
SHA1Init();
SHA1Update((unsigned char*)Chaff_passkey,Chaff_nLength);
SHA1Update(c,CHAFF_SOURCE_SIZE);
if (bad) {
  memrand(r,8);
  SHA1Update(r,8);
}
SHA1Final(output + CHAFF_SOURCE_SIZE);
}

void Chaff_Encrypt(const unsigned char *source,int len,unsigned char
*output, int *olen) {
int x,y,rp,cur;
char g[CHAFF_SOURCE_SIZE];
//TODO ASSERT(len % CHAFF_SOURCE_SIZE == 0);
cur = 0;
for (x=0;x<len;x += CHAFF_SOURCE_SIZE) {
  rp = SecureRand() % CHAFF_WHEAT; //where to insert the real packet
  for (y=0;y<CHAFF_WHEAT;y++) {
   if (y == rp) {
    Chaff_make_packet(source + x, output+cur, 0);
    cur += CHAFF_PACKAGED_SIZE;
   }
   memrand(g,CHAFF_SOURCE_SIZE); //TODO: better rand -- don't show source
stream
   Chaff_make_packet(g, output + cur, 1);
   cur += CHAFF_PACKAGED_SIZE;
  }
}
*olen = cur;
}

void Chaff_Decrypt(const unsigned char *source, int len, unsigned char
*output, int *olen) {
int x;
char s[CHAFF_SOURCE_SIZE];
int cur;
//p = len / CHAFF_PACKAGED_SIZE; //TODO: make sure that mod == 0
//TODO: *olen greater= than len (enc and dec)
cur = 0;
for (x=0;x<len;x+=CHAFF_PACKAGED_SIZE) {
  memcpy(s,source + x, CHAFF_SOURCE_SIZE);
  SHA1Init();
  SHA1Update((unsigned char*)Chaff_passkey,Chaff_nLength);
  SHA1Update(s,CHAFF_SOURCE_SIZE);
  SHA1Final(Chaff_hash);
  if (memcmp(source + x + CHAFF_SOURCE_SIZE,Chaff_hash,20) == 0) {
   memcpy(output + cur,s,CHAFF_SOURCE_SIZE);
   cur += CHAFF_SOURCE_SIZE;
  }
}
*olen = cur;
}

void Chaff_Kill() {
sfree(Chaff_passkey);
Chaff_nLength = 0;
}

New Message Reply About this list Date view Thread view Subject view Author view

 
All trademarks and copyrights are the property of their respective owners.

Other Directory Sites: SeekWonder | Directory Owners Forum

The following archive was created by hippie-mail 7.98617-22 on Fri Aug 21 1998 - 17:17:17 ADT