## July 30, 2009

### 1bc29b36f623ba82aaf6724fd3b16718

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

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

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

Pigeonhole principle!

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.

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.

1. Pigeon Hole Principle

2. MD5

Would it suffice to simply say, *collisions*?

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.

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

Blame AutoRaja

Pigeonhole principle, sha, problem – collisions

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.

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

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.

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_