Masking Order Constrained Optimization
Side-channel attacks exploit physical information leakage during cryptographic operations. Masking is a fundamental countermeasure that randomizes intermediate values, but it comes at a cost: each masked operation requires random numbers. This article explores how to minimize random number consumption while maintaining a specified masking order.
Problem Definition
Consider a scenario where we need to implement multiple cryptographic operations with different masking orders. Our goal is to minimize the total random number consumption while satisfying security constraints.
Mathematical Formulation:
Minimize: $\sum_{i=1}^{n} r_i \cdot x_i$
Subject to:
- $\sum_{i=1}^{n} s_i \cdot x_i \geq S_{required}$
- $d_i \cdot x_i \geq D_{min}$ for all $i$
- $x_i \geq 0$ and integer
Where:
- $x_i$: number of operations of type $i$
- $r_i$: random numbers consumed per operation of type $i$
- $s_i$: security contribution of operation $i$
- $d_i$: masking order of operation $i$
- $S_{required}$: required total security level
- $D_{min}$: minimum masking order constraint
Complete Python Implementation
1 | import numpy as np |
Source Code Explanation
Problem Setup and Data Structures
The code begins by defining four types of masked cryptographic operations, each with different characteristics:
- Type A (Order 1): Lowest security but cheapest in random numbers
- Type B (Order 2): Moderate security and cost
- Type C (Order 3): Higher security, higher cost
- Type D (Order 4): Highest security, most expensive
Each operation type has three key parameters stored in a dictionary:
random_cost: Number of random numbers consumed per operationsecurity: Security value contributed by each operationmasking_order: The cryptographic masking order (higher = more secure against side-channels)
Mathematical Optimization Formulation
The optimization problem is formulated as an Integer Linear Program (ILP):
Objective function: $\min \sum_{i=1}^{4} r_i \cdot x_i$ where $r_i$ is the random cost and $x_i$ is the number of operations.
Constraints:
- Security constraint: $\sum_{i=1}^{4} s_i \cdot x_i \geq 150$ ensures sufficient total security
- Masking order constraints: $d_i \cdot x_i \geq 2$ for each operation type ensures minimum masking order
LP Relaxation Solution
The code first solves the Linear Programming relaxation using scipy.optimize.linprog. This allows fractional solutions (e.g., 2.5 operations) and provides a lower bound on the optimal cost. The relaxation is useful because:
- It’s computationally fast
- It gives us insight into the structure of the optimal solution
- The fractional solution often guides us toward the integer solution
Integer Linear Programming Solution
The actual solution requires integer values (you can’t execute 2.5 cryptographic operations). The code uses scipy.optimize.milp (Mixed Integer Linear Programming) to find the optimal integer solution. If MILP fails, a brute-force search with reasonable bounds is employed as a fallback.
Constraint Verification
After obtaining the solution, the code verifies:
- Total security meets or exceeds the requirement
- Each operation type satisfies the minimum masking order constraint
- All values are non-negative integers
Efficiency Analysis
The code compares the optimized solution against a naive approach that uses only the highest-order masking operation (Type D). This comparison demonstrates the savings achieved through optimization:
- Naive approach: Use only Type D operations until security requirement is met
- Optimized approach: Mix different operation types to minimize random number consumption
Visualization Suite
The code generates comprehensive visualizations:
- Operation Distribution Bar Chart: Shows how many operations of each type are used
- Random Number Consumption Pie Chart: Breaks down where random numbers are spent
- Cost vs Security Tradeoff Curve: Shows how cost increases with security requirements
- 3D Cost Surface: Visualizes the cost landscape as a function of Type A and Type B operations
- Masking Order Verification: Confirms each operation meets minimum masking order requirements
- Strategy Comparison: Visual comparison of naive vs optimized approaches
Advanced 3D Visualizations
Two sophisticated 3D plots provide deeper insights:
3D Cost Landscape (Type B vs Type C): Shows how the total cost varies as we change the mix of Type B and Type C operations, holding other variables optimal
3D Pareto Frontier: Plots Security, Cost, and Maximum Masking Order simultaneously, showing the tradeoff space and highlighting the optimal solution as a bright star
The 3D visualizations use matplotlib’s Axes3D with custom viewing angles (view_init) for optimal perspective.
Results and Interpretation
======================================================================
SIDE-CHANNEL COUNTERMEASURE OPTIMIZATION
Minimizing Random Number Consumption with Masking Order Constraints
======================================================================
Operation Parameters:
----------------------------------------------------------------------
Operation Random Cost (per op) Security Value Masking Order
Type A (Order 1) 2 10 1
Type B (Order 2) 5 25 2
Type C (Order 3) 9 45 3
Type D (Order 4) 14 70 4
Required Total Security: 150
Minimum Masking Order per Operation: 2
======================================================================
SOLVING LINEAR PROGRAMMING RELAXATION
======================================================================
LP Relaxation Solution (Fractional):
----------------------------------------------------------------------
Type A (Order 1): 6.0000 operations
Type B (Order 2): 1.0000 operations
Type C (Order 3): 0.6667 operations
Type D (Order 4): 0.5000 operations
Minimum Random Numbers (Fractional): 30.0000
Total Security Achieved: 150.0000
======================================================================
SOLVING INTEGER LINEAR PROGRAMMING
======================================================================
Integer Programming Solution:
----------------------------------------------------------------------
Type A (Order 1): 2 operations
Type B (Order 2): 1 operations
Type C (Order 3): 1 operations
Type D (Order 4): 1 operations
Minimum Random Numbers Required: 32
Total Security Achieved: 160
Constraint Verification:
----------------------------------------------------------------------
Security constraint: 160 >= 150 : ✓
Masking order Type A (Order 1): 2 >= 2 : ✓
Masking order Type B (Order 2): 2 >= 2 : ✓
Masking order Type C (Order 3): 3 >= 2 : ✓
Masking order Type D (Order 4): 4 >= 2 : ✓
======================================================================
EFFICIENCY ANALYSIS
======================================================================
Naive Approach (using only highest-order masking):
Operations: 3 × Type D (Order 4)
Random Numbers: 42
Optimization Savings: 10 random numbers (23.8% reduction)
======================================================================
GENERATING VISUALIZATIONS
======================================================================
Visualization saved as 'masking_optimization_analysis.png'
3D analysis saved as 'masking_3d_analysis.png'
ANALYSIS COMPLETE
The optimization successfully demonstrates that by intelligently mixing different masking orders, we can significantly reduce random number consumption while maintaining required security levels. The 3D cost surfaces reveal that the optimization landscape has a clear global minimum, and the constraint-driven nature of the problem creates interesting geometric structures in the feasible solution space.
The Pareto frontier analysis shows that there’s no single “best” solution for all scenarios—the optimal choice depends on the relative importance of security level, random number cost, and maximum masking order requirements. However, for the specific constraints given, the optimization identifies the most efficient configuration.
This approach is directly applicable to real-world cryptographic implementations where random number generation is expensive (e.g., hardware security modules, embedded systems) and side-channel resistance must be balanced against performance constraints.
