boofun.analysis.cryptographic

Cryptographic analysis of Boolean functions.

This module provides cryptographic measures commonly used in symmetric cryptography, block cipher design, and S-box analysis. These measures help assess the resistance of Boolean functions against linear and differential cryptanalysis.

Key concepts: - Nonlinearity: Distance to the nearest affine function (resistance to linear attacks) - Bent functions: Functions achieving maximum nonlinearity (perfect nonlinearity) - Walsh spectrum: Fourier transform over F_2 (captures linear correlations) - Algebraic degree: Degree of the ANF (resistance to algebraic attacks) - Balancedness: Equal number of 0s and 1s (no bias in output)

Cross-validation: This module is designed to produce results that can be validated against: - thomasarmel/boolean_function (Rust): nonlinearity, is_bent, algebraic_degree - SageMath: walsh_hadamard_transform, nonlinearity - BooLSPLG: S-box analysis tools

References: - Carlet, “Boolean Functions for Cryptography and Coding Theory” - O’Donnell, “Analysis of Boolean Functions” (Fourier/Walsh connection) - Crama & Hammer, “Boolean Functions: Theory, Algorithms, and Applications”

Functions

`algebraic_degree`(f)	Compute the algebraic degree (ANF degree) of a Boolean function.
`algebraic_immunity`(f)	Compute the algebraic immunity of a Boolean function.
`algebraic_normal_form`(f)	Compute the Algebraic Normal Form (ANF) coefficients.
`anf_monomials`(f)	Return the monomials present in the ANF.
`correlation_immunity`(f)	Compute the correlation immunity order of a Boolean function.
`difference_distribution_table`(sbox)	Compute the Difference Distribution Table (DDT) of an S-box.
`differential_uniformity`(sbox)	Compute the differential uniformity of an S-box.
`is_balanced`(f)	Check if a Boolean function is balanced.
`is_bent`(f)	Check if a Boolean function is bent.
`linear_approximation_table`(sbox)	Compute the Linear Approximation Table (LAT) of an S-box.
`linearity`(sbox)	Compute the linearity of an S-box.
`nonlinearity`(f)	Compute the nonlinearity of a Boolean function.
`propagation_criterion`(f[, order])	Check if f satisfies the Propagation Criterion of order k.
`resiliency`(f)	Compute the resiliency order of a Boolean function.
`strict_avalanche_criterion`(f)	Check if f satisfies the Strict Avalanche Criterion (SAC).
`walsh_spectrum`(f)	Compute the Walsh spectrum (distribution of Walsh coefficients).
`walsh_transform`(f)	Compute the Walsh-Hadamard transform of a Boolean function.

Classes

`CryptographicAnalyzer`(f)	Comprehensive cryptographic analysis of a Boolean function.
`SBoxAnalyzer`(sbox)	Comprehensive S-box analysis for cryptographic applications.

boofun.analysis.cryptographic.walsh_transform(f: BooleanFunction) → np.ndarray[source]

Compute the Walsh-Hadamard transform of a Boolean function.

The Walsh transform W_f(a) measures the correlation between f and the linear function <a, x>:

W_f(a) = Σ_{x ∈ F_2^n} (-1)^{f(x) ⊕ <a,x>}

This is related to the Fourier transform by: W_f(a) = 2^n · f̂(a)

Parameters:: f – BooleanFunction to analyze
Returns:: Array of Walsh coefficients W_f(a) for a = 0, 1, …, 2^n - 1

Note

For balanced functions, W_f(0) = 0
For bent functions, |W_f(a)| = 2^{n/2} for all a

Cross-validation:: thomasarmel/boolean_function uses the same definition.

boofun.analysis.cryptographic.walsh_spectrum(f: BooleanFunction) → Dict[int, int][source]

Compute the Walsh spectrum (distribution of Walsh coefficients).

The spectrum is a histogram showing how many times each Walsh value appears.

Parameters:: f – BooleanFunction to analyze
Returns:: count}
Return type:: Dictionary {walsh_value

Example

>>> f = bf.parity(3)
>>> walsh_spectrum(f)
{-8: 1, 0: 7}  # XOR is bent-like, one large coefficient

boofun.analysis.cryptographic.nonlinearity(f: BooleanFunction) → int[source]

Compute the nonlinearity of a Boolean function.

Nonlinearity is the minimum Hamming distance to any affine function:

NL(f) = 2^{n-1} - (1/2) · max_a |W_f(a)|

Higher nonlinearity means better resistance to linear cryptanalysis.

Parameters:: f – BooleanFunction to analyze
Returns:: Nonlinearity (non-negative integer)

Bounds:

NL(f) ≤ 2^{n-1} - 2^{n/2 - 1} (bent bound, achieved iff bent)
NL(f) = 0 for affine functions

Cross-validation:

thomasarmel/boolean_function: f.nonlinearity() should match

Example

>>> f = bf.AND(3)
>>> nonlinearity(f)
2

boofun.analysis.cryptographic.is_bent(f: BooleanFunction) → bool[source]

Check if a Boolean function is bent.

A function is bent if it achieves maximum nonlinearity:: |W_f(a)| = 2^{n/2} for all a

Bent functions exist only for even n and are never balanced.

Parameters:: f – BooleanFunction to check
Returns:: True if f is bent

Cross-validation:: thomasarmel/boolean_function: f.is_bent() should match

Example

>>> # The function 0x0113077C165E76A8 (6 vars) is bent
>>> f = bf.from_hex("0113077C165E76A8", n_vars=6)
>>> is_bent(f)
True

boofun.analysis.cryptographic.is_balanced(f: BooleanFunction) → bool[source]

Check if a Boolean function is balanced.

A function is balanced if it has equal number of 0s and 1s in its truth table, equivalently W_f(0) = 0.

Parameters:: f – BooleanFunction to check
Returns:: True if f is balanced

Cross-validation:: thomasarmel/boolean_function: f.is_balanced() should match

boofun.analysis.cryptographic.algebraic_degree(f: BooleanFunction) → int[source]

Compute the algebraic degree (ANF degree) of a Boolean function.

The algebraic degree is the maximum number of variables in any monomial of the Algebraic Normal Form (ANF).

Parameters:: f – BooleanFunction to analyze
Returns:: Algebraic degree (0 for constant, n for full degree)

Note

This is computed via GF(2) analysis, not Fourier degree. For ±1-valued functions, ANF degree equals Fourier degree.

Cross-validation:: thomasarmel/boolean_function: f.algebraic_normal_form().degree()

boofun.analysis.cryptographic.algebraic_normal_form(f: BooleanFunction) → np.ndarray[source]

Compute the Algebraic Normal Form (ANF) coefficients.

The ANF represents f as a XOR of AND monomials over GF(2):: f(x) = ⊕_{S ⊆ [n]} a_S · ∏_{i ∈ S} x_i

Parameters:: f – BooleanFunction to analyze
Returns:: Array of ANF coefficients a_S (0 or 1) indexed by subset mask

Cross-validation:: thomasarmel/boolean_function: f.algebraic_normal_form()

boofun.analysis.cryptographic.anf_monomials(f: BooleanFunction) → List[Tuple[int, ...]][source]

Return the monomials present in the ANF.

Parameters:: f – BooleanFunction to analyze
Returns:: List of tuples, each tuple contains variable indices in the monomial Empty tuple () represents the constant term 1

Example

>>> f = bf.AND(2)  # x0 AND x1
>>> anf_monomials(f)
[(0, 1)]  # Just the monomial x0·x1

boofun.analysis.cryptographic.algebraic_immunity(f: BooleanFunction) → int[source]

Compute the algebraic immunity of a Boolean function.

Algebraic immunity AI(f) is the minimum degree d such that there exists a nonzero function g with degree d where f·g = 0 or (1⊕f)·g = 0.

This measures resistance to algebraic attacks on stream ciphers.

Parameters:: f – BooleanFunction to analyze
Returns:: Algebraic immunity (integer from 1 to ceil(n/2))

Note

AI(f) ≤ ceil(n/2) always holds. Computing exact AI is expensive for large n.

Reference:: Meier, Pasalic, Carlet: “Algebraic Attacks and Decomposition of Boolean Functions”

boofun.analysis.cryptographic.correlation_immunity(f: BooleanFunction) → int[source]

Compute the correlation immunity order of a Boolean function.

A function is t-th order correlation immune if it is statistically independent of any t input variables.

Equivalently, W_f(a) = 0 for all a with 1 ≤ |a| ≤ t.

Parameters:: f – BooleanFunction to analyze
Returns:: Maximum t such that f is t-th order correlation immune (0 if not CI)

boofun.analysis.cryptographic.resiliency(f: BooleanFunction) → int[source]

Compute the resiliency order of a Boolean function.

A function is t-resilient if it is balanced and t-th order correlation immune.

Parameters:: f – BooleanFunction to analyze
Returns:: Resiliency order (-1 if not balanced, 0+ otherwise)

boofun.analysis.cryptographic.propagation_criterion(f: BooleanFunction, order: int = 1) → bool[source]

Check if f satisfies the Propagation Criterion of order k.

PC(k) means: for all a with 1 ≤ |a| ≤ k, the function f(x) ⊕ f(x ⊕ a) is balanced.

Parameters:

f – BooleanFunction to check
order – Order k to check (default 1)

Returns:

True if f satisfies PC(k)

boofun.analysis.cryptographic.strict_avalanche_criterion(f: BooleanFunction) → bool[source]

Check if f satisfies the Strict Avalanche Criterion (SAC).

SAC means: flipping any single input bit changes the output with probability exactly 1/2. This is equivalent to PC(1).

Parameters:: f – BooleanFunction to check
Returns:: True if f satisfies SAC

boofun.analysis.cryptographic.linear_approximation_table(sbox: List[int]) → ndarray[source]

Compute the Linear Approximation Table (LAT) of an S-box.

The LAT measures linear correlations between input and output masks:: LAT[a,b] = #{x : <a,x> = <b,S(x)>} - 2^{n-1}

This is used in linear cryptanalysis of block ciphers.

Parameters:: sbox – S-box as list of output values (sbox[x] = S(x))
Returns:: 2D numpy array of size 2^n × 2^m where n=input bits, m=output bits

Note

For an n-bit to m-bit S-box, input masks range over 2^n, output masks range over 2^m.

Reference:: Matsui, “Linear Cryptanalysis Method for DES Cipher”
Cross-validation:: BooLSPLG computes the same LAT for S-box analysis.

boofun.analysis.cryptographic.difference_distribution_table(sbox: List[int]) → ndarray[source]

Compute the Difference Distribution Table (DDT) of an S-box.

The DDT measures differential propagation:: DDT[Δx, Δy] = #{x : S(x) ⊕ S(x ⊕ Δx) = Δy}

This is used in differential cryptanalysis of block ciphers.

Parameters:: sbox – S-box as list of output values (sbox[x] = S(x))
Returns:: 2D numpy array of size 2^n × 2^m

Note

DDT[0,0] = 2^n always (trivial differential).

Reference:: Biham & Shamir, “Differential Cryptanalysis of DES-like Cryptosystems”
Cross-validation:: BooLSPLG computes the same DDT.

boofun.analysis.cryptographic.differential_uniformity(sbox: List[int]) → int[source]

Compute the differential uniformity of an S-box.

Differential uniformity is the maximum non-trivial entry in the DDT:: δ = max{DDT[Δx, Δy] : Δx ≠ 0}

Lower values indicate better resistance to differential cryptanalysis. The minimum possible value is 2 for bijective S-boxes (APN functions).

Parameters:: sbox – S-box as list of output values
Returns:: Differential uniformity (positive integer)

Note

δ = 2: Almost Perfect Nonlinear (APN)
δ = 4: Used in AES S-box

boofun.analysis.cryptographic.linearity(sbox: List[int]) → int[source]

Compute the linearity of an S-box.

Linearity is twice the maximum absolute value in the LAT:: L = 2 × max{|LAT[a,b]| : (a,b) ≠ (0,0)}

Lower values indicate better resistance to linear cryptanalysis.

Parameters:: sbox – S-box as list of output values
Returns:: Linearity (positive integer)

Note

For n-bit S-boxes, L ≥ 2^{n/2} (bent bound). AES S-box has L = 32.

class boofun.analysis.cryptographic.CryptographicAnalyzer(f: BooleanFunction)[source]

Comprehensive cryptographic analysis of a Boolean function.

This class computes and caches various cryptographic measures.

Example

>>> f = bf.create([0, 1, 1, 0, 1, 0, 0, 1])  # 3-var bent-like
>>> analyzer = CryptographicAnalyzer(f)
>>> print(analyzer.summary())

__init__(f: BooleanFunction)[source]

Initialize analyzer with a Boolean function.

Parameters:: f – BooleanFunction to analyze

property n_vars: int: Number of variables.

property walsh: ndarray: Walsh transform (cached).

property anf: ndarray: ANF coefficients (cached).

nonlinearity() → int[source]: Compute nonlinearity.

is_bent() → bool[source]: Check if bent.

is_balanced() → bool[source]: Check if balanced.

algebraic_degree() → int[source]: Compute algebraic degree.

correlation_immunity() → int[source]: Compute correlation immunity order.

resiliency() → int[source]: Compute resiliency order.

satisfies_sac() → bool[source]: Check if satisfies SAC.

walsh_spectrum() → Dict[int, int][source]: Get Walsh spectrum.

summary() → str[source]: Return human-readable summary.

to_dict() → Dict[source]: Export all measures as dictionary (for cross-validation).

class boofun.analysis.cryptographic.SBoxAnalyzer(sbox: List[int])[source]

Comprehensive S-box analysis for cryptographic applications.

An S-box (Substitution box) is a basic component of symmetric key algorithms. This analyzer computes various measures of cryptographic strength.

Example

>>> # Analyze a 4-bit S-box
>>> sbox = [0xE, 0x4, 0xD, 0x1, 0x2, 0xF, 0xB, 0x8,
...         0x3, 0xA, 0x6, 0xC, 0x5, 0x9, 0x0, 0x7]
>>> analyzer = SBoxAnalyzer(sbox)
>>> print(analyzer.summary())

__init__(sbox: List[int])[source]

Initialize S-box analyzer.

Parameters:: sbox – S-box as list where sbox[x] = S(x)

property n_inputs: int: Number of input bits.

property n_outputs: int: Number of output bits.

property lat: ndarray: Linear Approximation Table (cached).

property ddt: ndarray: Difference Distribution Table (cached).

is_bijective() → bool[source]: Check if S-box is a bijection (permutation).

differential_uniformity() → int[source]: Compute differential uniformity.

linearity() → int[source]: Compute linearity.

nonlinearity() → int[source]

Compute nonlinearity of the S-box.

For an S-box, nonlinearity is:: NL = 2^{n-1} - L/2

where L is the linearity.

is_apn() → bool[source]: Check if S-box is Almost Perfect Nonlinear (differential uniformity = 2).

summary() → str[source]: Return human-readable summary.

to_dict() → Dict[source]: Export measures as dictionary.