Prince (cipher)

Prince
General
Designers Technical University of Denmark, INRIA, Ruhr University Bochum and NXP Semiconductors
First published 2012
Derived from AES, PRESENT
Cipher detail
Key sizes 128 bits
Block sizes 64 bits
Structure SPN
Rounds 11 (but 12 non linear layers)
Best public cryptanalysis

a single key can be recovered with a computational complexity of 2125.47 using the structural linear relations.[1]

In the related key setting, the data complexity is 233 and the time complexity 264.[1]

Using related key boomerang attack the complexity is 239 for both data and time.[1]

Prince is a block cipher targeting low latency, unrolled hardware implementations. It is based on the so-called FX construction.[2] Its most notable feature is the "alpha reflection": the decryption is the encryption with a related key which is very cheap to compute. Unlike most other "lightweight" ciphers, it has a small number of rounds and the layers constituting a round have low logic depth. As a result, fully unrolled implementation are able to reach much higher frequencies than AES or PRESENT. According to the authors, for the same time constraints and technologies, PRINCE uses 6-7 times less area than PRESENT-80 and 14-15 times less area than AES-128.[3]

Overview

The block size is 64 bits and the key size is 128 bit. The key is split in two 64 bit keys K0 and K1. The input is xored with K0, then is processed by a core function using K1. The output of the core function is xored by K0' to produce the final output (K0' is a value derived from K0). The decryption is done by exchanging K0 and K0' and by feeding the core function with K1 xored with a constant denoted alpha.

The core function contain 5 "forward" rounds, a middle round and then 5 "backward" rounds, so 11 rounds in total. The original paper mention 12 rounds without explicitly depicting them. The middle round can be seen as two rounds as it contains two non linear layers, then the total number of rounds is 12.

A forward round start by a xor with a round constant xor K1, then a non linear layer S and then a linear layer M. The "backward" rounds are exactly the inverse of the "forward" rounds except for the round constants.

The non-linear layer is based on a single 4-bit S-box which can be chosen among the affine-equivalent of 8 specified sboxes.

The linear layer consist of a multiplication by a 64x64 matrix M' and a shift row similar to the one of AES but operating on 4 bits nibble rather than bytes.

M' is constructed from 16x16 matrices M0 and M1 in such a way that the multiplication by M' can be computed by four smaller multiplications, two using M0 and two using M1.

The middle round consist of the S layer followed by M' followed by S−1 layer.

Cryptanalysis

To encourage cryptanalysis of the Prince cipher, the organizations behind it created the "Prince challenge". 

The paper "Security analysis of PRINCE"[1] presents several attacks on full and round reduced variants. In particular, an attack of complexity 2125.1 and a related key attack requiring 233 data.

A generic time-memory-data tradeoffs for FX constructions has been published, with an application to Prince.[4] The paper argue that the FX construction is a fine solution to improve the security of a widely deployed cipher (like DES-X did for DES) but that it is a questionable choice for new designs. It present a tweak to the Prince cipher to strengthen it against this particular kind of attack.

A biclique cryptanalysis attack has been published on the full cipher. It is somewhat inline with the estimation of the designers since it reduces the key search space by 21.28 (the original paper mention a factor 2) [5]

The paper "Reflection Cryptanalysis of PRINCE-Like Ciphers" focus on the alpha reflection and establish choice criteria for the alpha constant. It shows that poorly chosen alpha would lead to efficient attacks on the full cipher, fortunately the value randomly chosen by the designers is not among the weak ones[6]

Several meet in the middle attacks have been published on round reduced versions[7][8][9]

An attack in the multi-user setting find the keys of 2 users among a set of 232 users in time 265[10]

An attack on 10 rounds with overall complexity of 118.56 bits has been published[11]

An attack on 7 rounds with time complexity of 257 operations has been published.[12]

A differential fault attack has been published using 7 faulty cipher texts under random 4 bit nibble fault model[13]

The paper "New approaches for round-reduced PRINCE cipher cryptanalysis"[14] presents boomerang attack and known plaintext attack on reduced round versions up to 6 rounds.

In 2015 few additional attacks have been published but are not freely available[15][16]

Most practical attacks on reduce round versions

Number of rounds Time Data Method
4 243.4 33 Meet-in-the-Middle[7]
4 5*28 80 Integral[12]
5 229 96 Integral[12]
6 225.1 30574 Differential cryptanalysis[7]
6 241 393216 Integral[12]
6 234 232 Boomerang[14]
8 250.7 216 Meet-in-the-Middle[7]

References

  1. 1 2 3 4 Jean, Jérémy; Nikolic, Ivica; Peyrin, Thomas; Wang, Lei; Wu, Shuang. "Security analysis of PRINCE" (PDF).
  2. ↑ Kilian, Joe; Rogaway, Phillip. "How to Protect DES Against Exhaustive Key Search". In Neal Koblitz, editor, CRYPTO, volume 1109 of Lecture Notes in Computer Science, pages 252–267. Springer, 1996.
  3. ↑ Borghoff, Julia; Canteaut, Anne; Guneysu, Tim; Bilge Kavun, Elif; Knezevic, Miroslav; Knudsen, Lars R.; Leander, Gregor; Nikov, Ventzislav; Paar, Christof; Rechberger, Christian; Rombouts, Peter; Thomsen, Søren S.; Yalcın, Tolga. "PRINCE – A Low-latency Block Cipher for Pervasive Computing Applications" (PDF).
  4. ↑ Dinur, Itai. "Cryptanalytic Time-Memory-Data Tradeoffs for FX-Constructions with Applications to PRINCE and PRIDE" (PDF).
  5. ↑ Abed, Farzaneh; List, Eik; Lucks, Stefan. "On the Security of the Core of PRINCE Against Biclique and Differential Cryptanalysis" (PDF).
  6. ↑ Soleimany, Hadi; Blondeau, Céline; Yu, Xiaoli; Wu, Wenling; Nyberg, Kaisa; Zhang, Huiling; Zhang, Lei; Wang, Yanfeng. "Reflection Cryptanalysis of PRINCE-Like Ciphers" (PDF).
  7. 1 2 3 4 Perrin, Leo; Derbez, P. "Meet-in-the-Middle Attacks and Structural Analysis of Round-Reduced PRINCE" (PDF).
  8. ↑ Li, Leibo; Jia, Keting; Wang, Xiaoyun. "Improved Meet-in-the-Middle Attacks on AES-192 and PRINCE" (PDF).
  9. ↑ Canteaut, A.; Naya-Plasencia, M.; Vayssière, B. "Sieve-in-the-Middle: Improved MITM Attacks". Advances in Cryptology–CRYPTO 2013, 222-240.
  10. ↑ Fouque, Pierre-Alain; Joux, Antoine; Mavromati, Chrysanthi. "Multi-user collisions: Applications to Discrete Logs, Even-Mansour and Prince" (PDF).
  11. ↑ Canteaut, Anne; Fuhr, Thomas; Gilbert, Henri; Naya-Plasencia, Maria; Reinhard, Jean-René. "Multiple Differential Cryptanalysis of Round-Reduced PRINCE" (PDF).
  12. 1 2 3 4 Morawiecki, P. "Practical Attacks on the Round-reduced PRINCE" (PDF).
  13. ↑ Song, Ling; Hu, Lei. "Differential Fault Attack on the PRINCE Block Cipher" (PDF).
  14. 1 2 Posteuca, R.; Duta, C.; Negara, G. "New approaches for round-reduced PRINCE cipher cryptanalysis" (PDF).
  15. ↑ Posteuca, R.; Negara, G. "Integral cryptanalysis of round-reduced PRINCE cipher". Proc. Rom. Acad. Ser. A Math. Phys. Tech. Sci. Inf. Sci. 16 (2015), Special issue, 265–269.
  16. ↑ Zhao, G.; Sun, B.; Li, C.; Su, J. "Truncated differential cryptanalysis of PRINCE". Security and Communication Networks, 2015.

External links

This article is issued from Wikipedia - version of the 11/22/2016. The text is available under the Creative Commons Attribution/Share Alike but additional terms may apply for the media files.