Distinguishing attacks on block ciphers by differentials of two-block texts

We present the observation model (random two-block texts encrypted on random independent keys) such that differential distinguishing attacks completely correspond to the generally accepted schemes of their statistical calculation. In this model, we get low bounds for data complexity of multiple differential distinguishing attacks. Let $n$ be the block size, $M=2^n-1$, $D(a)$ be a set of high-probabilily output differences at a fixed input difference $a\in\mathbb{Z}_2^n$ in $R$-round encryption, $P_1=\dfrac{|D(a)|}{M} < P_2=\textstyle\sum\limits_{b\in D(a)} p_{a,b}^{(R)} \le \dfrac{1}{2}$. Let $\nu(D(a))$ be the number of these differences appearances. Suppose the attack is based on statistics $\nu(D(a))$ and have error probabilities $\alpha,\beta\in(0,1/2)$. Then attack needs $N_{1,a*}> N_{2,a*}=\dfrac{4P_1 (1-P_1)(1-\alpha-\beta)^2}{(P_2-P_1)^2}$ two-block texts. In particulary, in the case of $D(a)=\{b\}$, $1/M < p_{a,b}^{(R)}\le 1/2$, we have low bound $N_{2,a,b*}= \dfrac{4\left(1-1/{M}\right)(1-\alpha-\beta)^2}{M\left(p_{a,b}^{(R)}-1/{M}\right)^2}$. Consequently, the frequently used estimate $O(1/p_{\max})$ for data complexity is not enough for successful attack at small values of $(p_{\max}-1/{M})$, where $p_{\max}$ is the maximal transition probability of differentials. We also get asymptotic estimates for data complexity of the most powerful criterion (MPC) in the case of converging hypotheses. Let $\rho(a,R)=\big|\mathbb{P}_a^{(R)}-\dfrac1M 1\big|$ is the Euclidean distance from the row $\mathbb{P}_a^{(R)}$ of transition probabilities matrix to the uniform distribution vector. Suppose $\max_{b\ne 0} |p_{a,b}^{(R)}M-1|\to 0$ in the series scheme with a growing $R$, $N(R)\sim N_{\rm MPC}(R,a)=\dfrac{(\kappa_{1-\alpha}+\kappa_{1-\beta})^2} {M \rho^2(a,R)}$. Then MPC errors tend to $\alpha$, $\beta$ (for some criteria bounds). We make experiments with Markov models of SmallPresent cipher for block size up to $n=28$ bits and $R=10$ rounds: we find inpute differences that minimize $N_{\rm MPC}(R,a)$ and we calculate empirical error probabilities for this number of texts.