# Explanations for the complexity values for second preimage attack on GOST?

I've been reading the article "A (second) preimage attack on the GOST hash function" by F. Mendel et al (link) and I'm having some difficulty to grasp some of the values of complexities/probabilities in the attack. Specifically:

1. On page 228, how is the probability that two pairs lead to the corresponding values $x_1$, $x_2$, and $x_3$ amount to $2^{-192}$?

2. On page 230, how is $2^{128}$ used in the calculation of the complexity of the compression function?

3. On page 230, why construct $2^{32}$ pseudo-preimages for the last iteration of GOST?

4. On page 231, how was the value for the probability of finding the right $M_{257}$ in the list $L$ obtained?

5. Finally, on another issue, what operation is referred to by the squared $\ominus$ symbol on page 231: $\Sigma^m = \Sigma^t \ominus M_{257}$. [My guess: subtraction modulo $2^{256}$ -- am I right?]

Thanks very much.

Preliminary: Almost the same article is available for free without breaking any law, nor downloading 5GB (formatting is shifted by at most one third of a page). It is also (as well as all other articles of IACR crypto conferences from 2000-2011) in the IACR Online Proceedings, specifically in the FSE 2008 section, but then you need to subtract about 223 from the page numbers quoted in the question to get the page number in the PDF. For this reason it is best to use section (rather than page) numbers to designate a section of an article.

I have now answered all the points (and learned along the way), but anyone remains welcome to improve that answer, made community wiki.

### 1) In section 3, why does the probability that two pairs lead to the corresponding values $x_1$, $x_2$, and $x_3$ amount to $2^{−192}$?

By construction, $x_i$, $y_i$, $z_i$, $s_i$ are 64-bit. We assume that the process that uncovered each pair, being independent of the relations $x_i=y_i\oplus z_i\oplus s_i$ for $i\in\{1,2,3\}$ (only concerned with that relation for $i=0$), makes each of these relations for $i\in\{1,2,3\}$ true with odds about $2^{-64}$; hence makes the three true with odds about $2^{-192}$ (again, without proof of independence).
That's typical in cryptanalysis: we assume odds that $a=b$ holds with odds $2^{-n}$ when $a$ and $b$ are $n$-bit with at least one of these quantity produced by a process that is engineered for a purpose independent of matching that relation, and that process's output or the other quantity has no clear bias. That probability would follow from assuming either quantities is uniformly distributed.

### 2) In section 4.1, how is $2^{128}$ used in the calculation of the complexity?

In section 4.1 it is considered a multicollision of $t=256$ message blocks, with for each block a pair of values that can be used interchangeably without changing the result in $H_{256}$: For each of $t$ message blocks, the pair is found by the birthday attack on the output of $f$, which has $n=256$ bits, thus with about $2^{n/2}$ evaluations of $f$ using a technique such as Paul C. van Oorschot and Michael J. Wiener's Parallel Collision Search with Cryptanalytic Applications. Here comes the $2^{n/2}=2^{128}$ term!
The total cost of finding the multicollision is about $t\cdot2^{n/2}=2^{136}$. Notice that this is already totally impracticable in a foreseeable future: we are discussing a theoretical attack

### 3) In section 4.2, why construct $2^{32}$ pseudo-preimages for the last iteration of GOST?

That's a compromise between the work required in 4.2, which increases proportionally to the number $w$ of pseudo-preimages made; and the work required in 4.3, which decreases proportionally to $w$. The sum of work required for the two steps is thus of the form $a\cdot w+b/w$, and the minimum for that is for $w=\sqrt{b/a}$.
Here $a=2^{192}$, and $b=2^{256}$ (not quite in the same unit unless I err, but since this is a purely theoretical attack, that does not matter much), and it comes $w=2^{32}$ for the minimum.
In other words: one can change $2^{32}$ a little, the attack will still (theoretically) work. With an increase of that to say $2^{33}$, the expected work in 4.3 will be halved, but that's at the price of twice more work in 4.2, and twice more memory. Thus if we increase too much the work will be raised overall (dominated by 4.2), and if we decrease too much the work will be raised overall (dominated by 4.3). The value $2^{32}$ balances the work in 4.2 and 4.3, and is in the right ballpark for a minimum overall attack effort.

### 4) In section 4.3, how was the probability of finding the right $M_{257}$ in the list $L$ obtained?

The list $L$ contains $w=2^{32}$ pairs $(H,M)$ with $H$ of $n=256$ bits (distinct with high odds since $w\ll2^{n/2}$, under the standard assumption that the $H$ are random-like for reasons discussed in 1).
We want to find an $M_{257}$ that makes $H_{258}$ matching the $H$ of some $(H,M)$ in $L$. $H_{258}$ is next to uniformly distributed (no matter how we enumerate distinct $M_{257}$, because that's a design goal for $f$) thus each value tried has odds $2^{-n}$ to match any particular $H$ in the list, thus odds (only very slightly above) $2^{-n}\cdot w=2^{-224}$ to match one $H$ in the list, and that's the probability we wanted.
That part of the attack alone is expected to require trying $2^{224}$ values of $M_{257}$, thus $2^{225}$ evaluations of $f$, and that's also the stated cost of the attack: at this degree of impracticality, it is common to consider $u+v\approx u$ whenever $v<u$ and we repeat such approximation only a few times.

### 5) What operation is referred to by the $\boxminus$ symbol?

Indeed, $\boxminus$ (written $\boxminus$ on this website) is used in this article for subtraction modulo $2^{256}$. That is quite clear in the context of use of section 4.3 of the paper, given the definition of $\boxplus$ ($\boxplus$) in section 2 as addition modulo $2^{256}$. Note: to determine how to render a symbol in $\TeX$, I often try a detexifyer, and in that case it worked.

### 6) In Section 3, why does the system of equations with $5⋅64$ equations in $8⋅64$ variables results in $2^{192}$ solutions?

A linear system of $x$ linearly independent equations in $y>x$ variables is under-determined, and $y-x$ variables can be fixed to any value. If these are binary variables, that leads to $2^{y-x}$ solutions. We obtain $2^{192}$ as $2^{8⋅64-5⋅64}$.
The same occurs when solving the system of equations with $6⋅64$ equations in $8⋅64$ variables leading to $2^{128}$ solutions: we obtain $2^{128}$ as $2^{8⋅64-6⋅64}$.

• Thanks very much for the comprehensive response fgrieu. Your answer is most helpful. I will take a bit of time to go through and try to understand it all, and get back if any questions persist. Thank you so very much. – IT_guy Mar 25 '14 at 11:44
• I've gone through the paper again and most of my misapprehensions have been clarified by your answer. Everything seems to make more sense now (except question 3, for which the answer is still somewhat "strange"), thank you again, Sir! I had one more concern though: In Section 3, I did not get how the system of equations with $5 \cdot 64$ equations in $8 \cdot 64$ variables results in $2^{192}$ solutions, then further on, solving the system of equations with $6 \cdot 64$ equations in $8 \cdot 64$ variables leads to $2^{128}$ solutions? Any idea? – IT_guy Mar 26 '14 at 13:42
• Thank you so much @fgrieu, +1! That is PERFECT, it's all so much clearer now. Merci beaucoup! – IT_guy Mar 27 '14 at 12:54