# Bicliques for permutations

So I'm trying to understand the complexity of the biclique attack on Grostl and I have some questions:

1) The paper introduces sliced bicliques where on Grostl one constructs a biclique of dimension 1 and accordingly, we get 4 $Q's$ at state#5 and 4 $P's$ at state#8. What I understood is that each pair of $Q's$ should hash to the same value at the matching point (state#13), similarly for the $P's$. My question is how is this possible if we have 4 different $Q's$? My understanding is that can happen if we consider only the parts at state#13 that are not affected by the difference (white bytes), is my undarstanding correct?

2) The complexity of the attack should be equal to #bicliques(cost of biclique construction + cost of computing forward and backwards to the matching point + cost of checking for a full match if partial matching took place), right?

3) Cost of biclique construction is the $2^{70}$ for the super Sbox solutions and consequently using the free 48 bytes in the $Q's$, we can have $2^{384}$ bicliques without the need to construct new one. However I cannot understand the $2\times(8 + 16 + 2 + 7 + 56 + 8) = 194$ Sboxes for both the forward and backward recomputation. I understand that we're supposed to recompute the white bytes that affects the 4 leftmost columns white bytes at the matching states only but howcome there are 6 terms in the above computation althought we only have 2 rounds in each direction after the biclique? and how are the 194 Sboxes equal to $2^{-3}$ call of the permutation if the 10-rounds permutation has 640 Sbox lookups in Total?

4) What about the complexity of checking for the full match if we get a partial match?

-

A sliced biclique over $g$ is two set of states ${Q_{i,j}}$ and ${P_{i,j}}$ such that for every pair $(i,j)$ $$P_{i,j} = Q_{i,j}.$$ The states are chosen so that the difference between $Q_{i,j}$ for fixed $i$ is small, and the same must hold for $P_{i,j}$ and fixed $j$.

$Q$ and $P$ map to the same hash value $H$, but it is not state #13, but rather $$H = \#1\oplus\#13.$$ You use this equation to filter out incompatible pairs $(i,j)$. The entire trick is to treat some $Q$ as the same, and similarly with $P$ to reduce the computations.

3) These are the numbers of recomputed S-boxes in each round from 1 to 6th. There are $6*64 = 384$ S-boxes in total, so there must be $2^{-2}$ calls, not $2^{-3}$.
Thanks for your help. But lets consider the case for one sliced biclique, i.e., $2^2$ states, after the Supersbox construction, we recompute 2 states only from each direction. Specifically, from state #8 to #12 forward and given the hash target, from state #5 to #13 backward. Why should we consider all the sboxes in the whole six rounds, if the two rounds in the middle are already accounted for during the biclique construction? and how is $194/384 \approx 2^{-2}$? –  Ricoz Feb 5 at 19:33
Thank you. I'll take your advice and ask :) At the matching point, we need the knowlage of the white bytes at the 4 rightmost columns (28 Sboxes at each direction at states #12 and #1). When we trace these Sboxes backwards to P and Q, we need to pass by 56 Sboxes at each direction too (states #10 and #3). Accordingly, $2(56+28) = 168$ Sbox recomputations are needed for each biclique, right? –  Ricoz Feb 6 at 21:20
Suppose, we will be trying $2^{254}$ bicliques (as each one $=2^2$ states), all of them are derived from the same 4 differences (one biclique), after the SuperSbox construction, we store them? Memory complexity is $2^{256+3}$ states? –  Ricoz Feb 6 at 21:39
The $2^{254}$ bicliques give us $2^{256}$ candidate matching pairs at the matching point. As we have 24 bytes matching variables, $2^{64}$ pairs are expected to partially match and only one of them is expected to fully match. How the attack deals with checking for this? do we collect partially matching pairs and then recheck for full match an so the complexity is negligible compared with the testing stage? –  Ricoz Feb 6 at 21:40