Cryptography-Digest Digest #103, Volume #12 Sun, 25 Jun 00 14:13:01 EDT
Contents:
Re: Compression and known plaintext in brute force analysis (restatements caused by
the missing info .... thread) (zapzing)
Re: Compression and known plaintext in brute force analysis (restatements caused by
the missing info .... thread) (Guy Macon)
Re: Compression & Encryption in FISHYLAND (wtshaw)
Re: Compression & Encryption in FISHYLAND (wtshaw)
Re: Compression & Encryption in FISHYLAND (tomstd)
Re: "And the survey says" ("Scott Fluhrer")
Re: Compression & Encryption in FISHYLAND (Tim Tyler)
Re: Variability of chaining modes of block ciphers (Tim Tyler)
Re: Compression and known plaintext in brute force analysis (restatements caused by
the missing info .... thread) (wtshaw)
Re: Quantum computing ([EMAIL PROTECTED])
Re: MD5 Expansion (David A. Wagner)
Re: Variability of chaining modes of block ciphers (Mok-Kong Shen)
Re: Variability of chaining modes of block ciphers (Mok-Kong Shen)
Re: software protection schemes (JPeschel)
----------------------------------------------------------------------------
From: zapzing <[EMAIL PROTECTED]>
Subject: Re: Compression and known plaintext in brute force analysis (restatements
caused by the missing info .... thread)
Date: Sun, 25 Jun 2000 15:07:50 GMT
In article <[EMAIL PROTECTED]>,
"Douglas A. Gwyn" <[EMAIL PROTECTED]> wrote:
> zapzing wrote:
> > And another problem: suppose a random (or already encrypted)
> > file is encrypted. Then an amount of predictable
> > information will be added to a file that was previously
> > perfectly unpredicatble.
>
> ? That is false in general.
A "compression" program cannot "compress" all
files, while still maintaining the same amount
of information. If you attempt to compress a
random file, therefore, the resultant
"compressed" file will actually be larger.
Either there must be a short header (perhaps
only one bit) that states "this looks random
to me - I couldn't compress it" or some sort
of table must be transmitted which states
something like "each character represents
itself" or something like that (I cannot
help being vague because the exact situation
depends on the exact compression algorithm
used.)
If you still disagree, I challenge you to
present a "compression" algorithm that will
compress *all* files without loss of
information.
--
If you know about a retail source of
inexpensive DES chips, please let
me know, thanks.
Sent via Deja.com http://www.deja.com/
Before you buy.
------------------------------
From: [EMAIL PROTECTED] (Guy Macon)
Subject: Re: Compression and known plaintext in brute force analysis (restatements
caused by the missing info .... thread)
Date: 25 Jun 2000 12:05:21 EDT
zapzing wrote:
>
>
>In article <[EMAIL PROTECTED]>,
> "Douglas A. Gwyn" <[EMAIL PROTECTED]> wrote:
>> zapzing wrote:
>> > And another problem: suppose a random (or already encrypted)
>> > file is encrypted. Then an amount of predictable
>> > information will be added to a file that was previously
>> > perfectly unpredicatble.
>>
>> ? That is false in general.
>
>A "compression" program cannot "compress" all
>files, while still maintaining the same amount
>of information. If you attempt to compress a
>random file, therefore, the resultant
>"compressed" file will actually be larger.
>Either there must be a short header (perhaps
>only one bit) that states "this looks random
>to me - I couldn't compress it" or some sort
>of table must be transmitted which states
>something like "each character represents
>itself" or something like that (I cannot
>help being vague because the exact situation
>depends on the exact compression algorithm
>used.)
>
>If you still disagree, I challenge you to
>present a "compression" algorithm that will
>compress *all* files without loss of
>information.
One slight correction; The above is true for some random files
and not true for others. A 100K random file has a very small
but still non-zero chance of being all zeros, a chapter from
shakespeare, etc.
No compression program can compress all random files, but all
compression programs can compress some random files.
------------------------------
From: [EMAIL PROTECTED] (wtshaw)
Subject: Re: Compression & Encryption in FISHYLAND
Date: Sun, 25 Jun 2000 09:48:24 -0600
In article <[EMAIL PROTECTED]>, tomstd
<[EMAIL PROTECTED]> wrote:
> Simon Johnson <[EMAIL PROTECTED]> wrote:
> >Then again, you could always put your differences behind you.
> >Rather than trying to slur each other.
> >
> >I don't know, maybe i'm wrong.
> >
> >S. Johnson
>
> Here's something funnier. Some attacks actually work better
> against compressed data. The full 16r Differential Attack on
> DES for example doesn't work so well with only ASCII plaintext
> blocks...
>
> Anyways...
>
> Tom
>
That means that DES was less than universal, but we know that already.
Imaging that with all other ciphers that ASCII always is the best idea
uses the same bad emphasis on narrow logic.
--
Some Turkeys can fly, for short distances. If you are to depend on
birds for communication, if it's with turkeys, consider the
discussions that might occur while feasting on one.
------------------------------
From: [EMAIL PROTECTED] (wtshaw)
Subject: Re: Compression & Encryption in FISHYLAND
Date: Sun, 25 Jun 2000 09:43:23 -0600
In article <[EMAIL PROTECTED]>, tomstd
<[EMAIL PROTECTED]> wrote:
> "David S. Hansen" <[EMAIL PROTECTED]> wrote:
> >WTF??
> >
> >Where on earth did you get the impression that this Scott guy
> >is an "arrogant foolish mean person"? Is June 23rd National
> >Presumptuous Bastards Day or something?
>
> You must be new here. I know I should be polite and I know I
> should just ignore him but he gets the best of me. He is rude,
> ignorant and just plain mean.
>
Have you watched C-SPAN lately? It seems that all, at times, are capable
of gushing when the pressure might be otherwise directed. I might, even
me, get a little excited and stand atop the Acme soapbox occationally.
What bothers me more is when there is lots of zeal and little intelligent
thought somewhare behind it, or when people are afrid to say anything in
public.
There are lots of reasonable gripes about the technical side of
cryptography, and there should be in a true scientific sense. There is no
room for worship in seeking the truth, but all like praise when what they
say is memorable, and dislike criticism, even when they deserve it.
--
Some Turkeys can fly, for short distances. If you are to depend on
birds for communication, if it's with turkeys, consider the
discussions that might occur while feasting on one.
------------------------------
Subject: Re: Compression & Encryption in FISHYLAND
From: tomstd <[EMAIL PROTECTED]>
Date: Sun, 25 Jun 2000 09:22:25 -0700
[EMAIL PROTECTED] (wtshaw) wrote:
>In article <[EMAIL PROTECTED]>, tomstd
><[EMAIL PROTECTED]> wrote:
>
>> Simon Johnson <[EMAIL PROTECTED]>
wrote:
>> >Then again, you could always put your differences behind you.
>> >Rather than trying to slur each other.
>> >
>> >I don't know, maybe i'm wrong.
>> >
>> >S. Johnson
>>
>> Here's something funnier. Some attacks actually work better
>> against compressed data. The full 16r Differential Attack on
>> DES for example doesn't work so well with only ASCII plaintext
>> blocks...
>>
>> Anyways...
>>
>> Tom
>>
>That means that DES was less than universal, but we know that
already.
>Imaging that with all other ciphers that ASCII always is the
best idea
>uses the same bad emphasis on narrow logic.
I don't follow ya. I never intended to suggest that compression
will make it weaker, I just wanted to point out an interesting
observation about how compression can make a cipher stronger
(which it can't).
Tom
Got questions? Get answers over the phone at Keen.com.
Up to 100 minutes free!
http://www.keen.com
------------------------------
From: "Scott Fluhrer" <[EMAIL PROTECTED]>
Subject: Re: "And the survey says"
Date: Sun, 25 Jun 2000 09:13:42 -0700
Paul Pires <[EMAIL PROTECTED]> wrote in message
news:L_955.35834$[EMAIL PROTECTED]...
> Care to indulge in an experiment?
>
> I wanted some input on something that has been bothering me for awhile.
Some
> old hands in here seem to be coming from a particular viewpoint that
modern
> symmetric ciphers contain all of the cryptographic art that could be
> desired. To my knowledge, that viewpoint has never been stated. I was
> wondering if a tabulation of viewpoints might be useful.
>
> What would be the attributes of an "Ultimate" symmetric cipher and how do
> the various approaches compare to this yardstick? Notice, I said
Attributes.
> Is it possible to describe the cage that this beast lives in and therefore
> understand the beast itself? Other disciplines pursue design by first
> defining the constraints and required degrees of freedom required of a
> solution. Would this approach have benefit here?
Ok, if you want a fantasy list of what properties the perfect symmetric
cipher would have, how about:
1. Provable security. A formal proof that any Turing machine with an
encryption/decryption constrained [1]oracle, given a ciphertext encrypted
with a random key, is unable to find the corresponding plaintext with
probability greater than epsilon in less than (huge number) of steps. Or, a
proof of something at least as interesting.
2. Efficiently implementable. It can be done with a minimum of memory/gates
on hardware, and any CPU anyone is interested in
3. Fast. It should be take perhaps 1 cycle per byte encrypted/decrypted on
a high end CPU, and not that much slower on low end CPUs. Oh, and it should
be blazingly fast in hardware too.
4. Key agility. There should be no penalty for switching keys.
5. Build in MAC. The algorithm should have an optional MAC property that,
if you switch it on, causes minor ciphertext expansion and possibly minor
slowdown, and has provable forgability resistance.
6. Plaintext size. It should be able to encrypt/decrypt any length of
plaintext, not just those at a particular 'block boundary'.
7. Ciphertext expansion. Without the MAC feature turned on, there should be
no ciphertext expansion.
8. Moderate key size. Key size should not need to be any longer than what
can be convienently transported using current public-key operations.
256-512 bits would be good. I'm willing to make them a bit larger to get
property #1 (:-)
Now, obviously, no known cipher has all, or even most, of these properties.
For that matter, I don't know of any cipher (practical or impractical) that
has property #1 (with an Oracle, you can break an OTP trivially). Those
ciphers that do fufill (or at least come close to fufulling) a subset of
these properties have other drawbacks that make them inapplicable to other
applications. In other words: you need to select the appropriate cipher for
the application.
I'll let others decide whether all the items on the list are relevant
(although, I believe every item is useful for some application), or there
are other items that should be on the list. And, I'll let others list how
various ciphers come close to meeting items on this list.
[1] The constraint on the Oracle is that you can't ask the decryption of the
input ciphertext.
--
poncho
------------------------------
From: Tim Tyler <[EMAIL PROTECTED]>
Subject: Re: Compression & Encryption in FISHYLAND
Reply-To: [EMAIL PROTECTED]
Date: Sun, 25 Jun 2000 15:51:39 GMT
John Savard <[EMAIL PROTECTED]> wrote:
: [...] a method of converting Huffman-coded compressed text into a
: whole number of bytes which, since it offers a bijective mapping
: of input random-bit-length symbol-terminating messages to
: integral-number-of-bytes arbitrary messages, is claimed to produce
: unbiased output bytes. I have disputed that claim; my take on
: the basic ideas involved can be found at
: http://home.ecn.ab.ca/~jsavard/crypto/mi060303.htm
: The idea of using what I call a "pseudo-Morse" code for the last
: symbol - which I think is sort of like the first half of what he does
: for his compression (I'm not sure it's what he does, and in any case I
: suspect it's an old idea that's been around a long time: if not, I may
: have to change this page to give him credit by name) - is valid, but
: while padding with 10000..., the standard technique used in SHA, is
: bijective, it is not unbiased. I believe his technique, which is *not*
: that technique, has the same sort of bias.
I've read - and attempted to understand - the section entitled
"Terminating Compression" on the page of yours you cited.
It's not entirely clear to me what you're claiming for this Huffman ending
scheme.
It seems to say that it provides a method of allowing arbitrary messages
to terminate on byte boundaries.
Yet looking at what you're proposing (and comparing it to what David
did), it seems that your method can't possibly work, since do don't
appear to do anything equivalent to his "recursing" backwards into the
file when choosing your final Huffman symbol. I beleive /something/ like
this is necessary for a proper ending scheme.
I can see how this would allow byte-terminated messages to decompress to
something - but does your method produce a bijection?
Having arbitrary byte streams decompress to something is trivial -
what is desirable (and non-trivial) is that they should compress to
something *unique*.
I don't think your scheme can possibly produce a bijection.
You say various negative things about the code David has written.
When you "dispute his claim" - are you saying David has /failed/ to
get a bijection?
If so, a counter example - in the form of a message that doesn't
recompress to what it was decompressed from - should exist.
If you claim his method is "biased", you might need to me more specific.
Nobody's claiming that David's compressor always produces an unbiased
stream of output - in the sense that all output bytes occur with equal
frequency. What sort of bias are you talking about?
The padding used in SHA doesn't seem to be a suitable comparison.
It only produces unique results if you append the length after the,
padding. As a form of pre-compression padding, this would not be good.
FWIW, I think David's ending scheme is about as good as you can get.
There may be other, equivalent schemes, but I don't /think/ there will
be any that improve upon it.
--
__________ Lotus Artificial Life http://alife.co.uk/ [EMAIL PROTECTED]
|im |yler The Mandala Centre http://mandala.co.uk/ Namaste.
------------------------------
From: Tim Tyler <[EMAIL PROTECTED]>
Subject: Re: Variability of chaining modes of block ciphers
Reply-To: [EMAIL PROTECTED]
Date: Sun, 25 Jun 2000 16:03:15 GMT
Mok-Kong Shen <[EMAIL PROTECTED]> wrote:
: Tim Tyler wrote:
:> Mok-Kong Shen <[EMAIL PROTECTED]> wrote:
:> : Eric Lee Green wrote:
:> :> Mok-Kong Shen wrote:
:> :> > [...] By combinatorics this gives 8 variants.
:> :>
:> :> Great. You just added 3 bits to the key space [snip at what expense]
:>
:> : If you use CBC, then switching to PCBC (using both plaintext and
:> : ciphertext) may result in a difference more than what can easily be
:> : quantified by bits.
:>
:> Why can't the attacker just split his resources and attack both ways?
:> Using one of two types of chaining mode won't add more than 1 bit to the
:> keyspace.
: If, in doing a little thing, you could cause your (mighty) opponent to
: split his resources, isn't that something that well deserves your
: consideration?
Why, certainly.
I've a feeling you might need to make some things on this thread more
concrete before they can be debated properly.
For example, can you present a class of chaining modes which
you think are immune to David Hopwood(?)'s criticism that an attacker may
sometimes be able to recover the chaining mode used in some types of
chosen plaintext attack, by flipping bits and watching the results.
Do you think large classes of such chaining modes exist, so the security
benefit is more than just a few bits of keyspace?
--
__________ Lotus Artificial Life http://alife.co.uk/ [EMAIL PROTECTED]
|im |yler The Mandala Centre http://mandala.co.uk/ Legalise IT.
------------------------------
From: [EMAIL PROTECTED] (wtshaw)
Subject: Re: Compression and known plaintext in brute force analysis (restatements
caused by the missing info .... thread)
Date: Sun, 25 Jun 2000 10:01:57 -0600
In article <[EMAIL PROTECTED]>, [EMAIL PROTECTED] wrote:
>
> If the compressor actually compresses, then a larger proportion of
> cyphertexts will result in expansion to valid plaintexts (for any given
> length of cyphertext) - so you'll typically need a larger cyphertext (as
> well as a larger original plaintext) to reduce the number of possible
> plaintexts to 1.
Whether compression is keyed or not can make all the difference between
inconvenience and added strength. Presuming that compression must be
unkeyed is marching under a similar reasoned banner as presuming that all
text must be ASCII.
--
Some Turkeys can fly, for short distances. If you are to depend on
birds for communication, if it's with turkeys, consider the
discussions that might occur while feasting on one.
------------------------------
From: [EMAIL PROTECTED]
Reply-To: [EMAIL PROTECTED]
Subject: Re: Quantum computing
Date: Sun, 25 Jun 2000 10:18:39 -0700
If I understand it correctly, theorem proving is an NP type of problem.
Therefore there is no guarantee that we will ever find a proof - unless
we have a machine that can compute exponential problems in polynomial
time. Maybe we will not find the proof unless we have a general purpose
quantum computer.
Douglas A. Gwyn wrote:
> [EMAIL PROTECTED] wrote:
> > What will come first a quantum computer or a proof that P != NP?
>
> We *know* what is involved in building quantum computers,
> and many people are in fact working on building them.
>
> We do *not* know what would be involved in a successful
> proof of P?=NP.
------------------------------
From: [EMAIL PROTECTED] (David A. Wagner)
Subject: Re: MD5 Expansion
Date: 25 Jun 2000 09:28:44 -0700
In article <[EMAIL PROTECTED]>,
Mark Wooding <[EMAIL PROTECTED]> wrote:
> Let H be a hash
> function, and let K be a cipher. Let M = (a, b) be a message split into
> two halves (it doesn't really matter how). Compute:
>
> a' = E_{H(b)}(a)
> b' = E_{H(a)}(b)
>
> Then let the extended hash be
>
> H'(M) = H(a', b') || H(b', a')
>
> Any analysis? (Yes, it's much slower than just hashing the data twice.)
David Hopwood already posted one attack, so this is probably
irrelevant, but here's another, just in case you're interested.
Define F(a,b') = E_{H(D_{H(a)}(b'))}(a), noting that if (a', b') are
calculated from (a, b) as above then F(a,b') = a'. Fix b', and let
G(a) = F(a,b'). Heuristically, we can expect G to behave about like
a random function, so if E has a n-bit block size, with about 2^{n/2}
random choices of a, we expect to see a collision in the output of G.
Furthermore, since we've fixed b', a collision in the output of G
yields a collision in (a', b'), which creates a collision in the
output of H. So collisions in H can be found in 2^{n/2} time.
David Hopwood's attack relied on symmetry in the calculation of
(a', b'). This attack does not, so this attack shows that merely
breaking the symmetry is not enough to repair this scheme.
------------------------------
From: Mok-Kong Shen <[EMAIL PROTECTED]>
Subject: Re: Variability of chaining modes of block ciphers
Date: Sun, 25 Jun 2000 20:02:00 +0200
Scott Fluhrer wrote:
> Mok-Kong Shen <[EMAIL PROTECTED]> wrote:
> > The most popular block chaining mode seems to be CBC.
> > There is also PBC which chains with plaintext blocks.
> > One can also accumulate the previous blocks for doing the
> > chaining and use plaintext as well as ciphertext for
> > chaining. (I used this in one of my own designs.) By
> > combinatorics this gives 8 variants. Obviously one can
> > also use modular addition instead of xor and do some
> > random rotations if one likes. I think that the variability
> > of chaining modes could be advantageousy exploited such
> > that the actual chanining mode used in a message has to be
> > guessed by the opponent, thus redering his task much more
> > difficult.
> Why would it? All these operations can be summarized as:
>
> C_i = Encrypt( F( P_i, C_{i-1}, P_{i-1} ) )
>
> for a relatively small set of F's, where:
>
> P_i is the ith plaintext block
> C_i is the ith ciphertext block
> Encrypt is the underlying block cipher (on a single block in encrypt mode)
>
> Given that the number of possible F's is relatively small, and assuming that
> P_i, P_{i-1} are known (that is, this is the known-plaintext attack), the
> attacker can easily compute all 8 possible values of F( P_i, C_{i-1},
> P_{i-1} ), and then do a brute force calculation of:
>
> Decrypt( C_i )
>
> looking for any of the 8 possible values. When he finds one, it is easy to
> verify if he got the key, or a false hit.
>
> This allows the attacker to look through all 8 possibilities with a
> relatively small additional effort beyond a brute force search of the
> underlying block cipher. Thus, you have gained no additional security for
> your additional complexity.
How about the case where IVs are secret? I am not claiming tremendous
gain but some gain that may overweigh the cost. As to added complexity,
I'll say that's very trivial according to experience of implementation
of one of my own algorithm.
M. K. Shen
------------------------------
From: Mok-Kong Shen <[EMAIL PROTECTED]>
Subject: Re: Variability of chaining modes of block ciphers
Date: Sun, 25 Jun 2000 20:01:41 +0200
Mark Wooding wrote:
> Mok-Kong Shen <[EMAIL PROTECTED]> wrote:
>
> > O.k. We could discuss on that. Please give your arguments. (Note that
> > this issue is independent of the issue of whether chaining only adds
> > a couple of bits to the key space.)
>
> No. Just using *a* chaining mode doesn't affect the key space at all.
> Using an secretly chosen chaining mode will add a few effective key
> bits.
If you use a secret IV, that should help a little bit.
> > (I could have instead given an example like this: My boss, who happens
> > to be a friend of an amateur crypto designer, insists on using and
> > buying the software developed by the latter, the security of which I
> > am however not very sure. Do you find this version of an example
> > better for you?)
>
> Not really. Either explain to your boss that he needs to get a clue
> from somewhere, or find a different boss.
I am not sure that's always a recommendalble stragegy (especially
in times of unemployment problems).
[snip]
> > O.k. Suppose that the best cipher you could manage to get is not
> > good enough, but almost. Suppose adding the strength due to chaining
> > renders it above the capability of the opponent. Would you care to use
> > chaining in this situation or not?
>
> I'm disputing whether this situation can happen at all! It calls for an
> impractically fine judgement of the adversary's capabilities.
I was providing a 'boundary' case for consideration. One's judgement
in crypto is indeed in my opinion necessarily fairly subjective and gross
in general. But there could also be (admittedly rare) special situations
where one could have sufficient materials to do fairly accurate estimate
of the opponent's capability. For example, if one somehow knows
the computing power of the opponent and brute force is the analysis
method being used.
M. K. Shen
------------------------------
From: [EMAIL PROTECTED] (JPeschel)
Subject: Re: software protection schemes
Date: 25 Jun 2000 17:51:40 GMT
Yes, and breaking software protection in a Windows
environment is often even easier.
Many of these alleged protection schemes are (more
importantly for this newsgroup, anyway)
used to protect the password of many commercial
encryption programs. When this protection is broken,
for example, by changing a line or two of code,
or by creating a key genereator, the encryption
is broken.
Randy Nichols gives an example of cracker logic
in the <i>ICSA Guide to Cryptography</I>, where
he presents Casimir's crack of MaeDae's Encrypt-It.
Casimir's original essay and crack, as well as
other essays and demonstrations, can be found
at the site in the signature below.
Also, my Russian friend Pavel Semjanov has a
collection of mostly-free crackers at:
http://www.password-crackers.com/crack.html
You can, if you like, purchase a commercial
cracker from AccessData, or from John K., HGWIC,
at Crak.com.
-- Joe
"Thomas J. Boschloo" [EMAIL PROTECTED] writes in part:
>lament wrote:
>>
>> In article <g4u35.30$[EMAIL PROTECTED]>, [EMAIL PROTECTED]
>says...
>>
>> > Almost any software protection scheme running on the PC suffers from this
>> > same vulnerability. If the attacker finds the magic bit that finally
>> > authenticates the user, the software protection will not work.
>>
>> Big "If."
>>
>> > Usually it
>> > is very easy to find this bit. If there are multiple levels of checks
>with
>> > many bits scattered throughout the executable, the job is a little more
>> > difficult.
>>
>> Given that billions of instructions transpire, how do you know which one(s)
>are the
>> one?
>
>I have broken a few copy protection schemes in the DOS era and if there
>is some input required from the user, you just break there and go up a
>few subroutines to see what changes when you enter the correct data and
>what happens when you don't.
__________________________________________
Joe Peschel
D.O.E. SysWorks
http://members.aol.com/jpeschel/index.htm
__________________________________________
------------------------------
** 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
******************************
