logo

SCIENCE CHINA Information Sciences, Volume 64 , Issue 5 : 159103(2021) https://doi.org/10.1007/s11432-018-9772-0

STP models of optimal differential and linear trail for S-box based ciphers

More info
  • ReceivedSep 25, 2018
  • AcceptedJan 18, 2019
  • PublishedMar 23, 2021

Abstract

There is no abstract available for this article.


Acknowledgment

This work was supported by National Cryptography Development Fund (Grant No. MMJJ20170102), National Natural Science Foundation of China (Grant Nos. 61572293, 61502276, 61692276), Natural Science Foundation of Shandong Province (Grant No. ZR2016FM22), and Major Scientific and Technological Innovation Projects of Shandong Province, China (Grant No. 2017CXGC0704).


References

[1] Abdelkhalek A, Sasaki Y, Todo Y, et al. MILP modeling for (Large) S-boxes to optimize probability of differential characteristics. IACR Transactions on Symmetric Cryptology, 2017, 2017: 99-129 DOI: https://doi.org/10.13154/tosc.v2017.i4.99-129. Google Scholar

[2] Banik S, Pandey S K, Peyrin T, et al. GIFT: a small PRESENT. In: Proceedings of International Conference on Cryptographic Hardware and Embedded Systems. Berlin: Springer, 2017. 321--345. Google Scholar

[3] Sun Y. Linear Cryptanalysis of light-weight block cipher ICEBERG. In: Advances in Electronic Commerce, Web Application and Communication. Berlin: Springer, 2012. 529--532. Google Scholar

[4] Biryukov A, Nikolić I. Search for Related-Key Differential Characteristics in DES-Like Ciphers. In: Proceedings of International Workshop on Fast Software Encryption. Berlin: Springer, 2011. 18--34. Google Scholar

[5] Abdelkhalek A, Tolba M, Youssef A M. Improved linear cryptanalysis of round-reduced ARIA. In: International Conference on Information Security. Berlin: Springer, 2016. 18--34. Google Scholar

[6] Su B Z, Wu W L, Zhang W T. Security of the SMS4 Block Cipher Against Differential Cryptanalysis. J Comput Sci Technol, 2011, 26: 130-138 CrossRef Google Scholar

[7] Ganesh V, Hansen T, Soos M, et al. STP. 2014. https://stp.github.io/. Google Scholar

  •   

    Algorithm 1 Algorithm to calculate $n_f$, given $N_{S}$ and the DDTs

    Input: number of active S-boxes $N_{S}$, DDTs. Output: $n_{f}\in\mathbb{Z^{+}}.$

    Data: $V_{\rm~count}$: number of rows in the list $T_{N}$; $f_p[i]$: the $i$-th $f_p$ value in the list $T_{N}$; $G^*[i]$: value of the approximation function corresponding to the $i$-th $(2^{m-1}-1)$-tuple in the list $T_{N}$.

    $V_{\rm~count}~\leftarrow~0$;

    for all possible $(2^{m-1}-1)$-tuples $\{N_{2^m-2},$$\ldots,$$N_{4},$$N_{2}\}$

    $f_p~\leftarrow\frac{1}{2^{N_S\cdot~p~m}}\cdot\prod_{k=1}^{2^{m-1}-1}(2k)^{N_{2k}}$;

    Add $\{f_p,N_{2^m-2},\ldots,N_{4},N_{2}\}$ to $T_N$;

    $V_{\rm~count}++$;

    end for

    Sort $T_{N}$ according to the keywords $f_p,$ $N_{2^m-2},$ $\ldots,$ $N_{4},$ $N_{2}$ in ascending order;

    $n_f\leftarrow~1$;

    $G^*[1]~\leftarrow~-~\sum_{k=1}^{2^{m-1}-1}(N_{2k}\times~\lceil~(\log_{2}2k-m)\times~10^{n_{f}}~\rceil)$ corresponding to the first $(2^{m-1}-1)$-tuple in $T_N$;

    for $i~\leftarrow~2$ to $V_{\rm~count}$

    $G^*[i]~\leftarrow~-~\sum_{k=1}^{2^{m-1}-1}(N_{2k}\times~\lceil~(\log_{2}2k-m)\times~10^{n_{f}}~\rceil)$ corresponding to the $i$-th $(2^{m-1}-1)$-tuple in $T_N$;

    if $(G^*[i]~$$>~$$G^*[i-1])$$\|($$G^*[i]~$$=~$$G^*[i-1]$ $f_{p}[i]~$$=$$~f_{p}[i-1]$) then

    continue

    else

    $n_{f}++$;

    goto Line 9;

    end if

    end for

    return $n_{f}$.

  •   
  •   

    Algorithm 2 Model for generating differential trails with the expected number of active S-boxes

    Input: number of rounds $r$, expected threshold, and flag. (Flags of 0 and 1 indicate related-key and single-key settings, respectively.) Output: a differential trail with the expected number of active S-boxes.

    for round $\leftarrow~1$ to $r$

    List equations for S-Boxes satisfying Property probabilitydifferential.

    Write equations for the linear layer.

    end for

    if flag = 1 then

    Generate equations that set the input differences to non-zero values.

    else

    Generate equations that set the master key differences to non-zero values.

    List equations corresponding to the key schedule.

    end if

    Write equations that set the number of S-boxes to below the expected threshold.

    Solve the above equations using the STP solver.

  •   

    Algorithm 3 Algorithm for finding differential trails with the expected probability

    Input: number of rounds $r$, expected threshold $G^*_{\rm~th}$, $N_{S}$, flag. (Flags of 0 and 1 indicate related-key and single-key settings, respectively.) Output: a differential trail with a probability of less than $G^*_{\rm~th}$.

    for round $\leftarrow~1$ to $r$

    List equations for S-Boxes satisfying Property probabilitydifferential.

    Write equations for the linear layer.

    end for

    if flag=1 then

    Generate equations that set the input differences to non-zero values.

    else

    Generate equations that set the master key differences to non-zero values.

    List equations corresponding to the key schedule.

    end if

    Write equations that set $G^{*}<~G^*_{\rm~th}$.

    Write equations that set the number of active S-boxes to $N_{S}$.

    Solve all the above equations with the STP solver.

  •   

    Algorithm 4 General procedure for finding differential trails with optimal probabilities

    Input: number of rounds $r$, $P_{\rm~max}$. Output: a differential trail with optimal probability. Data: $P_{\rm~max}$ represents the maximum probability over all DDTs.

    Execute Algorithm 2 to obtain the differential trail with the minimum number of active S-boxes $N_s$.

    Compute the probability $p$ of this trail.

    Store this trail in the list $L$.

    $t~\leftarrow~0$.

    Set the number of active S-boxes to $N_s~+~t$, then compute the value of $n_f$ with Algorithm 1.

    Gradually reduce the value of $G^*_{\rm~th}$ and execute Algorithm 3 to find the optimal trail with $N_s~+~t$ active S-boxes.

    Compute the probability $p&apos;$ of this trail.

    if $p&apos;>p$ then

    $p~\leftarrow~p&apos;$;

    Use this trail update $L$.

    end if

    $t++$.

    if $(P_{\rm~max})^{N_S+t}~>~p$ then

    goto Line 5;

    else

    return $L$ and $p$.

    end if

qqqq

Contact and support