finding key pairs with colliding fingerprints (Re: How thorough are the hash breaks, anyway?)

2004-08-28 Thread Adam Back
You would have to either: - search for candidate collisions amongst public keys you know the private key for (bit more expensive) - factorize the public key after you found a collision the 2nd one isn't as hard as it sounds because the public key would be essentially random and have

Re: How thorough are the hash breaks, anyway?

2004-08-28 Thread Nicholas Bohm
At 16:09 26/08/2004, Trei, Peter wrote: [snip] Looking over the recent work on hash collisions, one thing that struck me was that they all seem to be attacks on known plaintext - the 'plaintexts' which collided were very close to each other, varying in only a few bits. While any weakness is a

Re: More problems with hash functions

2004-08-28 Thread Jerrold Leichter
| Bear writes: | One interesting idea which I came up with and haven't seen a way | past yet is to XOR each block with a value computed from its | sequence number, then compute the hash function on the blocks in | a nonsequential order based on the plaintext of the blocks | in their new

Re: More problems with hash functions

2004-08-28 Thread Hal Finney
Jerry Leichter writes: However ... *any* on-line algorithm falls to a Joux-style attack. An algorithm with fixed internal memory that can only read its input linearly, exactly once, can be modeled as an FSM. A Joux-style attack then is: Find a pair of inputs M1 and M1' that, starting from

Re: Cryptography and the Open Source Security Debate

2004-08-28 Thread lrk
On Wed, Aug 25, 2004 at 03:17:15PM +0100, Ben Laurie wrote: lrk wrote: My examination of RSAREF and OpenSSL code was more toward understanding how they handled big numbers. It appears both generate prime numbers which are half the length of the required N and with both of the two most

Re: More problems with hash functions

2004-08-28 Thread Jerrold Leichter
| However ... *any* on-line algorithm falls to a Joux-style attack. An | algorithm with fixed internal memory that can only read its input linearly, | exactly once, can be modeled as an FSM. A Joux-style attack then is: Find | a pair of inputs M1 and M1' that, starting from the fixed

Re: More problems with hash functions

2004-08-28 Thread Hal Finney
Jerry Leichter writes: It all depends on how you define an attack, and how you choose to define your security. I explored the outer edge: Distinguishability from a random function. For a random function from {0,1}*-{0,1}^k, we expect to have to do 2^k work (where the unit of work is an