Prince | |
Publish Date: | 2012 |
Derived From: | AES, PRESENT |
Key Size: | 128 bits |
Block Size: | 64 bits |
Structure: | SPN |
Rounds: | 11 (but 12 non-linear layers) |
Cryptanalysis: | a single key can be recovered with a computational complexity of 2125.47 using the structural linear relations. In the related key setting, the data complexity is 233 and the time complexity 264. Using related key boomerang attack the complexity is 239 for both data and time. |
Prince is a block cipher targeting low latency, unrolled hardware implementations. It is based on the so-called FX construction.[1] 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.[2]
The block size is 64 bits and the key size is 128 bits. The key is split into two 64 bit keys
K0
K1
K0
K1
K'0
K0'
K0
K0
K'0
K1
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
K1
S
M
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
M'
M'
M0
M1
M'
M0
M1
The middle round consists of the
S
M'
S-1
To encourage cryptanalysis of the Prince cipher, the organizations behind it created the Web site: Prince challenge. 2016-10-09. 2016-10-23. https://web.archive.org/web/20161023201531/https://www.emsec.rub.de/research/research_startseite/prince-challenge/. dead.
The paper "Security analysis of PRINCE"[4] 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]
Number of rounds | Time | Data | Method | |||
---|---|---|---|---|---|---|
4 | data-sort-value="43.4" | 243.4 | 33 | Meet-in-the-middle | ||
4 | data-sort-value="8.5" | 5*28 | 80 | Integral | ||
5 | data-sort-value="29" | 229 | 96 | Integral | ||
6 | data-sort-value="33.7" | 225.1 | 30574 | Differential cryptanalysis | ||
6 | data-sort-value="41" | 241 | 393216 | Integral | ||
6 | data-sort-value="34" | 234 | data-sort-value="2000000.32" | 232 | Boomerang | |
8 | data-sort-value="50.7" | 250.7 | data-sort-value="2000000.16" | 216 | Meet-in-the-middle |