Chaffing and Winnowing -- Part Deux!

Mark Rosen (mrosen@peganet.com)
Tue, 19 May 1998 22:51:35 -0400

• Next message: Greg Noel: "re: question on campus computer security"
• Previous message: David Jablon: "re: question on campus computer security"

    Sorry for taking so long to make the changes to my chaffing and
winnowing software. However, I think I have spent my time well. The
announcement is not appropriate to CodherPlunks, so I didn't post it here, but
it's at the bottom of the message. Basically, the BXA is on the prowl again,
and we may soon have a new case with which to contest the EAR.
    I have modified the chaffing and winnowing code per the suggestions I
received. Source code is below (after the message), but my implementation of
chaffing and winnowing more closely follows Rivest's implementation -- the
message is read in one bit at a time, with that bit either followed or
preceeded by an "chaff" packet. Packets are still 21 bytes long (the 1 bit
is stored as either a 1 or 0, followed by the hash). The hash is computed by
combining the passphrase, a 64-bit IV (stored at the beginning), an implied
serial number (packets are stored in order), and the source bit.
    The weakness is still the RNG, which is a normal LFSR. The RNG produces
a 16 bit value, but I've modified it to use only the lower eight bits (which
should help some). Again, I need to implement the packaging function.
Another idea would be to occasionally generate 2 chaff packets per wheat --
this would require an attacker to search all permutations of the output,
making a brute force attack on order n!, rather than 2^n.
    This version seems much more secure than the original. Would someone
overseas e-mail me an encrypted letter? :-)

    You can get the code from
    http://www.mach5.com/download/k221c_b2.exe
    and read about it at:
    http://www.mach5.com/kremlin/chaff/

    It's more efficient than before, but still pretty bad -- 1k of text
(with pre-encryption compression) goes to 177k of encrypted data!

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

Posted to cryptography@c2.net:
    The BXA is on the prowl again. Charles Booher, who developed his
cryptography application, SecureOffice, in his spare time, has received a
Subopena to appear before the Department of Commerce in late May. Mr. Booher
did not place any restrictions on the export of his software. Anyone,
regardless of their nationality or residence, can currently download
SecureOffice from http://www.filesafety.com/.
    I am writing on behalf of Mr. Booher, who is now working with my
company, Mach5 Software (http://www.mach5.com).
    First, what are your opinions of his case? From what I understand, the
Bernstein case essentially got off on a technicality. Mr. Booher is in
flagrant violation of the export laws; there is no room for such legal
manuvering in this case. I see this as the case that could break open the
crypto floodgates.
    Does anyone from the ACLU subscribe to this list? Mr. Booher is a
professional software programmer, but legal bills can run through the roof.
How would we make a formal request for assistance from the ACLU in this
case?
    Thanks for your help.

(I have received many replies and we are now talking with the president of
the EFF about arranging legal help. And Mr. Booher's subopena has most
likely turned into an indictment).

Source code:

(Again, this uses the Kremlin SDK -- e-mail me if you want to see code for
that too).

#define CHAFF_PACKAGED_SIZE (1 + 20)
#define CHAFF_IV_SIZE (8)

unsigned char *Chaff_passkey;
int Chaff_nLength;
unsigned char Chaff_hash[20];
unsigned char Chaff_IV[CHAFF_IV_SIZE];
unsigned char *Chaff_pBuffer;
unsigned long Chaff_nCur;
unsigned char Chaff_nBit;
unsigned long Chaff_nPacketNum;
unsigned char Chaff_cc;

void Chaff_InitBits(const unsigned char *pBits) {
 Chaff_pBuffer = pBits;
 Chaff_nCur = 0;
 Chaff_nBit = 0;
 Chaff_cc = Chaff_pBuffer[0];
}

unsigned char Chaff_GetBit() {
 char c;
 if (Chaff_nBit >= 8) {
  Chaff_nBit = 0;
  Chaff_nCur++;

  Chaff_cc = Chaff_pBuffer[Chaff_nCur];
 }
 c = Chaff_cc & 0x00000001;
 Chaff_cc >>= 1;
 Chaff_nBit++;
 return c;
}

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

void Chaff_make_packet(const unsigned char c, unsigned char
output[CHAFF_PACKAGED_SIZE], int bad) {
 unsigned char r[8];
 output[0] = c;
 SHA1Init();
 SHA1Update((unsigned char*)Chaff_passkey,Chaff_nLength);
 SHA1Update(&c,1);
 if (bad) {
  memrand(r,8);
  SHA1Update(r,8);
 }
 SHA1Update((unsigned char*)&Chaff_nPacketNum,4);
 SHA1Update(Chaff_IV,CHAFF_IV_SIZE);
 SHA1Final(output + 1);
 Chaff_nPacketNum++;
}

void Chaff_Encrypt(const unsigned char *source,int len,unsigned char
*output, int *olen) {
 unsigned long x,y,cur;
 unsigned char rp,b,c;
 memcpy(output,Chaff_IV,CHAFF_IV_SIZE);
 output += CHAFF_IV_SIZE;
 Chaff_InitBits(source);
 cur = 0;
 for (x=0;x<len * 8;x ++) {
  memrand(&rp,sizeof(rp));
  rp = rp & 0x01; //where to insert the real packet

  memrand(&c,sizeof(c));
  c = c & 0x01;
  for (y=0;y<2;y++) {
   b = rp == y;
   Chaff_make_packet(b ? Chaff_GetBit() : c, output + cur, !b);
   cur += CHAFF_PACKAGED_SIZE;
  }
 }
 *olen = cur + 8;
}

void Chaff_Decrypt(const unsigned char *source, int len, unsigned char
*output, int *olen) {
 int x;
 unsigned char s;
 int cur;
 unsigned char c,nBits;

 nBits = 0;
 c = 0;
 ASSERT((len - 8) % CHAFF_PACKAGED_SIZE == 0);

 memcpy(Chaff_IV,source,CHAFF_IV_SIZE);
 source += CHAFF_IV_SIZE;
 len -= 8;

cur = 0;
 for (x=0;x<len;x+=CHAFF_PACKAGED_SIZE) {
  s = source[x];
  ASSERT((s == 0) || (s == 1));
  SHA1Init();
  SHA1Update((unsigned char*)Chaff_passkey,Chaff_nLength);
  SHA1Update(&s,1);
  SHA1Update((unsigned char*)&Chaff_nPacketNum,4);
  SHA1Update(Chaff_IV,CHAFF_IV_SIZE);
  SHA1Final(Chaff_hash);
  Chaff_nPacketNum++;
  if (memcmp(source + x + 1,Chaff_hash,20) == 0) {
   c += (s << nBits);
   nBits ++;
   if (nBits >= 8) {
    output[cur] = c;
    cur++;
    c = 0;
    nBits = 0;
   }
  }
 }
 *olen = cur;
}

void Chaff_Kill() {
 sfree(Chaff_passkey);
 Chaff_nLength = 0;
 memrand(Chaff_hash,20);
 memrand(Chaff_IV,CHAFF_IV_SIZE);

 memrand(&Chaff_nCur,sizeof(Chaff_nCur));
 memrand(&Chaff_nBit,sizeof(Chaff_nBit));
 memrand(&Chaff_nPacketNum,sizeof(Chaff_nPacketNum));
 memrand(&Chaff_cc,sizeof(Chaff_cc));
}

• Next message: Greg Noel: "re: question on campus computer security"
• Previous message: David Jablon: "re: question on campus computer security"