Free-start collision vs Semi-free-start collision

pioneer

1/4/24, 10:19 AM

Recently, I am very interested in the hash function attack paper, so I am reading it closely.

I found out that there are Free-start and Semi-free-start settings among the attacks on the hash function.

The example below introduces these two definitions. (The definition is similar to other papers, so I brought it here.)

https://eprint.iacr.org/2017/800.pdf

There are two attack models on the compression function. One is called free-start collision attack, the other is semi-free-start collision attack. The free-start collision attack is to find two different pairs of message and chaining value $(CV, M)$, $(CV', M')$ which satisfy $H(CV, M)=H(CV', M')$. The semi-free-start collision attack works in the same way apart from an additional condition that $CV = CV'$.

A few questions arose here.

According to this definition, can a semi-free-start collision attack be considered a free-start collision attack?
If an r-round Semi-free-start collision attack exists for a certain hash function, does a t-round free-start collision attack for a round smaller than r become meaningless (t<r)? If not, does it have its own meaning in different applications?
Can I assume that Free-start collision attack selects the difference of IV and Semi-free-start collision selects the actual value of IV?

I think there is a reason why it is divided into two settings: Free-start and Semi-free-start. But it is difficult to derive the reason.

Thank you.

1 + 0

collision-resistance

Score:1

Crypto

Daniel S

1/4/24, 10:51 AM

Yes, the conditions for a free-start collision are implied by a semi-free-start collision. Any attack on the semi-free-start problem would also count as an attack on the free-start problem.
Here we appear to have switched from talking about collisions on the compression function to collisions on the full hash function (which consists of several rounds of the compression function). An $r$-round semi-free-start collision would automatically provide us with a $t$-round free-start collision for all $t<r$, just by evaluating $r-t$ rounds of compression and using the outputs as initial chaining values for the free-start-collision. These are not necessarily "meaningless". In particular, they may be very relevant for "hash herding" if we can find multiple ways of arriving at these states rather than simply the two provided by a single semi-free-start collision. Free-start-collisions are easier to find and may or may not extend back to semi-free-start collisions; semi-free start collisions and may or may not extend back to full collisions. Thus finding free-start collisions can be a first step to finding semi-free-start collisions which can be a step to finding full collisions. Even if we know an $r$-round semi-free-start attack, a $t$-round free-start attack might still be interesting, particularly if it uses less work/memory or if it generates many instances in which case it might be a better route to a full collision attack.
I think it best to think that when we have a compression function that maps $n+m$-bits to $n$ bits a free-start attack has $2n+2m$ degrees of freedom and a semi-free-start attack has $n+2m$ degrees of freedom. If a free-start attack succeeds, we have 2 chaining values and 2 message blocks, but taking another two chaining values with the same difference would not lead to another collision instance.

+ 2

pioneer

1/4/24, 11:16 AM

Thank you for answer. In question 2, I tried to ask if it makes sense to find a t-round free-start collision attack (assuming there is an r-round semi-free-start collision attack). Also, if it is meaningful, are there any related applications?

Daniel S

1/4/24, 12:16 PM

I've added some extra words to my answer for 2; let me know if I'm still not quite understanding your question.

Elon Musk

I sit in a Tesla and translated this thread with Ai:

EN: Free-start collision vs Semi-free-start collision

Post an answer

Most people don’t grasp that asking a lot of questions unlocks learning and improves interpersonal bonding. In Alison’s studies, for example, though people could accurately recall how many questions had been asked in their conversations, they didn’t intuit the link between questions and liking. Across four studies, in which participants were engaged in conversations themselves or read transcripts of others’ conversations, people tended not to realize that question asking would influence—or had influenced—the level of amity between the conversationalists.