New binary Hadamard-like transform with avalanche effect
Tags: math, cryptanalysis
Published: 2024-05-09 10:11:53

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 {% katex inline %}\operatorname{SHA256}{% endkatex %} hash function. Given a random input {% katex inline %}A{% endkatex %} and its hash {% katex inline %}\operatorname{SHA256}(A){% endkatex %}, flipping just one bit in {% katex inline %}A{% endkatex %} to create {% katex inline %}A'{% endkatex %}  results in a new hash {% katex inline %}\operatorname{SHA256}(A'){% endkatex %} that differs from {% katex inline %}\operatorname{SHA256}(A){% endkatex %} 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 {% katex inline %}P(A){% endkatex %}, that:

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

This characteristic was hypothesized to potentially weaken the avalanche effect when applied prior to {% katex inline %}\operatorname{SHA256}{% endkatex %} hashing. Although this particular application did not alter {% katex inline %}\operatorname{SHA256}{% endkatex %} 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 {% katex inline %}A{% endkatex %} can be expressed as:

{% katex %}
H(A)=A⋅H
{% endkatex %}

Where {% katex inline %}H{% endkatex %} represents the Hadamard matrix.

![Hadamard transform](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/8upqtm5m0qrx8pk5j90f.png)

Hadamard transform: the product of a binary vector and a Hadamard matrix {% katex inline %}(1, 0, 1, 0, 0, 1, 1, 0) × H(8) = (4, 2, 0, −2, 0, 2, 0, 2){% endkatex %}

#### 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:

{% katex %}
P(A)=A⋅P \operatorname{mod} 2
{% endkatex %}

Here, {% katex inline %}P{% endkatex %} matrix is constructed to retain the involutive property and the desired avalanche effect.

#### Constructing P matrix of size 4×4

To construct the {% katex inline %}P{% endkatex %} 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 {% katex inline %}N{% endkatex %} will aim to have sums equal {% katex inline %} N /2 − 1{% endkatex %}, 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: 

![4x4 and 8x8 P matrices](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/e63kk86pivyoquwdtif6.png)

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

![16×16 and 32×32 P matrices](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/nc6aexcp2mr9qwwe7o3q.png)

_16×16 and 32×32 P matrices_

Iterative process generates beautiful self-similar patterns:

![512×512 P-matrix](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/rc5ng7t1z0k5ncimsd5p.png)

_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](https://github.com/denys-potapov/p_transform).

First we can preview the transform with same numbers as for {% katex inline %}\operatorname{SHA256}{% endkatex %} 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 {% katex inline %}\operatorname{SHA256}{% endkatex %}, the transformed vectors look less _random_ than {% katex inline %}\operatorname{SHA256}{% endkatex %}.

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

1. Generate random input vector {% katex inline %}A{% endkatex %}
2. Flip one bit in {% katex inline %}A{% endkatex %} to get {% katex inline %}B{% endkatex %}
3. Calculate average distance between {% katex inline %}Fn(A){% endkatex %} and {% katex inline %}Fn(B){% endkatex %}.

```
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.