Re: A basic cryptanalysis question

From: DSCOTT (daVvid_a_scott_at_email.com)
Date: 07/10/03 

Date: 10 Jul 2003 14:00:39 GMT

scpoarnmers@sbcglobal.net (Corners) wrote in
<T58Pa.648$uj1.679980179@newssvr11.news.prodigy.com>:

>
>
>--
>To email, first remove spam from my address.
>"DSCOTT" <daVvid_a_scott@email.com> wrote in message
>news:93B3FE9EEH110W296LC45WIN3030R@130.133.1.4...
>> scpoarnmers@sbcglobal.net (Corners) wrote in
>> <5w6Pa.644$lw7.673040542@newssvr11.news.prodigy.com>:
>>
>> >
>> >
>> >--
>> >To email, first remove spam from my address.
>> >"DSCOTT" <daVvid_a_scott@email.com> wrote in message
>> >news:93B35FB95H110W296LC45WIN3030R@130.133.1.4...
>> >> rwash@citi.umich.edu (Rick Wash) wrote in
>> >> <slrnbgn273.10o.rwash@elysium.citi.umich.edu>:
>> >> ...
>> >
>> >> Though there are theorms that state you can't in general make a
>> >> system
>> >> that is more secure than one of the ciphers done in series.
>> >
>> >Do you have a reference to such theorems? I am aware of a theorem
>> >that says that for unrelated keys, two ciphers in series are at least
>> >as secure as either one alone, but that is not the same as your
>> >description.
>> >
>>
>> They have been stated on this forum many times. However the
>> therom you state is not one of them. But what is one of them
>> is two ciphers in series can be as weak as the first. What this
>> means is that sometimes if you have a weak cipher and than a
>> strong cipher. You may be provably better off if you used only
>> the stronger cipher by itself. And I am talking about unrelated
>> keys.
>
>Okay, but I don't see how you can use the idea that two ciphers might be
>as weak as one, to support the conclusion that
>
>>>> Though there are theorms that state you can't in general make a
>>>> system that is more secure than one of the ciphers done in series.
>
>If you mean that you can't always count on two ciphers being stronger
>than one, I can certainly agree. If you mean that two ciphers can't be
>stronger than one, then I would disagree. If I've misunderstood or
>misconstrued something here, I apologize for being dense.
>

   Thats ok. I don't explain the best. But one way to think of the
therom is like this. Take two general cipher that use independent
keys. Call strong one S and weak one W say they work on all files.
I am not saying that S or W are bijective since most encryption systems
aren't bijective.
If W is so weak that a cipher text only attack can break it easily meaning
c = W(p) and if S is so strong that if one used c = S(p) the p could
not be easily recovered. Then one might think this fact alone makes
c = S(W(p)) a stronger cipher than using S alone. This has been
proven false. I hope that stated it clearly. If example desired
I will provide you with one.

>> >> such a function look at my second order bijective compression of
>> >> english text as an example.
>> >
>> >I think it would be helpful, when we talk about bijective operations,
>> >to identify what sets the term "bijective" applies to.
>> >
>>
>> Basically I mean this from some infinite set of files A and
>> the infinite set of all real 8 bit byte files B.
>> Then for any file a1 a file in A there exists a unique file
>> in B called b1 such than
>> b1 = compress(a1) and a1 = decompress(b1)
>> Also for any file b2 in file set B there exists a unique file
>> a2 in file set A such that
>> a2 = decompress(b2) and b2 = compress(a2)
>> the above is for bijective file compression. In my second order
>> bijective english compression file Set A is any file of one or
>> more groupings of letters a to z with single spaces btween such
>> groupings and not trailing or leading spaces. What this means
>> is that any file can be decompressed uniquely to a file in
>> Set A there are no gaps.
>
>So, every bitstream has a "compressed" representation, and every
>bitstream has a "decompressed" representation. That sounds quite
>reasonable, and it's a bigger achievement that it might seem to those
>who haven't worked with this stuff before. So, your algorithm is
>bijective when it maps an element of the set "any bitstream" to/from
>some other element of the same set. (Or, I suppose, some elements might
>map to/from themselves.)

  My general bijective compressors would map any bitstream to a
unique bitstream weather doing compression or decompression. Hoever
I prefer working only with files. Many don't but I do. In the
file case the gernal bijective compressors will compress or decompress
any file uniquely. However as with any general file compressor most
files will not be smaller. What really occurs is just a reordering of
the files from one set to another so that you can maybe more accurately
call them bijective transforms.

>
>However, I think that mentioning "English" could be the source of some
>confusion. You do not seem to be claiming that every bitstream can be
>"uncompressed" using your algorithm, to produce English. That could not
>even be possible if every bitstream, English or not, has a "compressed"
>representation. Such a bijective function would be an important
>contribution to cryptography, but as I understand it, only limited
>results have been achieved so far.
>

  For the second order one I mention. It only means the tables are
based on second order english. The closer the input file matches
second order english the better it compresses. Of course nonsense
words will compress. However if they don't match second order english
files of the same length they will not compress very well. The second
order english compressor is meant to work only on files of groups of
letters and single spaces so the infinite input set is only on files
of that form. It is a lossless bijective compressor. Example from
http://bijective.dogma.net/compres2bse.htm
" NOW IS THE TIME " this file is not in the input set. For lossless
 bijective compression to allow some flexability on compression I filter
 files that don't match the input criteria. so this file becomes
"NOW IS THE TIME" which compresses to 6 bytes. On decompression the
second file comes back. In fact the first file can never come
back since only files that start with "A"- "Z" can come back. No leading
spaces. Likewise there can never be a file that decompresses to a file
that has trailing or connected spaces. If you take a long random string
and decompress it with this decompressor it will most likely look like
second order english. However any file of letter groupsing with single
internal spaces is possible. But of one modeled higher order english
you would more and more apt get a file on decompression that matched
higher order english. IF one designed the compressor to only compress
words from some fixed dictionary than the matching decompressor would
only decompress to files of that type. The main feature of bijective
compression is that any binary file decompresses to a file that the
input is matched to.

>This important distinction is why I suggested explicitly identifying the
>set(s) involved when discussing a bijective function. There are many
>bijective functions that map the set of "any bitstream" onto itself.
>Some are useful, some are not. A function that could bijectively map
>elements from the set "English plaintext" to and from the set "random
>bitstream" would be, I think, pretty important news.
>

  I don't think its important news. The trick is what you use for a
model of english. And I feel there is no true general model. Meaning
some people mispell words would you reject there writting as not english
as one attempts to design a compressor for true english it might be
better to have an adaptive filter based on the individual user.
If you allow more than one letter case or commas and such it starts
to become debatable what english is.

  Example suspose I am sending a friend some encrypted messages
and am using an english compressor before I do encrypted phase.
If an attacker some how can rapidly test keys he might reject
those keys that lead to what a machine thinks is not english.
But if I mispell frequently that would be a mistake since I cant
write perfect english. To do it correctly it would have to assign
a rejection probability based on my own stule of english. Or it
would be impossible to break my code. Now suppose the attacker
cleverly notices I don't use "their" I only use "there" for any
sound of the word. I hate alternare speellings for same sound.
The attacker might make his dectection program when testing keys
reject any key that leads to a file containing the word "their"
since I don't use it. Or least assign a very low probability to
a files that decyrypts to it. So in the war of crypto I change my
public (if a wish ) system that is bijective but prevents the
spelling of "their" or at least forces a very long compressed sequence
to occur matching the unlikely hood of me using it. Thus again
making the attackers testing of correct keys more difficult.

 One of the best kept secrets of real encryption is make every
key work. Unlike PGP or most new style modern encryption where
only hoped for complexity keeps a ciphertext secure. One should
strive for a system where every key leads to a possible encrypted
message to confuse the attack. An example of such a system using
modern AES as basis with bijective matching transforms is BICOM
http://www3.sympatico.ca/mt0000/bicom/bicom.html
it was done by a friend of mine. It does a PPM compress on file
then does full block CBC AES encryption and transforms back to
the set of all files. Any file is either an input or output and
any key works. The example I like to use is take a one byte
output file say "0x00" try decrypting it with a thousand different
keys. You will get a thousand different input files each of which
when encrypted with key used for decryption come back to that
same single byte. Many here are not bright enough to understand
the concept and falsely assume that there can only be 256 files
on decryption. The funny thing is the most vocally critic are
so pompus they will not get off there fat asses to even test this
simple fact. Which group are you in?

David A. Scott 

-- 
My Crypto code
http://cryptography.org/cgi-bin/crypto.cgi/Misc/scott19u.zip
http://cryptography.org/cgi-bin/crypto.cgi/Misc/scott16u.zip
http://www.jim.com/jamesd/Kong/scott19u.zip old version
My Compression code http://bijective.dogma.net/
**TO EMAIL ME drop the roman "five" **
Disclaimer:I am in no way responsible for any of the statements
 made in the above text. For all I know I might be drugged.
As a famous person once said "any cryptograhic
system is only as strong as its weakest link"

Relevant Pages

  • Re: A basic cryptanalysis question
    ... Lets accept Shannon's estimate of 1 bit of>>entropy per character of English. ... one in every 2**560 trial decryptions would accidentally resemble English. ... For the short message case you have selected here, compression makes the difference between "breakable" and "nearly perfect" secrecy. ... Many years ago, someone in this group suggested to me that I should use compression to compress the data, and use encryption to encrypt the data. ...
    (sci.crypt)
  • Re: Data Compression Before or After Encryption ?
    ... Then consider english. ... Compression works by finding a more compact notion for languages that ... Out of all the possible sequences of twenty character very few will be ... this mapping has absolutely no effect on a string of random ...
    (sci.crypt)
  • Re: XOR and OTPs used more then once
    ... using only the Cipher output, ... like it is english or account numbers... ... With good compression the number of cipher ... Note the above is advice if you belive in Shanon modern systems are ...
    (sci.crypt)
  • Re: A basic cryptanalysis question
    ... >entropy per character of English. ... so in first case you have no compression you send 5 encrypted blocks. ... On avery how many keys would lead to a valid message. ...
    (sci.crypt)
  • Re: fast static alphabetic (order preserving) compression algorithms/implementations
    ... The algorithm must be unencumbered by patents. ... time required to perform key search on the compressed keys (hence the ... compression keywords and you'll be on your way. ... RDF database, where the keys are an array of three 64-bit long ...
    (comp.compression)
Loading