logo

SCIENCE CHINA Information Sciences, Volume 63, Issue 1: 112106(2020) https://doi.org/10.1007/s11432-019-1507-1

Cryptanalysis of PRIMATEs

More info
  • ReceivedMar 16, 2019
  • AcceptedAug 2, 2019
  • PublishedDec 24, 2019

Abstract

PRIMATEs is a family of authenticated encryption design submitted to competition for authenticated encryption: security, applicability, and robustness. The three modes of operation in PRIMATEs family are: APE, HANUMAN, GIBBON with security levels: 80, 120 bits. APE is robust despite the nonce misusing. In this study, we revise the algebraic model and find new integral distinguishers for both PRIMATE permutation and its inverse permutation. Moreover, we construct a zero-sum distinguisher for full 12-round PRIMATE-80/120 permutation with the $2^{100}/2^{105}$ complexity, improving over previous work. We also perform an integral attack on 8-round finalization of APE-80/120 with $2^{30}$ chosen messages. The key recovery process is optimized using the FFT technique presented by Todo and Aoki. Our work is the best attack against APE, demonstrating the practical attack on 8-round finalization of APE-80. The new integral distinguishers apply to create forgeries on 5/6-round finalization of APE and HANUMAN that require $2^{15}/2^{30}$ chosen messages, which is the first forgery attack against APE and HANUMAN.


Acknowledgment

This work was supported by National Cryptography Development Fund (Grant No. MMJJ20170102), National Natural Science Foundation of China (Grant Nos. 61572293, 61502276, 61692276), Major Scientific and Technological Innovation Projects of Shandong Province (Grant No. 2017CXGC0704), National Natural Science Foundation of Shandong Province (Grant No. ZR2016FM22), and Open Research Fund from Shandong Provincial Key Laboratory of Computer Network (Grant No. SDKLCN-2017-04).


References

[1] Rogaway P. Authenticated-encryption with associated-data. In: Proceedings of ACM Conference on Computer and Communications Security (CCS), 2002. 98--107. Google Scholar

[2] Bellare M, Namprempre C. Authenticated encryption: relations among notions and analysis of the generic composition paradigm. In: Proceedings of the 6th International Conference on the Theory and Application of Cryptology and Information Security: Advances in Cryptology, 2000. 531--545. Google Scholar

[3] Jutla C. Encryption modes with almost free message integrity. In: Proceedings of the International Conference on the Theory and Application of Cryptographic Techniques: Advances in Cryptology, 2001. 529--544. Google Scholar

[4] Gligor V, Donescu P. Fast encryption and authentication: XCBC encryption and XECB authentication modes. In: Proceedings of International Workshop on Fast Software Encryption, 2002. 92--108. Google Scholar

[5] Rogaway P, Bellare M, Black J, et al. OCB: a block-cipher mode of operation for efficient authenticated encryption. In: Proceedings of ACM Transactions on Information and System Security (TISSEC), 2003. 365--403. Google Scholar

[6] National Institute of Standards and Technology (NIST). Advanced encryption standard (AES). FIPS 197. https://csrc.nist.gov/csrc/media/publications/fips/197/final/documents/fips-197.pdf. Google Scholar

[7] Dworkin M. Recommendation for block cipher modes of operation: Galois/counter mode (GCM) and GMAC. NIST Special Publication 800-38D, 2007. https://www.govinfo.gov/content/pkg/GOVPUB-C13-1e1d0b2a761f50d919d892b9e020965b/pdf/GOVPUB-C13-1e1d0b2a761f50d919d892b9e020965b.pdf. Google Scholar

[8] The CAESAR Committee. CAESAR: competition for authenticated encryption: security, applicability, and robustness. http://competitions.cr.yp.to/caesar.~html. Google Scholar

[9] Andreeva E, Bilgin B, Bogdanov A, et al. PRIMATEs v1.02: submission to the CAESAR competition. http://primates.ae/. Google Scholar

[10] Saha D, Kuila S, Chowdhury D R. EscApe: diagonal fault analysis of APE. In: Proceedings of International Conference on Cryptology in India, 2014. 197--216. Google Scholar

[11] Minaud B. Improved beer-recovery attack against APE. https://aezoo.compute.dtu.dk/doku.php?id=primates. Google Scholar

[12] Morawiecki P, Pieprzyk J, Srebrny M, et al. Applications of key recovery cube-attack-like. 2015. http://eprint.iacr.org/2015/1009.pdf. Google Scholar

[13] Lukas K, Daemen J. Cube attack on primates. Proc Rom Acad, 2017, 18: 293--306. Google Scholar

[14] Todo Y, Aoki K. FFT key recovery for integral attack. In: Proceedings of International Conference on Cryptology and Network Security, 2014. 64--81. Google Scholar

[15] Daemen J, Rijmen V. The wide trail design strategy. In: Proceedings of the 8th IMA International Conference on Cryptography and Coding, 2001. 222--238. Google Scholar

[16] Daemen J, Rijmen V. The Design of Rijndael. Berlin: Springer, 2002. Google Scholar

[17] Boura C, Canteaut A. A zero-sum proposition for the Keccak-$f$ permutation with 18 rounds. In: Proceedings of IEEE International Symposium on Information Theory, 2010. 2488--2492. Google Scholar

[18] Yang M H, Lai X J. The computational method of the algebraic degree of Boolean functions (in Chinese). In: Proceedings of Annual Meeting of Chinese Association for Cryptologic Research, 2009. Google Scholar

[19] Aumasson J P, Meier W. Zero-sum distinguishers for reduced Keccak-$f$ and for the core functions of Luffa and Hamsi. 2009. http://www.131002.net/data/papers/AM09.pdf. Google Scholar

  • Figure 1

    The encryption of APE.

  • Figure 2

    The encryption of HANUMAN.

  • Figure 3

    (Color online) Zero-sum distinguisher for PRIMATE-80.

  • Figure 4

    (Color online) The 8-round integral attack on APE-80.

  • Table 1   Results for PRIMATEs
    Attack type Variants Rounds Data complexity Time complexity Method Scenario Source
    DistinguisherPRIMATE-8012/12 $2^{130}$ Zero-sumRef. [11]
    12/12 $2^{100}$ Section sect. 4
    PRIMATE-12012/12 $2^{130}$ Ref. [11]
    12/12 $2^{105}$ Section sect. 4
    Key recoveryAPE-808/12 $2^{33}$ $2^{61}$ Cube Nonce-misuseRef. [11]*
    8/12 $2^{35}$ $2^{61}$ Cube Ref. [11]
    8/12 $2^{35}$ $2^{39.29}$ Integral Nonce-misuseSection sect. 5
    8/12 $2^{30}$ $2^{39.29}$ Integral Section sect. 5
    Key recoveryAPE-1208/12 $2^{33}$ $2^{71}$ Cube Nonce-misuseRef. [11]*
    8/12 $2^{35}$ $2^{71}$ Cube Ref. [11]
    8/12 $2^{35}$ $2^{50.26}$ Integral Nonce-misuseSection sect. 5
    8/12 $2^{30}$ $2^{50.26}$ Integral Section sect. 5
    ForgeryAPE-80 5/12 $2^{15}$ $2^{15}$ IntegralNonce-misuseSection sect. 6
    APE-80 6/12 $2^{30}$ $2^{30}$ Section sect. 6
    APE-120 5/12 $2^{15}$ $2^{15}$ Section sect. 6
    APE-120 6/12 $2^{30}$ $2^{30}$ Section sect. 6
    Key recovery HANUMAN-120 6/12 $2^{65}$ $2^{65}$ Cube-like Nonce-respecting Ref. [12]
    ForgeryHANUMAN-80 5/12 $2^{15}$ $2^{15}$ IntegralNonce-misuseSection sect. 6
    HANUMAN-80 6/12 $2^{30}$ $2^{30}$ Section sect. 6
    HANUMAN-120 5/12 $2^{15}$ $2^{15}$ Section sect. 6
    HANUMAN-120 6/12 $2^{30}$ $2^{30}$ Section sect. 6

    *

  •   

    Algorithm 1 Distinguisher searching algorithm for 5-round PRIMATE permutation

    for $0<s<\lceil~1.0294(n+1)\rceil$

    Pick $x$ randomly;

    Compute ${\rm~tmp}=\sum_{i=0}^{2^{15}-1}f(x\oplus~i)$;

    if ${\rm~tmp}~\neq~0$ then

    Output “Proposition 3.3 does not hold";

    end if

    end for

  • Table 2   Notations
    Symbol Definition
    $x\in~\{0,1\}^k$ Bitstring $x$ of length $k$ (variable if $k=*$)
    $x\oplus~y$ XOR of bitstrings $x$ and $y$
    $x||y$ Concatenation of bitstrings $x$ and $y$
    $x_i$ $i$-th bit of the state used in PRIMATE permutation
    $X_i$ 5-bit state word of the state used in PRIMATE permutation
    $K$, $N$, $T$ Secret key $K$, nonce $N$, tag $T$
    $P$, $C$, $A$ Plaintext $P$, ciphertext $C$, associated data $A$ (in blocks $P_i$, $C_i$, $A_i$)
    $p_1$, $p_2$, $p_3$, $p_4$ Four different permutations used in PRIMATEs
  •   

    Algorithm 2 Distinguisher searching algorithm for 6-round PRIMATE permutation

    for $0<s<\lceil~1.0294(n+1)\rceil$

    Pick $x$ randomly;

    Compute ${\rm~tmp}=\sum_{i=0}^{2^{30}-1}f(x\oplus~i)$;

    if ${\rm~tmp}~\neq~0$ then

    Output “Proposition 3.4 does not hold";

    end if

    end for

  • Table 3   The $S$-box of PRIMATEs
    $x$ 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
    $S(x)$ 1 0 25 26 17 29 21 27 20 5 4 23 14 18 2 28
    $x$ 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31
    $S(x)$ 15 8 6 3 13 7 24 16 30 9 31 10 22 12 11 19

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

京ICP备18024590号-1