Implementation of CLEFIA S-box Using Normal Basis — Inspired by A Very Compact Rijndael S-box

A few years ago, I explored one of my favorite cryptographic building blocks: the substitution box (S-box). Back then, I came across the elegant paper A Very Compact Rijndael S-box, which showed how to eliminate lookup tables by leveraging normal basis representation and logical operations in $F_{2^{8}}$. That approach deeply resonated with me—compact, efficient, and mathematically sound.

Recently, I decided to revisit that work—but this time with a new challenge: re-implementing the CLEFIA S-box using the same principles. CLEFIA, Sony’s lightweight block cipher, uses two $8 \times 8$ S-boxes ($S_0$ and $S_1$), and I focused on reconstructing S₁ using field inversion and affine transformations—all without tables.

This blog walks you through that journey—from understanding the S-box structure in CLEFIA, finding a suitable normal basis, and implementing the logic step by step.

🧩 CLEFIA S-box1 (S₁) Formula

The S₁ function in CLEFIA is defined as follows:

$$ S_1(x) = \begin{cases} g(f(x)^{-1}) & \text{if } f(x) \ne 0 \ g(0) & \text{if } f(x) = 0 \end{cases} $$

Where:

  • $f(x)$ is an affine transformation in $F_{2^{8}}$
  • Inversion is performed in $F_{2^{8}}$ defined by the irreducible polynomial:

$$ z^8 + z^4 + z^3 + z^2 + 1 $$

  • $g(x)$ is another affine transformation over $F_{2^{8}}$

🔢 Affine Transformation Matrices

The affine transformations $f(x)$ and $g(x)$ can be represented as matrix operations over GF(2):

$$ f(x) = A_f \cdot x + b_f $$

$$ g(x) = A_g \cdot x + b_g $$

Where:

  • $A_f$ and $A_g$ are $8 \times 8$ binary matrices.
  • $b_f$ and $b_g$ are 8-bit binary vectors.
  • $x$ is the 8-bit input vector.

For example, the matrix $A_f$ and vector $b_f$ might be defined as:

$$ A_f = \begin{bmatrix} 1 & 0 & 0 & 0 & 1 & 1 & 0 & 1 \\ 1 & 1 & 0 & 0 & 1 & 0 & 0 & 1 \\ 0 & 1 & 1 & 1 & 0 & 0 & 0 & 1 \\ 0 & 0 & 0 & 0 & 1 & 1 & 0 & 1 \\ 0 & 0 & 1 & 0 & 0 & 0 & 1 & 0 \\ 1 & 0 & 0 & 0 & 1 & 0 & 1 & 1 \\ 0 & 1 & 1 & 1 & 0 & 0 & 0 & 0 \\ 1 & 1 & 0 & 1 & 0 & 1 & 1 & 0 \end{bmatrix} ,b_f = \begin{bmatrix} 1 \\ 1 \\ 0 \\ 0 \\ 0 \\ 1 \\ 1 \\ 0 \end{bmatrix} $$

Similarly, define $A_g$ and $b_g$ as per the CLEFIA specification.

🔬 From Table to Logic: Why Normal Basis?

In normal basis:

  • Squaring becomes a cyclic shift — perfect for efficient hardware or bit-sliced software
  • Multiplication and inversion can be expressed as boolean formulas
  • No lookup tables → smaller memory, better side-channel resistance

⚙️ SAGE/C Implementation Steps

I used the Normal-Basis project as a foundation and modified it to support CLEFIA’s field and transformations.

1. Define GF(2⁸) With CLEFIA Polynomial

1. Defining the Playground: Finite-Field Setup

The file const.sage establishes the mathematical landscape. It lists all 36 irreducible polynomials of degree 8 over GF(2), along with their exponent representations (IR_power) to ease polynomial evaluation. It also encodes affine transformation matrices for both AES and CLEFIA, which will be applied after inversion in the S-box pipeline.

IR = [
    x^8 + x^4 + x^3 + x + 1,
    x^8 + x^4 + x^3 + x^2 + 1,
    ...
    x^8 + x^7 + x^6 + x^5 + x^4 + x^3 + 1
]

AF_AES = [
    [1,1,1,1,1,0,0,0],
    [0,1,1,1,1,1,0,0],
    ...
    [1,1,1,1,0,0,0,1]
]

AF_CLEFIA = [
    [0,0,0,0,1,0,1,0],
    [0,1,0,0,0,0,0,1],
    ...
    [0,1,0,0,0,1,0,0]
]

2. Generating Change-of-Basis Matrices with Sage

NBG.sage is the computational engine responsible for generating the matrices required to switch between different bases in GF(2⁸) operations.
It plays a key role in preparing data for efficient normal-basis arithmetic in S-box implementations.

This script:

  • Imports constant definitions from const.sage
  • Constructs log/antilog tables for GF(2⁸)
  • Derives normal bases
  • Produces change-of-basis matrices between:
    • Affine basis
    • Polynomial basis
    • Normal basis

Key Steps

  1. Sort primitive elements for each irreducible polynomial.
  2. Build log/antilog tables across subfields for efficient multiplication and inversion.
  3. Produce conversion arrays:
    • X2A → Normal basis → Affine basis
    • A2X → Affine basis → Normal basis
    • X2S → Normal basis → S-box basis
    • S2X → S-box basis → Normal basis

Function: matrix_generation

The matrix_generation function creates and outputs the transformation matrices needed for basis conversions.

def matrix_generation(X):
    XB = hex_to_bin(X)
    X2A = concatenate_horizontal(XB)
    printout("X2A", X2A)
    
    M = matrix(GF(2), XB)
    X_1 = M.inverse()
    A2X = concatenate_horizontal(X_1)
    printout("A2X", A2X)
    
    CM = matrix(GF(2), AF_CLEFIA)
    MX = M * CM.transpose()
    X2S = concatenate_horizontal(MX)
    printout("X2S", X2S)
    
    MX_1 = MX.inverse()
    S2X = concatenate_horizontal(MX_1)
    printout("S2X", S2X)

The calculate_basis function orchestrates table generation and final matrix output:

def calculate_basis(Root_IR, Y_1, Y_16, Z_1, Z_4, W_1, W_2):
    F.<a> = GF(2^8, modulus=IR[Root_IR])
    LT = generate_logtable(Root_IR)
    ALT = generate_antilogtable(LT)
    CM = change_matrix(Y_1, Y_16, Z_1, Z_4, W_1, W_2)
    ...
    matrix_generation(CMH)
    wzy_N_V(Y_1, Y_16, Z_1, Z_4, W_1, W_2, LT, ALT)

3. Precomputed Matrices for C Implementations

The generated matrices are stored in matrix.h and selected via a compile-time OPTION macro. Multiple configurations are commented, enabling experimentation with different normal bases.

#define OPTION 6

static int X2A[8] = { 0xb4, 0xae, 0xf6, 0xfe, 0xbe, 0xeb, 0x2b, 0x6d };
static int A2X[8] = { 0x1e, 0x18, 0x75, 0x48, 0x30, 0xa3, 0xb8, 0xff };
static int X2S[8] = { 0x31, 0x3f, 0xd4, 0x74, 0x15, 0x1f, 0x7c, 0x98 };
static int S2X[8] = { 0x74, 0xff, 0x44, 0x67, 0x12, 0xcc, 0x1e, 0xa3 };

4. C Implementations of Normal-Basis S-Boxes

Two C programs illustrate matrix and arithmetic usage: Sbox_NB_new.c — CLEFIA support using an extra transformation matrix Clefia_transform. sbox_NB_NW.c — AES-style S-box using normal-basis operations without the extra transformation.