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


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