The PRINCE Challenge

The paper describing the algorithm has been published at ASIACRYPT 2012, a full version is available here. Furthermore, to simplify the work and to rule out any potential confusion we will provide a reference C implementation here which allows in particular to set the number of rounds to be processed (coming soon).

The Challenges

The challenges come in two flavors, one in the known plaintext setting and the other in the chosen plaintext setting. For each setting there are 5 challenges which differ by the number of rounds to be attacked.

Setting 1: Given 2²⁰ chosen plaintexts/cipher texts

• How fast can you break 4 rounds?
  – Round-1 winner: Paweł, 2⁷ CP, time 2¹¹
  – Final-Round winner:
  • Integral attack by Håvard Raddum and Shahram Rasoolzadeh, 2⁶ texts, time: 2^7.4
  • Subspace trail attack by Lorenzo Grassi and Christian Rechberger: 17 texts, time: 2¹⁹
• How fast can you break 6 rounds?
  – Round-2 winner: Raluca and Gabriel, 2^14.6 CP, time 2³⁷
  – Final-Round winner:
  • Integral attack by Håvard Raddum and Shahram Rasoolzadeh, 2¹³ texts, time: 2^24.6, memory: 2¹³
• How fast can you break 8 rounds?
  – Winner: Patrick: 2¹⁶ CP, time 2^66.4
• How fast can you break 10 rounds?
• How fast can you break 12 rounds?

Setting 2: Given 2³⁰ known plaintexts

• How fast can you break 4 rounds?
  – Round-1 winner: Patrick: 2⁵ KP, time 2⁴³
• How fast can you break 6 rounds?
  – Round-1 winner: Patrick: 2⁶ KP, time 2¹⁰¹
  – Final-Round winner:
  • Accelerated Exhaustive Search attack by Håvard Raddum and Shahram Rasoolzadeh, 2 texts, time: 2^86.0 + 2^⁹⁴ M.A. = 2⁸⁹, memory: 2^24.6
• How fast can you break 8 rounds?
  – Final-Round winner:
  • Accelerated Exhaustive Search attack by Håvard Raddum and Shahram Rasoolzadeh, 2 texts, time: 2^122.7
  • MITM attack by Håvard Raddum and Shahram Rasoolzadeh, 2 texts, time: 2^109.3, memory: 2^65>
• How fast can you break 10 rounds?
  – Final-Round winner:
  • Accelerated Exhaustive Search attack by Håvard Raddum and Shahram Rasoolzadeh, 2 texts, time: 2^124.1
  • MITM attack by Håvard Raddum and Shahram Rasoolzadeh, 2 texts, time: 2^122.2, memory: 2^53.3>
• How fast can you break 12 rounds?
  – Final-Round winner:
  • Accelerated Exhaustive Search attack by Håvard Raddum and Shahram Rasoolzadeh, 2 texts, time: 2^125.1

For the second setting, we will provide (large!) files with plaintexts/cipher text pairs upon request (prince-challenge@compute.dtu.dk).

Winners of Round 1

• Patrick Derbez
  SnT, University of Luxembourg
• Léo Perrin
  SnT, University of Luxembourg
• Paweł Morawiecki
  Polish Academy of Sciences, Computer Science Institute, and Kielce University of Commerce, Poland

Winners of Round 2

• Patrick Derbez
  SnT, University of Luxembourg
• Raluca Posteucå and Gabriel Negarå
  Alexandru Ioan Cuza University, Romania

Winners of Round 3

• Shahram Rasoolzadeh and Håvard Raddum
  Simula Research Laboratory, Norway
• Christian Rechberger
  Technical University of Denmark
• Lorenzo Grassi
  Lund University, Sweden

Submission

If you have a successful attack submit the technical report/paper/code/keys explaining the attack to prince-challenge@compute.dtu.dk

The attack procedure must become clear from your submission, submitting a key only is not a valid submission. All submissions before the deadline will be considered.

The committee will evaluate the submissions and might give bonus points for even lower data complexities and bonus points for interesting observations used in the attack. If attacks with identical complexities are submitted the prizes might be distributed among the winning participants.

The committee will make a short description of the winning attack(s) public on this website.

Deadline

There are (for now) two rounds of the competition planned. Depending on how things evolve this is subject to change. In particular we might add additional rounds later.

• 1st round submission deadline: one week before Crypto 2014
• 2nd round submission (extended) deadline: 24.4.2015, just before Eurocrypt 2015
• 3rd round submission deadline: April 2016

The Prizes

There are two categories of prizes.

Appetizers

For all the above settings we provide Belgian chocolate and/or Belgian beers. Details and quantities depend on budget, travel, and taste.

Money Prizes

For real breaks there will be real prizes. To qualify for those, the attack has to meet additional criteria. Namely:

• Break 8, 10 or 12 rounds
• Time complexity below an equivalent of 2⁶⁴ encryptions of the corresponding round reduced variant
• Memory complexity below 2⁴⁵ bytes

The prizes are:

• 1,000 EUR for 8 rounds
• 4,000 EUR for 10 rounds
• 10,000 EUR for 12 rounds

The Rules

The submitter/submitters hereby consent to all decisions of the committee regarding the selection or non-selection of this submission. The submitter/submitters acknowledge that the committee decisions reflect the collective expert judgments of the committee members and are not subject to appeal.

Committee

• Gregor Leander (RUB)
• Ventzi Nikov (NXP)
• Christian Rechberger (DTU)
• Vincent Rijmen (KU Leuven)

Existing Cryptanalysis

Besides the initial cryptanalysis in the original paper, quite a lot of work has been published on PRINCE already. We provide a list of papers we are aware of here (if you know of/are an author of an article we missed, please let us know)

• Faster Key Recovery Attack on Round-Reduced PRINCE (available at eprint 2016/828)
  S. Rasoolzadeh, H. Raddum
• Cryptanalysis of 6-round PRINCE using 2 Known Plaintexts (available at eprint 2016/132)
  S. Rasoolzadeh, H. Raddum
• Cryptanalysis of PRINCE with Minimal Data (available at eprint 2016/080)
  S. Rasoolzadeh, H. Raddum
• Integral cryptanalysis of round-reduced PRINCE cipher (Proc. Rom. Acad. Ser. A Math. Phys. Tech. Sci. Inf. Sci. 16 (2015), Special issue, 265–269, available in MathSciNet)
  R. Posteuca, G. Negara
• New approaches for round-reduced PRINCE cipher cryptanalysis (Proc. Rom. Acad. Ser. A Math. Phys. Tech. Sci. Inf. Sci. 16 (2015), Special issue, 253–264, available in MathSciNet)
  R. Posteuca, C. Duta, G. Negara
• Meet-in-the-Middle Attacks and Structural Analysis of Round-Reduced PRINCE (FSE 2015, available at eprint 2015/239)
  P. Derbez, L. Perrin
• Practical Attacks on the Round-reduced PRINCE (available at eprint 2015/245)
  P. Morawiecki
• Truncated differential cryptanalysis of PRINCE (Security and Communication Networks, 2015)
  G. Zhao, B. Sun, C. Li, J. Su
• Multiple Differential Cryptanalysis of Round-Reduced PRINCE (FSE 2014, available at eprint 2014/089)
  Anne Canteaut and Thomas Fuhr and Henri Gilbert and Maria Naya-Plasencia and Jean-René Reinhard
• Multi-user collisions: Applications to Discrete Logs, Even-Mansour and Prince (available at eprint 2013/761)
  Pierre-Alain Fouque and Antoine Joux and Chrysanthi Mavromati
• Improved Meet-in-the-Middle Attacks on AES-192 and PRINCE (available at eprint 2013/573)
  Leibo Li and Keting Jia and Xiaoyun Wang
• Differential Fault Attack on the PRINCE Block Cipher (available at eprint 2013/043)
  Ling Song and Lei Hu
• Reflection Cryptanalysis of PRINCE-Like Ciphers (FSE 2013, and Journal of Cryptology 2013, available here)
  Hadi Soleimany, Céline Blondeau, Xiaoli Yu, Wenling Wu, Kaisa Nyberg, Huiling Zhang, Lei Zhang, Yanfeng Wang
• Security analysis of PRINCE (available here)
  Jérémy Jean, Ivica Nikolic, Thomas Peyrin, Lei Wang and Shuang Wu
• Sieve-in-the-Middle: Improved MITM Attacks (Advances in Cryptology–CRYPTO 2013, 222-240)
  A. Canteaut, M. Naya-Plasencia, B. Vayssière
• On the Security of the Core of PRINCE Against Biclique and Differential Cryptanalysis (available at eprint 2012/712)
  Farzaneh Abed and Eik List and Stefan Lucks