International Association for Cryptologic Research

International Association
for Cryptologic Research

Transactions on Cryptographic Hardware and Embedded Systems 2026

LFSRs and Boolean Masking:

An In-depth Security Analysis


README

Artifact for the extended version of the paper "LFSRs and Boolean Masking: An In-depth Security Analysis" by Anna Guinet, Jan Schoone, Niklas Höher, Dina Hesse and Tim Güneysu, published at TCHES 2026, Issue 3.

TCHES Published paper: https://doi.org/10.46586/tches.v2026.i3.426-464

TCHES Artifact: TBA

Extended version of the TCHES published paper: https://eprint.iacr.org/2026/1614

1. Supplementary material

We explicit in this README the general description of the LFSRs, the S-boxes, the gadgets, and how the LFSRs were used in the masked implementations for this paper.

1.1 Folder structure

.
├── sage            # Scripts to run the masked S-boxes verification with the LFSRs
└── verilog         # Verilog files with testbenches

We provide the verilog files generated by HADES [1] in ./verilog to create first-order masked implementations of the Skinny S-boxes and the AES S-box. We provide as well testbenches to simulate these designs: They are identified by the file name TB_XXX.v in the folder.

We symbolically translate the circuits from those verilog files into Sagemath scripts in the folder ./sage/ Then, we run our security verification by assuming that the randomness comes from a single LFSR; the results are reported in the tables of the paper.

[1] Publication available at https://doi.org/10.46586/tches.v2025.i4.1-45. Git available at https://github.com/Chair-for-Security-Engineering/HADES/.

2. LFSR description

We provide standalone Python functions to run an LFSR in either Galois or Fibonacci mode, as described in Section 3 of the paper, with an example for 1 + X^2 + X^3 + X^4 + X^7.

2.1 Galois

def compute_next_state_Galois_LFSR(state, poly):
    #  Equation 3 of paper
    #  Output bit of the LFSR: next_state[-1]
    #  poly[0] = poly[len(state)] = 1 always
    next_state    = [0] * len(state)
    next_state[0] = state[-1]
    for i in range(1,len(state)):
  next_state[i] = state[i-1] ^ poly[i] * state[-1]
    return next_state

# Length of LFSR
len_LFSR = 7

# Number of desired output bits
num_out = 8

# Seed [s0, ..., s{size-1}]
state = [0,1,0,1,0,1,0] # size 7

# Characteristic polynomial [p0, ..., p{len-1}]
poly = [1,0,1,1,1,0,0]  # 1 + X^2 + X^3 + X^4 + X^7

assert (len(state) == len_LFSR) & (len(poly) == len_LFSR), print('Length poly and/or length seed != length LFSR')

for i in range(num_out):
    state = compute_next_state_Galois_LFSR(state, poly)
    output_bit = state[-1]
    print(output_bit)

2.2 Fibonacci

def compute_next_state_Fibonacci_LFSR(state, poly):
    #  Equation 5 of paper
    #  Output bit of the LFSR: next_state[-1]
    #  poly[0] = poly[len(state)] = 1 always
    next_state     = [0] * len(state)
    next_state[1:] = state[:-1]

    for state_i, poly_i in zip(state, poly[::-1]):
  next_state[0] ^= state_i & poly_i
    return next_state

# Length of LFSR
len_LFSR = 7

# Number of desired output bits
num_out = 8

# Seed [s0, ..., s{size-1}]
state = [0,1,0,1,0,1,0] # size 7

# Characteristic polynomial [p0, ..., p{len-1}]
poly = [1,0,1,1,1,0,0]  # 1 + X^2 + X^3 + X^4 + X^7

assert (len(state) == len_LFSR) & (len(poly) == len_LFSR), print('Length poly and/or length seed != length LFSR')

for i in range(num_out):
    state = compute_next_state_Fibonacci_LFSR(state, poly)
    output_bit = state[-1]
    print(output_bit)

3. S-boxes Description

We write the unmasked descriptions of the considered S-boxes in this paper. We refer to the files in ./verilog for their masked implementations in hardware with XOR, AND and NOT gadgets. For the Skinny S-boxes, their implementations are straightforward from those descriptions; we explicit in more details the one of the AES S-box. We used those descriptions to run our security verification in SageMath on the first-order masked version, see files in ./sage.

Field: F_2 where * is the multiplication (AND) and + is the addition (XOR). The parenthesis () give the order in which the operations are executed. Each multiplication is replaced by a multiplication gadget.

3.1 4-bit Skinny S-Box

Boolean Functions of component functions (without masking) in F_2.

y3 = x0 + ((x3 + 1) * (x2 + 1))   
y2 = x3 + ((x2 + 1) * (x1 + 1))  
y1 = x2 + ((x1 + 1) * (y3 + 1))  
y0 = x1 + ((y3 + 1) * (y2 + 1))

3.2 8-bit Skinny S-Box

Boolean Functions of component functions (without masking) in F_2.

y_7 = x_5 + (y_6 + 1) * (y_5 + 1)   
y_6 = x_4 + (x_7 + 1) * (x_6 + 1)   
y_5 = x_0 + (x_3 + 1) * (x_2 + 1)     
y_4 = x_3 + (y_7 + 1) * (y_6 + 1)    
y_3 = x_1 + (y_5 + 1) * (x_3 + 1)  
y_2 = x_6 + (x_2 + 1) * (x_1 + 1)  
y_1 = x_7 + (y_7 + 1) * (y_2 + 1)  
y_0 = x_2 + (y_3 + 1) * (y_1 + 1)

3.3 8-bit AES S-Box by Boyar and Peralta

Implementation of the component functions (without masking) in F_2.

xor_0 = x7 + x4  
xor_1 = x7 + x2  
xor_2 = x7 + x1  
xor_3 = x4 + x2  
xor_4 = x3 + x1   
xor_5 = xor_0 + xor_4  
xor_6 = x6 + x5  
xor_7 = x0 + xor_5   
xor_8 = x0 + xor_6   
xor_9 = xor_5 + xor_6  
xor_10 = x6 + x2  
xor_11 = x5 + x2  
xor_12 = xor_2 + xor_3   
xor_13 = xor_5 + xor_10  
xor_14 = xor_4 + xor_10   
xor_15 = xor_4 + xor_11  
xor_16 = xor_8 + xor_15  
xor_17 = x4 + x0  
xor_18 = xor_6 + xor_17  
xor_19 = xor_0 + xor_18  
xor_20 = x1 + x0  
xor_21 = xor_6 + xor_20  
xor_22 = xor_1 + xor_21  
xor_23 = xor_1 + xor_9  
xor_24 = xor_19 + xor_16  
xor_25 = xor_2 + xor_15  
xor_26 = xor_0 + xor_11  

and_0 = xor_12 * xor_5  
and_1 = xor_22 * xor_7  
and_2 = xor_18 * x0  
and_3 = xor_2  * xor_15   
and_4 = xor_21 * xor_8   
and_5 = xor_19 * xor_16  
and_6 = xor_0 * xor_14   
and_7 = xor_3 * xor_26  
and_8 = xor_1 * xor_9  

xor_54 = xor_13 + and_0  
xor_55 = and_2 + and_0  
xor_56 = xor_25 + and_3  
xor_57 = and_5 + and_3  
xor_58 = and_7 + and_6  
xor_59 = and_8 + and_6  
xor_60 = xor_54 + and_1  
xor_61 = xor_55 + xor_23  
xor_62 = xor_56 + and_4  
xor_63 = xor_57 + xor_59  
xor_64 = xor_60 + xor_58  
xor_65 = xor_61 + xor_59  
xor_66 = xor_62 + xor_58  
xor_67 = xor_63 + xor_24  
xor_68 = xor_66 + xor_67  

and_9 = xor_66 * xor_64  

xor_69 = xor_65 + and_9  
xor_70 = xor_64 + xor_65  
xor_71 = xor_67 + and_9  
xor_72 = xor_70 + and_9  
xor_73 = xor_68 + and_9  

and_10 = xor_71 * xor_70  
and_11 = xor_69 * xor_68  
and_12 = xor_64 * xor_67  
and_13 = xor_70 * and_12  
and_14 = xor_65 * xor_66  
and_15 = xor_68 * and_14  

xor_74 = xor_65 + and_10  
xor_75 = and_13 + xor_72  
xor_76 = xor_67 + and_11  
xor_77 = and_15 + xor_73  
xor_78 = xor_75 + xor_77  
xor_79 = xor_74 + xor_76  
xor_80 = xor_74 + xor_75  
xor_81 = xor_76 + xor_77  
xor_82 = xor_79 + xor_78  

and_16 = xor_81 * xor_5  
and_17 = xor_77 * xor_7  
and_18 = xor_76 * x0  
and_19 = xor_80 * xor_15  
and_20 = xor_75 * xor_8   
and_21 = xor_74 * xor_16  
and_22 = xor_79 * xor_14  
and_23 = xor_82 * xor_26  
and_24 = xor_78 * xor_9   
and_25 = xor_81 * xor_12  
and_26 = xor_77 * xor_22  
and_27 = xor_76 * xor_18  
and_28 = xor_80 * xor_2   
and_29 = xor_75 * xor_21  
and_30 = xor_74 * xor_19  
and_31 = xor_79 * xor_0  
and_32 = xor_82 * xor_3  
and_33 = xor_78 * xor_1  

xor_83 = and_31 + and_32  
xor_84 = and_20 + and_26  
xor_85 = and_16 + and_18  
xor_86 = and_17 + and_25  
xor_87 = and_24 + and_28   
xor_88 = and_19 + and_31   
xor_89 = and_32 + xor_88  
xor_90 = and_16 + xor_86  
xor_91 = and_21 + and_29  
xor_92 = and_22 + and_23   
xor_93 = and_23 + xor_87   
xor_94 = and_30 + xor_85   
xor_95 = and_18 + and_21  
xor_96 = and_20 + xor_83   
xor_97 = and_22 + and_31  
xor_98 = and_25 + xor_84   
xor_99 = and_26 + xor_83   
xor_100 = and_27 + xor_84   
xor_101 = and_28 + xor_91  
xor_102 = and_33 + xor_87  
xor_103 = xor_83 + xor_84   
xor_104 = xor_84 + xor_90   
xor_105 = xor_86 + xor_95   
xor_106 = xor_101 + xor_85   
xor_107 = xor_98 + xor_92   
xor_108 = xor_89 + xor_93  
xor_109 = xor_90 + xor_92   
xor_110 = xor_91 + xor_93   
xor_111 = xor_94 + xor_97   
xor_112 = xor_94 + xor_100   
xor_113 = xor_89 + xor_107 // y_7   
xor_114 = xor_99 + xor_109   
xor_115 = xor_102 + xor_111   
xor_116 = xor_89 + xor_104 // y_4  
xor_117 = xor_103 + xor_105 // y_3  
xor_118 = xor_108 + xor_112 // y_2  
xor_119 = xor_96 + xor_110   
xor_120 = xor_89 + xor_106   

not_10 = xor_114 + 1 // y_6   
not_11 = xor_115 + 1 // y_5  
not_12 = xor_119 + 1 // y_1  
not_13 = xor_120 + 1 // y_0

4. First-order Gadgets Description and Probe Locations

We describe the first-order multiplication gadgets used in this paper, as in the verilog files, as well as the probe locations to run our security analysis with the scripts in ./sage. The considered multiplications gadgets are DOM, HPC1, HPC2 and HPC3.

Field: F_2 where * is the multiplication (AND) and + is the addition (XOR). The parenthesis () give the order in which the operations are executed, i.e., stored in registers. Each multiplication is replaced by a multiplication gadget. For the probe locations, we consider probe on each individual input variable of each gadget, each output share and each intermediate computation in a multiplication gadget (). If an intermediate computation sums the output of several registers (e.g., (A) + (B) + (C)), we consider in addition all linear combinations of those registers outputs (e.g., (A) + (B), (A) + (C), (B) + (C)).

4.1 DOM Multiplication

c0 = (a0 * b0)      + (a0 * b1 + r0)
c1 = (a1 * b0 + r0) + (a1 * b1)

with r0 random value

4.2 HPC1 Multiplication

c0 = (a0 * (b0 + s0))        + ((a0 * (b1 + s0)) + r0)
c1 = ((a1 * (b0 + s0)) + r0) + (a1 * (b1 + s0))

with s0, r0 random values

4.3 HPC2 Multiplication

c0 = (a0 * b0) + ((a0 + 1) * r0) + (a0 * (b1 + r0))
c1 = (a1 * b1) + ((a1 + 1) * r0) + (a1 * (b0 + r0))

with r0 random value

4.4 HPC3 Multiplication

c0 = (a0 * b0) + (a0) * (b1 + s0) + ((a0 + 1) * s0 + r0)
c1 = (a1 * b1) + (a1) * (b0 + s0) + ((a1 + 1) * s0 + r0)

with s0, r0 random values

5. How the LFSR randomness was used

5.1 First-Order Masking

We explicit how the LFSR outputs were used in the first-order masked implementations of the S-boxes with the different gadgets, to run the security verification in ./sage/.

5.1.1 4-bit Skinny Sbox - DOM and HPC2 gadgets

# First share
x0_0 = x0 + x0_1
x1_0 = x1 + x1_1
x2_0 = x2 + x2_1
x3_0 = x3 + x3_1

# Second share
x0_1 = lfsr[0] # first output of LFSR (after doing one round on the seed)
x1_1 = lfsr[1] # second output of LFSR
x2_1 = lfsr[2]
x3_1 = lfsr[3]

# Refresh in DOM/HPC2 gadgets
and_0_r = lfsr[4] # 5-th output of LFSR
and_1_r = lfsr[5]
and_2_r = lfsr[6]
and_3_r = lfsr[7]

5.1.2 4-bit Skinny Sbox - HPC1 and HPC3 gadgets

# First share
x0_0 = x0 + x0_1
x1_0 = x1 + x1_1
x2_0 = x2 + x2_1
x3_0 = x3 + x3_1

# Second share
x0_1 = lfsr[0] # first output of LFSR (after doing one round on the seed)
x1_1 = lfsr[1] # second output of LFSR
x2_1 = lfsr[2]
x3_1 = lfsr[3]

# Rand in gadgets
and_0_r[0] = lfsr[4] # for refresh part of HPC1            - for masking part of HPC3
and_0_r[1] = lfsr[5] # for masking part of HPC1 (like DOM) - for refresh part of HPC3
and_1_r[0] = lfsr[6] # for refresh
and_1_r[1] = lfsr[7] # for masking
and_2_r[0] = lfsr[8]
and_2_r[1] = lfsr[9]
and_3_r[0] = lfsr[10]
and_3_r[1] = lfsr[11]

5.1.3 8-bit Sboxes

# First share
x0_0 = x0 + x0_1
x1_0 = x1 + x1_1
x2_0 = x2 + x2_1
x3_0 = x3 + x3_1
x4_0 = x4 + x4_1
x5_0 = x5 + x5_1
x6_0 = x6 + x6_1
x7_0 = x7 + x7_1

# Second share
x0_1 = lfsr[0] # first output of LFSR (after doing one round on the seed)
x1_1 = lfsr[1] # second output of LFSR
x2_1 = lfsr[2]
x3_1 = lfsr[3]
x4_1 = lfsr[4]
x5_1 = lfsr[5]
x6_1 = lfsr[6]
x7_1 = lfsr[7]

The same pattern is used for DOM, HPC1, HPC2 and HPC3 gadgets as given for the 4-bit Skinny Sbox.

5.2 Second-Order Masking

We explicit how the LFSR outputs were used in the second-order masked implementations of the S-boxes with the different gadgets, to run the security verification in ./sage/.

5.2.1 4-bit Skinny Sbox - Creating the shares

# First share
x0_0 = x0 + x0_1 + x0_2
x1_0 = x1 + x1_1 + x1_2
x2_0 = x2 + x2_1 + x2_2
x3_0 = x3 + x3_1 + x3_2

# Second share
x0_1 = lfsr[0] # first output of LFSR (after doing one round on the seed)
x1_1 = lfsr[1] # second output of LFSR
x2_1 = lfsr[2]
x3_1 = lfsr[3]

# Third share
x0_2 = lfsr[4] # 5-th output of LFSR 
x1_2 = lfsr[5] 
x2_2 = lfsr[6]
x3_2 = lfsr[7]

The same pattern is used for the 8-bit Skinny Sbox.

5.2.2 4-bit Skinny Sbox - Refreshing the gadgets

For the implementation with the second-order DOM/HPC2 gadget:

and_0_r[0] = lfsr[8] # 9-th output of LFSR
and_0_r[1] = lfsr[9] 
and_0_r[2] = lfsr[10] 
# etc.
and_3_r[0] = lfsr[17] 
and_3_r[1] = lfsr[18]
and_3_r[2] = lfsr[19]

For the implementation with the second-order HPC1 gadget:

and_0_r[0] = lfsr[8] # 9-th output of LFSR
and_0_r[1] = lfsr[9] 
and_0_r[2] = lfsr[10] 
and_0_r[3] = lfsr[11] 
and_0_r[4] = lfsr[12] 
# etc.
and_3_r[0] = lfsr[23]
and_3_r[1] = lfsr[24]
and_3_r[2] = lfsr[25]
and_3_r[3] = lfsr[26]
and_3_r[4] = lfsr[27]

For the implementation with the second-order HPC3 gadget:

and_0_r[0] = lfsr[8] # 9-th output of LFSR
and_0_r[1] = lfsr[9] 
and_0_r[2] = lfsr[10] 
and_0_r[3] = lfsr[11] 
and_0_r[4] = lfsr[12] 
and_0_r[5] = lfsr[13]
# etc.
and_3_r[0] = lfsr[26]
and_3_r[1] = lfsr[27]
and_3_r[2] = lfsr[28]
and_3_r[3] = lfsr[29]
and_3_r[4] = lfsr[30]
and_3_r[5] = lfsr[31]

The same pattern is used for the 8-bit Skinny Sbox.

6. License and Contact

Please contact Anna Guinet ([email protected]) for questions about this artifact.

The files in the folders

verilog/
	DOM/
	HPC1/

follow the license of https://github.com/Chair-for-Security-Engineering/AGEMA/

The files in the folders

verilog/
	HPC2/
	HPC3/

follow the license of https://github.com/Chair-for-Security-Engineering/HPC3

The remaining verilog .v files in the folder

verilog/

follow the license of https://github.com/Chair-for-Security-Engineering/HADES/

The files in the folder

sage/

fall under the GNU General Public License version 3 (see LICENSE.txt), except the ones in ./sage/lfsr/ which are provided by Philip Koopman (https://users.ece.cmu.edu/~koopman/lfsr/).