differential_cryptanalysis.md - Open-CP/OCP GitHub Wiki

Differential_Cryptanalysis Module

This module provides an automated MILP/SAT modeling framework for performing differential cryptanalysis, integrating a wide range of functionalities and modeling techniques to evaluate various ciphers under multiple attack scenarios.

Supported Functionalities

  • Calculating the minimum number of (related-key) differentially active S-boxes.
  • Searching for the best (related-key) differential trails.
  • Searching for the best truncated (related-key) differential trails.
  • Searching for differential distinguishers for constructing attacks, such as collision and forgery attacks.

Automated Modeling Methods

  • Traditional MILP and SAT-based modeling techniques.
  • Integration of Matsui's branch-and-bound method into both MILP- and SAT-based methods.

diff_attacks(cipher, model_type, goal="search_best_diff_trail", add_constraints=None, model_args=None, solving_args=None)

diff_attacks is an interface that performs automated MILP/SAT-based differential cryptanalysis on block ciphers, supporting flexible model configuration and constraint injection.

Parameters

  • cipher (Cipher) The cipher object to analyze.

  • model_type (str) The automated model framework.

    • 'milp': Mixed Integer Linear Programming
    • 'sat': Boolean Satisfiability

  • goal (str) The specific cryptanalysis goal.

    • 'calculate_min_diff_active_sbox': Calculate the minimum number of differentially active S-boxes
    • 'search_best_diff_trail': Search for the best (lowest-weight/highest-probability) differential trail (default)
    • 'search_best_truncated_diff_trail': Search for the best truncated differential trail

  • add_constraints (list of string) User-specified additional constraints to be added to the model.

  • model_args (dict): Optional advanced arguments for modeling:

    • 'model_version' (str): Custom model version identifier. If not provided or set to 'DEFAULT', uses the default version based on goal.
    • 'input_non_zero' (str): If not provided or set to 'DEFAULT', automatically add input non-zero constraints as required by the goal.
    • 'obj_sat' (int): Starting objective value for SAT model. Defaults to 0 if not provided.
    • 'matsui_constraint' (dict): Arguments for Matsui branch-and-bound constraints (e.g., {"Round": 1, "best_obj": [...]}.)
    • (Any other model-specific options for building models.)

  • solving_args (dict): Optional advanced arguments for solving:

    • 'solver' (str): The solver for solving the model (e.g., "gurobi", "scip").
    • 'show_mode' (int): Level or mode for solution/result visualization.
    • (Any other solver-specific options for solving models.)

Function Workflow

The function workflow is illustrated below (call tree):

diff_attacks
    ├── configure_model_version
    ├── gen_input_non_zero_constraints
    └── attacks.modeling_solving_optimal_solution
            └── [model construction, constraint injection, solver execution, result formatting]

Main Steps:

  1. Configure Model Version: Configure model version if not specified by the user. If "model_version" is not provided or set to "DEFAULT", use the default setting based on the analysis goal.
  2. Add Constraints: Add user-provided and input constraints if enabled, based on the analysis goal.
  3. Build & Solve Model: Calls the modeling_solving_optimal_solution function, passing all options and constraints.
  4. Return Results:
    • solution: Variable assignment of the optimal trail (e.g., differences, activity pattern).
    • obj: Objective value of the optimal solution (e.g., minimal active S-boxes or best differential probability).

Example Usage

import OCP
from attacks.differential_cryptanalysis import diff_attacks
cipher = OCP.PRESENT_PERMUTATION(r=2)

sol, obj = diff_attacks(cipher, "milp") # Search for the best differential trail by using milp

sol, obj = diff_attacks(cipher, "sat") # Search for the best differential trail by using sat

sol, obj = diff_attacks(cipher, "milp", goal="calculate_min_diff_active_sbox") # Calculate the minimum number of active S-boxes by using milp

sol, obj = diff_attacks(cipher, "sat", goal="calculate_min_diff_active_sbox") # Calculate the minimum number of active S-boxes by using sat

sol, obj = diff_attacks(cipher, "milp", model_args={"matsui_constraint": {"Round": r, "best_obj": [2], "matsui_milp_cons_type": "all"}}) # Search for the best differential trail by using milp, incorporating with matsui's branch-and-bound strategy

sol, obj = diff_attacks(cipher, "sat", model_args={"obj_sat": 2, "matsui_constraint": {"Round": r, "best_obj": [2], "GroupConstraintChoice": 1, "GroupNumForChoice":1}}) # Search for the best differential trail by using sat, incorporating with matsui's branch-and-bound strategy

sol, obj = diff_attacks(cipher, "milp", goal="calculate_min_diff_active_sbox", model_args={"matsui_constraint": {"Round": r, "best_obj": [1], "matsui_milp_cons_type": "all"}}) # Calculate the minimum number of active S-boxes by using milp, incorporating with matsui's branch-and-bound strategy

sol, obj = diff_attacks(cipher, "sat", goal="calculate_min_diff_active_sbox", model_args={"obj_sat": 1, "matsui_constraint": {"Round": r, "best_obj": [1], "GroupConstraintChoice": 1, "GroupNumForChoice":1}}, solving_args={"solver": "Cadical103", "show_mode": 2}) # Calculate the minimum number of active S-boxes by using milp, incorporating with matsui's branch-and-bound strategy

Functionalities

The implemented functionalities are summarized in the table below:

Cipher NumAS BestDT BestTDT Dist.
SPECK – MILP-basic MILP-matsui SAT-basic SAT-matsui – -
SIMON – MILP-basic MILP-matsui SAT-basic SAT-matsui – -
PRESENT MILP-basic MILP-matsui SAT-basic SAT-matsui MILP-basic MILP-matsui SAT-basic SAT-matsui – -
GIFT MILP-basic MILP-matsui SAT-basic SAT-matsui MILP-basic MILP-matsui – -
AES – – MILP-basic –
SKINNY
ASCON MILP-basic MILP-matsui MILP-basic MILP-matsui – -
ROCCA_AD – – – MILP (forgery attacks)
SIPHASH

Legend

  • NumAS: Search for the minimum number of (related-key) differentially active S-boxes
  • BestDT: Search for the best (related-key) differential trails
  • BestTDT: Search for the best truncated (related-key) differential trails
  • Dist.: Search for distinguishers for constructing attacks