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 2^125.47 using the structural linear relations.[1] In the related key setting, the data complexity is 2^33 and the time complexity 2^64.[1] Using related key boomerang attack the complexity is 2^39 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 bits. The key is split into two 64 bit keys ${\displaystyle K_{0}}$ and ${\displaystyle K_{1}}$. The input is XORed with ${\displaystyle K_{0}}$, then is processed by a core function using ${\displaystyle K_{1}}$. The output of the core function is xored by ${\displaystyle K'_{0}}$ to produce the final output (${\displaystyle K_{0}'}$ is a value derived from ${\displaystyle K_{0}}$). The decryption is done by exchanging ${\displaystyle K_{0}}$ and ${\displaystyle K'_{0}}$ and by feeding the core function with ${\displaystyle K_{1}}$ xored with a constant denoted alpha.^[4]

The core function contain 5 "forward" rounds, a middle round, and 5 "backward" rounds, for 11 rounds in total. The original paper mentions 12 rounds without explicitly depicting them; if the middle round is counted as two rounds (as it contains two nonlinear layers), then the total number of rounds is 12.

A forward round starts with a round constant XORed with ${\displaystyle K_{1}}$, then a nonlinear layer ${\displaystyle S}$, and finally a linear layer ${\displaystyle M}$. The "backward" rounds are exactly the inverse of the "forward" rounds except for the round constants.

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

The linear layer consists of multiplication by a 64x64 matrix ${\displaystyle M'}$ and a shift row similar to the one in AES but operating on 4-bit nibbles rather than bytes.

${\displaystyle M'}$ is constructed from 16x16 matrices ${\displaystyle M_{0}}$ and ${\displaystyle M_{1}}$ in such a way that the multiplication by ${\displaystyle M'}$ can be computed by four smaller multiplications, two using ${\displaystyle M_{0}}$ and two using ${\displaystyle M_{1}}$.

The middle round consists of the ${\displaystyle S}$ layer followed by ${\displaystyle M'}$ followed by the ${\displaystyle S^{-1}}$ layer.

Cryptanalysis

To encourage cryptanalysis of the Prince cipher, the organizations behind it created the "Prince challenge". Archived from the original on 2016-10-23. Retrieved 2016-10-09.

The paper "Security analysis of PRINCE"^[1] presents several attacks on full and round reduced variants, in particular, an attack of complexity 2^125.1 and a related key attack requiring 2³³ data.

A generic time–memory–data tradeoff for FX constructions has been published, with an application to Prince.^[5] The paper argues 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 presents 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 2^1.28 (the original paper mentions a factor 2). ^[6]

The paper "Reflection Cryptanalysis of PRINCE-Like Ciphers" focuses on the alpha reflection and establishes choice criteria for the alpha constant. It shows that a poorly chosen alpha would lead to efficient attacks on the full cipher; but the value randomly chosen by the designers is not among the weak ones.^[7]

Several meet-in-the-middle attacks have been published on round reduced versions.^[8][9][10]

An attack in the multi-user setting can find the keys of 2 users among a set of 2³² users in time 2⁶⁵.^[11]

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

An attack on 7 rounds with time complexity of 2⁵⁷ operations has been published.^[13]

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

The paper "New approaches for round-reduced PRINCE cipher cryptanalysis"^[15] 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.^[16][17]

Most practical attacks on reduced round versions

Number of rounds	Time	Data	Method
4	2^43.4	33	Meet-in-the-middle[8]
4	5*2^8	80	Integral[13]
5	2^29	96	Integral[13]
6	2^25.1	30574	Differential cryptanalysis[8]
6	2^41	393216	Integral[13]
6	2^34	2^32	Boomerang[15]
8	2^50.7	2^16	Meet-in-the-middle[8]

References

1. Jean, Jérémy; Nikolic, Ivica; Peyrin, Thomas; Wang, Lei; Wu, Shuang (2013). "Security analysis of PRINCE" (PDF). Fast Software Encryption.
2. Kilian, Joe; Rogaway, Phillip (1996). "How to Protect DES Against Exhaustive Key Search". Advances in Cryptology – CRYPTO '96. Lecture Notes in Computer Science. Vol. 1109. pp. 252–267. doi:10.1007/3-540-68697-5_20. ISBN 978-3-540-61512-5.
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). {{cite journal}}: Cite journal requires |journal= (help)
4. International Conference on the Theory and Application of Cryptology and Information Security, ed. (2012). Advances in cryptology--ASiACRYPT 2012: 18th international conference on the theory and application of cryptology and information security, Beijing, China, December 2-6, 2012 proceedings. Lecture notes in computer science. Heidelberg New York: Springer. ISBN 978-3-642-34961-4.
5. Dinur, Itai. "Cryptanalytic Time-Memory-Data Tradeoffs for FX-Constructions with Applications to PRINCE and PRIDE" (PDF). {{cite journal}}: Cite journal requires |journal= (help)
6. Abed, Farzaneh; List, Eik; Lucks, Stefan. "On the Security of the Core of PRINCE Against Biclique and Differential Cryptanalysis" (PDF). {{cite journal}}: Cite journal requires |journal= (help)
7. Soleimany, Hadi; Blondeau, Céline; Yu, Xiaoli; Wu, Wenling; Nyberg, Kaisa; Zhang, Huiling; Zhang, Lei; Wang, Yanfeng. "Reflection Cryptanalysis of PRINCE-Like Ciphers" (PDF). {{cite journal}}: Cite journal requires |journal= (help)
8. Perrin, Leo; Derbez, P. "Meet-in-the-Middle Attacks and Structural Analysis of Round-Reduced PRINCE" (PDF). {{cite journal}}: Cite journal requires |journal= (help)
9. Li, Leibo; Jia, Keting; Wang, Xiaoyun. "Improved Meet-in-the-Middle Attacks on AES-192 and PRINCE" (PDF). {{cite journal}}: Cite journal requires |journal= (help)
10. Canteaut, A.; Naya-Plasencia, M.; Vayssière, B. (2013). "Sieve-in-the-Middle: Improved MITM Attacks". Advances in Cryptology – CRYPTO 2013. Lecture Notes in Computer Science. Vol. 8042. pp. 222–240. doi:10.1007/978-3-642-40041-4_13. ISBN 978-3-642-40040-7.
11. Fouque, Pierre-Alain; Joux, Antoine; Mavromati, Chrysanthi. "Multi-user collisions: Applications to Discrete Logs, Even-Mansour and Prince" (PDF). {{cite journal}}: Cite journal requires |journal= (help)
12. Canteaut, Anne; Fuhr, Thomas; Gilbert, Henri; Naya-Plasencia, Maria; Reinhard, Jean-René. "Multiple Differential Cryptanalysis of Round-Reduced PRINCE" (PDF). {{cite journal}}: Cite journal requires |journal= (help)
13. Morawiecki, P. "Practical Attacks on the Round-reduced PRINCE" (PDF). {{cite journal}}: Cite journal requires |journal= (help)
14. Song, Ling; Hu, Lei. "Differential Fault Attack on the PRINCE Block Cipher" (PDF). {{cite journal}}: Cite journal requires |journal= (help)
15. Posteuca, R.; Duta, C.; Negara, G. "New approaches for round-reduced PRINCE cipher cryptanalysis" (PDF). {{cite journal}}: Cite journal requires |journal= (help)
16. Posteuca, R.; Negara, G. (2015). "Integral cryptanalysis of round-reduced PRINCE cipher". Proceedings of the Romanian Academy. Series A. Mathematics, Physics, Technical Sciences, Information Science. 16.
17. Zhao, G.; Sun, B.; Li, C.; Su, J. (2015). "Truncated differential cryptanalysis of PRINCE". Security and Communication Networks. 8 (16): 2875–2887. doi:10.1002/sec.1213. S2CID 30147147.

External links

• http://eprint.iacr.org/2012/529.pdf original paper: "PRINCE – A Low-latency Block Cipher for Pervasive Computing Applications"
• https://www.emsec.rub.de/research/research_startseite/prince-challenge The Prince challenge home page
• https://github.com/sebastien-riou/prince-c-ref Software Implementations in C
• https://github.com/weedegee/prince Software Implementations in Python
• https://github.com/huljar/prince-vhdl Hardware Implementation in VHDL