Cryptography-Digest Digest #216, Volume #10 Fri, 10 Sep 99 11:13:03 EDT
Contents:
Re: some information theory (SCOTT19U.ZIP_GUY)
Re: Looking for an asymmetric system (DJohn37050)
Re: unix clippers that implement strong crypto. (SCOTT19U.ZIP_GUY)
Double encryption is patented (mabey) (Anonymous)
Re: Help me please with *.mpg.00* (Richard Herring)
Re: some information theory
Re: Looking for an asymmetric system (Emmanuel Drouet)
Re: Looking for an asymmetric system (Tom St Denis)
Re: Schneier/Publsied Algorithms (Anonymous)
Re: some information theory (Mok-Kong Shen)
----------------------------------------------------------------------------
From: [EMAIL PROTECTED] (SCOTT19U.ZIP_GUY)
Subject: Re: some information theory
Date: Fri, 10 Sep 1999 14:07:35 GMT
In article <[EMAIL PROTECTED]>, Anti-Spam
<[EMAIL PROTECTED]> wrote:
>John Savard wrote:
>>
>> Anti-Spam <[EMAIL PROTECTED]> wrote, in
>> part:
>>
>> >Compression with huffman-encoding type schemes is identical to a
>> >substition encipherment.
>> >The relative order of SYMBOLS as ENCODED in the uncompressed data/file
>> >with ASCII, UNICODE or any other binary representation is PRESERVED by
>> >the compression
>>
>> Yes, with static Huffman compression. Not with _adaptive_ Huffman, or
>> Lempel-Ziv.
>>
>> >Compressing data/files prior to encryption with a cipher system does not
>> >alter the frequency of the SYMBOLS encoded in the compressed data/file
>> >relative to their original frequencies in the uncompressed file/data.
>> >Compressing prior to encrypting does not permutate the order of the
>> >SYMBOLS encoded in the compressed data/file relative to their original
>> >order as encoded in the uncompressed file/data. Compression only alters
>> >the encoding of the SYMBOLS to achieve the maximal entropy possible as a
>> >function of the probabilites of the SYMBOLS themselves.
>>
>> Not compression in general, but a particular limited form of
>> compression.
>>
>> For cryptographic purposes, it is important to compress as well as
>> possible.
>>
>> So instead of using single ASCII characters as SYMBOLS, how about
>> compression where digraphs, trigraphs, and even English words are
>> SYMBOLS? Even simply a multi-mode Huffman code, where letters are
>> coded based on their frequencies after a vowel, or after a consonant,
>> or at the beginning of a word, will help.
>>
>> >First, Compressed data is NOT necessarily random data. Many of us assume
>> >the compressed form of a file is "equivalent" in some form to true
>> >random data. It is not.
>>
>> No, but the better the compression, the closer the compressed file
>> will resemble random data.
>>
>> You are right, though, that it is very difficult to compress well
>> enough to get very close to randomness.
>>
>> But it is incorrect, and confusing, to conclude from that that it is
>> impossible to derive any benefit from compression. The benefit is,
>> unfortunately, limited.
>
>I DO NOT conclude that it is impossible to derive any benefit from
>compression prior to encryption. I am exploring the logical holes in
>the assertion that compression supplies the diffusion and confusion
>properties of encryption in and of itself. Many of the posts read here
>imply ( or is just the way I read it? :) ) that compression achieves the
>desired effects of encryption without using encryption.
>
>The static Huffman encoding for compression is equal to a simple
>substitution of the binary codes for the symbols in the uncompressed
>data/file into another binary code for those symbols in the compressed
>data/file. The order and frequency of the symbols remains invariant.
>That's not a very secure "hiding" of symbols.
>
>I am on the hook to extend this analysis to adaptive encoding for
>compression (such as adaptive huffman encoding for compression.) I've
>thought about it most of the day. I can only post at night. I've enjoyed
>the responses.
>
John unless you can break new ground your fighting an uphill
battle. In staic huffman coding you can send just the last
half of file and it is trivial to reconsturct the underlying message.
This is not so with "adaptive huffman compression". If you have
a normal ascii message it would be very hard to even determine
what the last symbol sent was. Using my file ending method
the "all zero" weakness is not as weak as you may think. I still
use a tree with only 256 leaves and one can not even tell by looking
at the end of the file where the last symbol ended or started.
If you only have the last half of a file. You don't even know where
any symbol starts. You may be starting in the fragment of a symbol
since there is no reference point for the start or end of any symbol.
To decode you would have to guess the starting position of the first
complete symbol and then guess its value. This is not a trivail task
and has been looked at for years. It is not like your multisubsittution
cipher in that they can be broken by plain text attacks. What you
have when your looking at the last half of a file compressed with an
adaptive huffman compressor is unique for that message alone.
I would say if you can come up with a method to recover what the
underlying text is in an ascii file that is compressed wiith an
adaptive huffman compresser having only the last half of the file
then you should be elevated to the status of Crypto God.
David A. Scott
--
SCOTT19U.ZIP NOW AVAILABLE WORLD WIDE
http://www.jim.com/jamesd/Kong/scott19u.zip
http://members.xoom.com/ecil/index.htm
NOTE EMAIL address is for SPAMERS
------------------------------
From: [EMAIL PROTECTED] (DJohn37050)
Subject: Re: Looking for an asymmetric system
Date: 10 Sep 1999 13:18:48 GMT
Three asymmetric systems are well-recognised today, based on integer
factorization, (normal) discrete logarithm, and elliptic curve discrete
logarithm. See IEEE P1363. Of these 3, EC is the strongest as there is no
known subexponential time algorithm to solve the ECDLP.
Don Johnson
------------------------------
From: [EMAIL PROTECTED] (SCOTT19U.ZIP_GUY)
Crossposted-To: comp.security.unix
Subject: Re: unix clippers that implement strong crypto.
Date: Fri, 10 Sep 1999 14:19:42 GMT
In article <[EMAIL PROTECTED]>, Martin Pauley
<[EMAIL PROTECTED]> wrote:
>
>Armin Ollig <[EMAIL PROTECTED]> wrote:
>> AFAIK it is better to first encrypt and then compress the data.
>> This means more cpu cycles but better security, because the compression
>> may leave a characteristic pattern that may be usefull for
>> crytpanalysis. ?!
>
>I compress first and then encrypt, for two reasons:
>1. an encrypted file does not compress well; quite often an encrypted
> file will increase in size when you try to compress it.
>2. compressed files contain less of a pattern than most plain files.
> This is by design, since most (all?) compression algorithms work by
> detecting and removing patterns. In contrast, plain files tend to
> have well-defined patterns, which is why they compress.
>
>I'm not an encryption expert, but I met one once! :-)
>
>-- Martin Pauley
But one must be very carful of which compression program is used to
compress. SInce compression can sometimes make it easier to break
your encryption.
To test if a compression decompression method adds information while
compressing thus weakening your ability to keep you datat secure.
Test your compression method.
Take a several random binary file. Run them through you decompressor
and then compress them back. If they all come back to the same file then
you may have method worth using. IF the decompressor BARFS on any
file dump it.
I am of course assuming the method is also good enough that any file
can be compressed and then decompressed back to the sasme file.
If your having trouble finding a compressor that meets this standard you
can have mine for FREE source code included written C at
http://members.xoom.com/ecil/compress.htm
David A. Scott
--
SCOTT19U.ZIP NOW AVAILABLE WORLD WIDE
http://www.jim.com/jamesd/Kong/scott19u.zip
http://members.xoom.com/ecil/index.htm
NOTE EMAIL address is for SPAMERS
------------------------------
Date: Fri, 10 Sep 1999 15:39:17 +0200 (CEST)
From: Anonymous <[EMAIL PROTECTED]>
Subject: Double encryption is patented (mabey)
>From a recent post on sci.crypt titled: Hash of a file as key:
>"John Savard" <[EMAIL PROTECTED]> wrote:
> One technique:
>
> - divide a file into a hash-length piece and the rest,
> - hash the rest, XOR the result with the first piece
> - encrypt the rest with the XORed first piece and hash as the key
> - use RSA to encrypt the first piece, also the session key for the rest,
> plus as much of the rest as will fit
>
> while I think it's optimal, seems to be covered by a patent.
>Both your Hash/Encrypt construction and Mihir Bellare's CBC-MAC/CBC
>construction in particular are very similar to construction used by Ross
>Anderson and Eli Biham for the the BEAR cipher. Unfortunately, the
technical
>report in which BEAR appears was published ten months after Bellare applied
>for his patent, so it appears that it can't be used to as an example of
prior art.
>-Richard
>
Peter Gutmann wrote: (from the original thread)
>Actually there's prior art from 1993, this is the no-IV encryption I used
for disk
>sector encryption in SFS, http://www.cs.auckland.ac.nz/~pgut001/sfs/.
>The method was designed by Colin Plumb, for speed reasons it doesn't use
two
>passes of CBC but one pass of an SHA-1 style scrambler which produces a
160-
>bit plaintext-dependant IV, and a second pass which does the actual
encryption.
>IANAL, and my eyes were starting to hurt reading that scanned text, but
apart
>from the use of a (slow) MAC vs a (fast) simple checksum, the two
techniques
>appear pretty much identical.
>
In any case, the invention in question (U.S. patent 5673319) is NOT the same
as being described here. What is being described here is very close to what
is described in "Applied Cryptography" on page 222, of chapter 10. Heading:
"Providing random access to an encrypted drive." I invite those with the
book to look at it.
The invention in question is a method to avoid using an IV in the classic
way. (by concatenating it with the text) The invention uses CBC, but allows
the ciphertext to be the same length as the plaintext, and be resistant
against replay attacks. (as is the case if using a classic IV) BTW, it uses
*two* secret keys. And it has nothing to do with session keys. A session key
would mean that it is *not* length preserving.
Look it up for yourself: http://www.uspto.gov
So, does anybody contend that *any* use of a file/message's content to
influence the encryption of it's self would be subject to this patent????
If so, Hmmmmm.
jmp
Here are key excerpts from the patent:
These and other objects of the invention are achieved in a method, using
first and second secret keys, to encrypt a plaintext string to a ciphertext
string. The method begins by cipher block chaining the plaintext string
using the first key and a fixed initialization vector to generate a CBC
message authentication code (CBC-MAC) of length equal to the block length.
Thereafter, the method continues by cipher block chaining the plaintext
string using the second key, and using the aforementioned CBC message
authentication code as the initialization vector, to thereby generate an
enciphered string. The CBC message authentication code and a prefix of the
enciphered string are then combined (typically by concatentation) to form
the ciphertext string. Preferably, the technique is length-preserving; the
prefix includes all but the final block so that the length of the ciphertext
is equal to the length of the plaintext.
Thus according to the preferred method the plaintext string is processed
using CBC twice, first to generate the CBC-MAC, and then to generate a
portion of the ciphertext itself. In the first pass, the initialization
vector used in the CBC is the null vector (meaning a string of 0-bits having
length equal to the block length). In the second pass, the initialization
vector is the CBC-MAC generated in the first pass. The keys are distinct for
the two passes. The method is useful for generating ciphertext when the
plaintext string has a length that is a multiple of a length of a block. A
variant of the scheme can be used when the plaintext string has a length
that is a fraction of the block length.
To decrypt the ciphertext, the enciphered string portion thereof is cipher
block chained using the second key and the CBC-MAC as the initialization
vector to generate a deciphered string. The deciphered string is then cipher
block chained using the first key and a null IV to generate a string having
a last block. The plaintext is then taken as the combination (e.g., by
concatenation) of the deciphered string and a predetermined function (e.g.,
an XOR) of the last block, and the inverse of the block cipher under the
first key at the CBC-MAC.
------------------------------
From: [EMAIL PROTECTED] (Richard Herring)
Subject: Re: Help me please with *.mpg.00*
Date: 10 Sep 1999 13:51:09 GMT
Reply-To: [EMAIL PROTECTED]
In article <7r6bfr$j0i$[EMAIL PROTECTED]>, Sasha Court ([EMAIL PROTECTED]) wrote:
> Could someone explain to me how to view a decoded file of the type *.mpg.00#
It's probably a .mpg that has been split by a shareware tool called
Mastersplitter. It isn't encrypted in any way.
If so, the .mpg.000 file contains some administrative data;
the remaining files .mpg.001 .mpg.002 ... .mpg.NNN contain sections of the
original .mpg file.
If you don't own Mastersplitter, you can glue them together by using the
DOS COPY or Unix cat command (omit the .mpg.000 file), or by running
the .mpg.bat file that was probably posted with them.
--
Richard Herring | <[EMAIL PROTECTED]>
------------------------------
From: [EMAIL PROTECTED] ()
Subject: Re: some information theory
Date: 10 Sep 99 13:32:01 GMT
Anti-Spam ([EMAIL PROTECTED]) wrote:
: I DO NOT conclude that it is impossible to derive any benefit from
: compression prior to encryption. I am exploring the logical holes in
: the assertion that compression supplies the diffusion and confusion
: properties of encryption in and of itself. Many of the posts read here
: imply ( or is just the way I read it? :) ) that compression achieves the
: desired effects of encryption without using encryption.
You are certainly correct that compression doesn't usually supply much
diffusion.
Even if compression was 'perfect', it wouldn't necessarily supply any
security of itself, since no key is involved. As compression improves in
quality, in achieving higher compression ratios, some "diffusion" is
required, because it is necessary to use larger and larger objects as
symbols. Instead of a dictionary of letters, digraph-based compression.
>From a dictionary of words to compression with multiple modes based on the
parts of speech. So far, compression techniques don't usually go that far.
Compression only changes the plaintext to a new kind of plaintext, one
that gives the cryptanalyst less assistance. It is when the plaintext is
not known that compression can stymie analysis; glimpses of earlier
plaintext aren't enough to reconstruct an adaptive Huffman compression
tree, one needs all the prior plaintext (up to, as you point out, the
point where the tree becomes static, if it does - a low-frequency letter
appearing late in the message can shift things).
Don't forget the fact that symbol boundaries are no longer visible.
John Savard
------------------------------
From: Emmanuel Drouet <[EMAIL PROTECTED]>
Subject: Re: Looking for an asymmetric system
Date: Fri, 10 Sep 1999 16:28:33 +0100
> > 1/ I would like to know what is the strongest asymetric cryptosystem
> For what purpose?
[Manu]
For the transfert of multimedia data.
------------------------------
From: Tom St Denis <[EMAIL PROTECTED]>
Subject: Re: Looking for an asymmetric system
Date: Fri, 10 Sep 1999 13:49:28 GMT
In article <[EMAIL PROTECTED]>,
Emmanuel Drouet <[EMAIL PROTECTED]> wrote:
> Hello !
>
> 1/ I would like to know what is the strongest asymetric cryptosystem
For what purpose?
> 2/ What do you think about :
> RSA, elgamal, McEliece, elliptic curves, Merkle-hellman
RSA is simple to describe and appears difficult to attack. elliptic
curve methods are just extensions to all other methods. Dunno about
the others.
> 3/ Do you know another asymetric cryptosystem ?
Nope, wouldn't you like to know.
Tom
--
damn windows... new PGP key!!!
http://people.goplay.com/tomstdenis/key.pgp
(this time I have a backup of the secret key)
Sent via Deja.com http://www.deja.com/
Share what you know. Learn what you don't.
------------------------------
Date: Fri, 10 Sep 1999 16:30:07 +0200
From: Anonymous <[EMAIL PROTECTED]>
Subject: Re: Schneier/Publsied Algorithms
Mr Green...could you please let Bruce Schneier reply to my question...
The Question was not addressed for you...Are you incharge of the Schneier fanclub..??
Bruce..perhaps you can answer this q?
The coe for 2fish on your site is 16 months old...
Do you have any new code or cleaner implementation for commercial use??????
When will you update this Ver 1 April 1998 Code ...please reply
------------------------------
From: Mok-Kong Shen <[EMAIL PROTECTED]>
Subject: Re: some information theory
Date: Fri, 10 Sep 1999 16:52:59 +0200
Anti-Spam wrote:
>
> Adaptive encoding for compression usually begins with an assumed model
> for the probabilites of occurance for the symbol set ("alphabet" based
> on some sample of text, data, file using those symbols. Each of the
> symbols in the "alphabet" gets an a priori probability. We can use this
> initial probability model to define an initial encoding for the
> symbols.
>
> As we process the data/file we update the frequencies for the symbols as
> they appear. The encoding for a given symbol changes "rapidly" early
> on. We encounter subsets of the "alphabet" as we progress through the
> data/file. Now here's what charms me about this problem.
>
> What is the spatial "rate of change" of probability of occurance for a
> symbol as I process the uncompresses data/file from its beginning to its
> end? At some point in the data/file binary stream the statistics
> should/may (a conjecture - no proof yet) tend to steady-state values and
> thus the encoding for symbols in the compressed data/file will not
> change over time.
> Autocorrelation testing of the compressed data/file may/should identify
> candidate binary values for the encoded symbols.
.............
> If the encoding reaches a "steady state" then we should expect to see
> the same codes for symbols from that point on in the compressed
> data/file. We would need to guess at the value of k (how many unique
> symbols there are) and by the assumption that frequencies are not
> changing or changing "slowly" (can't define that yet), and assuming the
> encoding is optimal, use the 5 points above as a guide to sort through
> candidate code strings.
>
> I would look for autocorrelations in the later part of the data/file
> with binary sequencies of length Ln - 1 constrained by a guess for the
> number of symbols k. If I knew something about the symbols as the
> appeared in the uncompressed data/file, I'd start with that. If its a
> short text message this would prove fruitless, since many of the
> characters in the alpabet may not occur in the uncompressed text. I
> (conjecture) would think text longer than the unnicity distance for
> English would mean I could just assume all letters of the alphabet did
> appear, and use static freq. of occurance models for the letters and
> establish which letter should have the shortest, the next shortest, then
> next, etc... bit length encoding.
As said in a previous follow-up, the codes are of non-constant length
and hence it is necessary for the analyst to identify the boundaries
between the symbols in the binary string if any frequency count
is to be done. While additional arguments can certainly be offered
(by other writers), I suppose that this is already sufficient to
establish that compression does render the job of the analyst more
difficult. On the other hand, to be conservative, one should
in my humble opinion regard compression and encryption as orthogonal
(this is the common standpoint, as far as I am aware), i.e. one
should access the security of one's system based on the strength of
the proper encryption methods employed and consider the benefits
arising from using the diverse well-known compression methods (which
have been designed by their authors without considering cryptology)
merely as some bonus.
M. K. Shen
------------------------------
** FOR YOUR REFERENCE **
The service address, to which questions about the list itself and requests
to be added to or deleted from it should be directed, is:
Internet: [EMAIL PROTECTED]
You can send mail to the entire list (and sci.crypt) via:
Internet: [EMAIL PROTECTED]
End of Cryptography-Digest Digest
******************************
