July 30, 2009
1bc29b36f623ba82aaf6724fd3b16718
— devadutta @ 11:44 pm, GMT +0000 ( 1248997481 ) 
Play
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. 
2. 
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
Subscribe
Play
Lite Version
July 31st, 2009 at 4:11 am, GMT +0000 ( 1249013492 )
Pigeon Hole Principle, Cryptographic Hash Algorithm and weakness being Collision Attack (Collision-large set of names mapped into small bit strings.)
July 31st, 2009 at 6:26 am, GMT +0000 ( 1249021600 )
Pigeonhole principle!
July 31st, 2009 at 8:53 am, GMT +0000 ( 1249030417 )
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.
July 31st, 2009 at 11:59 am, GMT +0000 ( 1249041580 )
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.
July 31st, 2009 at 3:18 pm, GMT +0000 ( 1249053488 )
1. Pigeon Hole Principle
2. MD5
July 31st, 2009 at 10:23 pm, GMT +0000 ( 1249079005 )
Would it suffice to simply say, *collisions*?
July 31st, 2009 at 11:19 pm, GMT +0000 ( 1249082346 )
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.
August 1st, 2009 at 8:36 am, GMT +0000 ( 1249115782 )
The pigeon-hole principle makes the Boolean satisfiability problem NP-hard ?
August 1st, 2009 at 10:33 am, GMT +0000 ( 1249122812 )
Pigeonhole principle, sha, problem – collisions
August 1st, 2009 at 9:01 pm, GMT +0000 ( 1249160512 )
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.
August 2nd, 2009 at 1:49 am, GMT +0000 ( 1249177782 )
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
August 2nd, 2009 at 4:36 am, GMT +0000 ( 1249187787 )
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.
August 2nd, 2009 at 5:23 am, GMT +0000 ( 1249190604 )
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_