What are the differences weak and strong collision resistance?

Subject Computer and Network Security
NU Year Set: 3.(d) Marks: 4 Year: 2017

Weak collision resistance
A good example where we are actually only interested in weak collision resistance would be a simple password storage scheme. Assume we store user-provided passwords in a database by storing their hash. Authentication would succeed when the hash of some password a user provides is equal to the value that was stored previously (this is an inherently insecure scheme though, but please bear with me for the moment). Now in that case, the given x is the (unknown) original password that was provided earlier. If an attacker were capable of solving the "second preimage" problem efficiently, he could obtain an x' whose hash value is the same as that of the original x, and would thus be authenticated successfully. Please note that the capability to produce arbitrary collisions (i.e. solving the strong collision problem) is useless in general in this scenario because it is not too likely that the x and x' we get resemble actual passwords whose hashes have already been stored in the database.
Strong collision resistance
A different scenario where our concern is strong collision resistance instead is for example an application where you want to be able to look up arbitrary data stored in a database with the help of unique ids. Instead of issuing queries on the original data (which would often be very slow due to the potentially unbounded size of the data), you would compute hashes of the data instead. Hashes are very compact, limited in their size and can thus be queried much more efficiently. As a matter of fact, in these cases you often don't mind the (second) pre-image resistance property of a hash function at all, mostly because the preimages themselves are no secret. What you do care about, though, is that you would absolutely want to avoid two distinct data sets to hash to the same value, which is essentially a collision. You don't care about any collision in particular, but you want this property to hold universally - i.e. you don't want any two data sets hash to the same value (imagine there is a 'unique constraint' defined on that column). Because security is often no issue in these applications, we often use non-cryptographic hashes, mostly because they perform better.
The relationship between both
Intuitively and also implied by their names, we would assume that strong collision resistance is something that is harder to provide than weak collision resistance. Luckily for us, our intuition can be proven to be correct under the Random Oracle Model. We can prove this by contrapositive by assuming that if we had an efficient probabilistic polynomial algorithm for solving "second preimage", then this would also give us an efficient algorithm for solving "collision".

Login to post your comment.