Cryptography-Digest Digest #501, Volume #10 Wed, 3 Nov 99 14:13:06 EST
Contents:
Re: Compression: A ? for David Scott (Tim Tyler)
Re: Q: Removal of bias (Mok-Kong Shen)
Re: An encryption proposal from a Newbie... (Scott Fluhrer)
Re: Newbie entropy question.. (Anton Stiglic)
Re: What is the deal with passwords? (wtshaw)
crypto and dependencies ([EMAIL PROTECTED])
Re: Steganography Academy (wtshaw)
Re: cryptohoping (wtshaw)
Re: cryptohoping (wtshaw)
Re: the ACM full of Dolts? (Mok-Kong Shen)
Re: An encryption proposal from a Newbie... (Scott Fluhrer)
Re: crypto and dependencies (Scott Fluhrer)
----------------------------------------------------------------------------
From: Tim Tyler <[EMAIL PROTECTED]>
Subject: Re: Compression: A ? for David Scott
Reply-To: [EMAIL PROTECTED]
Date: Wed, 3 Nov 1999 16:45:49 GMT
Tom <[EMAIL PROTECTED]> wrote:
: On Tue, 2 Nov 1999 22:27:26 GMT, Tim Tyler <[EMAIL PROTECTED]> wrote:
:>Tom <[EMAIL PROTECTED]> wrote:
:>: On Sun, 31 Oct 1999 11:34:34 GMT, Tim Tyler <[EMAIL PROTECTED]> wrote:
:>:>Tom <[EMAIL PROTECTED]> wrote:
:>:>: On Sat, 30 Oct 1999 17:29:55 GMT, Tim Tyler <[EMAIL PROTECTED]> wrote:
:>:>:>Tom <[EMAIL PROTECTED]> wrote:
[snip]
:>:>One-on-one compressors have only just been invented. I don't know if
:>:>people have been very interested in quantifying how bad non-one-on-one
:>:>compressors are before now.
:>
:>: If "one-on-one" (symmetric compression) was better at reducing
:>: patterning, the files would be smaller
:>
:>Indeed. When I said "bad" I was referring to giving away information to
:>attackers, not *just* file size.
: But what's the difference? If you don't compress as well, you have
: more patterning, thus more information to potential attackers.
For one thing, one type of information may /always/ be present - while the
other depends for its existence on patterns in the input files.
:>:>Certainly I'm more interested in building compressors which avoid adding
:>:>clues of their own to files than I am in measuring /exactly/ how shafted
:>:>ordinary compressors are on this front ;-)
:>
:>: Or if they are at all!
:>
:>They are. They add information. It has been demonstrated for a number of
:>compressors. In fact, no other one-on-one compressor has been found yet.
: Or in another form: Say an uncompressed file contains X amount of
: information in Y bytes, yet can be represented in Z bytes in
: compressed form. This means that the uncompressed file contains Y-Z
: bytes of redundant information, which is effectively known
: information. In general, if the information added by compression is
: less than the redundant information removed, you have an improvement.
It depends. If the "added information" is of the same form for evey
possible type of file being sent, you may well be worse off,
despite there being less patterned information overall.
: To say that non symmetrical compression is advantageous because it
: guarantees that any possible output is possible, even those with
: patterns, is to say that a traditionally compressed file is a weakness
: because it has no patterns. [...]
Unfortunately, /both/ of these phrases appear to misstate our position.
:>How severe the problem is, and how easy it is for analysts to make use of
:>the information has not been so widely studied, AFAIK.
:>
:>: If the point is to reduce patterning, why not address that [...]
:>
:>The point is to increase the entropy per bit. You *can't* increase the
:>entropy of the whole file, without injecting "real" randomness.
:
: No, but you can increase the entropy per bit by compressing the file.
: Without any measure of overall entropy discussed or suggested, the
: only sure way to maximize the result is to minimize the file size.
Maximising entropy per-bit involves using the best (size-wise)
compressor available.
However, maximising this value is /not/ the only priority - if the best
compressor you have available adds information in an obviously patterened
way to the files it produces, using it will be the source of possibly
severe security problems.
:>: I can certainly understand the rationale for looking at compression
:>: without added patterning, but what does symmetry have to do with it?
:>
:>It's a condition which prevents the compressor from adding information of
:>its own making to the file, when the one-on-one property is present.
:
: In doing so it *must* be weaker in compression, as in some cases it
: will make the file larger!
I keep hearing this utterly worthless point repeated.
*All* lossless compressors will make some input files larger. SO WHAT?
: So we come back to the information per byte question, or even the
: overall information question. Again, if overall information were the
: issue, file size would be more related to decryption ease than it is.
Are you sure you have distinguished information from data in the above?
It is quite possible for a large file can transmit precious little
information.
:>:>: Everything I've seen has been subjective, based on viewing the file, or
:>:>: anecdotal; and even these examples weren't specific as to whether the
:>:>: patterning was confined to the header and footer or not.
:>:>
:>:>Perhaps you need to look again at the eariler posts. David has discussed
:>:>ordinary Huffman compression on a number of occasions. This is now the
:>:>third time I have mentioned that LZ compression schemes typically map both
:>:>"3X + 5X" and "4X + 4X" and "8X" to "XXXXXXXX".
:>
:>: But that's an example of a pattern in the input, not the output.
:>: We're not talking about the input.
:>
:>?
:>
:>These patterns are in the input to the decompressor.
: But that's not an example of patterning on the output of the
: compressor, which for use with encryption is the only part that
: matters. [...]
My example was intended to demonstrate that a common compression system
systematically added information to the file, in a manner not confined to
the file's header/footer.
Your latest objection seems to indicate that you were under the impression
I was attempting to demonstrate something else...?
:>They illustrate clearly that the non-one-on-one property can be
:>distributed throughout the file - and not confined to "headers".
:
: But this example does not show that standard compression adds
: information.
It /does/. Assuming the attacker knows that a given encryption system has
been used, then he can eliminate keys based purely on failure of
Xomp(Decomp(X)) to equal X. This is information about the file's
contents he didn't have before compression was employed.
[much snip]
:>Information added by the compressor may be qualatitatively different from
:>redundant information in the plaintext that has not been squeezed out.
: I'd agree. But is this information more useful to the attacker than
: the patterning left in the file by less than optimal compression?
Very possibly. It may not depend on the data being sent for example.
:>In particular information added may be essentially the same in every file,
:>independent of the plaintext of the messages.
:
: This is certainly a problem, and I'm calling it "housekeeping
: information" & will describe what I mean below.
:>You should be able to see why we are emphasising "added information" over
:>"redundancy that has failed to be squeezed from the messages" from this.
:
: I can see you're emphasizing it, but don't believe that one type of
: information is more valuable than the other to an attacker.
That depends on the files being transmitted, the relative volumes of the
information, etc.
Part of the reason I'm emphasising it is that everyone understands why a
low compression ration can be bad. However, the point about added data
seems very important, yet is apparently not so widely gasped.
:>If the compression is good enough, /all/ decompressed messages will
:>look plausible.
: That can't be true. [...]
*Sure* it can. Say only a hundred messages are to be sent.
A pretty good way of compressing them is to number the messages from 1
to 100 and send the number, rather than the message.
:>: Finally, it seems of interest only for a brute force attack, and
:>: this shouldn't be a concern with a decent algorithm and key size.
:>
:>I agree that brute-force attacks should not get too much attention.
:>
:>However, there will be cases where the attack can be used.
:>
:>Imagine you have extractes 102 bits of the key from agent orange before he
:>commits suicide.
:>
:>Suddenly a brute-force attack on the remainder becomes plausible.
:>
:>There are other circumstances in analysis where the ability to rule out
:>particular keys is useful.
: But you could still do this by using one-on-one, by simply
: decompressing. [...]
Not if decompressing always results in plausible-looking files.
: Additionally, brute force seems a lot likely than chosen plaintext, as
: discussed in other posts and a weakness of one-on-one.
Was that "more" or "less" likely?
I don't see chosen-plaintext attacks as a weakness of one-on-one
compression.
Perhaps someone has an example of where compression has seriously hindered
an attacker from making a chosen-plaintext attack?
:>:>: I'll grant you that poor compression can increase patterning, and provide
:>:>: for known plaintext attacks, but again, unless random data or a keyed
:>:>: system is added, the compression will still result in some form of
:>:>: known plaintext attack being possible.
:>:>
:>:>This appears to be a questionable notion. In the case where compression
:>:>reduces the size of the message to the size of the key, the entire system
:>:>reduces to a OTP.
:>
:>: Even if it's a OTP, it still allows a known plaintext attack.
:>
:>Yes, /if/ the keys have been generated by a less-than perfectly random
:>process, such an attack might work.
:
: OTP is always vulnerable to known plaintext.
If you know the entire plaintext, you can recover the key.
Unfortunatey this is of little use with any other messages - unless
the key-generation is less-than perfectly random.
:>:>Perhaps. However it depends on the volume of information concerned
:>:>in each case, and various other factors.
:>:>
:>:>Note that the compressor may add the /same/ type of regularity to all the
:>:>files it treats, even random files where an analytic attack based on
:>:>patterns in the data would not normally be feasible.
:>:>
:>:>You need to quantify your problems before claiming one is smaller than
:>:>another. With qualatatively different security problems - such as the
:>:>ones faced here - this can be difficult.
:>:>
:>:>Fortunately - in principle - both problems can be eliminated.
:>:>
:>:>However "perfect" compressors are rare beasts - but fortunately there
:>:>is at least one compressor that has completely eliminated the other
:>:>problem.
:>:
:>: Having a compressor that doesn't have a defined header format or CRC's
:>: is certainly an advantage, but I don't see how that has anything to do
:>: with the concept of "one-on-one".
:>
:>It doesn't necessarily. Did anyone claim otherwise?
:
: The added information of pkzip has been used as an argument for
: one-on-one
That's different. The sentence above seemed to imply the lack of a header
implied the one-on-one property. It does not.
:>: That the compression is non-symtetrical or non-unique doesn't equate
:>: with added data.
:>
:>Yes it does. Sorry.
: In that non perfect, non one-on-one reduces the number of possible
: values at the output of the compression, you're right. But I'd
: contend that what were talking about is mapping the input file to a
: smaller output file which is a subset of all possible output files of
: that size. In other words, the added information is specifically
: because the compression isn't perfect. If the compression were
: perfect, then the set of possible output files would be the same as
: the set of all possible files of the same size. Even if you can prove
: that this must be a one-on-one compression [...]
Up to here seems largely OK.
: it doesn't prove that the quality of not being-one-on-one adds information.
The proof you mention doesn't lead to this conclusion, it's true.
However, failure to be one-on-one means the attacker can rule out
certain keys on a-priori grounds. He wasn't able to do this before the
compression was employed. He has gained information about the encryption
process. This information is not contained in a knowledge of the
compression technique used /alone/. This information must have come from
somewhere ;-)
:>:>There are probably patterns in the compressed file remaining from
:>:>inadequate compression - but that has nothing to do with wther or not
:>:>there are additional patterns generated by the compressor there as well.
:>:
:>: I would agree - there are two issues. I'd contend that the patterns
:>: resulting from inadequate compression would tend to be lower with
:>: compression algorithms of higher compression ratio, and I again
:>: haven't seen examples of patterns added by compression, again
:>: excepting housekeeping information, which of course is a problem.
:>
:>What counts as "housekeeping information"?
: Used the term loosely. Apologies. Was referring to the typically
: well defined header left by compression programs, as well as error
: checks and formatting information left at the end of a file.
...and *not* (say) other potential added information, such as
referencing dicrtionary entries before they have been defined,
and so forth?
:>:>:>No. Most compression programs are specifically designed not to do this.
:>:>
:>:>: I'll agree with programs, but not algorithms, as the programs add the
:>:>: CRC information you've mentioned. This I'll also agree is a problem,
:>:>: especially if there are checksums scattered within the file.
:>:>
:>:>Algorithms with no concern for error recovery or detection may not be
:>:>"designed to do this". A number of them do /still/ scatter their own data
:>:>carelessly through the file, though. See the LZW family, for example.
:>
:>: But how much is added patterning, and is this more than they gain by
:>: having a higher compression ratio?
:>
:>Added patterning is fifferent from failure to compress as well as is
:>possible. Different types of attack result.
:>
:>You can't very usefully say one is "more" than the other - unless
:>one of them is zero.
: I'd say that sounds true even if one didn't add information. [...]
That would be the "zero" case I mentioned.
: We're trying to figure out which is better to leave/add, without having
: quantitative information about either the value of the types of
: information or the amount. Seems pointless.
We can eliminate one source of added information completely.
Hopefully soon we will be able to do this iwth no cost in terms of
compression ration for a range of data types.
Since it appears that one security problem can be eliminated,
it makes sense to try to eliminate it.
: I'm beginning to see both have weaknesses, and am wondering if the
: "added" information of standard compression is just the byproduct of
: non optimal compression [...]
Definitely not in /theory/. All the best compressors are one-on-one.
--
__________
|im |yler The Mandala Centre http://www.mandala.co.uk/ [EMAIL PROTECTED]
- This space for rent -
------------------------------
From: Mok-Kong Shen <[EMAIL PROTECTED]>
Subject: Re: Q: Removal of bias
Date: Wed, 03 Nov 1999 17:39:16 +0100
Tom St Denis wrote:
>
> In article <[EMAIL PROTECTED]>,
> Mok-Kong Shen <[EMAIL PROTECTED]> wrote:
> > Could anyone give references to practical results of removal of
> > bias in random number/bit sequences, showing the efficiency of
> > the techniques? Thanks in advance.
> >
> > M. K. Shen
>
> Efficient?
>
> For x = 0 to size
> Ax = 0
> For y = nx to nx + n
> Ax = Ax xor By
> next y
> next x
Please re-read my sentences to see whether you were answering
to that. I was questioning whether there are publically availbable
results of removing statistical bias from given random number/bit
sequences and whether the techniques involved prove to ge good
in practice. What has your program have to do with that at all???
M. K. Shen
------------------------------
From: Scott Fluhrer <[EMAIL PROTECTED]>
Subject: Re: An encryption proposal from a Newbie...
Date: Wed, 03 Nov 1999 16:46:50 GMT
In article <[EMAIL PROTECTED]>,
[EMAIL PROTECTED] (CoyoteRed) wrote:
>On 3 Nov 99 12:47:01 GMT, [EMAIL PROTECTED] () wrote:
>
>>
>>I think some schemes of this type have been proposed and used in real
>>life. IBM has SEAL, and there was another scheme based on a large pool of
>>random numbers that was even exportable because it included key escrow.
>
>I thought it couldn't have been an original idea... :)
>
>>
>>One weakness is that you're sending the 64 bit key in the clear, and it
>>*could* be a key with very few 1 bits in it.
>
>Well, the key would encrypted with an asymmetrical key. See "Next, we
>use our partners public key to encrypt our 65 bit index key
>and add it to the beginning of our ciphertext." in my message.
>
>One thing I thought of is if the attacker ever broke the asymmetrical
>system and he could go back and decrypt all of the previous messages
>and get these index keys. Now if we had ever used a index key with
>only 1 bit "on" then he has that one 1k file, bang, in the clear and
>that message (or portion) is decrypted. We would have to test for
>"weak" keys. So therefore we would have somewhat less than 2^64
>possible indexes and thus possible random files.
Actually, if the attacker ever broke the asymmetrical system (and has
reasonable guesses for 64 of your messages), he's got the entire
system. Using linear algebra, he can rederive the original 1k files,
and then can read everything.
>I'm also running with the idea that you can XOR any combination of
>these 1k files and get an equally random file out. If you can, then
>the strength relies on the 64 bit index key and it's protection. But
>once the key's protection is broken then we have to rely on not using
>any "weak" keys.
>
>As I see it so far, a "weak" key is a key that is only 1 bit off from
>a previously used key (which also then becomes "weak.") This would
>mean that we automatically cut our number of usable keys by half.
>(...and much more if my suspisions are correct.) So, the next question
>is: just how many strong keys do we have and how do we get back to
>having more strong keys?
Nope: you don't have to worry about "weak" keys (other than the all-0
key, obviously). Any linearly independant combination of 64 messages
will allow an attacker who remembers what he learned in math class to
break it.
Oh, and I don't think this scheme is as blazingly fast as you think.
Glancing through it looks like it should take about 16 cycles per byte
(assuming everything's in cache, which might be tricky) to implement,
which is (IIRC) about as fast as Twofish.
--
poncho
------------------------------
From: Anton Stiglic <[EMAIL PROTECTED]>
Subject: Re: Newbie entropy question..
Date: Wed, 03 Nov 1999 11:42:30 -0500
> I think your confusion arises from a question of message-length units.
> The rate of normal English is between 1.0 and 1.5 bits/letter (I think
> that's a little low, but let that pass). Inherent in this measurement
> is that you are counting the message length in *LETTERS*; and, of
> course, there are more than two letters... in fact, there at least
> twenty-six, depending on how you count.
> [...]
> -kitten
I beleive kitten has correctly spoted the source of error (which many
people make). In fact, Stinson has a better formula:
the rate of a language is in fact
R = 1 - H_L/H(P)
where P is the set of letters, and H_L is defined by:
H_L = limint n-> infinity of H(P^n)/n
where P^n is the set of n-digrams (n successive letters).
See Stinson's book. I think Mr Schneier over simplyfied things a bit
here.
Anton
------------------------------
From: [EMAIL PROTECTED] (wtshaw)
Subject: Re: What is the deal with passwords?
Date: Wed, 03 Nov 1999 10:55:20 -0600
In article <[EMAIL PROTECTED]>, "Trevor Jackson, III"
<[EMAIL PROTECTED]> wrote:
> Tom St Denis wrote:
>
> > But the chances of someone stealing my floppy disk is about the same as
> > me inventing a brain ray and stealing your thoughts.
>
> Actually the chance is much smaller. Zero to be precise. OTOH, the chance
> of someone _copying_ your floppy is much higher. Idle cusriosity on the
> part of an "opponent" or even a f(r)iend, and a moment's inattention by you
> is all it takes.
>
> And you would never know.
And, the fact that you chose a recycled AOL floppy that is destined to die
when you most need it should make you want to actually remember a
password/passphrase.
--
Geo. W. never met a dollar he did not like.
As for people, he likes their dollars.
------------------------------
From: [EMAIL PROTECTED]
Subject: crypto and dependencies
Date: Wed, 03 Nov 1999 16:42:07 GMT
I'm trying to build a model for Internet Security, one component
of which is cryptography. Upon what (example: time, bandwidth, ...)
does "cryptography" depend for the purpose of generating capability
trends?
Thank you
Sent via Deja.com http://www.deja.com/
Before you buy.
------------------------------
From: [EMAIL PROTECTED] (wtshaw)
Subject: Re: Steganography Academy
Date: Wed, 03 Nov 1999 11:10:58 -0600
In article <[EMAIL PROTECTED]>, [EMAIL PROTECTED]
(Johnny Bravo) wrote:
> On Tue, 02 Nov 1999 18:14:36 GMT, [EMAIL PROTECTED] (SCOTT19U.ZIP_GUY)
> wrote:
>
> >break the scott16u contest. I hope my encryption which is orders of
> >magnitude stronger than the weak short keyed methods of the AES
....
>
> You have stated on numerous occasions the AES finalists are weak, prove it.
> Or are you just dealing in snake oil.
>
In the light of my definition of what constitutes a strong cipher, how
much plaintext must be involved to confirm the correct key, all AES
candidates are near or in the weak category axiomaticaly.
--
Geo. W. never met a dollar he did not like.
As for people, he likes their dollars.
------------------------------
From: [EMAIL PROTECTED] (wtshaw)
Subject: Re: cryptohoping
Date: Wed, 03 Nov 1999 11:18:31 -0600
In article <toKT3.22552$[EMAIL PROTECTED]>, "Steven
Alexander" <[EMAIL PROTECTED]> wrote:
> Couldn't this actually detriment security if the same key was used for
> different algorithms? If attacks against the different algorithms were able
> to recover different key bits this could actually weaken security. The
> solution is of course, to use different keys for different algorithms.
>
Different algorithms can create keys in different ways. There are
incredible many ways to do this kind of thing to keep algorithms and their
respective key structures different.
If you are looking at a simpler key structure, then you must ask is one
algorithm is useful in the break of another, a possible touchy subject.
--
Those who think that all useful encryption is done in binary
are destined to be thought of as mere bit-players.
------------------------------
From: [EMAIL PROTECTED] (wtshaw)
Subject: Re: cryptohoping
Date: Wed, 03 Nov 1999 11:14:22 -0600
In article <[EMAIL PROTECTED]>, fungus
<[EMAIL PROTECTED]> wrote:
>
> ....A brute-force search for
> and n-bit key is still a brute-force search for an n-bit key,
> no matter how weird the algorithm is.
>
Unless bits are not involved. Unexpected and useful weirdness is nice for
some, ungodly awful for others.
--
Those who think that all useful encryption is done in binary
are destined to be thought of as mere bit-players.
------------------------------
From: Mok-Kong Shen <[EMAIL PROTECTED]>
Subject: Re: the ACM full of Dolts?
Date: Wed, 03 Nov 1999 17:57:13 +0100
Tim Tyler wrote:
>
> Mok-Kong Shen <[EMAIL PROTECTED]> wrote:
> : Tim Tyler wrote:
>
> :> How does your partner (to whom you are sending the message) get
> :> information relating to this distribution? [snip]
>
> : One way could be like this: One uses an agreed upon PRNG to generate
> : the intitial frequencies and load that into the adaptive Huffman. As
> : mentioned previously, this means however that the partners use, in
> : addition to the key of the proper encryption, some additional key
> : bits (the seed of the PRNG).
>
> You have, in effect, increased the size of the key.
>
> It is thus not terribly suprising that the attacker will probably have a
> harder time of breaking the resulting system.
I thought that my sentences contain in meaning what you wrote.
M. K. Shen
------------------------------
From: Scott Fluhrer <[EMAIL PROTECTED]>
Subject: Re: An encryption proposal from a Newbie...
Date: Wed, 03 Nov 1999 17:12:31 GMT
In article <[EMAIL PROTECTED]>,
[EMAIL PROTECTED] (CoyoteRed) wrote:
>On Wed, 03 Nov 1999 03:50:06 GMT, "Douglas A. Gwyn" <[EMAIL PROTECTED]>
>wrote:
>
>>CoyoteRed wrote:
>>> It has nearly the security of a OTP, it's not as secure because ...
>>
>>Your example had a lot of discrepancies, but it didn't seem
>>very "secure" to me... How are you determining its "security"?
>
>Could you please point out the discrepancies.
After thinking about it, I realized how you can break it, even
assuming the asymmeteric system is perfect. The attacker needs:
- 70 known plaintexts (that is, about 70 1k outputs of your
program, using unknown keys)
- 70 known bits from the 1k message you're trying to read
Then, using the 70 known bit positions and the 70 known plaintexts,
the attacker can (with high probability) use linear operations to
form a 64x64 identity matrix (I specify 70 because a few spares
increases the probability of there being 64 independant vectors).
Once he has done that, he has 64 vectors which are equivilant to
the secret 1k files, and can then be directly used to break the
unknown message.
--
poncho
------------------------------
From: Scott Fluhrer <[EMAIL PROTECTED]>
Subject: Re: crypto and dependencies
Date: Wed, 03 Nov 1999 17:17:07 GMT
In article <7vpokv$2st$[EMAIL PROTECTED]>,
[EMAIL PROTECTED] wrote:
>I'm trying to build a model for Internet Security, one component
>of which is cryptography. Upon what (example: time, bandwidth, ...)
>does "cryptography" depend for the purpose of generating capability
>trends?
Your question is really unclear. To answer precisely what you asked:
"cryptography" does not try to generate capability trends, so it
doesn't depend on anything to do it. (:-)
Maybe you want to reask your question, this time stating what you
are asking clearly.
--
poncho
------------------------------
** 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
******************************
