Cryptography-Digest Digest #465, Volume #10 Fri, 29 Oct 99 15:13:04 EDT
Contents:
Re: Build your own one-on-one compressor (Mok-Kong Shen)
Re: Unbiased One to One Compression (Tim Tyler)
Re: "Risks of Relying on Cryptography," Oct 99 CACM "Inside Risks" column (David
Wagner)
Re: Build your own one-on-one compressor (SCOTT19U.ZIP_GUY)
Re: Compression: A ? for David Scott (SCOTT19U.ZIP_GUY)
Re: Compression: A ? for David Scott (Tom St Denis)
Re: Unbiased One to One Compression (SCOTT19U.ZIP_GUY)
Re: Unbiased One to One Compression (SCOTT19U.ZIP_GUY)
Re: "Risks of Relying on Cryptography," Oct 99 CACM "Inside Risks" column (Jerry
Coffin)
----------------------------------------------------------------------------
From: Mok-Kong Shen <[EMAIL PROTECTED]>
Crossposted-To: comp.compression
Subject: Re: Build your own one-on-one compressor
Date: Fri, 29 Oct 1999 16:11:59 +0200
SCOTT19U.ZIP_GUY wrote:
>
> In article <[EMAIL PROTECTED]>, Mok-Kong Shen
><[EMAIL PROTECTED]> wrote:
> >SCOTT19U.ZIP_GUY wrote:
> >>
> >
> >> TIm I did a quick look at it and yes I feel it would work. I have been
> >> thinking of a more complicated version but yours is more straight forward.
> >> I hope to is clear to users that as you search the long strings are
> >> replaced by the short one and that if a short string is found it is replaced
> >> by the long one.
> >>
> >> The weird way I was thinking of doing it was things like "th" replace with
> >> "q" if "th" not followed by "u" this way since q is usually followed by u
> >> then it would not be replaced and since th seldom has a u after it it would
> >> generally be replaced by a q
> >> So you can see mine would be messier.
> >>
> >> An alternate approoach is to allow for more than 256 symbols. You can expand
> >> from 8 bits to 9 bits with leading bit a zero for common stuff that way
> >> ( note the 9 bit or even 16 bit is a temporary file to allow for more than
> >> 256 leaves at start mabye only 267 leaves in huffman tree)
> >> "th" could be replaced by a new symbol when at the compression stage since I
> >> can easily allow 512 symbols with a slight mod to the current compressor.
> > Know
> >> on decompression if a "th" not there as a special symbol. It would be count
> > as
> >> a repeat of "th" where combinations of "th" and specail new symbol would
> >> represent the repeat count. This is what I am playing with lately.
> >>
> >> Keep up the good work
> >
> >If I understand correctly, you are now on compression not operating
> >on groups of 8 bits but on group of bytes. That certainly removes
> >the remaining bits problem at the last byte of file on decompression
> >of an arbitrary file which is a factor giving rise to the original
> >one-to-one problem. However: (1) the frequency counts of such group
> >of bytes takes much larger work and the Huffman tree is much much
> >larger, (2) due to the larger granularity the compression ratio is
> >likely to be poor, I believe.
> >
> >M. K. Shen
> You lost me Mok. I was using groups of 8 bits to mean bytes. Some
> people don't use the common defination of byte to mean 8 bits. There
> was no change. To clarify
> "8bits==byte"
Did I ever deviate from the common naming convention of bytes??
Note also the arguments of mine in an addendum given in a follow-up
posted some hours later. No comments to any argument are yet seen.
M. K. Shen
------------------------------
From: Tim Tyler <[EMAIL PROTECTED]>
Subject: Re: Unbiased One to One Compression
Reply-To: [EMAIL PROTECTED]
Date: Fri, 29 Oct 1999 15:13:25 GMT
Xav2 <[EMAIL PROTECTED]> wrote:
: "SCOTT19U.ZIP_GUY" writes:
:> I am perffectly happy with files that are made up of 8 bit bytes.
:> However there is an ending problem in Normal Huffman coding. Since one
:> would not know if the random fill bits added are random padding or the
:> next token.
: I'd guess one will just have to reserve a spot in the huffman tree as an
: EOF then.
That approach would ceratinly make transforming the result into a
one-on-one algorithm more difficult.
If you allocate a EOF marker like this, what would happen to bijectivity
if it was referenced several times? ;-(
--
__________
|im |yler The Mandala Centre http://www.mandala.co.uk/ [EMAIL PROTECTED]
The more I learn about people, the more I like my cat.
------------------------------
From: [EMAIL PROTECTED] (David Wagner)
Subject: Re: "Risks of Relying on Cryptography," Oct 99 CACM "Inside Risks" column
Date: 29 Oct 1999 08:45:15 -0700
In article <[EMAIL PROTECTED]>, Terry Ritter <[EMAIL PROTECTED]> wrote:
> Oddly, this doesn't sound like anything we have been talking about. I
> have never heard -- and certainly never made -- a suggestion that the
> adversary will choose the cipher. On the contrary, I have suggested
> that each user be able to create a list of ciphers they will accept,
> and then negotiate agreement -- automatically, in the background, and
> secretly, under the cover of cipher. This would be an ordinary
> handshake selection, not a cryptographic protocol, but nevertheless
> clearly neither exposed to nor under the control of the opponents.
> How is that related to the adversary choosing the cipher?
Hmm. I didn't realize that was what you meant by a non-cryptographic
negotiation. If it's encrypted, it sounds cryptographic to me.
This also raises a further question. I'm not very clear on how we reach
agreement on what cipher to use to encrypt our negotiation in the first
place. Another negotiation? But then is it turtles all the way down?
When I hear the word "negotiation", I think of the following problem:
Alice supports some list of ciphers, Bob supports some (potentially
different) list of ciphers; now Alice and Bob would like to discover which
ciphers they share in common, and hopefully find the "best" such cipher.
Is that what you mean by the "negotiation problem", and if so, how can
we solve the bootstrapping problem securely?
------------------------------
From: [EMAIL PROTECTED] (SCOTT19U.ZIP_GUY)
Crossposted-To: comp.compression
Subject: Re: Build your own one-on-one compressor
Date: Fri, 29 Oct 1999 17:02:33 GMT
In article <[EMAIL PROTECTED]>, Mok-Kong Shen <[EMAIL PROTECTED]>
wrote:
>SCOTT19U.ZIP_GUY wrote:
>>
>> In article <[EMAIL PROTECTED]>, Mok-Kong Shen
> <[EMAIL PROTECTED]> wrote:
>> >SCOTT19U.ZIP_GUY wrote:
>> >>
>> >
>> >> TIm I did a quick look at it and yes I feel it would work. I have been
>> >> thinking of a more complicated version but yours is more straight forward.
>> >> I hope to is clear to users that as you search the long strings are
>> >> replaced by the short one and that if a short string is found it is
> replaced
>> >> by the long one.
>> >>
>> >> The weird way I was thinking of doing it was things like "th" replace
> with
>> >> "q" if "th" not followed by "u" this way since q is usually followed by
> u
>> >> then it would not be replaced and since th seldom has a u after it it
> would
>> >> generally be replaced by a q
>> >> So you can see mine would be messier.
>> >>
>> >> An alternate approoach is to allow for more than 256 symbols. You can
> expand
>> >> from 8 bits to 9 bits with leading bit a zero for common stuff that way
>> >> ( note the 9 bit or even 16 bit is a temporary file to allow for more than
>> >> 256 leaves at start mabye only 267 leaves in huffman tree)
>> >> "th" could be replaced by a new symbol when at the compression stage
> since I
>> >> can easily allow 512 symbols with a slight mod to the current compressor.
>> > Know
>> >> on decompression if a "th" not there as a special symbol. It would be
> count
>> > as
>> >> a repeat of "th" where combinations of "th" and specail new symbol would
>> >> represent the repeat count. This is what I am playing with lately.
>> >>
>> >> Keep up the good work
>> >
>> >If I understand correctly, you are now on compression not operating
>> >on groups of 8 bits but on group of bytes. That certainly removes
>> >the remaining bits problem at the last byte of file on decompression
>> >of an arbitrary file which is a factor giving rise to the original
>> >one-to-one problem. However: (1) the frequency counts of such group
>> >of bytes takes much larger work and the Huffman tree is much much
>> >larger, (2) due to the larger granularity the compression ratio is
>> >likely to be poor, I believe.
>> >
>> >M. K. Shen
>> You lost me Mok. I was using groups of 8 bits to mean bytes. Some
>> people don't use the common defination of byte to mean 8 bits. There
>> was no change. To clarify
>> "8bits==byte"
>
>Did I ever deviate from the common naming convention of bytes??
>Note also the arguments of mine in an addendum given in a follow-up
>posted some hours later. No comments to any argument are yet seen.
>
Then reask your question so I know what your asking. You have be
confused since "on groups of 8 bits but on group of bytes" seems to
me to mean you don't think 8bits is a typical byte.
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] (SCOTT19U.ZIP_GUY)
Subject: Re: Compression: A ? for David Scott
Date: Fri, 29 Oct 1999 16:59:24 GMT
In article <7vc81f$128$[EMAIL PROTECTED]>, "Tim Wood" <[EMAIL PROTECTED]>
wrote:
>True. But it does depend on your definition of bad (low
>compression/predictable structure).
My defination of bad is a compressor that adds information
to a file as it compresses.
>
>>If the problem is only that a
>>good compression program (i.e. pkzip) adds known information to the
>>header (as exist in many file formats), why wouldn't moving the
>header
>>to the end of the plaintext, and running in a feedback mode
>>effectively eliminate or greatly reduce the problem?
>
>Running in a feedback mode would reduce the problem - however it would
>be better to eliminate the problem (i.e. find a cure not treat the
>symptoms) by removing all added structure from the post-compression
>plaintext.
And one way to do that is to use a one to one compression scheme.
>
>>Additionally,
>>why wouldn't running a bad compression program be potentially as bad
>>as no compression, as it could lead to predictable patterns within
>the
>>body of the plaintext?
>
>Running a compressor that adds sinificant predictable
>structure/information to your plaintext is probably as bad or worse
>than no compression (depending on the plaintext you are commpressing).
>And certainly not more secure than no compression.
It is definitely worse.
>
>>What if the "compression" program is actually designed to
>allow/insert
>>patterns specifically to provide someone with a known plaintext
>>attack?
>
>This should be avoided. Although it is certainly possible. All third
>party programs suffer from similar possible problems; it comes down to
>who you trust... micro$oft for instance? ;-)
>
>>If the compression program doesn't actually compress,
>
>The compression program should compress (only random data should be
>uncompressible).
Becasue of the counting theorm all compressors only make a subset set
of files smaller. In fact most files would incearse in lenght of you looked at
the class of all real binary files.
>
>>wouldn't it make
>>a whole lot more sense to use an unrelated but standard cipher
>>(different key, of course) first?
>
>That is a whole diffrent issue.... encrypted data should be mostly
>uncompresible.
>
>>It just seems like trying to use a screwdriver as a hammer, and not
>>doing either very well.
>
>This is possibly true, it would be wrong to rely on compression to
>secure your cipher, but there is nothing wrong with adding extra
>security. Compression complements encryption.
Compression can complement security if used correctly however
in practice this seems to seldom be done. Since people have not taken
the time to really look at the security issues involvled. Except for groups
like the NSA which undoubtly through there contacts with the public and
through the chosen few like Mr BS who talk about his great contacts with
the NSA I am sure would not like the masses to learn about bad compression
that is used with encryption or his book would have had a decent discussion
on the topic which it does not. Makes one wonder what else is missing or
worded to misinform the person trying to really learn about crypto. I am
graetly disappointed that Wagner has choosen to keep the disception and
misinformation about compression and encryption alive.
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: Tom St Denis <[EMAIL PROTECTED]>
Subject: Re: Compression: A ? for David Scott
Date: Fri, 29 Oct 1999 16:13:59 GMT
In article <7vc2q3$1fug$[EMAIL PROTECTED]>,
[EMAIL PROTECTED] (SCOTT19U.ZIP_GUY) wrote:
> IF your saying use the best compressor possible and use a OTP.
> Which is the only proveable good way to use random data. Yes this
> would work. However if one is going to use an OTP in the first place
> there really is no need for any other type of encryption. The problem
> with an OTP is getting the random data. IF you have an excellent
> source and a secure way of getting this random data to you and you
> buddy who is decrypting. Then you don't need to be concerned with
> 99% of the stuff on encryption that everyone is talking about since
> the OTP which relies on random data is proveably secure.
> For that matter just XOR your data with the random data in the
> first place and kiss off compression all together.
That doesn't make sense, maybe they want to use compression to, um, i
dunno, MAKE THE MESSAGE SMALLER!!!
[as an added bonus you waste less of your OTP].
Tom
Sent via Deja.com http://www.deja.com/
Before you buy.
------------------------------
From: [EMAIL PROTECTED] (SCOTT19U.ZIP_GUY)
Subject: Re: Unbiased One to One Compression
Date: Fri, 29 Oct 1999 17:56:25 GMT
In article <[EMAIL PROTECTED]>, [EMAIL PROTECTED] wrote:
>Xav2 <[EMAIL PROTECTED]> wrote:
>: "SCOTT19U.ZIP_GUY" writes:
>
>:> I am perffectly happy with files that are made up of 8 bit bytes.
>:> However there is an ending problem in Normal Huffman coding. Since one
>:> would not know if the random fill bits added are random padding or the
>:> next token.
>
>: I'd guess one will just have to reserve a spot in the huffman tree as an
>: EOF then.
>
>That approach would ceratinly make transforming the result into a
>one-on-one algorithm more difficult.
>
>If you allocate a EOF marker like this, what would happen to bijectivity
>if it was referenced several times? ;-(
If you add an EOF marker and you are compressing a single file
then you can't have a 1-1 compression program. However you can add
a EOF if you are compressing many files from a given set. That way
every time an EOF token appears it is the EOF token for current compressed
file. If more than one EOF appears together then it is just marking that
compressed file as a NULL file. When the last file ends you do not write
the EOF token since at the end of a compressed file that token would only
mark an empty file. You actaully have one less EOF token in the file than
you have files compressed together.
I have been playing with this concept it would just be an extra leaf in the
tree it is not to hard to add in the code if one really had a need for this.
The hard part is if one wanted to add the file names as this would vary
greatly from machine to machine and operating system to operating
system.
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] (SCOTT19U.ZIP_GUY)
Subject: Re: Unbiased One to One Compression
Date: Fri, 29 Oct 1999 17:59:17 GMT
In article <[EMAIL PROTECTED]>, "Trevor Jackson, III" <[EMAIL PROTECTED]>
wrote:
>Xav2 wrote:
>
>> "SCOTT19U.ZIP_GUY" writes:
>> > In article <[EMAIL PROTECTED]>, "Trevor Jackson, III"
> <[EMAIL PROTECTED]> wrote:
>> > >There is no file ending problem any more than there is a file sector
> padding
>> > > problem. Simply
>> > >pad the byte with random bits.If you are truly concerned use a
> communication
>> > > mechanism that
>> > >tracks bits instead of bytes.
>> >
>> > I am perffectly happy with files that are made up of 8 bit bytes.
> However
>> > there is an ending problem in Normal Huffman coding. Since one would
>> > not know if the random fill bits added are random padding or the next
> token.
>>
>> I'd guess one will just have to reserve a spot in the huffman tree as an
>> EOF then.
>
>Or put the file size in bits in the message. On does not lose thereby as one
> usually assumes
>the opponent knows the size of the message.
No one does not assume the opponent ususally knows the size of the message.
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] (Jerry Coffin)
Subject: Re: "Risks of Relying on Cryptography," Oct 99 CACM "Inside Risks" column
Date: Fri, 29 Oct 1999 11:35:42 -0600
In article <[EMAIL PROTECTED]>, [EMAIL PROTECTED] says...
[ ... ]
> Oddly, this doesn't sound like anything we have been talking about. I
> have never heard -- and certainly never made -- a suggestion that the
> adversary will choose the cipher. On the contrary, I have suggested
> that each user be able to create a list of ciphers they will accept,
> and then negotiate agreement -- automatically, in the background, and
> secretly, under the cover of cipher. This would be an ordinary
> handshake selection, not a cryptographic protocol, but nevertheless
> clearly neither exposed to nor under the control of the opponents.
> How is that related to the adversary choosing the cipher?
IMO, to maintain any hope of improving security, you need to ensure
that the cipher used in the negotiation phase is _different_ from any
of the ciphers that can be selected by the negotiation.
If the protocol allows the same cipher to be used both for negotiation
and for messages, then breaking that single cipher allows a MITM to
force the same cipher to be selected with the negotiation as well, so
he can then break the messages being sent.
By NOT allowing the same cipher to be used for both negotiation and
messages, the opponent has to break both the negotiation-phase cipher
and at least one more before he can really accomplish anything.
--
Later,
Jerry.
The universe is a figment of its own imagination.
------------------------------
** 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
******************************
