Boiledbeans

Drama! Intrigue! Geekiness!

July 30, 2009

1bc29b36f623ba82aaf6724fd3b16718

devadutta @ 11:44 pm, GMT +0000 ( 1248997481 ) Play

This question was sent in a simpler form by shenoyvarun86. Thanks for the pointer saar!

Tell us how 1 wreaks havoc for algorithms like 2

1. 740px-TooManyPigeons 2. 300px-MD5.svg

Cracked by: akhi , shenoyvarun86 , Logik , Ananth , madhur , Rogi , blackrat , kiran , Joshan , username , Deepthi JS and p vs np.

Answer:

Pigeon Hole Principle and Hash collisions causing all vulnerabilities in hash algorithms


13 Responses to “1bc29b36f623ba82aaf6724fd3b16718”

  1. akhi
    2
    1

    Pigeon Hole Principle, Cryptographic Hash Algorithm and weakness being Collision Attack (Collision-large set of names mapped into small bit strings.)


  2. Pigeonhole principle!


  3. Logik
    1
    5
    3

    Block Ciphers cannot create a code which is smaller than the input length, because by Pigeon hole principle, there’d be a one-to-many correspondence, which means the cipher wouldn’t be invertible, which means a total waste of an algorithm.
    So generally the length of the input ( plaintext) is equivalent to length of the output ( cipher ).

    Nice question.


  4. Ananth
    4
    5
    9

    1) Pigeon hole principle
    2) Some hashing algo ( SHA1 I guess)

    Accd Pigeon hole principle: No hashing algorithm, no matter how clever, can avoid collisions.


  5. madhur
    1

    1. Pigeon Hole Principle
    2. MD5


  6. Rogi
    48
    10
    5

    Would it suffice to simply say, *collisions*?


  7. The pigeonhole principle (fig. 1) forms the basis of collision resolution techniques. An unfortunate juxtaposition also being, you cannot escape collisions when it comes to hashing.
    Any good hashing algorithm avoids collision. However that becomes a distinct impossibility as soon as the data-size(pigeons) exceeds the checksum size(pigeonholes), regardless of algorithmic jugglery.

    The Vulnerability of SHA-1 (fig. 2) was brought to light by Xiaoyun Wang @ Shandong U. Devising a method for replicating collisions nearly 2^12 times faster(in terms of algo. complexity) than what is agreed to be computationally secure.


  8. piezocake

    The pigeon-hole principle makes the Boolean satisfiability problem NP-hard ?


  9. kiran

    Pigeonhole principle, sha, problem – collisions


  10. Joshan

    pigeon hole principle…….This principle states that, given two natural numbers n and m with n > m, if n items are put into m pigeonholes, then at least one pigeonhole must contain more than one item.


  11. username
    3
    3
    1

    1. Pigeonhole principle
    2. MD5: hash algorithm

    collisions are inevitable in a hash table because the number of possible keys exceeds the number of indices in the array. No hashing algorithm, no matter how clever, can avoid these collisions.

    http://en.wikipedia.org/wiki/Pigeonhole_principle


  12. Deepthi JS

    1–> Pigeon Hole Principle and 2–> algorithm for hashing.According to wiki,collisions are inevitable in a hash table because the number of possible keys exceeds the number of indices in the array.


  13. p vs np
    1

    It’s the Pigeon Hole Principle doing kireek in Hash tables,_quote_ because the number of possible keys exceeds the number of indices in the array. No hashing algorithm, no matter how clever, can avoid these collisions. _quote_


« Previous « Damaar! « | » I can’t figure out what’s really new, but still… » Next »