# How can we ensure that (symmetric) cryptographic primitives are trustworthy?

Léo Perrin

► To cite this version:

Léo Perrin. How can we ensure that (symmetric) cryptographic primitives are trustworthy?. Rostock University Seminar, Jun 2023, Rostock, Germany. 2023. [hal-04327478](https://hal HAL Id: hal-04327478)

Submitted on 6 Dec 2023

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

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

Distributed under a Creative Commons Attribution 4.0 International License
How can we ensure that (symmetric) cryptographic
primitives are trustworthy?

Léo Perrin

Based on joint works with Biryukov, Bonnetain, Canteaut,

Duval, Tian and Udovenko

June, 2023

University of Rostock

informatics mathematics
Inria
$\pi' = (252, 238, 221, 17, 207, 110, 49, 22, 251, 196, 250, 218, 35, 197, 4, 77, 233, 119, 240, 219, 147, 46, 153, 186, 23, 54, 241, 187, 20, 205, 95, 193, 249, 24, 101, 90, 226, 92, 239, 33, 129, 28, 60, 66, 139, 1, 142, 79, 5, 132, 2, 174, 227, 106, 143, 160, 6, 11, 237, 152, 127, 212, 211, 31, 235, 52, 44, 81, 234, 200, 72, 171, 242, 42, 104, 162, 253, 58, 206, 204, 181, 112, 14, 86, 8, 12, 118, 18, 191, 114, 19, 71, 156, 183, 93, 135, 21, 161, 150, 41, 16, 123, 154, 199, 243, 145, 120, 111, 157, 158, 178, 177, 50, 117, 25, 61, 255, 53, 138, 126, 109, 84, 198, 128, 195, 189, 13, 87, 223, 245, 36, 169, 62, 168, 67, 201, 215, 121, 214, 246, 124, 34, 185, 3, 224, 15, 236, 222, 122, 148, 176, 188, 220, 232, 40, 80, 78, 51, 10, 74, 167, 151, 96, 115, 30, 0, 98, 68, 26, 184, 56, 130, 100, 159, 38, 65, 173, 69, 70, 146, 39, 94, 85, 47, 140, 163, 165, 125, 105, 213, 149, 59, 7, 88, 179, 64, 134, 172, 29, 247, 48, 55, 107, 228, 136, 217, 231, 137, 225, 27, 131, 73, 76, 63, 248, 254, 141, 83, 170, 144, 202, 216, 133, 97, 32, 113, 103, 164, 45, 43, 9, 91, 203, 155, 37, 208, 190, 229, 108, 82, 89, 166, 116, 210, 230, 244, 180, 192, 209, 102, 175, 194, 57, 75, 99, 182).

How can we go from $\uparrow$ to $\downarrow$ ?

$$ \pi: \left\{ \begin{array}{lcl} \mathbb{F}_{2^8} & \to & \mathbb{F}_{2^8} \\ 0 & \mapsto & \kappa(0), \\ (\alpha^{2^m+1}) & \mapsto & \kappa(2^m - j), \text{ for } 1 \le j \le 2^m - 1, \\ \alpha^{j+(2^m+1)} & \mapsto & \kappa(2^m - i) \oplus (\alpha^{2^m+1})^{s(j)}, \text{ for } 0 < i, 0 \le j < 2^m - 1. \end{array} \right. $$
$\pi' = (252, 238, 221, 17, 207, 110, 49, 22, 251, 196, 250, 218, 35, 197, 4, 77, 233, 119, 240, 219, 147, 46, 153, 186, 23, 54, 241, 187, 20, 205, 95, 193, 249, 24, 101, 90, 226, 92, 239, 33, 129, 28, 60, 66, 139, 1, 142, 79, 5, 132, 2, 174, 227, 106, 143, 160, 6, 11, 237, 152, 127, 212, 211, 31, 235, 52, 44, 81, 234, 200, 72, 171, 242, 42, 104, 162, 253, 58, 206, 204, 181, 112, 14, 86, 8, 12, 118, 18, 191, 114, 19, 71, 156, 183, 93, 135, 21, 161, 150, 41, 16, 123, 154, 199, 243, 145, 120, 111, 157, 158, 178, 177, 50, 117, 25, 61, 255, 53, 138, 126, 109, 84, 198, 128, 195, 189, 13, 87, 223, 245, 36, 169, 62, 168, 67, 201, 215, 121, 214, 246, 124, 34, 185, 3, 224, 15, 236, 222, 122, 148, 176, 188, 220, 232, 40, 80, 78, 51, 10, 74, 167, 151, 96, 115, 30, 0, 98, 68, 26, 184, 56, 130, 100, 159, 38, 65, 173, 69, 70, 146, 39, 94, 85, 47, 140, 163, 165, 125, 105, 213, 149, 59, 7, 88, 179, 64, 134, 172, 29, 247, 48, 55, 107, 228, 136, 217, 231, 137, 225, 27, 131, 73, 76, 63, 248, 254, 141, 83, 170, 144, 202, 216, 133, 97, 32, 113, 103, 164, 45, 43, 9, 91, 203, 155, 37, 208, 190, 229, 108, 82, 89, 166, 116, 210, 230, 244, 180, 192, 209, 102, 175, 194, 57, 75, 99, 182).

How can we go from $\uparrow$ to $\downarrow$ ?

$$ \pi: \left\{ \begin{array}{lcl} \mathbb{F}_{2^8} & \to & \mathbb{F}_{2^8} \\ 0 & \mapsto & \kappa(0), \\ (\alpha^{2^m+1}) & \mapsto & \kappa(2^m - j), \text{ for } 1 \le j \le 2^m - 1, \\ \alpha^{j+(2^m+1)} & \mapsto & \kappa(2^m - i) \oplus (\alpha^{2^m+1})^{s(j)}, \text{ for } 0 < i, 0 \le j < 2^m - 1. \end{array} \right. $$

Why do we care?
## Outline

1 What are S-Boxes?

2 On Standardization and Trust

3 Don't Trust, Verify (and How to do it)

4 Conclusion
# Outline

1 What are S-Boxes?

2 On Standardization and Trust

3 Don't Trust, Verify (and How to do it)

4 Conclusion
# Plan of this Section

1 What are S-Boxes?

■ Basics of Symmetric Cryptography

■ Block Cipher Design

2 On Standardization and Trust

3 Don't Trust, Verify (and How to do it)

4 Conclusion
# Symmetric Cryptography

There are many **symmetric algorithms**! Hash functions, MACs...
# Symmetric Cryptography

There are many **symmetric** algorithms! Hash functions, MACs...

## Definition (Block Cipher)

* Input: $n$-bit block $x$

* Parameter: $k$-bit key $\kappa$

* Output: $n$-bit block $E_{\kappa}(x)$

* Symmetry: $E$ and $E^{-1}$ use the same $\kappa$

<figure><img src="image_2.png" /></figure>
# Symmetric Cryptography

There are many **symmetric** algorithms! Hash functions, MACs...

## Definition (Block Cipher)

* Input: $n$-bit block $x$

* Parameter: $k$-bit key $\kappa$

* Output: $n$-bit block $E_{\kappa}(x)$

* Symmetry: $E$ and $E^{-1}$ use the same $\kappa$

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

**Properties needed:**

Diffusion

Confusion

No cryptanalysis!
# No Cryptanalysis?

Let us look at a typical cryptanalysis technique: the **differential attack**.
Differential Attacks

<figure><img src="image_4.png" /></figure>
Differential Attacks

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

<figure><img src="image_6.png" /></figure>
Differential Attacks

<figure><img src="image_7.png" /></figure>
Differential Attacks

<figure><img src="image_8.png" /></figure>
# Differential Attacks

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

## Differential Attack

If there are many x such that $E_{f_c}(x) \oplus E_{f_c}(x \oplus a) = b$, then the cipher is not secure.
# Basic Block Cipher Structure

How do we build block ciphers that prevent such attacks (as well as others)?
# Basic Block Cipher Structure

How do we build block ciphers that prevent such attacks (as well as others)?

<figure><img src="image_10.png" /></figure>
# Basic Block Cipher Structure

How do we build block ciphers that prevent such attacks (as well as others)?

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

## Substitution-Permutation Network

Such a block cipher iterates the round function above several times. S is the **Substitution Box (S-Box)**.
The S-Box (1/2)

π' = (252, 238, 221, 17, 207, 110, 49, 22, 251, 196, 250, 218, 35, 197, 4, 77, 233, 119, 240, 219, 147, 46, 153, 186, 23, 54, 241, 187, 20, 205, 95, 193, 249, 24, 101, 90, 226, 92, 239, 33, 129, 28, 60, 66, 139, 1, 142, 79, 5, 132, 2, 174, 227, 106, 143, 160, 6, 11, 237, 152, 127, 212, 211, 31, 235, 52, 44, 81, 234, 200, 72, 171, 242, 42, 104, 162, 253, 58, 206, 204, 181, 112, 14, 86, 8, 12, 118, 18, 191, 114, 19, 71, 156, 183, 93, 135, 21, 161, 150, 41, 16, 123, 154, 199, 243, 145, 120, 111, 157, 158, 178, 177, 50, 117, 25, 61, 255, 53, 138, 126, 109, 84, 198, 128, 195, 189, 13, 87, 223, 245, 36, 169, 62, 168, 67, 201, 215, 121, 214, 246, 124, 34, 185, 3, 224, 15, 236, 222, 122, 148, 176, 188, 220, 232, 40, 80, 78, 51, 10, 74, 167, 151, 96, 115, 30, 0, 98, 68, 26, 184, 56, 130, 100, 159, 38, 65, 173, 69, 70, 146, 39, 94, 85, 47, 140, 163, 165, 125, 105, 213, 149, 59, 7, 88, 179, 64, 134, 172, 29, 247, 48, 55, 107, 228, 136, 217, 231, 137, 225, 27, 131, 73, 76, 63, 248, 254, 141, 83, 170, 144, 202, 216, 133, 97, 32, 113, 103, 164, 45, 43, 9, 91, 203, 155, 37, 208, 190, 229, 108, 82, 89, 166, 116, 210, 230, 244, 180, 192, 209, 102, 175, 194, 57, 75, 99, 182).

The S-Box $\pi$ of the latest Russian standards, Kuznyechik (BC) and Streebog (HF).
# The S-Box (2/2)

## Importance of the S-Box

If S is such that

$$S(x) \oplus S(x \oplus a) = b$$

does not have many solutions x for all (a, b) then the cipher may be proved secure against differential attacks.
# The S-Box (2/2)

## Importance of the S-Box

If S is such that

$$S(x) \oplus S(x \oplus a) = b$$

does not have many solutions x for all (a, b) then the cipher may be proved secure against differential attacks.

In academic papers presenting new block ciphers, the choice of S is carefully explained.
# S-Box Design

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

AES S-Box

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

Inverse (other)

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

Exponential

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

Math (other)

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

SPN

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

Misty

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

Feistel

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

Lai-Massey

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

Pseudo-random

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

Hill climbing

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

Unknown
S-Box Design

<figure><img src="image_23.png" /></figure>
S-Box Design

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

1. What are S-Boxes?

2. On Standardization and Trust

3. Don't Trust, Verify (and How to do it)

4. Conclusion
# Plan of this Section

1. What are S-Boxes?

2. On Standardization and Trust
   - How Standardization Works
   - How Standardization Fails

3. Don't Trust, Verify (and How to do it)

4. Conclusion
# Life Cycle of a Cryptographic Primitive

## Fundamental Research
# Life Cycle of a Cryptographic Primitive

<figure><img src="image_25.png" /></figure>
# Life Cycle of a Cryptographic Primitive

<figure><img src="image_26.png" /></figure>
# Life Cycle of a Cryptographic Primitive

<table><thead><tr><th colspan="3">Fundamental Research</th></tr><tr><th>Design</th><th>Public Analysis</th><th>Deployment</th></tr></thead><tbody><tr><td>Small teams<br><ul><li>Scope statement</li><li>Algorithm specification</li><li>Design choices justifications</li><li>Security analysis</li></ul></td><td>Academic community</td><td>Industry</td></tr><tr><td colspan="3">→ time</td></tr><tr><td>Publication<br>Conf, competition</td><td>Standardization<br>NIST, ISO, IETF...</td><td></td></tr></tbody></table>
# Life Cycle of a Cryptographic Primitive

<figure><img src="image_27.png" /></figure>
# Life Cycle of a Cryptographic Primitive

<table><thead><tr><th colspan="4">Fundamental Research</th></tr><tr><th>Design</th><th>Public Analysis</th><th>Deployment</th></tr></thead><tbody><tr><td>Small teams<br><ul><li>Scope statement</li><li>Algorithm specification</li><li>Design choices justifications</li><li>Security analysis</li></ul></td><td>Academic community<br><br>Try and break published algorithms</td><td>Industry</td></tr><tr><td colspan="3">→<br>time</td></tr><tr><td>Publication<br>Conf, competition</td><td>Standardization<br>NIST, ISO, IETF...</td><td></td></tr></tbody></table>
# Life Cycle of a Cryptographic Primitive

<figure><img src="image_28.png" /></figure>
# Life Cycle of a Cryptographic Primitive

<table><thead><tr><th colspan="4">Fundamental Research</th></tr><tr><th>Design</th><th>Public Analysis</th><th>Deployment</th></tr></thead><tbody><tr><td>Small teams<br>■ Scope statement<br>■ Algorithm specification<br>■ Design choices justifications<br>■ Security analysis</td><td>Academic community<br>Try and break published algorithms<br>Unbroken algorithms are eventually trusted</td><td>Industry<br>Implements algorithms in actual products...<br>...unless a new attack is found</td></tr><tr><td>Publication<br>Conf, competition</td><td>Standardization<br>NIST, ISO, IETF...</td><td>time</td></tr></tbody></table>
# Some Examples

* Advanced Encryption Standard competition → AES block cipher

* Secure Hashing Algorithm-3 competition → SHA-3 hash function
# Some Examples

* Advanced Encryption Standard competition → AES block cipher

* Secure Hashing Algorithm-3 competition → SHA-3 hash function

## Lightweight Cryptography (not) Competition
# Some Examples

* Advanced Encryption Standard competition → AES block cipher

* Secure Hashing Algorithm-3 competition → SHA-3 hash function

## Lightweight Cryptography (not) Competition

March 2014 First mentions of a LW standardization process
# Some Examples

* Advanced Encryption Standard competition → AES block cipher

* Secure Hashing Algorithm-3 competition → SHA-3 hash function

## Lightweight Cryptography (not) Competition

* March 2014 First mentions of a LW standardization process

* 2015-2018 Calls for comments (several iterations)
# Some Examples

* Advanced Encryption Standard competition → AES block cipher

* Secure Hashing Algorithm-3 competition → SHA-3 hash function

## Lightweight Cryptography (not) Competition

* March 2014 First mentions of a LW standardization process

* 2015-2018 Calls for comments (several iterations)

* August 2018 Call for submissions
# Some Examples

- Advanced Encryption Standard competition → AES block cipher

- Secure Hashing Algorithm-3 competition → SHA-3 hash function

## Lightweight Cryptography (not) Competition

- March 2014 First mentions of a LW standardization process

- 2015-2018 Calls for comments (several iterations)

- August 2018 Call for submissions

- March 2019 Submission deadline/start of first round (62 candidates)
# Some Examples

* Advanced Encryption Standard competition → AES block cipher

* Secure Hashing Algorithm-3 competition → SHA-3 hash function

## Lightweight Cryptography (not) Competition

* March 2014 First mentions of a LW standardization process

* 2015-2018 Calls for comments (several iterations)

* August 2018 Call for submissions

* March 2019 Submission deadline/start of first round (62 candidates)

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

CRYPTANALYSIS TIME
# Some Examples

- Advanced Encryption Standard competition → AES block cipher

- Secure Hashing Algorithm-3 competition → SHA-3 hash function

## Lightweight Cryptography (not) Competition

- March 2014 First mentions of a LW standardization process

- 2015-2018 Calls for comments (several iterations)

- August 2018 Call for submissions

- March 2019 Submission deadline/start of first round (62 candidates)

- August 2019 start of second round (32 candidates left)
# Some Examples

* Advanced Encryption Standard competition → AES block cipher

* Secure Hashing Algorithm-3 competition → SHA-3 hash function

## Lightweight Cryptography (not) Competition

* March 2014 First mentions of a LW standardization process

* 2015-2018 Calls for comments (several iterations)

* August 2018 Call for submissions

* March 2019 Submission deadline/start of first round (62 candidates)

* August 2019 start of second round (32 candidates left)

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

CRYPTANALYSIS TIME
# Some Examples

- Advanced Encryption Standard competition → AES block cipher

- Secure Hashing Algorithm-3 competition → SHA-3 hash function

## Lightweight Cryptography (not) Competition

- March 2014 First mentions of a LW standardization process

- 2015-2018 Calls for comments (several iterations)

- August 2018 Call for submissions

- March 2019 Submission deadline/start of first round (62 candidates)

- August 2019 start of second round (32 candidates left)

- March 2021 start of third (final) round (10 candidates left)
# Some Examples

* Advanced Encryption Standard competition → AES block cipher

* Secure Hashing Algorithm-3 competition → SHA-3 hash function

## Lightweight Cryptography (not) Competition

* March 2014 First mentions of a LW standardization process

* 2015-2018 Calls for comments (several iterations)

* August 2018 Call for submissions

* March 2019 Submission deadline/start of first round (62 candidates)

* August 2019 start of second round (32 candidates left)

* March 2021 start of third (final) round (10 candidates left)

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

not much cryptanalysis...
# Some Examples

* Advanced Encryption Standard competition → AES block cipher

* Secure Hashing Algorithm-3 competition → SHA-3 hash function

## Lightweight Cryptography (not) Competition

* March 2014 First mentions of a LW standardization process

* 2015-2018 Calls for comments (several iterations)

* August 2018 Call for submissions

* March 2019 Submission deadline/start of first round (62 candidates)

* August 2019 start of second round (32 candidates left)

* March 2021 start of third (final) round (10 candidates left)

* February 2023 NIST chose ASCON
The best approach is the one used in practice!
The best approach is the one used in practice!

All is well?
The best approach is the one used in practice!

All is well?

... no.
# Breaking the Pipeline

<figure><img src="image_32.png" /></figure>
# Breaking the Pipeline

<figure><img src="image_33.png" /></figure>
# Breaking the Pipeline

## Fundamental Research

Design

Public Analysis

Deployment

Small teams

Academic community

Industry

s in

Hidden defect?

Publication

Standardization

time
# Some (Counter-)Examples

https://eprint.iacr.org/<year>/<number>

## A5/2

- stream cipher

- 1980's

- used in 2G

- designer: ??

- wikipedia

## DUAL EC

- PRNG

- 2000's

- general standard

- designer: NSA

- 2015/767
  (2016/376)

## GEA-1

- 1990's

- stream cipher

- used in EDGE

- designer: ??

- 2021/819
# Outline

1 What are S-Boxes?

2 On Standardization and Trust

3 Don't Trust, Verify (and How to do it)

4 Conclusion
# Plan of this Section

1 What are S-Boxes?

2 On Standardization and Trust

3 Don't Trust, Verify (and How to do it)

■ Streebog and Kuznyechik

■ Decomposing the Mysterious S-Box

■ Generation Process

■ Cryptographic Properties

4 Conclusion
# Kuznyechik/Strebog

## Strebog

<table><tr><td>Type</td><td>Hash function</td></tr><tr><td>Publication</td><td>2012</td></tr></table>

## Kuznyechik

<table><tr><td>Type</td><td>Block cipher</td></tr><tr><td>Publication</td><td>2015</td></tr></table>

<figure><img src="image_34.png" /></figure>
# Kuznyechik/Strebog

## Strebog

<table><tr><td>Type</td><td>Hash function</td></tr><tr><td>Publication</td><td>2012</td></tr></table>

## Kuznyechik

<table><tr><td>Type</td><td>Block cipher</td></tr><tr><td>Publication</td><td>2015</td></tr></table>

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

## Common ground

- Both are standard symmetric primitives in Russia.

- Both were designed by the FSB (TC26).

- Both use the same $8 \times 8$ S-Box, $\pi$.
$\pi' = (252, 238, 221, 17, 207, 110, 49, 22, 251, 196, 250, 218, 35, 197, 4, 77, 233, 119, 240, 219, 147, 46, 153, 186, 23, 54, 241. 187, 20, 205, 95, 193, 249, 24, 101, 90, 226, 92, 239, 33, 129, 28, 60, 66, 139, 1, 142, 79, 5, 132, 2, 174, 227, 106, 143, 160, 6, 11, 237, 152, 127, 212, 211, 31, 235, 52, 44, 81, 234, 200, 72, 171, 242, 42, 104, 162, 253, 58, 206, 204, 181, 112, 14, 86, 8, 12, 118, 18, 191, 114, 19, 71, 156, 183, 93, 135, 21, 161, 150, 41, 16, 123, 154, 199, 243, 145, 120, 111, 157, 158, 178, 177, 50, 117, 25, 61, 255, 53, 138, 126, 109, 84, 198, 128, 195, 189, 13, 87, 223, 245, 36, 169, 62, 168, 67, 201, 215, 121, 214, 246, 124, 34, 185, 3, 224, 15, 236, 222, 122, 148, 176, 188, 220, 232, 40, 80, 78, 51, 10, 74, 167, 151, 96, 115, 30, 0, 98, 68, 26, 184, 56, 130, 100, 159, 38, 65, 173, 69, 70, 146, 39, 94, 85, 47, 140, 163, 165, 125, 105, 213, 149, 59, 7, 88, 179, 64, 134, 172, 29, 247, 48, 55, 107, 228, 136, 217, 231, 137, 225, 27, 131, 73, 76, 63, 248, 254, 141, 83, 170, 144, 202, 216, 133, 97, 32, 113, 103, 164, 45, 43, 9, 91, 203, 155, 37, 208, 190, 229, 108, 82, 89, 166, 116, 210, 230, 244, 180, 192, 209, 102, 175, 194, 57, 75, 99, 182).
S-Box Reverse-Engineering

<figure><img src="image_36.png" /></figure>
# S-Box Reverse-Engineering

<figure><img src="image_37.png" /></figure>
The Two Tables

Let $S : \mathbb{F}_2^n \to \mathbb{F}_2^n$ be an S-Box.
# The Two Tables

Let $S: \mathbb{F}_2^n \to \mathbb{F}_2^n$ be an S-Box.

## Definition (DDT)

The *Difference Distribution Table* of $S$ is a matrix of size $2^n \times 2^n$ such that

$$ \text{DDT}[a, b] = \#\{x \in \mathbb{F}_2^n \mid S(x \oplus a) \oplus S(x) = b\}. $$
# The Two Tables

Let $S: \mathbb{F}_2^n \to \mathbb{F}_2^n$ be an S-Box.

## Definition (DDT)

The *Difference Distribution Table* of $S$ is a matrix of size $2^n \times 2^n$ such that

$$ \text{DDT}[a, b] = \#\{x \in \mathbb{F}_2^n \mid S(x \oplus a) \oplus S(x) = b\}. $$

## Definition (LAT)

The *Linear Approximations Table* of $S$ is a matrix of size $2^n \times 2^n$ such that

$$ \begin{aligned} \text{LAT}[a, b] &= \#\{x \in \mathbb{F}_2^n \mid x \cdot a = S(x) \cdot b\} - 2^{n-1} \\ &= \frac{1}{2} \times \sum_{x \in \mathbb{F}_2^n} (-1)^{a \cdot x + b \cdot S(x)} \end{aligned} $$
## Example

$$S = [4, 2, 1, 6, 0, 5, 7, 3]$$

The DDT of S.

$$ \begin{bmatrix} 8 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 2 & 2 & 2 & 2 \\ 0 & 0 & 0 & 0 & 2 & 2 & 2 & 2 \\ 0 & 0 & 4 & 4 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 2 & 2 & 2 & 2 \\ 0 & 4 & 4 & 0 & 0 & 0 & 0 & 0 \\ 0 & 4 & 0 & 4 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 2 & 2 & 2 & 2 \end{bmatrix} $$

The LAT of S.

$$ \begin{bmatrix} 4 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 2 & 2 & 0 & 0 & 2 & -2 \\ 0 & 2 & 0 & 0 & 0 & 2 & -2 & 0 \\ 0 & 2 & 0 & 2 & 0 & -2 & 0 & 2 \\ 0 & 2 & 0 & -2 & 0 & -2 & 0 & -2 \\ 0 & -2 & 2 & 0 & 0 & -2 & -2 & 0 \\ 0 & 0 & -2 & 2 & 0 & -2 & -2 & 0 \\ 0 & 0 & 0 & 0 & -4 & 0 & 0 & 0 \end{bmatrix} $$
Coding Time!

1. Using the `sage/crypto.sboxes` module.

2. The AES S-box: differential uniformity, etc

3. The Jackon Pollock representation

4. Comparison with a random permutation
Coding Time! (Kuznyechik)

1. JP representation of the LAT of $n$

2. Reordering the columns

3. Reordering both rows and columns with linear permutations

4. Deduce an interesting permutation $L' \circ n \circ L$

5. Notice the integral distinguisher
# The TU-Decomposition

## Definition

The **TU-decomposition** is a decomposition algorithm working against S-Boxes with **vector spaces** of zeroes in their LAT.

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

T and U are mini-block ciphers; $\mu$ and $\eta$ are linear permutations.
Final Decomposition Number 1

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

⊙ Multiplication in $\mathbb{F}_{2^4}$

α Linear permutation

I Inversion in $\mathbb{F}_{2^4}$

$\nu_0, \nu_1, \sigma$ 4 × 4 permutations

$\phi$ 4 × 4 function

ω Linear permutation
Conclusion for Kuznyechik/Stribog?

The Russian S-Box was built like a
strange Feistel...
Conclusion for Kuznyechik/Stribog?

The Russian S-Box was built like a
strange Feistel...

... or was it?
# Conclusion for Kuznyechik/Stribog?

> The Russian S-Box was built like a
> strange Feistel...

> ... or was it?

## Belarusian inspiration

- The last standard of Belarus (BelT) uses an 8-bit S-box,

- somewhat similar to $\pi$...
# Conclusion for Kuznyechik/Stribog?

> The Russian S-Box was built like a
> strange Feistel...

> ... or was it?

## Belarusian inspiration

* The last standard of Belarus (BelT) uses an 8-bit S-box,

* somewhat similar to $\pi$...

* ... based on a finite field exponential!
Timeline

July 2012 GOST standardization of Streebog

Aug. 2013 RFC for Streebog (RFC6986)

June 2015 GOST standardization of Kuznyechik

Mar. 2016 RFC for Kuznyechik (RFC7801)

<footnote n="1">¹A. Biryukov, L. Perrin, A. Udovenko. *Reverse-engineering the S-box of Streebog, Kuznyechik and STRIBOBr1*. EUROCRYPT'16</footnote>
## Timeline

* July 2012 GOST standardization of Streebog

* Aug. 2013 RFC for Streebog (RFC6986)

* June 2015 GOST standardization of Kuznyechik

* Mar. 2016 RFC for Kuznyechik (RFC7801)

* May 2016 Publication of the first decomposition<fnref n="1" />

<footnote n="1">¹A. Biryukov, L. Perrin, A. Udovenko. *Reverse-engineering the S-box of Streebog, Kuznyechik and STRIBOBr1*. EUROCRYPT'16</footnote>
## Timeline

July 2012 GOST standardization of Streebog

Aug. 2013 RFC for Streebog (RFC6986)

June 2015 GOST standardization of Kuznyechik

Mar. 2016 RFC for Kuznyechik (RFC7801)

May 2016 Publication of the first decomposition<fnref n="1" />

Oct. 2018 ISO standardization of Streebog (ISO 10118-3)

<footnote n="1">¹A. Biryukov, L. Perrin, A. Udovenko. *Reverse-engineering the S-box of Streebog, Kuznyechik and STRIBOBr1*. EUROCRYPT'16</footnote>
# A Third and Final Decomposition: the TKlog

π is a TKlog!

π operates on $\mathbb{F}_{2^{2m}}$ where $m = 4$ using:

* α: a generator of $\mathbb{F}_{2^{2m}}$,

* κ: an affine function $\mathbb{F}_2^m \to \mathbb{F}_{2^{2m}}$ with $κ(\mathbb{F}_2^m) \oplus \mathbb{F}_{2^m} = \mathbb{F}_{2^{2m}}$,

* s: a permutation of $\mathbb{Z}/(2^m - 1)\mathbb{Z}$;

it works as follows:

$$ 
\left\{ 
\begin{array}{l}
\pi(0) = \kappa(0), \\
\pi((\alpha^{2^m+1})^i) = \kappa(2^m - j), \text{ for } 1 \le j \le 2^m - 1, \\
\pi(\alpha^{i+(2^m+1)j}) = \kappa(2^m - i) \oplus (\alpha^{2^m+1})^{s(j)}, \text{ for } 0 < i, 0 \le j < 2^m - 1.
\end{array}
\right. 
$$
## Timeline

* July 2012 GOST standardization of Streebog

* Aug. 2013 RFC for Streebog (RFC6986)

* June 2015 GOST standardization of Kuznyechik

* Mar. 2016 RFC for Kuznyechik (RFC7801)

* May 2016 Publication of the first decomposition

* Oct. 2018 ISO standardization of Streebog (ISO 10118-3)

* Jan. 2019 Publication of the final decomposition<fnref n="2" />

<footnote n="2">² L. Perrin. *Partitions in the S-box of Streebog and Kuznyechik*. IACR ToSC. 2019.</footnote>
## Timeline

* July 2012 GOST standardization of Streebog

* Aug. 2013 RFC for Streebog (RFC6986)

* June 2015 GOST standardization of Kuznyechik

* Mar. 2016 RFC for Kuznyechik (RFC7801)

* May 2016 Publication of the first decomposition

* Oct. 2018 ISO standardization of Streebog (ISO 10118-3)

* Jan. 2019 Publication of the final decomposition<fnref n="2" />

* Feb. 2019 Kuznyechik at ISO: decision post-poned

<footnote n="2">² L. Perrin. *Partitions in the S-box of Streebog and Kuznyechik*. IACR ToSC. 2019.</footnote>
## Timeline

<table><tr><td>July 2012</td><td>GOST standardization of Streebog</td></tr><tr><td>Aug. 2013</td><td>RFC for Streebog (RFC6986)</td></tr><tr><td>June 2015</td><td>GOST standardization of Kuznyechik</td></tr><tr><td>Mar. 2016</td><td>RFC for Kuznyechik (RFC7801)</td></tr><tr><td>May 2016</td><td>Publication of the first decomposition</td></tr><tr><td>Oct. 2018</td><td>ISO standardization of Streebog (ISO 10118-3)</td></tr><tr><td>Jan. 2019</td><td>Publication of the final decomposition<fnref n="2" /></td></tr><tr><td>Feb. 2019</td><td>Kuznyechik at ISO: decision post-poned</td></tr><tr><td>Sep. 2019</td><td>Kuznyechik at ISO: decision had to be taken!</td></tr></table>

<footnote n="2">² L. Perrin. *Partitions in the S-box of Streebog and Kuznyechik*. IACR ToSC. 2019.</footnote>
From the Designers, at ISO

questioned is the S-box $\pi$. This S-box was chosen from Streebog hash-function and it was synthesized in 2007. Note that through many years of cryptanalysis no weakness of this S-box was found. The S-box $\pi$ was obtained by pseudo-random search and the following properties were taken into account.

[...]

No secret structure was enforced during construction of the S-box. At the same time, it is obvious that for any transformation a lot of representations are possible (see, for example, a lot of AES S-box representations).
From the Designers, at ISO

questioned is the S-box $\pi$. This S-box was chosen from Streebog hash-function and it was synthesized in 2007. Note that through many years of cryptanalysis no weakness of this S-box was found. The S-box $\pi$ was obtained by pseudo-random search and the following properties were taken into account.

[...]

No secret structure was enforced during construction of the S-box. At the same time, it is obvious that for any transformation a lot of representations are possible (see, for example, a lot of AES S-box representations).

**Everything is wrong except for the green part.**
The Russian S-box is too simple

p(x){unsigned char* k="@`rFTDVbpPB
vdtfR@\xacp?\xe2>4\xa6\xe9{z\xe3q
5\xa7\xe8", a=2, l=0, b=17; while(x&&
(l++, a^x))a=2*a^a/128*29; return l
%b?k[l%b]^k[b+l/b]^b:k[l/b]^188;}

■ 165 ASCII characters that fit on 7 bits: this program is 1155-bit long

■ It is impossible that all 2¹⁶⁸⁴ 8-bit permutations have an implementation this short!
The Russian S-box is too simple

p(x){unsigned char* k="@`rFTDVbpPB
vdtfRQ\xacp?\xe2>4\xa6\xe9{z\xe3q
5\xa7\xe8", a=2, l=0, b=17; while(x&&
(l++, a^x))a=2*a^a/128*29; return l
%b?k[l%b]^k[b+l/b]^b:k[l/b]^188;}

■ 165 ASCII characters that fit on 7 bits: this program is 1155-bit long

■ It is **impossible** that all $2^{1684}$ 8-bit permutations have an implementation this short!

https://codegolf stackexchange.com/questions/186498/proving-that-a-russian-cryptographic-standard-is-too-structured
Cosets to Cosets

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

<figure><img src="image_41.png" /></figure>
# Cosets to Cosets

<figure><img src="image_42.png" /></figure>
# Cosets to Cosets

<figure><img src="image_43.png" /></figure>
# Cosets to Cosets

<figure><img src="image_44.png" /></figure>
# Why it is Worrying

## Russia's $\pi$

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

## Backdoored S-box

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

* July 2012 GOST standardization of Streebog

* Aug. 2013 RFC for Streebog (RFC6986)

* June 2015 GOST standardization of Kuznyechik

* Mar. 2016 RFC for Kuznyechik (RFC7801)

* May 2016 Publication of the first decomposition

* Oct. 2018 ISO standardization of Streebog (ISO 10118-3)

* Jan. 2019 Publication of the final decomposition³

* Feb. 2019 Kuznyechik at ISO: decision post-poned

* Sep. 2019 Kuznyechik at ISO: **thanks, but no thanks**

The Russian delegation failed to convince the experts that they were honest: the standardization of Kuznyechik was **refused**
# Outline

1. What are S-Boxes?

2. On Standardization and Trust

3. Don't Trust, Verify (and How to do it)

4. Conclusion
# Plan of this Section

1. What are S-Boxes?

2. On Standardization and Trust

3. Don't Trust, Verify (and How to do it)

4. Conclusion
Conclusion

■ Cryptographers use mathematics but mathematicians could also use crypto!
Conclusion

1. Cryptographers use mathematics but mathematicians could also use crypto!

2. If you **design** a cipher, **justify** every step of your design.
Conclusion

1 Cryptographers use mathematics but mathematicians could also use crypto!

2 If you **design** a cipher, **justify** every step of your design.

3 If you **choose** a cipher, **demand** a full design explanation.
Conclusion

1 Cryptographers use mathematics but mathematicians could also use crypto!

2 If you **design** a cipher, **justify** every step of your design.

3 If you **choose** a cipher, **demand** a full design explanation.

4 When in doubt, don't trust! (at least as far as crypto is concerned)
The Last S-Box

<table><tr><td>14</td><td>11</td><td>60</td><td>6d</td><td>e9</td><td>10</td><td>e3</td><td>2</td><td>b</td><td>90</td><td>d</td><td>17</td><td>c5</td><td>b0</td><td>9f</td><td>c5</td></tr><tr><td>d8</td><td>da</td><td>be</td><td>22</td><td>8</td><td>f3</td><td>4</td><td>a9</td><td>fe</td><td>f3</td><td>f5</td><td>fc</td><td>bc</td><td>30</td><td>be</td><td>26</td></tr><tr><td>bb</td><td>88</td><td>85</td><td>46</td><td>f4</td><td>2e</td><td>e</td><td>fd</td><td>76</td><td>fe</td><td>b0</td><td>11</td><td>4e</td><td>de</td><td>35</td><td>bb</td></tr><tr><td>30</td><td>4b</td><td>30</td><td>d6</td><td>dd</td><td>df</td><td>df</td><td>d4</td><td>90</td><td>7a</td><td>d8</td><td>8c</td><td>6a</td><td>89</td><td>30</td><td>39</td></tr><tr><td>e9</td><td>1</td><td>da</td><td>d2</td><td>85</td><td>87</td><td>d3</td><td>d4</td><td>ba</td><td>2b</td><td>d4</td><td>9f</td><td>9c</td><td>38</td><td>8c</td><td>55</td></tr><tr><td>d3</td><td>86</td><td>bb</td><td>db</td><td>ec</td><td>e0</td><td>46</td><td>48</td><td>bf</td><td>46</td><td>1b</td><td>1c</td><td>d7</td><td>d9</td><td>1b</td><td>e0</td></tr><tr><td>23</td><td>d4</td><td>d7</td><td>7f</td><td>16</td><td>3f</td><td>3</td><td>3</td><td>44</td><td>c3</td><td>59</td><td>10</td><td>2a</td><td>da</td><td>ed</td><td>e9</td></tr><tr><td>8e</td><td>d8</td><td>d1</td><td>db</td><td>cb</td><td>cb</td><td>c3</td><td>c7</td><td>38</td><td>22</td><td>34</td><td>3d</td><td>db</td><td>85</td><td>23</td><td>7c</td></tr><tr><td>24</td><td>d1</td><td>d8</td><td>2e</td><td>fc</td><td>44</td><td>8</td><td>38</td><td>c8</td><td>c7</td><td>39</td><td>4c</td><td>5f</td><td>56</td><td>2a</td><td>cf</td></tr><tr><td>d0</td><td>e9</td><td>d2</td><td>68</td><td>e4</td><td>e3</td><td>e9</td><td>13</td><td>e2</td><td>c</td><td>97</td><td>e4</td><td>60</td><td>29</td><td>d7</td><td>9b</td></tr><tr><td>d9</td><td>16</td><td>24</td><td>94</td><td>b3</td><td>e3</td><td>4c</td><td>4c</td><td>4f</td><td>39</td><td>e0</td><td>4b</td><td>bc</td><td>2c</td><td>d3</td><td>94</td></tr><tr><td>81</td><td>96</td><td>93</td><td>84</td><td>91</td><td>d0</td><td>2e</td><td>d6</td><td>d2</td><td>2b</td><td>78</td><td>ef</td><td>d6</td><td>9e</td><td>7b</td><td>72</td></tr><tr><td>ad</td><td>c4</td><td>68</td><td>92</td><td>7a</td><td>d2</td><td>5</td><td>2b</td><td>1e</td><td>d0</td><td>dc</td><td>b1</td><td>22</td><td>3f</td><td>c3</td><td>c3</td></tr><tr><td>88</td><td>b1</td><td>8d</td><td>b5</td><td>e3</td><td>4e</td><td>d7</td><td>81</td><td>3</td><td>15</td><td>17</td><td>25</td><td>4e</td><td>65</td><td>88</td><td>4e</td></tr><tr><td>e4</td><td>3b</td><td>81</td><td>81</td><td>fa</td><td>1</td><td>1d</td><td>4</td><td>22</td><td>0</td><td>6</td><td>1</td><td>27</td><td>68</td><td>27</td><td>2e</td></tr><tr><td>3b</td><td>83</td><td>c7</td><td>cc</td><td>25</td><td>9b</td><td>d8</td><td>d5</td><td>1c</td><td>1f</td><td>e5</td><td>59</td><td>7f</td><td>3f</td><td>3f</td><td>ef</td></tr></table>
What are S-Boxes?
On Standardization and Trust
Don't Trust, Verify (and How to do it)
Conclusion

Conclusion

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