New binary Hadamard-like transform with avalanche effect

In cryptography, the avalanche effect is a property observed in block ciphers and hash functions. This effect ensures that even a slight change in the input, such as flipping a single bit, results in significant changes in the output. Consider the $\operatorname{SHA256}$ hash function. Given a random input $A$ and its hash $\operatorname{SHA256}(A)$ , flipping just one bit in $A$ to create $A'$ results in a new hash $\operatorname{SHA256}(A')$ that differs from $\operatorname{SHA256}(A)$ by approximately 128 bits on average:

A = 0x0000000000000000000000000000000000000000000000000000000000000001
A' = 0x0000000000000000000000000000000000000000000000000000000000000003

SHA256(A) = 0x01d0fabd251fcbbe2b93b4b927b26ad2a1a99077152e45ded1e678afa45dbec5
SHA256(A') = 0x91d3827f052f5a4b44d5fe2bed657c752247365d94f80a33cb09c1436a16b125

# Number of different bits (Hamming distance)
DISTANCE(SHA256(A), SHA256(A')) = 126

Finding the P-Transform

During my recreational math practice I thought of transform $P(A)$ , that:

1. Transforms binary vector to binary vector of same length.
2. Involutive: $P(P(A))=A$ ;
3. Has an avalanche effect similar to that observed in $\operatorname{SHA256}$ .

This characteristic was hypothesized to potentially weaken the avalanche effect when applied prior to $\operatorname{SHA256}$ hashing. Although this particular application did not alter $\operatorname{SHA256}$ robustness as anticipated, the experiment was fun and resulting transform looks somehow beautiful.

Design Basis: The Hadamard Transform

I drew inspiration from the classical Hadamard transform, a well-known mathematical transformation used primarily in signal processing and data compression. The Hadamard transform operates on vectors of real numbers and transforms the input vector into a vector of outputs based on Hadamard matrices. The general equation for the Hadamard transform of a vector $A$ can be expressed as:

Where $H$ represents the Hadamard matrix.

Hadamard transform: the product of a binary vector and a Hadamard matrix $(1, 0, 1, 0, 0, 1, 1, 0) × H(8) = (4, 2, 0, −2, 0, 2, 0, 2)$

Adapting to Binary Inputs and Outputs

However, unlike the Hadamard transform which outputs are real numbers, I expect P-transform to produce binary outputs. To adapt the concept to binary inputs and outputs, we define the transform as a matrix product of the input vector with a specially designed matrix followed by taking the result modulo 2. This ensures that the output remains within the binary domain (0s and 1s). The transformation equation thus becomes:

Here, $P$ matrix is constructed to retain the involutive property and the desired avalanche effect.

Constructing P matrix of size 4×4

To construct the $P$ matrix that underpins the P-Transform, we start with a manageable size of 4×4. Our goal is to ensure that the matrix is involutive and that each operation changes about half of the bits in the input, aligning with the desired avalanche effect.
Key Considerations:

• Equal Row and Column Sums: We aim for uniformity in the influence each input bit has on the output, meaning each row and each column should sum to the same value.
• Simplicity and Symmetry: By reducing the number of variants through symmetry and fixed sums, we can simplify the construction and analysis.

Given these requirements, we manually iterate over all possible 4x4 matrices of 0s and 1s. To streamline this, we focus on matrices that meet our sum criteria and disregard row permutations. This approach leaves us with two primary candidates:

Reversed Diagonal Matrix

[0, 0, 0, 1]
[0, 0, 1, 0]
[0, 1, 0, 0]
[1, 0, 0, 0]

Inverse of Reversed Diagonal Matrix

[1, 1, 1, 0]
[1, 1, 0, 1]
[1, 0, 1, 1]
[0, 1, 1, 1]

We choose to proceed with the Reversed Diagonal Matrix for its simplicity and direct alignment with our criteria.

Expanding P-matrix

To extend this approach to larger sizes, we will apply an iterative process where we construct larger matrices based on the properties established with this 4×4 matrix. We anticipate that each row in a matrix of size $N$ will aim to have sums equal $N /2 − 1$ , thus approaching our goal of altering approximately half of the bits in any input.

To construct an 8×8 P matrix, we use two instances of the 4×4 reversed diagonal matrix we previously determined. These instances are placed in the top-left and bottom-right corners of the 8×8 matrix.

The remaining top-right and bottom-left quadrants of the 8x8 matrix are crucial for ensuring that the row and column sums across the matrix meet our uniformity requirement. Given the setup of the existing 4×4 blocks, each row and column in these quadrants must sum to 2 to maintain the balance.

The simplest solution that meets this requirement is a symmetric arrangement where each quadrant is filled with a pattern that has two '1's per row and column, structured as follows:

[0, 0, 1, 1]
[0, 0, 1, 1]
[1, 1, 0, 0]
[1, 1, 0, 0]

To make it more visual here is a 4×4 and 8×8 matrices:

4×4 and 8×8 P matrices. White pixel corresponds to 1, black — 0

16×16 and 32×32 P matrices

Iterative process generates beautiful self-similar patterns:

512×512 P-matrix

Code and results

I've implemented a sample Python version of the P-Transform, which you can view and download from this GitHub repository.

First we can preview the transform with same numbers as for $\operatorname{SHA256}$ at the beginning of article:

A = 0x0000000000000000000000000000000000000000000000000000000000000001
A' = 0x0000000000000000000000000000000000000000000000000000000000000003

P_transform(A) = 0x8f000ff0000ffff00000000ffffffff0000000000000000ffffffffffffffff
P_transform(A') = 0x0300000000000000000000000000000000000000000000000000000000000000

# Number of different bits (Hamming distance)
DISTANCE(P_transform(A), P_transform(A')) = 127

Through avalanche effect is close to that of $\operatorname{SHA256}$ , the transformed vectors look less random than $\operatorname{SHA256}$ .

Following the aim of this transform I also calculated the average avalanche effect of $\operatorname{SHA256}$ , $\operatorname{P-transform}$ and $\operatorname{P-transform}$ applied before $\operatorname{SHA256}$ :

1. Generate random input vector $A$
2. Flip one bit in $A$ to get $B$
3. Calculate average distance between $Fn(A)$ and $Fn(B)$ .

SHA256 Avalanche 127.9851
P_transform Avalanche 127.0
SHA256 + P_transform Avalanche 128.0161

Future work

1. Self-Similarity of Matrices: Investigating the self-similarity and properties of the underlying matrices in the P-Transform could yield practical applications.

2. Cryptographic Applications: Exploring the use of the P-Transform as a basis for deterministic length extension in cryptanalysis presents a promising avenue for further research.