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
hash function. Given a random input
and its hash
, flipping just one bit in
to create
results in a new hash
that differs from
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 , that:
- Transforms binary vector to binary vector of same length.
- Involutive: ;
- Has an avalanche effect similar to that observed in .
This characteristic was hypothesized to potentially weaken the avalanche effect when applied prior to hashing. Although this particular application did not alter 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 can be expressed as:
Where represents the Hadamard matrix.
Hadamard transform: the product of a binary vector and a Hadamard matrix
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, matrix is constructed to retain the involutive property and the desired avalanche effect.
Constructing P matrix of size 4×4
To construct the
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 will aim to have sums equal , 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
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 , the transformed vectors look less random than .
Following the aim of this transform I also calculated the average avalanche effect of , and applied before :
- Generate random input vector
- Flip one bit in to get
- Calculate average distance between and .
SHA256 Avalanche 127.9851
P_transform Avalanche 127.0
SHA256 + P_transform Avalanche 128.0161
Future work
Self-Similarity of Matrices: Investigating the self-similarity and properties of the underlying matrices in the P-Transform could yield practical applications.
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.
Top comments (0)