De Cifris Trends
in
Modern Cryptography:
the French Magisterium

<figure><img src="image_1.png" /></figure>

<figure><img src="image_2.png" /></figure>

Lecture 3

<figure><img src="image_3.png" /></figure>

<figure><img src="image_4.png" /></figure>
# Lightweight Symmetric Primitives

Anne Canteaut

Inria Paris, France

<figure><img src="image_5.png" /></figure>

<figure><img src="image_6.png" /></figure>
<figure><img src="image_7.png" /></figure>

<figure><img src="image_8.png" /></figure>

# INTRODUCTION

<figure><img src="image_9.png" /></figure>

<figure><img src="image_10.png" /></figure>

<figure><img src="image_11.png" /></figure>

<figure><img src="image_12.png" /></figure>

<figure><img src="image_13.png" /></figure>

<figure><img src="image_14.png" /></figure>

<figure><img src="image_15.png" /></figure>

<figure><img src="image_16.png" /></figure>

<figure><img src="image_17.png" /></figure>

<figure><img src="image_18.png" /></figure>

<figure><img src="image_19.png" /></figure>

<figure><img src="image_20.png" /></figure>

<figure><img src="image_21.png" /></figure>

<figure><img src="image_22.png" /></figure>
COMPUTERWORLDUK

THE VOICE OF IT MANAGEMENT

NEWS

IN-DEPTH

IT Topics

News

In Depth

IT Management

Profe

Home > Mobile & Wireless > News

<figure><img src="image_23.png" /></figure>

Mobile & Wireles

<figure><img src="image_24.png" /></figure>

Questions raised
about Oyster card
security

Its RFID chip is cracked by researchers

By Network World and Computerworld UK staff | Published 12:20, 07 March 08

<figure><img src="image_25.png" /></figure>

Smartcards with encrypted RFID chips, including London's
Oyster fare card, might not be as secure as previously thought.

New research at the University of Virginia is causing a major stir in Boston, because it raises question over the smart "CharlieCards" used by commuters on the city's "T" metro system.

However, London's Oyster card uses similar RFID technology –
the Mifare Classic made by Philips spinoff NXP Semiconductors.

Also in this channel

News

In Depth

How-Tos

Blogs

Slideshows

<figure><img src="image_26.png" /></figure>

<figure><img src="image_27.png" /></figure>
New implementation constraints

<figure><img src="image_28.png" /></figure>

HOME

<figure><img src="image_29.png" /></figure>

SECTIONS

<figure><img src="image_30.png" /></figure>

SEARCH

NEW YORK POST

NEWS

Cheney feared terrorists would
'hack' pacemaker

By Bob Fredericks

October 19, 2013 | 4:11am

<figure><img src="image_31.png" /></figure>

PLAY CBS NEWS VIDEO

<figure><img src="image_32.png" /></figure>

<figure><img src="image_33.png" /></figure>
Lightweight Competitions

CAESAR for authenticated encryption (2014-2019):

https://competitions.cr.yp.to/caesar.html

Use case 1: Lightweight (resource-constrained) applications

① Ascon [Dobraunig, Eichlseder, Mendel, Schläffer 16]

② Acorn [Wu 14]

NIST Lightweight Cryptography standardization (2015-23):

Ascon family (announced in Feb. 2023)

<figure><img src="image_34.png" /></figure>
# Why is minimalism interesting?

<figure><img src="image_35.png" /><figcaption>Tretyakov Gallery</figcaption></figure>

Besides (niche) application needs, it helps us **understand** where security comes from.

<figure><img src="image_36.png" /></figure>
① Symmetric encryption

② How to make it lightweight?

③ Ascon

④ Possible weaknesses coming from “minimal” building-blocks:

* Simple key-schedule

* ...

<figure><img src="image_37.png" /></figure>
<figure><img src="image_38.png" /></figure>

<figure><img src="image_39.png" /></figure>

Symmetric encryption

<figure><img src="image_40.png" /></figure>

<figure><img src="image_41.png" /></figure>

<figure><img src="image_42.png" /></figure>

<figure><img src="image_43.png" /></figure>

<figure><img src="image_44.png" /></figure>

<figure><img src="image_45.png" /></figure>
# Encryption scheme

## Two steps for encrypting plaintexts of an arbitrary length:

1. design a **permutation**, or a family of permutations, **operating on {0, 1}ⁿ**.

2. design a **mode of operation** describing how this primitive can be used for encrypting messages of any length (e.g. CTR, CBC).

<figure><img src="image_46.png" /></figure>

<figure><img src="image_47.png" /></figure>
CTR mode for encryption

<figure><img src="image_48.png" /></figure>

where $E_K = \text{family of permutations of } \{0,1\}^n \text{ indexed by the key.}$

<figure><img src="image_49.png" /></figure>
$$
E_K : \{0,1\}^n \to \{0,1\}^n
$$

* indistinguishable from randomly chosen bijections of {0, 1}^n with n ∈ {64, 128}

• implementable

-> Contradiction!

<figure><img src="image_50.png" /></figure>

<figure><img src="image_51.png" /></figure>
Iterated construction

<figure><img src="image_52.png" /></figure>

<figure><img src="image_53.png" /></figure>

<figure><img src="image_54.png" /></figure>
Iterated construction

<figure><img src="image_55.png" /></figure>

<figure><img src="image_56.png" /></figure>
Iterated construction

<figure><img src="image_57.png" /></figure>

<figure><img src="image_58.png" /></figure>
* blocksize: 128 bits

* 10 rounds for the 128-bit key version

* Sbox operates on 8 bits

* diffusion layer is linear over $F_{28}$

* nonlinear key schedule

<figure><img src="image_59.png" /></figure>

<figure><img src="image_60.png" /></figure>
<figure><img src="image_61.png" /></figure>

<figure><img src="image_62.png" /></figure>

# How to make it lightweight?

<figure><img src="image_63.png" /></figure>

<figure><img src="image_64.png" /></figure>

<figure><img src="image_65.png" /></figure>

<figure><img src="image_66.png" /></figure>

<figure><img src="image_67.png" /></figure>

<figure><img src="image_68.png" /></figure>
Lightweight block ciphers

AES [Daemen-Rijmen 98][FIPS PUB 197]

* blocksize: 128 bits

* Sbox operates on 8 bits

* diffusion layer is linear over $F_{28}$

To make it smaller in hardware:

* blocksize: 64 bits

* smaller Sbox, on 3 or 4 bits

* linear diffusion layer over a smaller alphabet

* simplified key-schedule

<figure><img src="image_69.png" /></figure>

<figure><img src="image_70.png" /></figure>
<figure><img src="image_71.png" /></figure>

<figure><img src="image_72.png" /></figure>

Lightweight but secure...

Increase the number of rounds!

* PRESENT [Bogdanov et al. 07]: 31 rounds

* LED [Guo et al. 11]:
  LED-64: 32 rounds, LED-128: 48 rounds

* SPECK [Beaulieu et al. 13]:
  SPECK64/128: 27 rounds, SPECK128/256: 34 rounds

* SIMON [Beaulieu et al. 13]:
  SIMON64/128: 44 rounds, SIMON128/256: 72 rounds

<figure><img src="image_73.png" /></figure>

<figure><img src="image_74.png" /></figure>
Does lightweight mean “light + wait”?

[Knežević et al. 12]

<figure><img src="image_75.png" /></figure>
# Duplex-Sponge mode for AEAD encryption

[Bertoni et al. 12]

<figure><img src="image_76.png" /></figure>

where $\mathcal{P}$ is a permutation of $\{0,1\}^n$.

<figure><img src="image_77.png" /></figure>
<figure><img src="image_78.png" /></figure>

<figure><img src="image_79.png" /></figure>

<figure><img src="image_80.png" /></figure>

<figure><img src="image_81.png" /></figure>

<figure><img src="image_82.png" /></figure>

<figure><img src="image_83.png" /></figure>

<figure><img src="image_84.png" /></figure>

<figure><img src="image_85.png" /></figure>

<figure><img src="image_86.png" /></figure>

<figure><img src="image_87.png" /></figure>

<figure><img src="image_88.png" /></figure>
<figure><img src="image_89.png" /></figure>

where $\mathcal{P}$ is a permutation on 320 bits
of which 64 are known/controlled.

<figure><img src="image_90.png" /></figure>
<figure><img src="image_91.png" /></figure>

Permutation operating on a 320-bit state:

* 8-bit constant addition;

* Nonlinear Sbox on 5 bits of degree 2 (on the 64 columns);

* 5 simple linear transformations on 64 bits

$$ \Sigma_i(X_i) = X_i \oplus (X_i \ggg a_i) \oplus (X_i \gg b_i) $$

→ 6 rounds

<figure><img src="image_92.png" /></figure>
# Possible weaknesses coming from minimal building-blocks

<figure><img src="image_93.png" /></figure>

<figure><img src="image_94.png" /></figure>

<figure><img src="image_95.png" /></figure>

<figure><img src="image_96.png" /></figure>

<figure><img src="image_97.png" /></figure>

<figure><img src="image_98.png" /></figure>

<figure><img src="image_99.png" /></figure>

<figure><img src="image_100.png" /></figure>

<figure><img src="image_101.png" /></figure>

<figure><img src="image_102.png" /></figure>
Lightweight key schedules

<figure><img src="image_103.png" /></figure>

where $RC_0, RC_1, \dots, RC_r$ are fixed round-constants.

<figure><img src="image_104.png" /></figure>
**Midori-64** [Banik et al. 15]:

$$E_K : (\{0, 1\}^4)^{16} \to (\{0, 1\}^4)^{16}$$

$$\text{with } K = (k_0, k_1, k_0 \oplus RC_2, k_1 \oplus RC_3, k_0 \oplus RC_4, \dots)$$

**Invariant set for Midori-64:**

If $k_0, k_1 \in \{0x0, 0x1\}^{16}$, then $\{0x8, 0x9\}^{16}$ is invariant under $E_K$.

**Example :**

$$\text{For } (k_0, k_1) = (0x1100110011001100, 0x0011001100110011),$$

$$m = 0x999999999999999 \mapsto c = 0x89999998898898$$

<figure><img src="image_105.png" /></figure>
<figure><img src="image_106.png" /></figure>

<figure><img src="image_107.png" /></figure>

<figure><img src="image_108.png" /></figure>
Fixed-key differential paths
for r iterations of Midori-64

Differential path ($\delta, \delta, \dots, \delta$) with $\delta = (0 \times 1)^{16}$

* On average over all key sequences

$$EDP(\delta, \dots, \delta) = 2^{-48r}$$

* For a fixed key

$$DP(\delta, \dots, \delta) = \begin{cases} 2^{-48} & \text{if } \forall i, k_i \in \{0 \times 0, 0 \times 1\}^{16} \\ 0 & \text{otherwise.} \end{cases}$$

<figure><img src="image_109.png" /></figure>

<figure><img src="image_110.png" /></figure>
Where does this come from?

* The key schedule is **compatible** with the fact that each $k_i$ lies in a (affine) subspace.

* The linear diffusion function is defined by an **orthogonal matrix**.

<figure><img src="image_111.png" /></figure>
<figure><img src="image_112.png" /></figure>

# De Componendis Cifris

https://www.decifris.it

<figure><img src="image_113.png" /></figure>