### Re: Compression theory reference?

On Aug 31, 2004, at 15:56, John Denker wrote: 4) Don't forget the _recursion_ argument. Take their favorite algorithm (call it XX). If their claims are correct, XX should be able to compress _anything_. That is, the output of XX should _always_ be at least one bit shorter than the input. Then

### Re: Compression theory reference?

On Tue, Aug 31, 2004 at 05:07:30PM -0500, Matt Crawford wrote: Plus a string of log(N) bits telling you how many times to apply the decompression function! Uh-oh, now goes over the judge's head ... Yeah, I just posted a lengthy description why I think that this counterexample is not a

### Re: Compression theory reference?

I wrote: 4) Don't forget the _recursion_ argument. Take their favorite algorithm (call it XX). If their claims are correct, XX should be able to compress _anything_. That is, the output of XX should _always_ be at least one bit shorter than the input. Then the compound operation XX(XX(...))

### Hashes, splints, and PRNGs

I'm really enjoying the current discussion about hash constructions and splints for current algorithms. I will make one observation in that discussion, which is that the proposal for a Hnew (2n - n) seems a little beyond the scope of a field splint that can be done using existing tools and

### Re: Compression theory reference?

Hadmut Danisch [EMAIL PROTECTED] writes: I need a literature reference for a simple problem of encoding/compression theory: comp.compression FAQ, probably question #1 given the number of times this comes up in the newsgroup. (I've just checked, it's question #9 in part 1. Question #73 in part

### More problems with hash functions

Jerrold Leichter wrote: Joux's attack says: Find single block messages M1 and M1' that collide on the blank initial state. Now find messages M2 amd M2' that collide with the (common) final state from M1 and M1'. Then you hav four 2-block collisions for the cost of two: M1|M2, M1'|M2, and so

### Re: Compression theory reference?

On Wed, Sep 01, 2004 at 04:02:02PM +1200, Peter Gutmann wrote: comp.compression FAQ, probably question #1 given the number of times this comes up in the newsgroup. (I've just checked, it's question #9 in part 1. Question #73 in part 2 may also be useful). Thanks, that's a pretty good

### RE: Compression theory reference?

On Tue, Aug 31, 2004 at 02:48:00PM +0200, Hadmut Danisch wrote: It can be easily shown that there is no lossless compression method which can effectively compress every possible input. Even more simply, if such a method existed, you could recursively apply it to its output and compress

### Re: ?splints for broken hash functions

From: Ivan Krstic [EMAIL PROTECTED] Sent: Aug 29, 2004 8:40 AM To: Metzdowd Crypto [EMAIL PROTECTED] Subject: Re: ?splints for broken hash functions This is Schneier's and Ferguson's solution to then-known hash function weaknesses in Practical Cryptography, Wiley Publishing, 2003: We do not

### Re: Approximate hashes

From: Marcel Popescu [EMAIL PROTECTED] Hence my question: is there some approximate hash function (which I could use instead of SHA-1) which can verify that a text hashes very close to a value? So that if I change, say, tabs into spaces, I won't get exactly the same value, but I would get a

### Implementation choices in light of recent attacks?

After digesting the various bits of information and speculation on the recent breaks and partial attacks on various popular hash functions I am wondering if anyone has suggestions for implementation choices for someone needing a (hopefully) strong hash today, but who needs to keep the hash

### Re: Approximate hashes

On Wed, 1 Sep 2004, Marcel Popescu wrote: My problem is that I don't know what happens with the email in transit some mail server might dislike ASCII characters with the high bit set, or Hence my question: is there some approximate hash function (which I could PGP has this issue with

### Re: ?splints for broken hash functions

John Kelsey critiques the proposal from Practical Cryptography: We do not know of any literature about how to fix the hash functions, but here is what we came up with when writing this book. ... Let h be one of the hash functions mentioned above. Instead of m-h(m), we use m-h(h(m) || m) as

### Re: Compression theory reference?

On Wed, 1 Sep 2004, Hadmut Danisch wrote: I have often heard that example and I used it myself several times. I do not use it anymore, because it is not that easy. There's a major flaw in this example, and therefore it is not really a counterexample. If the faculty found that flaw I'd be in a

### Re: Compression theory reference?

On Tue, 31 Aug 2004, John Denker wrote: I emphasize that I am only discussing messages of length N, where N is some pre-chosen number. For concreteness, let's choose N=10. I repeat my assertion that _if_ XX can compress any string, shortening it by one bit, and _if_ you know that the

### Re: Approximate hashes

From: Hal Finney [EMAIL PROTECTED] As you are probably aware, existing hashcash implementations do not base the stamp on the message content. Instead they only lock the stamp to the receiver's email address. Then the receiver keeps a list of the hashcash stamps he has seen recently, to

### Re: Approximate hashes

At 06:02 PM 9/1/04 +0300, Marcel Popescu wrote: From: Marcel Popescu [EMAIL PROTECTED] Hence my question: is there some approximate hash function (which I could use instead of SHA-1) which can verify that a text hashes very close to a value? So that if I change, say, tabs into spaces, I won't

### RE: Approximate hashes

-Original Message- From: [EMAIL PROTECTED] [mailto:[EMAIL PROTECTED] On Behalf Of Marcel Popescu Sent: Wednesday, September 01, 2004 9:56 AM To: [EMAIL PROTECTED] Subject: Approximate hashes I am trying to build a Windows anti-spam thingy; it's supposed to sit in between the

### ?splints for broken hash functions

Hal Finney writes: [John Denker proposes:] the Bi are the input blocks: (IV) - B1 - B2 - B3 - ... Bk - H1 (IV) - B2 - B3 - ... Bk - B1 - H2 then we combine H1 and H2 nonlinearly. This does not add any strength against Joux's attack. One can find collisions for this in 80*2^80 time with

### RE: Approximate hashes

| nilsimsa | Computes nilsimsa codes of messages and compares the codes and finds | clusters of similar messages so as to trash spam. | | What's a nilsimsa code? | | A nilsimsa code is something like a hash, but unlike hashes, a small change | in the message results in a small change in the

### Re: ?splints for broken hash functions

I wrote the Bi are the input blocks: (IV) - B1 - B2 - B3 - ... Bk - H1 (IV) - B2 - B3 - ... Bk - B1 - H2 then we combine H1 and H2 nonlinearly. (Note that I have since proposed a couple of improvements, but I don't think they are relevant to the present remarks.) David Wagner wrote: This