Re: ?splints for broken hash functions

2004-08-31 Thread John Denker
Jerry Leichter writes: However ... *any* on-line algorithm falls to a Joux-style attack. Hal Finney wrote: ... hashes that support incremental hashing, as any useful hash surely must, If you insist on being able to hash exceedingly long strings (i.e. longer than your storage capacity) here is a

A splint for broken hash functions

2004-08-31 Thread bear
Here's a handy way to build Joux-resistant hash functions with existing tools. This construction takes slightly more than twice as much work and twice as much internal state as a conventional hash function (embrace it guys, I don't think there's a way around it). H2(H1) = H1( H1(M) xor

Re: ?splints for broken hash functions

2004-08-31 Thread Hal Finney
John Denker writes: Run two hash-machines in parallel. The first one operates normally. The second one puts the first block of the string into a buffer (bounded size!) and then proceeds to hash the rest of the string, starting with the second block. At the end of the message, it appends

Re: A splint for broken hash functions

2004-08-31 Thread Hal Finney
Bear writes: This construction takes slightly more than twice as much work and twice as much internal state as a conventional hash function (embrace it guys, I don't think there's a way around it). H2(H1) = H1( H1(M) xor H1( TT( M))) TT denotes some trivial transformation (I

Re: ?splints for broken hash functions

2004-08-31 Thread John Denker
I agree with 99% of what Hal Finney wrote. I won't repeat the parts we agree on. But let's discuss these parts: how much harder? Well, probably a lot. Finding a regular B2 collision in a perfect 160 bit hash compression function takes 2^80 work. Finding a double collision like this is

Re: A splint for broken hash functions

2004-08-31 Thread bear
On Sun, 29 Aug 2004, John Denker wrote: bear wrote: H2(H1) = H1( H1(M) xor H1( TT( M))) I think that was intended to be something like H2(M) = H1( H1(M) xor H1( TT( M))) ^ Actually, it was intended to take a hash function as an argument and define a new hash function

Re: system reliability -- Re: titles

2004-08-31 Thread Ed Gerck
David Honig wrote: At 12:12 AM 8/27/04 -0700, Ed Gerck wrote: David Honig wrote: Applications can't be any more secure than their operating system. -Bram Cohen That sounds cute but I believe it is incorrect. Example: error- correcting codes. The theory of error-correcting codes allows information

Re: How thorough are the hash breaks, anyway?

2004-08-31 Thread Matt Crawford
certificates. The public key data is public, and it's a random bitpattern where nobody would ever notice a few different bits. If someone finds a collision for microsoft's windows update cert (or a number of other possibilities), and the fan is well and truly buried in it. Correct me if I'm wrong

[Publicity-list] DIMACS Workshop on Mobile and Wireless Security

2004-08-31 Thread Linda Casals
* DIMACS Workshop on Mobile and Wireless Security November 3 - 4, 2004 DIMACS Center, Rutgers University, Piscataway, NJ Organizers: Bill Arbaugh, University of Maryland, [EMAIL PROTECTED] Presented under

Compression theory reference?

2004-08-31 Thread Hadmut Danisch
Hi, I need a literature reference for a simple problem of encoding/compression theory: It can be easily shown that there is no lossless compression method which can effectively compress every possible input. Proof is easy: In a first step, consider all possible messages of length n bit, n0.

[Publicity-list] DIMACS Workshop on Computational Issues in Auction Design

2004-08-31 Thread Linda Casals
* DIMACS Workshop on Computational Issues in Auction Design October 7 - 8, 2004 DIMACS Center, Rutgers University, Piscataway, NJ Organizers: Jayant Kalagnanam, IBM Watson Lab, [EMAIL PROTECTED] Eric

RE: How thorough are the hash breaks, anyway?

2004-08-31 Thread Whyte, William
My understanding is that once you've used trial division to get rid of all the extremely short divisors, a random number of length n is about as hard to factor as an RSA modulus of the same length. I don't think there are a lot of easy-to-factor moduli around. William -Original

RE: How thorough are the hash breaks, anyway?

2004-08-31 Thread Whyte, William
To be more precise: Your odds of getting a modulus that you can divide by something are very high. Your odds of getting a modulus that you can factor efficiently are very low. William -Original Message- From: Matt Crawford [mailto:[EMAIL PROTECTED] Sent: Monday, August 30, 2004 11:47

Re: How thorough are the hash breaks, anyway?

2004-08-31 Thread Hal Finney
Dan Carosone wrote: There is one application of hashes, however, that fits these limitations very closely and has me particularly worried: certificates. The public key data is public, and it's a random bitpattern where nobody would ever notice a few different bits. If someone finds a

Re: Compression theory reference?

2004-08-31 Thread John Denker
Hadmut Danisch wrote: It can be easily shown that there is no lossless compression method which can effectively compress every possible input. OK. ... I need a book about computer science or encoding theory, which explicitely says that this is impossible, in a way that a person unexperienced in