Relay-Version: version B 2.10 5/3/83; site utzoo.UUCP
Path: utzoo!utgpu!water!watmath!clyde!rutgers!gatech!udel!burdvax!sdcrdcf!randvax!jim
From: jim@randvax.UUCP
Newsgroups: sci.math,sci.crypt
Subject: Re: Encryption of Hoffman coded text
Message-ID: <291@markle.randvax.UUCP>
Date: Mon, 10-Aug-87 12:33:19 EDT
Article-I.D.: markle.291
Posted: Mon Aug 10 12:33:19 1987
Date-Received: Thu, 13-Aug-87 01:25:25 EDT
References: <10489@linus.UUCP] <7876@mimsy.UUCP> <10604@linus.UUCP> <3515@cit-vax.Caltech.Edu>
Reply-To: jim@markle.UUCP (Jim Gillogly)
Organization: Banzai Institute
Lines: 32
Xref: utgpu sci.math:1740 sci.crypt:476

In article <3515@cit-vax.Caltech.Edu> palmer@tybalt.caltech.edu.UUCP (David Palmer) writes:
>If you are going to encrypt a message by the standard breakable techniques,
>(Caesar cypher, Ultra, Purple, NBS DES, whatever technique the NSA is
>selling to our allies :-)  Is decryption more difficult if you use
>Hoffman coding (including Hoffman coding of common combinations such as 'th')
>on the plaintext before encypherment?  I am assuming that the people doing
>the attack know that you are doing Hoffman coding and know what the code is.

Data compression methods such as Huffman coding will normally make
the cryptanalysis more difficult: the variable-length strings of the
underlying plaintext will make it hard for the cryptanalyst to spot
repetitions that are important for breaking in.

However, a common implementation of Huffman coding involves computing the
optimal tree of assignments of bit strings to ascii characters before
encoding, then prepending this tree to the compressed text.  The tree
is in a standard format, which we assume is available to the cryptanalyst;
this might result in half of several hundred bytes being known.  So rather
than improving the security, this implementation would actually give the
cracker a leg up...

Better would be the adaptive flavor of Huffman coding, which starts with a
standard English (or C code or assembler) decoding tree and changes the
tree on the fly as the symbol frequencies move away from the starting
tree.  This would eliminate the initial cribs, leaving the cryptanalyst
with only the usual tools, such as guessing or discovering pieces of the
underlying plaintext, Huffmanizing them with a standard tree, and testing
the result for consistency.
-- 
	Jim Gillogly
	{hplabs, ihnp4}!sdcrdcf!randvax!jim
	jim@rand-unix.arpa