How does it work ?

Let's say you have a message to transmit

PlainText="hello"

you split it in several parts 'h','e','l','l','o'
then you make packet with these parts :

(1,'h',CHECKSUM('h'+privatekey))
(2,'e',CHECKSUM('e'+privatekey))
(3,'l',CHECKSUM('l'+privatekey))
(4,'l',CHECKSUM('l'+privatekey))
(5,'o',CHECKSUM('o'+privatekey))

You can see that the packet are made of 3 parts :

1. the sequence number.
2. the message.
3. the checksum of the message and a secret key
   (this part will be used for authentication)

then you add chaffs, ie false packets.

(1,'r',CHECKSUM(random))
(1,'f',CHECKSUM(random))
(1,'z',CHECKSUM(random))
(1,'d',CHECKSUM(random))
(1,'t',CHECKSUM(random))
(2,'g',CHECKSUM(random))
(2,'z',CHECKSUM(random))
(2,'l',CHECKSUM(random))
(2,'m',CHECKSUM(random))
(2,'n',CHECKSUM(random))
(3,'r',CHECKSUM(random))
(3,'f',CHECKSUM(random))
(3,'z',CHECKSUM(random))
(3,'d',CHECKSUM(random))
(3,'t',CHECKSUM(random))
(4,'g',CHECKSUM(random))
(4,'h',CHECKSUM(random))
(4,'q',CHECKSUM(random))
(4,'e',CHECKSUM(random))
(4,'f',CHECKSUM(random))
(5,'W',CHECKSUM(random))
(5,'y',CHECKSUM(random))
(5,'z',CHECKSUM(random))
(5,'p',CHECKSUM(random))
(5,'v',CHECKSUM(random))

You send all those packets (after shuffling them)
The receiver who knows the private key check each packet
by calculating the CHECKSUM hash of the second value+the private key
and by compairing with the third value.
Either it's a match and the receiver knows it's a good packet,
and the first value show its position.
Either there's no match and it's a chaff that must be dropped.

Rivest use through his article the terms :

• Chaffing for the encryption process when you add random data.
• Winnowing for the decryption process when you sort out the data (wheat) out of the chaff.

Easy, isn't it ?

Ok may be too easy, probably even your little sister would be able to spot the wheat out of the chaff with example trivial like these.
And in more complex example when your data payload is bigger, it's even easier to distinguish true data (parts of the message) and chaff (random data).
Moreover there are trivial attack which could be lead using already guessed data to lead on further the cryptanalisis of this scheme using probability, dictionnary attack...
That's why RIVEST suggest to use and all-or-nothing encoding on the payload.

Now I hear you asking, why should I use this new scheme ?

• This can't be used for public key exchange (Further more RSA rules in that field)
• There are tons of excellent(faster with better plaintext/ciphertext ratio) RC6,Rijndael,Twofish....

You are right on this 2 point (although I think that wiht few work we could use this scheme with public keys).
However this scheme has several funny advantages :

• You can use it to achieve privacy WITHOUT encryption (usefull in some countries)
• This scheme is especially efficient when a lot of data are multiplexed.
• You could use a really useful feature which I'll call 'fake decryption' (Rivest uses 'denial encryption') to make people believe that they deciphered the text

Let's explain it a little bit more.

Encryption without privacy

The funny thing is that, as data aren't encrypted, this scheme is legal even in country where encryption isn't.
(technically speaking there's only authentication !)
I'd like you to refer to the original paper for a detailed explanation on this.

Multiplexing ready

The big drawback of this scheme is his plaintext/ciphertext (again I must stress that ciphertext isn't the appropriate word here, as there is no ENCRYPTION, I should use encodedtext but this word is never used ;-)
Now imagine several people send messages at the same time on the same canal, each 'wheat' is 'chaff' for the other messages !
The more people are sending messages the less you need random faked data.
will you recognize the easy 3 messages crafted without any random data here :

(1,m,checksum)
(1,f,checksum)
(1,h,checksum)
(2,o,checksum)
(2,o,checksum)
(2,e,checksum)
(3,n,checksum)
(3,l,checksum)
(3,l,lhecksum)
(4,k,ckecksum)
(4,k,checksum)
(4,l,checksum)
(5,s,checksum)
(5,o,checksum)
(5,s,checksum)

Some of you should have guessed 'monks' 'hello' 'folks'.
Now imagine I multiplex 3 or 4 other messages are you confident about your ability to succed to decrypt one ?
(corrolary question will you be sure that the guess message will be a REAL one ?)
(corrolary question2 what if I use a all-or-nothing encoding ?)

Fake decryption

I really like this feature.
Just imagine that you mix 2 differents messages (using 2 differents key for authentication) and use the chaff.
(One explaining to your buddy how you have managed to crack some B1 computers of the government, another saying how you love the wise governement...)
Now Mr SMITH from the NSA knock on your door saying :
"hey guy give me your key to decipher this message (it's not enciphered but you know the NSA is not so used with crypto stuff ;-)
otherwise I sue you for terrorism !"
in this case you'll give him the key enabling him to get the message telling how much you love the governement...
(without the other key all the other 'wheat' is only apparent 'chaff'...
In all other situation your buddy will probably use the right key to decipher the message and play with the B1 computers ;-)

There is really a lot to say about this scheme.
And I'd like to get your feedback about some points (or other I may have missed)

• First what do you think about it ?
• I didn't get the article about the all-or-nothing transform, so in my implemenatation I used a reversed compression as encoding. Is it correct ? If it's flawed how could I correct ?
• What attacks can be mounted against this scheme ?
• I thought about one improvement to enhance the signal/noise ratio.
  I'd suggest to not store the sequence number in the cipher text but use it to compute the checksum.
  Cryptanalisis is now MUCH harder ans you need less chaff...
  As a drawback the decryption process will be slower (as we'll have to 'guess' the sequence number)
  With the key a rough estimate of the complexity for decoding would be O(N*N) without a key a brute for would be O(N!)...
  (There is even an interesting extreme scenario with no chaff -> the algo would be a kind of shuffling scheme)
  However I wonder if it isn't encryption now...
  
• The first implementation of my prog is quite simple, and some problem needs better handling ( By example, loading all the files in memory only allow me to process only small files)
• How to compute the *best* packet size ?

Credits :

-The Napalm Zine where I first hear about this scheme.
Hi kynik ! Thanx for your great article !!!

-Chaffing and Winnowing: Confidentiality without Encryption
The original article from Rivest.

-The Checksum Team
Who convinced me to write this article, and help me to enhance my security skill...

"Only Bad Coders Code Badly In Perl" (OBC2BIP)