Differential bound of the S-Box in GOST R34.11-2012

Question

In Russian GOST R34.11-2012 LPS-transformation is used. LPS gets all of its non-linearity from the 8-bit S-box S, which apparently has been designed to offer resistance against classical methods of cryptanalysis. Its differential bound is P = $8/256$ and best linear approximation holds with P = $28/128$ . There seem to be no exploitable algebraic weaknesses.

Can you explain what is "differential bound of the S-Box"? I think that it's a probability: P(S($x_1$) $\oplus$ S($x_2$) = b | $x_1$ $\oplus$ $x_2$ = a) for random $a, b$. Is it a correct definition? And LPS seems to be no exploitable algebraic weaknesses because there are 64 S-Boxes and so, differential probability of the LPS at all is $(8/256)^{64}$?

Answer 1

Differential bound of the sbox is an upper bound on the probability of the differential characteristic below, i.e., $$P(S(x_1) \oplus S(x_2) = b | x_1 \oplus x_2 = a)\leq \frac{8}{256},$$ for all $a,b.$

A differential used for cryptanalysis is assembled by joining different differential characteristics from different rounds. This results in a number of Sboxes being 'active', i.e., taking part in the overall differential.

However the probability of a differential would be upper bounded only by $$(8/256)^k$$ where $k$ is the number of active sboxes that are part of the differential. If there are nontrivial attacks, this $k$ will be much smaller than 64.