Decomposition Search for Lightweight Block Ciphers

This repository contains the code for finding optimal state decompositions
for lightweight block ciphers (CRAFT, SKINNY, MIDORI/Qarma/Mantis).

Dependencies

• GCC (>= 4.9) with OpenMP support (-fopenmp)
• Python (>= 3.6)
• numpy (>= 1.16) -- used by generate_transition_matrix.py and
  find_decomposition_matrix.py
• termcolor (>= 1.1) -- used by find_decomposition.py

Install the Python dependencies with:

pip install numpy termcolor

Quick Start

Compiling

make

This compiles decomposition_search with -O3 -march=native -fopenmp.

Running the Decomposition Search

The search is configured via #define macros at the top of
decomposition_search.c:

Parameter	Description
MAX_DEPTH	Maximum number of rounds to traverse
MAX_COST	Maximum number of state cell guesses per round
MAX_IMBALANCE	Maximum imbalance between the two parts
IS_ITERATIVE	Set to 1 to only search for iterative decompositions
CONTINUE_SEARCH	Set to 1 to continue searching after finding a solution
CIPHER	0 = SKINNY, 1 = CRAFT, 2 = MIDORI/Qarma/Mantis

After editing the parameters, recompile and run:

make clean && make
./decomposition_search

The program outputs all found decompositions matching the given parameters.

Interpreting the Output

Each line of output has the form:

BEST: ABCD -> EFGH -> ABCD    C: XXYY    D: 2 IMB: 4

Field	Meaning
ABCD	State partition as 4 hex nibbles, one per column. Each bit indicates which part (0 or 1) a cell belongs to.
->	Transition between rounds (after MixColumn + permutation).
C: XXYY	Cost encoded as two bytes: YY = cost for part 0, XX = cost for part 1. Each byte counts the number of cell guesses across all rounds for that part.
D: N	Depth, i.e., the number of rounds in the decomposition.
IMB: N	Maximum imbalance (difference in size between the two parts) across all round states.

When IS_ITERATIVE=1, the first and last state in the chain are equal,
indicating the decomposition repeats every D rounds.

Generating Transition Matrices

Precomputed transition matrices are provided (transition_*.matrix). To
regenerate them, edit generate_transition_matrix.py to uncomment the
desired cipher matrix, then run:

python3 generate_transition_matrix.py > transition_craft.matrix

Converting Results to LaTeX

To convert the output of the decomposition search into a LaTeX table:

./decomposition_search | python3 result_to_latex.py

File Overview

File	Description
decomposition_search.c	Main decomposition search (C, OpenMP-parallelized)
generate_transition_matrix.py	Generates transition cost matrices from MixColumn
find_decomposition.py	Alternative Python-based decomposition search
find_decomposition_matrix.py	Alternative Python search using matrix representation
result_to_latex.py	Converts search output to LaTeX tables
convert_permutation.py	Utility for converting permutation representations
transition_*.matrix	Precomputed transition matrices per cipher

License

MIT License. See LICENSE.