The PRINCE Challenge

The Background

The idea behind this competition is that industry certainly cares about cryptanalysis. However, compared to academia, the focus is much more to practical attacks. Now, defining what practical means is not always easy and thus often not very concrete.

We will make it more concrete

The task of this competition is to find practical attacks on round-reduced version of the block cipher PRINCE. Here practical means that the data complexity is limited and that we actually want to see the secret key as a result of the attack - thus running time and memory must also be in practical ranges.

The Algorithm

The block cipher PRINCE is the result of a cooperation between the Technical University Denmark (DTU), NXP Semiconductors and the Ruhr University Bochum. It is a block cipher with 64-bit block size and 128-bit key and 12 layers of S-boxes. The rounds are symmetrically arranged around a linear layer in the middle.

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 220 chosen plaintexts/cipher texts

  • How fast can you break 4 rounds?
    - Round-1 winner: Paweł, 27 CP, time 211
    - Final-Round winner:
    • Integral attack Håvard Raddum and Shahram Rasoolzadeh, 26 texts, time: 9
    • Subspace trail attack by Lorenzo Grassi and Christian Rechberger: 17 texts, time: 219
  • How fast can you break 6 rounds?
    - Round-2 winner: Raluca and Gabriel, 214.6 CP, time 237
    - Final-Round winner:
    • Integral attack Håvard Raddum and Shahram Rasoolzadeh, 213 texts, time: 224.5
  • How fast can you break 8 rounds?
    - Winner: Patrick: 216 CP, time 266.4
  • How fast can you break 10 rounds?
  • How fast can you break 12 rounds?

Setting 2: Given 230 known plaintexts

  • How fast can you break 4 rounds?
    - Round-1 winner: Patrick: 25 KP, time 243
  • How fast can you break 6 rounds?
    - Round-1 winner: Patrick: 26 KP, time 2101
    - Final-Round winner:
    • MITM attack by Håvard Raddum and Shahram Rasoolzadeh, 2 texts, time: 297
  • How fast can you break 8 rounds?
    - Final-Round winner:
    • MITM attack by Håvard Raddum and Shahram Rasoolzadeh, 2 texts, time: 2124
  • How fast can you break 10 rounds?
  • How fast can you break 12 rounds?

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

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 264 encryptions of the corresponding round reduced variant
  • Memory complexity below 245 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)

  • 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