1.1 - Difference Between 2nd Preimage and Collision


#1

I’m going through the lectures (Karl sounds even more excited on 2x speed), and I had some difficulty understanding the difference between a 2nd preimage attack and a collision. I snooped around the web a bit, and found this to be the easiest answer for me, so I thought I’d leave it here for anyone else who’s interested:

Though there a bunch of different answers on different StackExchange sites:




#2

Hmmm… so let’s see if I get this.

So… first, preimage property ---- Dawg, you can’t go backward and find the input given the hash
Second preimage property ---- Dawg, you can’t go back and swap the input with another input to get the same hash

Collision resistance - dawg, you can’t find two inputs with the same hash, unless of course your hash function is broken (like with md5).

Random Oracle - Dawg, we can def take hash functions and use them as a source of randomness. Mind = blown.

From the links:

In Second Pre-Image Resistance, we give the attacker the preimage and challenge him/her to find an input with the same hash. In a collision, the attacker chooses both preimages arbitrarily. Second preimages attacks are harder because #math.

That is what I understand so far.


#3

Yeap. As the links explain, the difference is the freedom of choice for an input.

  • Collision: Try to find any 2 distinct messages that give the same hash value. (Free to choose inputs)
  • 2nd Preimage: Given 1 message, try to find another message that give the same hash value. (Fix 1 input)

Given the restriction, it makes sense that 2nd preimage attacks are harder to find.


#4

Preimage resistance: Given H(x), it is computationally difficult to determine x

Second preimage: Given x, it is computationally difficult to find some value of x derivative such that H(x) is the same as H(x derivative)

Collision resistance: It is computationally difficult to find x and y such that H(x) == H(y)

In more layman terms, I like the fingerprint anaology. Second preimage is about finding someone with the same fingerprint as you. Collision is about finding two random people with the same fingerprint.


#5

My best attempt :slight_smile:

If the attacker knows the value of x and tries to change it, the newly generated hash will always be different because of the preimage resistance.

Quickly:
bytes4(keccak256(“bad”)) = 0xded8b1fb
bytes4(keccak256(“bed”)) = 0xb3539225

If the attacker knows the hashed value of x H(x) but not the value x, it cannot find a value y whose hashed value H(y) is the same as H(x) because of the collision resistance.

Quickly:
0xded8b1fb = bytes4(keccak256(“bad”))
0xb3539225 = bytes4(keccak256(“bed”))