logo

SCIENCE CHINA Information Sciences, Volume 62 , Issue 3 : 032111(2019) https://doi.org/10.1007/s11432-018-9658-0

Automatic search method for multiple differentials and its application on MANTIS

More info
  • ReceivedSep 4, 2018
  • AcceptedNov 12, 2018
  • PublishedJan 29, 2019

Abstract

Multiple differential cryptanalysis is one of the extensions of classic differential cryptanalysis.In this paper, we present a generic automatic search method for clustering multiple differentials on a target block cipher.Our search method has two steps.Firstly, the sets of input and output differences will be determined. With these sets, we get different multiple differentials.Then for each one of these multiple differentials, we enumerate and record all satisfied differential trails, which leads to a more accurate evaluation of the multiple differentials distinguisher.Among these different multiple differentials distinguishers, we can choose the best one for key recovery attack.We demonstrate our search method by applying it on the part of differentials of the block cipher MANTIS.As a result, we find a new 10-round multiple differentials distinguisher with probability $2~^~{-55.98}$ and an 11-round multiple differentials distinguisher with probability $2~^~{-63.71}$, which is the longest distinguisher for MANTIS so far as we know.This new 10-round distinguisher can lead to a better signal-to-noise ratio, so we derive an improved key recovery attack on MANTIS-6 with the complexity of about $2^{51.79}$ chosen-plaintext queries, $2^{51.91}$ encryptions and data-time product $2^{103.70}$, which is better than the previous best one with data-time product $2~^~{110.61}$.Aiming at exploring the gap between the performance of multiple differential attack and the security margin on MANTIS, we also use the 11-round distinguisher to derive a key recovery attack on MANTIS-7 with the complexity of about $2~^~{61.86}$ chosen-plaintext queries, $2~^~{102.92}$ encryptions and data-time product $2~^~{164.78}$.It does not threat the security of full version MANTIS (MANTIS-7) since the security bound of data-time product claimed bythe designers is $2^{126}$.


Acknowledgment

This work was supported by National Cryptography Development Fund (Grant No. MMJJ201701- 02), National Natural Science Foundation of China (Grant No. 61572293), Major Scientific and Technological Innovation Projects of Shandong Province (Grant No. 2017CXGC0704), and Fundamental Research Fund of Shandong Academy of Sciences (Grant No. 2018:12-16).


Supplement

Appendix

Proof of Lemma 4.1

Proof. For the sake of simplicity, we use $K_{0,1}[a,b]$ to denote $$k_0[(a){\rm mod}64] \oplus k_1[(b){\rm mod}64],$$ $K_1[a,b,c]$ to denote $$k_1[(a){\rm mod}64]\oplus k_1[(b){\rm mod}64]\oplus k_1[(c){\rm mod}64].$$

If we know the $i$-th, $j$-th, $k$-th ($i,j,k~\in~\{0,~1,~\ldots,~14\}$) nibbles of $k_0~+~k_1$ and $k'_0~+~k_1$, which are the following 24 bits: \begin{align} &K_{0,1}[4i, 4i], K_{0,1}[4i + 1, 4i + 1], K_{0,1}[4i + 2, 4i + 2], K_{0,1}[4i + 3, 4i + 3], \tag{4} \\ &K_{0,1}[4j, 4j], K_{0,1}[4j + 1, 4j + 1], K_{0,1}[4j + 2, 4j + 2], K_{0,1}[4j + 3, 4j + 3], \tag{5} \\ &K_{0,1}[4k, 4k], K_{0,1}[4k + 1, 4k + 1], K_{0,1}[4k + 2, 4k + 2], K_{0,1}[4k + 3, 4k + 3], \tag{6} \\ &K_{0,1}[4i-1, 4i], K_{0,1}[4i, 4i + 1], K_{0,1}[4i + 1, 4i + 2], K_{0,1}[4i + 2, 4i + 3], \tag{7} \\ &K_{0,1}[4j-1, 4j], K_{0,1}[4j, 4j + 1], K_{0,1}[4j + 1, 4j + 2], K_{0,1}[4j + 2, 4j + 3], \tag{8} \\ &K_{0,1}[4k-1, 4k], K_{0,1}[4k, 4k + 1], K_{0,1}[4k + 1, 4k + 2], K_{0,1}[4k + 2, 4k + 3], \tag{9} \end{align} then we can combine first 3 bits in (4) and last 3 bits in (7) to get 3 bits \begin{equation*} K_{1}[4i, 4i + 1], K_{1}[4i + 1, 4i + 2], K_{1}[4i + 2, 4i + 3].\end{equation*}

Similarly, we can get \begin{align}&K_{1}[4j, 4j + 1], K_{1}[4j + 1, 4j + 2], K_{1}[4j + 2, 4j + 3], \\ &K_{1}[4k, 4k + 1], K_{1}[4k + 1, 4k + 2], K_{1}[4k + 2, 4k + 3]. \end{align} Once we get one bit $K_1[4i,~4j,~4k]$, as we already know $$K_{1}[4i, 4i + 1]\oplus K_{1}[4j, 4j + 1]\oplus K_{1}[4k, 4k + 1],$$ then we get another three bits $$K_1[4i+1, 4j+1, 4k+1], K_1[4i+2, 4j+2, 4k+2], K_1[4i+3, 4j+3, 4k+3].$$


References

[1] Biham E, Shamir A. Differential Cryptanalysis of the Data Encryption Standard. Berlin: Springer, 1993. Google Scholar

[2] Blondeau C, Gérard B. Multiple differential cryptanalysis: theory and practice. In: Proceedings of International Workshop on Fast Software Encryption, 2011. 35--54. Google Scholar

[3] Wang M Q, Sun Y, Tischhauser E, et al. A model for structure attacks, with applications to PRESENT and Serpent. In: Proceedings of International Workshop on Fast Software Encryption, 2012. 49--68. Google Scholar

[4] Bogdanov A, Knudsen L R, Leander G, et al. PRESENT: an ultra-lightweight block cipher. In: Proceedings of International Workshop on Cryptographic Hardware and Embedded Systems, 2007. 450--466. Google Scholar

[5] Dobraunig C, Eichlseder M, Kales D, et al. Practical key-recovery attack on MANTIS5. In: Proceedings of International Workshop on Fast Software Encryption, 2016. 248--260. Google Scholar

[6] Eichlseder M, Kales D. Clustering related-tweak characteristics: application to MANTIS-6. In: Proceedings of International Workshop on Fast Software Encryption, 2018. 111--132. Google Scholar

[7] Beierle C, Jean J, Kölbl S, et al. The SKINNY family of block ciphers and its low-latency variant MANTIS. In: Proceedings of Annual International Cryptology Conference, 2016. 123--153. Google Scholar

[8] Borghoff J, Canteaut A, Güneysu T, et al. PRINCE -- a low-latency block cipher for pervasive computing applications. In: Proceedings of International Conference on the Theory and Application of Cryptology and Information Security, 2012. 208--225. Google Scholar

[9] Sun S W, Hu L, Wang M Q, et al. Automatic enumeration of (related-key) differential and linear characteristics with predefined properties and its applications. 2014. https://eprint.iacr.org/eprint-bin/getfile.pl?entry=2014/747&version=20140926:084100&file=747.pdf. Google Scholar

[10] Sun S W, Hu L, Wang P, et al. Automatic security evaluation and (related-key) differential characteristic search: application to SIMON, PRESENT, LBlock, DES(L) and other bit-oriented block ciphers. In: Proceedings of International Conference on the Theory and Application of Cryptology and Information Security, 2014. 158--178. Google Scholar

[11] Gurobi Optimization. Gurobi optimizer reference manual. 2018. Google Scholar

[12] Balas E, Jeroslow R. Canonical Cuts on the Unit Hypercube. SIAM J Appl Math, 1972, 23: 61-69 CrossRef Google Scholar

[13] Sel?uk A A. On Probability of Success in Linear and Differential Cryptanalysis. J Cryptol, 2008, 21: 131-147 CrossRef Google Scholar

  • Figure 5

    MixColumns ($M$).

  • Figure 6

    (Color online) Multiple differential attack on MANTIS-6.

  • Figure 7

    (Color online) Multiple differential attack on MANTIS-7.

  • Figure 8

    (Color online) Key cells involved in condition (V1 & V2 & V3 & V4).

  • Table 1   Summary of attacks on MANTIS
    Target version Data ($D$) Time ($T$) $D~\times~T$ Source
    MANTIS-5 $2~^~{28}$ $2~^~{38}$ $2~^~{66}$ Ref. [5]
    MANTIS-6 $2~^~{55.09}$ $2~^~{55.52}$ $2~^~{110.61}$ Ref.[6]
    MANTIS-6 $2^{51.79}~$ $2^{51.91}$ $2^{103.70}$ Section sect. 4
    MANTIS-7 $2~^~{61.86}$ $2~^~{102.92}$ $2~^~{164.78}$ Section sect. 5
  •   

    Algorithm 1 New method to cluster multiple differentials

    Require:$\mathcal{M}$: $r$-round MILP differential model of the target cipher. $N_1$: the number of sample differential characteristics to find enough Patterns. $N_2$: the number of sample differential characteristics under each pair of Patterns.

    Output:${\rm~Dist}~=~\{{\rm~Dist}_{(\alpha,~\gamma)}~|(\alpha,~\gamma)~\in~{\rm~Act}_{\Delta_{\rm~in},\Delta_{\rm~out}}\}$: $~|{\rm~Act}_{\Delta_{\rm~in},\Delta_{\rm~out}}~|$ multiple differentials.

    $\mathcal{M}_1~=~\mathcal{M}$;

    ${\rm~sol\_count}~=~0$;

    ${\rm~Act}_{\Delta_{\rm~in},\Delta_{\rm~out}}$ := None;

    while ${\rm~sol\_count}~<~N_1$ do

    ${\rm~curr\_sol}$ = Solve the model $\mathcal{M}_1$ to get the best differential characteristic;

    Extract $(\Delta_{\rm~in},\Delta_{\rm~out})$ from ${\rm~curr\_sol}$ and get $(\bar{\Delta}_{\rm~in},~\bar{\Delta}_{\rm~out})$;

    ${\rm~Act}_{\Delta_{\rm~in},\Delta_{\rm~out}}$ = ${\rm~Act}_{\Delta_{\rm~in},\Delta_{\rm~out}}~\cup~(\bar{\Delta}_{\rm~in},~\bar{\Delta}_{\rm~out})$;

    Add $l^{({\rm~curr\_sol})}$ to update model $\mathcal{M}_1$;

    ${\rm~sol\_count}$+;

    end while

    ${\rm~Dist}$ := None;

    for each pair of Patterns $(\bar{\Delta}_{\rm~in},~\bar{\Delta}_{\rm~out})~\in~{\rm~Act}_{\Delta_{\rm~in},\Delta_{\rm~out}}$

    $\mathcal{M}_2~=~\mathcal{M}$;

    ${\rm~sol\_count}~=~0$;

    ${\rm~Dist}_{(\bar{\Delta}_{\rm~in},~\bar{\Delta}_{\rm~out})}$ := None;

    Add constrains corresponding with $(\bar{\Delta}_{\rm~in},~\bar{\Delta}_{\rm~out})$ to model $\mathcal{M}_2$;

    while ${\rm~sol\_count}~<~N_2$ do

    ${\rm~curr\_sol}$ = Solve the model $\mathcal{M}_2$ to get the best differential characteristic;

    Extract $(\Delta_{\rm~in},\Delta_{\rm~out})$ from ${\rm~curr\_sol}$;

    ${\rm~Dist}_{(\bar{\Delta}_{\rm~in},~\bar{\Delta}_{\rm~out})}~=~{\rm~Dist}_{(\bar{\Delta}_{\rm~in},~\bar{\Delta}_{\rm~out})}~\cup~(\Delta_{\rm~in},\Delta_{\rm~out})$;

    Add $l^{({\rm~curr\_sol})}$ to update model $\mathcal{M}_2$;

    ${\rm~sol\_count}$+;

    end while

    ${\rm~Dist}~=~{\rm~Dist}~\cup~{\rm~Dist}_{(\bar{\Delta}_{\rm~in},~\bar{\Delta}_{\rm~out})}$;

    end for

    return Dist.

  • Table 2   The distribution of active nibbles' differences of the state after $S$ in round 2 of 1664 trails with probability $2~^~{-28}$ under ${\rm~Dist}'_{\alpha_0}$
    Differences a f d 5 7
    $N_0$ 1408 160 16 16 64
    $N_5$* 1408 160 16 16 64
    $N_6$ 1160 328 88 88 0
    $N_7$ 1664 0 0 0 0
    $N_8$ 1664 0 0 0 0
    $N_{10}$* 1408 160 16 16 64
    $N_{12}$ 1160 328 88 88 0
    $N_{14}$ 1664 0 0 0 0

    *

  •   

    Algorithm 2 Improved multiple differentials enumerating algorithm

    Require:$\mathcal{M}_{(\bar{\Delta}_{\rm~in},~\bar{\Delta}_{\rm~out})}$: multiple differentials model of the target cipher under ${\rm~Dist}_{(\bar{\Delta}_{\rm~in},~\bar{\Delta}_{\rm~out})}$.

    Output: $O_{(\bar{\Delta}_{\rm~in},~\bar{\Delta}_{\rm~out})}$: all characteristics for multiple differentials under ${\rm~Dist}_{(\bar{\Delta}_{\rm~in},~\bar{\Delta}_{\rm~out})}$.

    $H~:=~{\rm~None}$;

    while True do

    Solve the model $\mathcal{M}_{(\bar{\Delta}_{\rm~in},~\bar{\Delta}_{\rm~out})}$;

    if model $\mathcal{M}_{(\bar{\Delta}_{\rm~in},~\bar{\Delta}_{\rm~out})}$ is infeasible then

    break;

    end if

    ${\rm~curr\_sol}$ = extract a characteristic from the solution returned by solver (get the approximate solution when the solution has continuous values);

    Check the status of ${\rm~curr\_sol}$;

    if the status of ${\rm~curr\_sol}$ is an invalid characteristic then

    Continue;

    end if

    if ${\rm~Hash}({\rm~curr\_sol})~\in~H$ then

    Continue;

    else

    $H$ = $H~\cup~{\rm~Hash}({\rm~curr\_sol})$;

    Record ${\rm~curr\_sol}$ to $O_{(\bar{\Delta}_{\rm~in},~\bar{\Delta}_{\rm~out})}$;

    end if

    Add $l^{({\rm~curr\_sol})}$ to update model $\mathcal{M}_{(\bar{\Delta}_{\rm~in},~\bar{\Delta}_{\rm~out})}$;

    end while

    return $O_{(\bar{\Delta}_{\rm~in},~\bar{\Delta}_{\rm~out})}$.

  • Table 3   Number of trails for each output state$^{\rm~a)}$
    State after $S$ in round 12 Number of differential trails
    $\{\rm~a,0,0,0,0,a,a,a,a,0,a,0,a,0,a,0\}$ 32
    $\{{\rm~a},0,0,0,0,{\rm~a},G_6,{\rm~a},{\rm~a},0,G_6,0,{\rm~a},0,G_6,0\}$ 52
    $\{G_7,0,0,0,0,{\rm~a},G_6,{\rm~a},G_7,0,G_6,0,G_7,0,G_6,0\}$ 116
    $\{{\rm~a},0,0,0,~0,{\rm~a},G_6,G_8,~{\rm~a},0,G_6,0,~{\rm~a},0,G_6,0\}$ 208
    $\{{\rm~a},0,0,0,~0,G_9,G_6,G_8,~{\rm~a},0,G_6,0,~{\rm~a},0,G_6,0\}$ 640

    a

  • Table 4   Conditions and their filter probabilities in key recovery on MANTIS-6
    Rounds Condition Nibbles Difference Probability Key bits
    1 (C1) $\delta_{2,8,13}$ $\{\rm~a,f,d,5\},{\rm~equal}^*$ $2~^~{-9.1}$ 12
    (C2) $\delta_{4,11,14}$ ${\rm~\{a,f,d,5\},equal[+a]}^{**}$ $2~^~{-9.21}$ 12
    (C3) $\delta_{10}$ $\rm{\{a,f,d,5\}+a}$ $2~^~{-1.81}$ 4
    (C4) $\delta_{6}$ $\rm{\{a,f,d,5\}}$ $2~^~{-1.7}$ 4
    12(C5) $\delta_{2,8,13}$ $\rm{\{a,f,d,5\}}$ $2~^~{-9.1}$ 12
    (C6) $\delta_{4,11,14}$ $\rm{\{a,f,d,5\},equal[+a]}$ $2~^~{-9.21}$ 12
    (C7) $\delta_{6}$ $\rm{\{a,f,d,5\}}$ $2~^~{-1.7}$ 4
    2,11 (C8) $\delta_{2\oplus~8~\oplus~13}$ $\rm{\{a\}}$ $2~^~{-4}$ 1
    (C9) $\delta_{4\oplus11~\oplus~14}$ $\rm{\{a,f,d,5\}}$ $2~^~{-2}$ 1

    *

  • Table 5   Conditions for key recovery and filter probabilities on MANTIS-6 (for 7 right pairs)
    Round Condition Nibbles Difference Probability
    2 (V1) $\delta_{14}$ $\rm{\{a\}}$ $2~^~{-2}$
    2 (V2) $\delta_{5,~10}$ $\rm{\{a,f,d,5,7\},~equal}$ $2~^~{-3.30}$
    11 (V3) $\delta_{10}$ $\rm{\{a,f,d,5\}}$ $2~^~{-1}$
    11 (V4) $\delta_{14}$ $\rm{\{a\}}$ $2~^~{-2}$
  • Table 6   Conditions for key recovery and filter probability on MANTIS-7
    Round Condition Nibbles Difference Probability Key bits
    1 (C1) $\delta_{3}$ a $1$ 4
    2 (C2) $\delta_{2\oplus~7~\oplus~13}$ a $2~^~{-2}$ 1
    13 (C3) $\delta_{2\oplus~7~\oplus~13}$ a $2~^~{-2}$ 1
    (C4) $\delta_{1\oplus~11~\oplus~14}$ a $2~^~{-2}$ 1
    (C5) $\delta_{3\oplus~6~\oplus~9}$ a $2~^~{-2}$ 1
    (C6) $\delta_{3\oplus~9~\oplus~12}$ a $2~^~{-2}$ 1
    (C7) $\delta_{0\oplus~10~\oplus~15}$ a $2~^~{-2}$ 4
    (C8) $\delta_{0\oplus~5~\oplus~10}$ a $2~^~{-2}$ 4
    12 (C9) $\delta_{2\oplus~8~\oplus~13}$ a $2~^~{-2}$ 4

Copyright 2020 Science China Press Co., Ltd. 《中国科学》杂志社有限责任公司 版权所有

京ICP备17057255号       京公网安备11010102003388号