Cryptography-Digest Digest #460, Volume #10 Thu, 28 Oct 99 11:13:04 EDT
Contents:
Re: Unbiased One to One Compression (SCOTT19U.ZIP_GUY)
Re: Unbiased One to One Compression (SCOTT19U.ZIP_GUY)
Re: Unbiased One to One Compression (SCOTT19U.ZIP_GUY)
Re: Unbiased One to One Compression (Geoffrey T. Falk)
VXD Memory Allocator for Win9x ("Rick Braddam")
Re: This compression argument must end now ("Tim Wood")
Re: Unbiased One to One Compression (SCOTT19U.ZIP_GUY)
----------------------------------------------------------------------------
From: [EMAIL PROTECTED] (SCOTT19U.ZIP_GUY)
Subject: Re: Unbiased One to One Compression
Date: Thu, 28 Oct 1999 03:26:44 GMT
In article <[EMAIL PROTECTED]>, [EMAIL PROTECTED]
(John Savard) wrote:
>[EMAIL PROTECTED] (SCOTT19U.ZIP_GUY) wrote, in part:
>
>> John has refused to comment on how the bias is there. As
>>I have told him at least 3 others times. Replace the last byte of
>>the compressed file with each of the 256 cases. You can then
>>uncompress each one of those files to a unique file. John has
>>yet to comment on this fact.
>
>Well, I came up with a method where 255 of the 256 cases for the last
>byte worked (not yet perfect like yours!) but a byte starting with
>00001 was twice as likely as a byte starting with 0001. Being possible
>isn't the same thing as being equiprobable (there, I've commented).
I am working with eight bit bytes. A last byte starting with 0001 is
obviously more likely then one that is 00001 but that is mainly do
to one is 4 bits long and the other is 5. So I guess I don't see your
point.
>
>Something similar - but apparently with both ...10000 vs ...1000 on
>the end and with ...01111 vs ...0111 on the end, or maybe just with
>one of them, seems to be true of your method as well.
I wish we could get together on a chalk board and hash this
out since I don't think we are going to get there from here.
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: Thu, 28 Oct 1999 03:38:20 GMT
In article <[EMAIL PROTECTED]>, [EMAIL PROTECTED] wrote:
>Geoffrey T. Falk <gtf[@]cirp.org> wrote:
>: SCOTT19U.ZIP_GUY <[EMAIL PROTECTED]> wrote:
>
>:>GTF>For that matter, I have never seen a proof that David's method
>:>GTF>itself introduces no bias. Is a proof of this forthcoming?
>:>
>:> IF you don't have the ability to see that a one to one mapping can
>:>only contain the information that was in a file. There is really not
>:>much I can do to help you. The proof is obvious. Either you have
>:>the IQ to see it or you don't.
>
>: That makes no sense. If your compression has bad statistical
>: properties, it can add information to the file even if it is 1-1.
>: Either you have the guts to admit that, or you don't.
>
>You two appear to be talking at cross purposes.
>
>David is talking about "information" - that which counts as suprising
>stuff the recipient didn't know. o-o-o compression leaves this quantity
>totally unchanged.
>
>Geoffrey is talking about "data" raw bytes.
>
>In one sense, o-o-o compression cannot introduce any "bias" - as it
>doesn't change the total information content of the file.
>
>o-o-o compression - in the cases where it makes files fatter - will
>probably help, rather than hinder analysys, though.
>
>If you use it on such files, it's simply a sign that you're probably using
>a bad compression model for your target data, though.
>
>Using a compressor which inflates your target files is probably a bad
>idea, o-o-o or no o-o-o.
Well Tim you may be right since you appear to understand what I
am driving at and very few other people seem to have a clue. So maybe
Geoffrey and I are talking about different things. I think you would be better
at evaluating that possiblity than me.
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: Thu, 28 Oct 1999 03:57:34 GMT
In article <[EMAIL PROTECTED]>, "Trevor Jackson, III" <[EMAIL PROTECTED]>
wrote:
>Tim Tyler wrote:
>
>> Trevor Jackson, III <[EMAIL PROTECTED]> wrote:
>> : Tim Tyler wrote:
>> :> Trevor Jackson, III <[EMAIL PROTECTED]> wrote:
>> :> : Tim Tyler wrote:
>>
>> :> [ruthless snip of preamble]
>> :>
>> :> : OK, above you mentioned "optimal compression programs". In this context
>> :> : optimality is defined with respect to some probability model. If your
>> :> : probabiliity model is flat, i.e., assumes all bitstrings are expected
>> :> : equally, then the densest compression of any string is the string
>> :> : itself and varitants thereof. I.e., a flat probability model cannot
>> :> : be compressed. No surprise as a flat probability model implies a source
>> :> : of pure entropy; randomness.
>> :>
>> :> ...
>> :>
>> :> : My point however, is distinct from the issue of optimality. For any
>> :> : compression routine, even the trivial copy-input-to-ouput, one can apply
>> :> : transforms that do not increase the file size, but do show that there
>> :> : is always some flexibility in encoding the compressed representation of
>> :> : a bitstring.
>> :>
>> :> : For example, mapping each bitstring onto its inverse is an option. It
>> :> : does not increase the string length of any string [...]
>> :> : The trivial inverstion routine is just as much a compression routine
>> :> : as the trivial copy routine. Thus, given a flat probability model you
>> :> : can choose either as an appropriate and "optimal" compressor.
>> :>
>> :> : For non-flat probability models equivalent encoding transforms exist.
>> :> : This is why I disputed your contention that there can only be one
>> :> : version of a perfectly compressed file.
>> :>
>> :> I said (to paraphrase from memory) "adding randomness to a compressed file
>> :> simply bulks it up".
>> :>
>> :> You appear to be discussing the possibility of choosing randomly between
>> :> a number of equally good compression programs.
>> :>
>> :> Since the best (sizewize) compression programs are one-on-one,
>> :> in order for your partner to decrypt the message you send, they /must/
>> :> know which compressor you are using.
>> :>
>> :> You can't just make a random decision about how to compress, and send the
>> :> message, expecting them to decrpty it. If you send a different message,
>> :> they will decode a different plaintext - since with "optimal" compression,
>> :> decrypting two files to the same message is not a possibility.
>> :>
>> :> If they know the algorithm in advance, there's no possibility of changing
>> :> the algorithm (by, say inverting all the bits).
>> :>
>> :> The /only/ way you can change the algorithm is if you include additional
>> :> information about how you have changed the algorithm with the message.
>> :> This fattens the message up.
>>
>> : Example: static Huffman compression against an alphabet consisting of
> three VHF
>> : characters amounting to 1/2, 1/4, and 1/4 of the message text, and 32 other
>> : characters each amounting to 1/128 of the message text. Thus a "perfect"
>> : compression. Assume at the head of the compressed file you have a table
>> : describing the decompression tree -- the encoded frequency info.
>>
>> What makes you think this the best possible compression of the data?
>> You have made no case to my mind that applying Huffman compression to
>> such a data set is the best possible way of compressing it.
>>
>> I can compress that file to a single bit if you've given it to me in
>> advance, and I can build a compressor to target it. You need to make
>> explict your assumptions about the frequency of the sympbols across a
>> range of target messages before you can e#ven discuss what a pefrect
>> compressor looks like.
>
>I mangled the example, which should have been 3 * 1/4 + 32 * 128. In any case,
> if all
>you know is the frequency of the characters in the message text, what more can
> you
>do? If source has the indicate probabilities then the obvious huffman encoding
>contains 100% entropy density. I.e., the ratio of infromation bits a la
> Shannon to
>data bits is 1/1 (pun intended I suppose).
>
IF all you know is the frequency you can't be guaranteed that what you did
is the best. You need to get more info to model it correctly. If you know
that the frequecys are just right for the huffman tree and that frequency
completely describes the data so no other reducing characteristics can be
taken advantage of then The Static Huffman has been proven to be the best.
Except it was proved to be the best with out consideration to the file ending
problem. In other words it might not end at a nice 8 bit bounary so would be
useless for most files systems. But my scott19u method with very little
modification could handle strange bit lenghts. But I think one still wants
a compression rouitine to end in 8 bit chunks. So even for this problem
you method is not perfect for real files and if you don't use your brain
a little you could cludge a fix that might not be one to one thus adding
info to the compression. Something you really don't want to do.
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: gtf[@]cirp.org (Geoffrey T. Falk)
Subject: Re: Unbiased One to One Compression
Date: Thu, 28 Oct 1999 03:56:43 GMT
In article <[EMAIL PROTECTED]>, Tim Tyler <[EMAIL PROTECTED]> wrote:
>Geoffrey T. Falk <gtf[@]cirp.org> wrote:
>: Again: Simply not being "one-on-one" itself, in general, only helps
>: the attacker if he can guess X and then compute Comp(Decomp(X)).
>
>No. Not at all. No, no, no, no, no!
OK, then give an example where the "not 1-1" helps the attacker, where
he does not know "X" and cannot compute Decomp(X).
g.
--
I conceal nothing. It is not enough not to lie. One should strive
not to lie in a negative sense by remaining silent. ---Leo Tolstoy
ADDRESS ALTERED TO DEFLECT SPAM. UNSOLICITED E-MAIL ADS BILLED $500
Geoffrey T. Falk <gtf(@)cirp.org> http://www.cirp.org/~gtf/
------------------------------
From: "Rick Braddam" <[EMAIL PROTECTED]>
Subject: VXD Memory Allocator for Win9x
Date: Thu, 28 Oct 1999 03:49:22 -0500
I've started working on a VxD for ?secure? memory allocation on Win95/98 (again).
I would appreciate any advice, criticism,
etc. to help with the implementation.
So far, I have a VxD made by modifying the Eatpages example from the Win98 DDK.
It is dynamically loaded. At present it
allocates four two-page control pages and one data page. The test program, in console
mode, outputs the starting addresses of each
page, writes data to the data page, and reads the data back. That was just to verify
that it would work. The pages are allocated
using _PageAllocate, from the system VxD memory space, using PageLocked for the flag.
No page faults or other errors are generated
during operation of the test program. However, I am still allocating 4K for an
allocation request regardless of request size.
Which brings me to the first major problem, Allocation Strategy. A poor choice
here can ruin the whole show. I'm thinking of a
multi-tiered approach as described below. Every allocation request would be tracked by
a structure containing information pertaining
to the request. The structures would be contained in "control" pages and the data in
"data" pages. The Page Control structure would
be as follows:
struct pageControl {
pNext // pointer to next structure
pPrev // pointer to previous structure
pData // pointer to B-Tree root in Data Used and Data Free
control pages
pPage // pointer to beginning of page (used by free())
}
for a total of 16 bytes. That's a lot of overhead for keeping track of pages, but it
may be worth it if it enhances speed and/or
security enough. Note that the pData will not be necessary if I use the first data
structure in each data page for the root B-Tree
pointer.
The Data Control structure used in Data Used and Data Free B-Trees would be:
struct dataControl {
pNext // pointer to next struct in this page
pPrev // pointer to previous struct in this page
pData // pointer to data in data page
LSize // 32-bit size of allocation
pOwner // process ID for access control, if hooking page fault
handler useable for
// access control, otherwise, not used or part of
the struct
}
Twenty bytes per allocation here, if hooking page fault handler can be used to control
access, otherwise only 16 bytes. Allocation
granularity can be one, two, four, eight, or any number of bytes, but must be
determined before compilation.
The Page Control pages would be used to track pages allocated for control pages or
data pages. Structures in the page control pages
would be ordered by Page Number to facilitate quickly adding a page when one is
allocated or deleting one when it is free()d.
The Data Used control pages would track allocations as requested by users. The
structures would be ordered by the data pointers,
since that is how users would indicate freeing them. I'm also thinking of using two
Data Used sets of pages, one for small
allocations, the other for large allocations. I haven't determined the max size of a
small allocation... that is, what size to
switch from small allocation to large allocation. If it's too large, practically all
allocations will be from the small allocation
control pages. That may be OK, though.
The Data Free control pages would track allocations free()d by users. They would be
ordered by size, to facilitate quickly finding
suitable blocks for re-allocation. It may be advantageous to have two sets of prev and
next pointers to be able to order both by
data pointer and size. That would help with consolidating free()d allocations with
previous ones which were contiguous. The strategy
would be consolidate first, then insert ordered by size.
If the first dataControl entry in a Data Control page is the root of the B-Tree, it
will not be necessary to go through the Page
Control to free() an allocation. If a free() releases the allocation pointed to by the
root entry, the page can be free()d and the
Page Control updated.
The second major problem: access control. I haven't yet checked out the page fault
handler to determine if it can be used to control
access to allocations. I know that a page can be marked as "not present" and if
accessed will cause a page fault. I don't know what
my options (if any) are in handling the page fault (if I hook it).
Third major problem: debuggers. I know it is possible to find out if a debugger is
running, at least if it is a Microsoft debugger.
I don't know about other debuggers. I believe I can check to find out if a debugging
kernel is installed, that may help. I would
like to return zero on all requests if debugging is in progress, or perhaps just if
debugging kernel is present / in use.
I'm sure all this will be substantially slower than the default methods. In
particular, secure mallocs and frees would have to go
through the DeviceIOControl interface using createFile() since direct calls from Ring
3 to Ring 0 are protected. However, data
access should be at "normal" speed if access control can not be included, otherwise,
it will also be slower. The reduction in speed
would be limited to secure allocations, which should be used sparingly.
When this is working I have further plans of implementing crypto primitives (ciphers,
hashes, compression, numbers, etc) as either
VxDs or devices. They will use Ring 0 to Ring 0 communication, which should be much
cleaner. It should also simplify user interface
to crypto.
Well, there it is. I'm sure I haven't thought of everything, and I'm looking forward
to your comments. I've written this after a
long shift at work, and am kind of sleepy. If it don't make sense, tell me.
Rick
------------------------------
From: "Tim Wood" <[EMAIL PROTECTED]>
Subject: Re: This compression argument must end now
Date: Thu, 28 Oct 1999 12:36:32 -0500
=====BEGIN PGP SIGNED MESSAGE=====
Hash: SHA1
erm, i'm confused. I thought the point of commpression before
encryption was to remove redundancy in the plaintext. This makes it
less lightly that the same plaintext will be encrypted twice.
However it is well know that having regular structures in the
plaintext can facilitate known plaintext attacks.
Thus an encryption algorhythm should:
remove redundancy in the plaintext.
Not add any regular/predictable information to the plaintext.
Of course this does not make up for cyphers which are not secure, but
it does make the attakers life harder (for instance increasing the
amount of cyphertext he must gather to have a viable attack.)
So if 1-on-1 compresion acheives this it is a good thing. I am
presently looking at Scott's document's and algorhythm, If I get any
results I'll post them here.
Later
Tim
=====BEGIN PGP SIGNATURE=====
Version: PGPfreeware 6.0.2i
iQA/AwUBOBiJnwxsvHBiP5HDEQJ8qwCgjmLyOs/3SIWpgMEW9iM9J07aDdwAnA2u
7VMtVXUICFAR5GtYiWUlVZDR
=WoE1
=====END PGP SIGNATURE=====
------------------------------
From: [EMAIL PROTECTED] (SCOTT19U.ZIP_GUY)
Subject: Re: Unbiased One to One Compression
Date: Thu, 28 Oct 1999 13:53:55 GMT
In article <VKPR3.380$[EMAIL PROTECTED]>, gtf[@]cirp.org (Geoffrey T.
Falk) wrote:
>In article <7v8cuu$1vi8$[EMAIL PROTECTED]>,
>SCOTT19U.ZIP_GUY <[EMAIL PROTECTED]> wrote:
>>Tim Tyler wrote:
>>>You two appear to be talking at cross purposes.
>> Well Tim you may be right since you appear to understand what I
>>am driving at and very few other people seem to have a clue. So maybe
>>Geoffrey and I are talking about different things. I think you would be better
>>at evaluating that possiblity than me.
>
>Well, we must be using different definitions, otherwise we are both
>right, and that's a contradiction :-) We should start again by getting
>our definitions straight.
>
>Again, I'm really not saying that 1-1 compression is a bad idea.
>I'm just saying that you are exaggerating its utility. Relying
>on a 1-1 method as "good" would be a mistake.
But I am saying relyiing on a non 1-1 compression that is
used as a pass before encryption does weaken the overall
encryption.
>
>1-1 compression does not guarantee good statistical properties
>in the output. I really am not trying to establish more than
>this.
1-1 compression progperty alone does not guarnatee good
statistical peoperties in the output. But it does guarntee that
no added information is added to the file for the attacker
to exploit when attacking the encryption process.
With a little thought I think most compression processes
can be modifed to add this property while not affecting the
type of compression the non 1-1 compression was original
designed for. Much like the changes I made to a standard
adaptive huffman coder. Mine is like the original put produces
smaller files. However like I said I have yet a clever way to
get the BTW to act 1-1.
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
------------------------------
** 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
******************************
