Re: k-way hash collisions

From: Jean-Luc Cooke (jlcooke_at_engsoc.org)
Date: 12/10/04 

Date: 10 Dec 2004 16:48:14 GMT

kaskati <kaskati2003@yahoo.com> wrote:
> For an ideal hash function, the complexity of finding a k-way
> collision is
> O(2^{(k-1)n/k}) therefore as k becomes larger, the complexity of a
> k-way collision attack approaches the complexity of a pre-image
> attack.

> Recently, Joux showed a generic multi-collision attack for iterated
> hash functions to reduce the k-way collision complexity to
> O(log(k)*2^{(n/2)}). But in his attack the pre-images are not
> independent. They are just combinations of block collisions of k
> blocks. Here are my questions:

> 1. How can the formula for the complexity of finding a k-way collision
> be derived?

Read a high-school math text on finite statistics or search fo "birthday
paradox" on MathWorld's website.

> 2. Is there any hash design that allows to reduce the complexity of
> k-way collision for "independent" pre-images while preserving the
> complexity of the pre-image attack? 

--

Relevant Pages

  • RE: ADS Password Storage Protection-$100 reward to crack my password hashes
    ... characters and do character substitution using words instead of letters ... when doing a dictionary attack. ... complexity in their passphrase. ... Clues Normal Password Cracker Would Not Have: ...
    (Security-Basics)
  • RE: ADS Password Storage Protection
    ... If length is the tool for a secure windows passphrase then, in theory, a password of "aaaaaaaaaaaaaaa" should be just as strong as a 15-character password consisting of random characters? ... No complexity, but length prevents it from being easily ... that, while they would be working on a brute force attack, they ... Hacking, like any art, will take years of dedicated study and practice ...
    (Security-Basics)
  • Timing attack on general purpose processor
    ... First of all the purpose of my work is to deal with timing attack on GPP. ... Then we can try to distinguish collision which ... We can have a table with size twice the cache ... If the table are too big this technique won't work. ...
    (sci.crypt)
  • Re: [PROPOSAL/PATCH] Fortuna PRNG in /dev/random
    ... The only attack that would be vaguely relevant ... Collision resistance isn't a requirment for its ... No, it is, by design, 100% collision-resistant. ...
    (Linux-Kernel)
  • RE: ADS Password Storage Protection
    ... treat each word as character, and apply varying combinations of those ... But if one was created, mathematically, a passphrase only using words ... way to guarantee real complexity on shorter passwords. ... its hybrid attack. ...
    (Security-Basics)
Loading