Keep It Simple, Stupid | |
PerlMonks |
Privacy without Encryptionby arhuman (Vicar) |
on Jun 04, 2001 at 12:38 UTC ( [id://85426]=perlmeditation: print w/replies, xml ) | Need Help?? |
I'd like to talk about an old but unknown way to achieve privacy without encryption. This method is another gift from R. RIVEST (You know the 'R' in RSA, RC4, RC6 and MD5 ;-) The basic Idea is to hide valid data (the wheat) in a lot of useless data (the chaff). I've read once somebody talking about his scheme as a kind of textual steganography, I think the 'picture' (is there a better word for a comparison with steganography ;-) is quite true. Note : Please feel free to comment/correct this code(beware it's an alpha release, not so tested) after reading this post
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 :
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 :
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 ?
However this scheme has several funny advantages :
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)
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)
Back to
Meditations
|
|