Prince (cipher)

Last updated
Prince
General
Designers Technical University of Denmark, INRIA, Ruhr University Bochum and NXP Semiconductors
First published2012
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 2

Contents

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 and . The input is XORed with , then is processed by a core function using . The output of the core function is xored by to produce the final output ( is a value derived from ). The decryption is done by exchanging and and by feeding the core function with 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 , then a nonlinear layer , and finally a linear layer . 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 and a shift row similar to the one in AES but operating on 4-bit nibbles rather than bytes.

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

The middle round consists of the layer followed by followed by the 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 2125.1 and a related key attack requiring 233 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 21.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 232 users in time 265. [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 257 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 roundsTimeDataMethod
4243.433 Meet-in-the-middle [8]
45*2880 Integral [13]
522996 Integral [13]
6225.130574 Differential cryptanalysis [8]
6241393216 Integral [13]
6234232 Boomerang [15]
8250.7216 Meet-in-the-middle [8]

Related Research Articles

In cryptography, a block cipher is a deterministic algorithm that operates on fixed-length groups of bits, called blocks. Block ciphers are the elementary building blocks of many cryptographic protocols. They are ubiquitous in the storage and exchange of data, where such data is secured and authenticated via encryption.

<span class="mw-page-title-main">Data Encryption Standard</span> Early unclassified symmetric-key block cipher

The Data Encryption Standard is a symmetric-key algorithm for the encryption of digital data. Although its short key length of 56 bits makes it too insecure for modern applications, it has been highly influential in the advancement of cryptography.

Differential cryptanalysis is a general form of cryptanalysis applicable primarily to block ciphers, but also to stream ciphers and cryptographic hash functions. In the broadest sense, it is the study of how differences in information input can affect the resultant difference at the output. In the case of a block cipher, it refers to a set of techniques for tracing differences through the network of transformation, discovering where the cipher exhibits non-random behavior, and exploiting such properties to recover the secret key.

<span class="mw-page-title-main">International Data Encryption Algorithm</span> Symmetric-key block cipher

In cryptography, the International Data Encryption Algorithm (IDEA), originally called Improved Proposed Encryption Standard (IPES), is a symmetric-key block cipher designed by James Massey of ETH Zurich and Xuejia Lai and was first described in 1991. The algorithm was intended as a replacement for the Data Encryption Standard (DES). IDEA is a minor revision of an earlier cipher, the Proposed Encryption Standard (PES).

<span class="mw-page-title-main">Serpent (cipher)</span>

Serpent is a symmetric key block cipher that was a finalist in the Advanced Encryption Standard (AES) contest, in which it ranked second to Rijndael. Serpent was designed by Ross Anderson, Eli Biham, and Lars Knudsen.

<span class="mw-page-title-main">GOST (block cipher)</span> Soviet/Russian national standard block cipher

The GOST block cipher (Magma), defined in the standard GOST 28147-89, is a Soviet and Russian government standard symmetric key block cipher with a block size of 64 bits. The original standard, published in 1989, did not give the cipher any name, but the most recent revision of the standard, GOST R 34.12-2015, specifies that it may be referred to as Magma. The GOST hash function is based on this cipher. The new standard also specifies a new 128-bit block cipher called Kuznyechik.

<span class="mw-page-title-main">Tiny Encryption Algorithm</span> Block cipher

In cryptography, the Tiny Encryption Algorithm (TEA) is a block cipher notable for its simplicity of description and implementation, typically a few lines of code. It was designed by David Wheeler and Roger Needham of the Cambridge Computer Laboratory; it was first presented at the Fast Software Encryption workshop in Leuven in 1994, and first published in the proceedings of that workshop.

<span class="mw-page-title-main">DES-X</span> Block cipher

In cryptography, DES-X is a variant on the DES symmetric-key block cipher intended to increase the complexity of a brute-force attack. The technique used to increase the complexity is called key whitening.

In cryptography, Khufu and Khafre are two block ciphers designed by Ralph Merkle in 1989 while working at Xerox's Palo Alto Research Center. Along with Snefru, a cryptographic hash function, the ciphers were named after the Egyptian Pharaohs Khufu, Khafre and Sneferu.

The slide attack is a form of cryptanalysis designed to deal with the prevailing idea that even weak ciphers can become very strong by increasing the number of rounds, which can ward off a differential attack. The slide attack works in such a way as to make the number of rounds in a cipher irrelevant. Rather than looking at the data-randomizing aspects of the block cipher, the slide attack works by analyzing the key schedule and exploiting weaknesses in it to break the cipher. The most common one is the keys repeating in a cyclic manner.

Introduced by Martin Hellman and Susan K. Langford in 1994, the differential-linear attack is a mix of both linear cryptanalysis and differential cryptanalysis.

KeeLoq is a proprietary hardware-dedicated block cipher that uses a non-linear feedback shift register (NLFSR). The uni-directional command transfer protocol was designed by Frederick Bruwer of Nanoteq (Pty) Ltd., the cryptographic algorithm was created by Gideon Kuhn at the University of Pretoria, and the silicon implementation was by Willem Smit at Nanoteq Pty Ltd in the mid-1980s. KeeLoq was sold to Microchip Technology Inc in 1995 for $10 million. It is used in "code hopping" encoders and decoders such as NTQ105/106/115/125D/129D, HCS101/2XX/3XX/4XX/5XX and MCS31X2. KeeLoq is or was used in many remote keyless entry systems by such companies as Chrysler, Daewoo, Fiat, GM, Honda, Toyota, Volvo, Volkswagen Group, Clifford, Shurlok, and Jaguar.

In cryptography, COCONUT98 is a block cipher designed by Serge Vaudenay in 1998. It was one of the first concrete applications of Vaudenay's decorrelation theory, designed to be provably secure against differential cryptanalysis, linear cryptanalysis, and even certain types of undiscovered cryptanalytic attacks.

The cube attack is a method of cryptanalysis applicable to a wide variety of symmetric-key algorithms, published by Itai Dinur and Adi Shamir in a September 2008 preprint.

<span class="mw-page-title-main">Threefish</span> Block cipher

Threefish is a symmetric-key tweakable block cipher designed as part of the Skein hash function, an entry in the NIST hash function competition. Threefish uses no S-boxes or other table lookups in order to avoid cache timing attacks; its nonlinearity comes from alternating additions with exclusive ORs. In that respect, it is similar to Salsa20, TEA, and the SHA-3 candidates CubeHash and BLAKE.

<span class="mw-page-title-main">Twofish</span> Block cipher

In cryptography, Twofish is a symmetric key block cipher with a block size of 128 bits and key sizes up to 256 bits. It was one of the five finalists of the Advanced Encryption Standard contest, but it was not selected for standardization. Twofish is related to the earlier block cipher Blowfish.

This article summarizes publicly known attacks against block ciphers and stream ciphers. Note that there are perhaps attacks that are not publicly known, and not all entries may be up to date.

<span class="mw-page-title-main">Speck (cipher)</span> Family of block ciphers

Speck is a family of lightweight block ciphers publicly released by the National Security Agency (NSA) in June 2013. Speck has been optimized for performance in software implementations, while its sister algorithm, Simon, has been optimized for hardware implementations. Speck is an add–rotate–xor (ARX) cipher.

<span class="mw-page-title-main">Simon (cipher)</span> Family of lightweight block ciphers

Simon is a family of lightweight block ciphers publicly released by the National Security Agency (NSA) in June 2013. Simon has been optimized for performance in hardware implementations, while its sister algorithm, Speck, has been optimized for software implementations.

QARMA is a lightweight tweakable block cipher primarily known for its use in the ARMv8 architecture for protection of software as a cryptographic hash for the Pointer Authentication Code. The cipher was proposed by Roberto Avanzi in 2016. Two versions of QARMA are defined: QARMA-64 and QARMA-128. The design of the QARMA was influenced by PRINCE and MANTIS. The cipher is intended for fully-unrolled hardware implementations with low latency. Unlike the XTS mode, the address can be directly used as a tweak and does not need to be whitened with the block encryption first.

References

  1. 1 2 3 4 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. 1 2 3 4 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. 1 2 3 4 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. 1 2 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.
This page is based on this Wikipedia article
Text is available under the CC BY-SA 4.0 license; additional terms may apply.
Images, videos and audio are available under their respective licenses.