[SC] 7. Block Ciphers: PRESENT

Introduction

PRESENT cipher was developed together by the Orange Labs in France, The Ruhr University Bochum in Germany and the Technical University of Denmark; and was first published on August 23 of 2007.

PRESENT cipher is one of the most compact encryption methods ever designed and is 2.5 times smaller than AES (Advanced Encryption Standard).

http://en.wikipedia.org/wiki/PRESENT_(cipher)

The specifications of PRESENT cipher was written in the paper "PRESENT: An Ultra-Lightweight Block Cipher", published in 2007 in the event CHES 2007 (Cryptographic Hardware and Embedded Systems Workshop) in Vienna, Austria , the authors are:

• A. Bogdanov, G. Leander and C. Paar from Horst-Görtz-Institute for IT-Security at Ruhr-University Bochum in Germany
• A. Poschmann, L.R. Knudsen and C. Vikkelsoe from Technical University Denmark at Lyngby, Denmark
• M.J.B. Robshaw and Y. Seurin from France Telecom R&D at Issy les Moulineaux, France

Background

Actually the computation paradigm are shifting to Pervasive Computing, so, there are a lot of devices with a limited amount of CPU, memory, power, and energy consumption. The problem is that all known ciphers are designed for high performance devices.

The goals of the PRESENT cipher are:

• The cipher is to be implemented directly in the hardware, efficiently
• Applications with moderate security levels (80 bit)
• Small amounts of encrypted data
• Often no rekeying possible (Encryption only core)
• Metrics:
• Security
• Power consumption
• Time

That means that in very small devices such as RFID cards or microcontrollers is possible to implement a cipher for simple security tasks, that with other ciphers was not possible due to the system requirements.

Some concepts

• GE (Gate Equivalent): http://en.wikipedia.org/wiki/Gate_equivalent. Refers to a physical area, one GE is equivalent to the area which is required by the two-input NAND gate with the lowest driving strength of the corresponding technology. The area in GE is derived by dividing the area in µm² by the area of a two-input NAND gate.
• SP (Substitution-Permutation): http://en.wikipedia.org/wiki/Substitution-permutation_network
• S-Box (Substitution Box): http://en.wikipedia.org/wiki/S-box
• P-Layer or P-Box (Permutation Layer/Box): http://en.wikipedia.org/wiki/Permutation_box

Specification

The PRESENT cipher is a simple SP-network with 64-bits block size and 80 or 128 bits of key lenght (PRESENT128 for the 128 bit version). A key lenght of 80-bits provides a good security level for many RFID or other small applications.

PRESENT uses a round-based algorithm, 32 rounds in total, where 31 rounds are regular rounds that consists in a key mixing step, a substitution layer and a permutation layer; the final round consists only in the key mixing step.

The recommended functions are:

• addRoundKey: Given round key K_i = [K₆₃, K₆₂, ..., K₁, K₀], and a current state b_i = [b₆₃, b₆₂, ..., b₁, b₀]; the key mixing step addRoundKey consists in a XOR operation:

b_j = b_j ⊕ K_j; for j ≤ 0 ≤ 63

• sBoxLayer: The S-box used in PRESENT is a 4-bit to 4-bit S-box, the 64-bit block is divided in chunks of 4-bits, each 4-bit chunk is the input to a S-box. The S-Box Layer consist in 16 parallel S-boxs. The substitutions, written in hexadecimal (1111 = F) are given by the following table:

PRESENT cipher S-box, from http://www.lightweightcrypto.org/present/present_cardis2008.pdf

• pLayer: Performs a bit permutation, where the bit i of the block is moved to bit position P(i).  The permutation used in PRESENT is given by the following table.

PRESENT cipher P-box, from http://www.lightweightcrypto.org/present/present_cardis2008.pdf

• keyRegisterUpdate: The key register stores a 80-bit key, where, only the 64 leftmost bits are used in the key mixing step. After that, the key register is updated, the key register is rotated 61-bits to the left, the left-most four bits are passed through the present S-box, finally the round counter is XOR-ed with the bits 15-19 of the key register. 

The whole SP-Network of PRESENT cipher is represented as follows:

PRESENT cipher SP-Network, from http://www.lightweightcrypto.org/present/present_cardis2008.pdf

Finally, the pseudocode algorithm and flow diagram are represented as follows:

PRESENT cipher pseudocode, from http://www.lightweightcrypto.org/present/present_cardis2008.pdf

Example (v0.1)

For this report I was trying to write my own implementation of PRESENT in python, but, something went wrong, as you can see in the following picture.



Basically, I have 2 errors:

• The implementation only accept numeric strings.
• The implementation only decode the last 2 characters of the string

I think there are some errors in my conversion logic because I need to convert the strings from bin to hex to ascii and viceversa, so, maybe the encrypt-decrypt engine is half ok.

I will update this entry when the code is ready, sorry for my failure.

In the references (bottom) are some implementations of PRESENT in C and Python.

Vulnerability

An example of vulnerability in PRESENT cipher is the Statistical Saturation Attack. The attack is based on a weakness in the permutation layer of PRESENT. 

This weakness can be found making a closer look to the permutation layer, in this example, the S-boxes 5,6,9 and 10 (counting from S-box 0 at the right), only 8 out of 16 input bits are directed to other S-boxes, and the other 8 input bits are fixed in all rounds!.

Permutation Layer Poor Diffusion example 1, from "A Statistical Saturation Attack against the Block Cipher PRESENT"

There are many other examples of poor diffusion in the permutation. So, if the 16 bits at the input of the S-boxes 5-6-9-10 are fixed, then 8 bits will be known at the very same input for the next round. We can iteratively repeat this process round by round and observe a non-uniform behavior at the output of the S-boxes 5-6-9-10.

The attack 

from: "A Statistical Saturation Attack against the Block Cipher PRESENT"

"In order to exploit this weakness, we first evaluate theoretically the distribution of the 8 bits in the bold trail of the above picture at the output of the S-box layer, for a fixed value of the same 8 bits of plaintext. This requires to guess the 8 subkey bits involved in the trail. One also needs to assume that the bits not situated in the trail are uniformly distributed. This is a reasonable assumption as soon as the 56 remaining bits of plaintext (excluding the 8 bits in the trail) are randomly generated. Then, given the distribution of the 8-bit trail at the input of a round, it is possible to compute the 8-bit distribution at the output of the round. Iteratively, we can compute the distribution for an arbitrary number of rounds.

For each key guess, the work needed to compute the theoretical distribution of the target trail after r rounds is equivalent to r · 216 partial encryptions.

Once we have computed the theoretical distributions of the trail for each possible key guess, we can attack the cipher by simply comparing them with a practical distribution obtained by encrypting a large number of plaintexts with a secret key. The key guess minimizing the distance between theoretical and practical distributions is chosen as the correct key. We can construct a list of key candidates sorted according to the distance between theory and practice. The better the position of the right key in the list, the better the attack."

Permutation Layer Poor Diffusion example 2, from "A Statistical Saturation Attack against the Block Cipher PRESENT"

Referencias

http://www.lightweightcrypto.org/present/present_cardis2008.pdf
http://www.lightweightcrypto.org/present/present_ches2007.pdf
http://www.emsec.rub.de/media/crypto/veroeffentlichungen/2011/01/29/present_ches2007_slides.pdf
http://homes.esat.kuleuven.be/~abogdano/talks/present_rfidsec07.pdf
http://math.fau.edu/~eisenbarth/pdf/SLEsolvers.pdf

http://www.lightweightcrypto.org/implementations.php