Movatterモバイル変換

[0]ホーム
URL:

Skip to content

Navigation Menu

Search code, repositories, users, issues, pull requests...

Provide feedback

We read every piece of feedback, and take your input very seriously.

Saved searches

Use saved searches to filter your results more quickly

 Sign up

Revisiting Differential-Linear Attacks via a Boomerang Perspective

License

NotificationsYou must be signed in to change notification settings

hadipourh/DL

Repository files navigation

This repository contains the source code for the tools utilized in our paper accepted toCRYPTO 2024 titled as:Revisiting Differential-Linear Attacks via a Boomerang Perspective with Application to AES, Ascon, CLEFIA, SKINNY, PRESENT, KNOT, TWINE, WARP, LBlock, Simeck, and SERPENT

Table of Contents

Requirements

Our tool requires the following software:

  • MiniZinc to compile and solve our CP models.
  • latexmk to build the.tex file and generate the shapes of our attacks (can be replaced by just calling lualatex directly).
  • Or-Toolsto solve our CP/MILP models.
  • Gurobi to solve our CP/MILP models.
  • SageMath to run our analytical formulas.

Our tool for identifying distinguishers relies exclusively on MiniZinc, Or-Tools, and Gurobi. It is worth noting that SageMath is necessary only for executing the analytical estimations.

Installation

Method 1

In this method, we provide a Docker file that contains all the necessary software to run our tool (except for Gurobi).To build the Docker image, navigate to thedocker directory and run the following command:

sudo docker build -f Dockerfile -t dl.

Note that Gurboi is not included in the Docker image, as downloading it requires an account on the Gurobi website, and it also requires a license. To install Gurobi, please follow the instructions providedhere.After building the Docker image, you can run the Docker container using the following command:

docker run --rm -it dl

Method 2

In this method, we provide a script that installs all the necessary software to run our tool (except for Gurobi).

Several Constraint Programming (CP) solvers come pre-packaged with MiniZinc, requiring no additional installation steps.We use Or-Tools as one of the CP solvers.Fortunately,OR Tools CP-SAT is bundled with MiniZinc after version 2.8.0.Thus, by installing the latest version of MiniZinc, one can useOR Tools CP-SAT without any further installation.Additionally, we need the Python package namedminizinc to work with MiniZinc in Python.To install MiniZinc and required Python packages in Ubuntu, one can use the following commands:

apt updateapt upgradeapt install python3-fullapt install gitapt install wgetcd /home LATEST_MINIZINC_VERSION=$(curl -s https://api.github.com/repos/MiniZinc/MiniZincIDE/releases/latest| grep -oP'"tag_name": "\K(.*)(?=")')wget"https://github.com/MiniZinc/MiniZincIDE/releases/download/$LATEST_MINIZINC_VERSION/MiniZincIDE-$LATEST_MINIZINC_VERSION-bundle-linux-x86_64.tgz"tar -xvzf MiniZincIDE-$LATEST_MINIZINC_VERSION-bundle-linux-x86_64.tgzmv MiniZincIDE-$LATEST_MINIZINC_VERSION-bundle-linux-x86_64 minizincrm MiniZincIDE-$LATEST_MINIZINC_VERSION-bundle-linux-x86_64.tgzln -s  /home/minizinc/bin/minizinc /usr/local/bin/minizincapt install python3-pippython3 -m pip install minizincpython3 -m pip install sagemath

Sometimes, we use Gurobi to solve our CP models.The Python interface of Gurobi, namelygurobipy, can be installed by runningpython3 -m pip install gurobipy.To install Gurobi, and its academic license, one can follow the instructions providedhere.

Structure of Our Tool

We have developed our tools following a modular approach.
One module creates CP/MILP models, another calls the solver and processes results, and a third visualizes outcomes.However, the core idea is to first generate a CP/MILP model for each application, then solve it using a CP/MILP solver.We have employed two different approaches for model creation:

  • When employing Or-Tools as the solver, we created the CP model in.mzn format and utilized the Python interface of Or-Tools to solve and process the results.
  • When employing Gurobi as the solver, we utilize the Python interface to first create the MILP model in.lp format. Subsequently, we employ the Python interface of Gurobi to solve and process the results.

The primary distinction lies in the fact that for.mzn files, we do not employ Python to create the CP model; instead, we directly write them in the MiniZinc language.

Usage

Utilizing our tool is straightforward.Simply specify the number of attacked rounds or the length of the distinguisher and select the solver.Our tool will then identify the distinguisher and visualize its shape.

For a quick guide on each application, run the following command:

python3<application_name>.py --help

We give a few examples, but the same applies to other applications.

Example 1: TWINE

To discover distinguishers for TWINE, begin by navigating intotwine directory.Let us assume we aim to find a distinguisher for 16 rounds of TWINE, with the lengths of the upper, middle, and lower parts of the distinguisher set to(RU, RM, RL) = (3, 10, 3).We can then employ the following command to identify the distinguisher:

python3 attack.py -RU 3 -RM 10 -RL 3

The subsequent field illustrates a portion of the terminal output from the preceding command:

Academic license - for non-commercial use only - expires 2024-06-10Read LP format model from file warp_3_10_3.lpReading time = 0.00 seconds: 1074 rows, 528 columns, 2560 nonzerosGurobi Optimizer version 10.0.1 build v10.0.1rc0 (linux64)CPU model: 11th Gen Intel(R) Core(TM) i7-1165G7 @ 2.80GHz, instruction set [SSE2|AVX|AVX2|AVX512]Thread count: 4 physical cores, 8 logical processors, using up to 8 threadsOptimize a model with 1074 rows, 528 columns and 2560 nonzerosModel fingerprint: 0x4005271dVariable types: 0 continuous, 528 integer (528 binary)Coefficient statistics:  Matrix range     [1e+00, 1e+00]  Objective range  [2e+00, 4e+00]  Bounds range     [1e+00, 1e+00]  RHS range        [1e+00, 1e+00]Found heuristic solution: objective 352.0000000Presolve removed 625 rows and 328 columnsPresolve time: 0.01sPresolved: 449 rows, 200 columns, 1152 nonzerosVariable types: 0 continuous, 200 integer (200 binary)Found heuristic solution: objective 256.0000000Root relaxation: objective 9.872727e+00, 191 iterations, 0.00 seconds (0.00 work units)    Nodes    |    Current Node    |     Objective Bounds      |     Work Expl Unexpl |  Obj  Depth IntInf | Incumbent    BestBd   Gap | It/Node Time     0     0    9.87273    0  151  256.00000    9.87273  96.1%     -    0sH    0     0                      82.0000000    9.87273  88.0%     -    0sH    0     0                      74.0000000    9.87273  86.7%     -    0sH    0     0                      52.0000000    9.87273  81.0%     -    0s     0     0   25.44594    0  192   52.00000   25.44594  51.1%     -    0sH    0     0                      48.0000000   32.84932  31.6%     -    0s     0     0   32.84932    0  184   48.00000   32.84932  31.6%     -    0s     0     0   32.84932    0  184   48.00000   32.84932  31.6%     -    0s     0     2   32.84932    0  184   48.00000   32.84932  31.6%     -    0sCutting planes:  Gomory: 5  Implied bound: 43  Clique: 38  Zero half: 5Explored 9 nodes (1379 simplex iterations) in 0.12 seconds (0.12 work units)Thread count was 8 (of 8 available processors)Solution count 6: 48 52 74 ... 352Optimal solution found (tolerance 1.00e-04)Best objective 4.800000000000e+01, best bound 4.800000000000e+01, gap 0.0000%Number of active S-boxes: 48.0Upper Truncated Trail:00001100000001110000000100110000000000001100000000000000000001000000000000100000001000000100000001001010000000001001000110001000100011101010010110110111111011101111111011111111111111111111111111111111111111111111111111111111++++++++++++++++++++++++++++++++################################Lower Truncated Trail:11111111111111111111111111111111111111111111111111111110111111111111111000111011101111000000101100001100000010110000000000001011000000000000001100000000000000100000000000010000001000000100000001000010000001001001010000100001################################################################Middle Part:0*0*0*0*0*0*0*0*0*0*0*0*0*1*0*0*0*1*0*0*0*0*0*0*0*0*1*0*0*0*0*0*1*0*0*0*0*0*0*0*0*0*1*0*0*0*0*0*0*0*0*0*0*0*0*1*0*0*0*0*0*0*0*1*0*0*0*0*0*0*0*1*0*0*0*0*0*0*0*0*Number of common active S-boxes: 8Read LP format model from file twine_nr_3.lpReading time = 0.00 seconds: 2365 rows, 424 columns, 11332 nonzerosThe probability of the best differential characteristic: 2^-(8.0)Differential trail:Roundsx                 pr     --------------------------------00000a70000000798  -4                10000000a00790000  -2                200000000a7000000  -2                30000000000000a00  none              Weight: -8.00Time used: 0.01Read LP format model from file twine_nr_3.lpReading time = 0.00 seconds: 2385 rows, 424 columns, 11352 nonzerosSet parameter TimeLimit to value 1200Set parameter PoolSearchMode to value 2Set parameter PoolSolutions to value 1Current weight: 8.0Number of trails: 1Current Probability: 2^(-8.0)Time used = 0.0023 secondsRead LP format model from file twine_nr_3.lpReading time = 0.00 seconds: 2221 rows, 400 columns, 11452 nonzerosThe correlation of the best linear characteristic: 2^-(8.0)Linear trail:Roundsx                 pr     --------------------------------000000000000a0000  -2                100a0000001000000  -2                20a00001000000d00  -4                3a001010000d00008  none              Weight: -8.00Time used: 0.02Read LP format model from file twine_nr_3.lpReading time = 0.00 seconds: 2241 rows, 400 columns, 11472 nonzerosSet parameter TimeLimit to value 1200Set parameter PoolSearchMode to value 2Set parameter PoolSolutions to value 1Current weight: 8.0Number of trails: 1Current Probability: 2^(-8.0)Time used = 0.0029 seconds#######################################################Summary of the results:A differential trail for EU:Roundsx                 pr     --------------------------------00000a70000000798  -4                10000000a00790000  -2                200000000a7000000  -2                30000000000000a00  none              Weight: -8.00-------------------------------------------------------Sandwich 10 rounds in the middle with 8 active S-boxes-------------------------------------------------------A linear trail for EL:Roundsx                 pr     --------------------------------000000000000a0000  -2                100a0000001000000  -2                20a00001000000d00  -4                3a001010000d00008  none              Weight: -8.00#######################################################differential effect of the upper trail: 2^(-8.00)squared correlation of the lower trail: 2^(-8.00)#######################################################Total correlation = p*r*q^2 = 2^(-8.00) x r x 2^(-8.00)2^(-28.00) <= Total correlation <= 2^(-20.00)To compute the accurate value of total probability, r should be evaluated experimentally or using the DLCT frameworkNumber of attacked rounds: 16Configuration: RU=3, RM=10, RL=3, RMU=0, RML=0, WU=4, WM=2, WL=4Elapsed time: 0.20 seconds

Executing this command typically requires less than a second on a standard laptop (11th Gen Intel(R) Core(TM) i7-1165G7 @ 2.80GHz with 16GB RAM).It is noteworthy to compare the execution time of this tool with that of identifying boomerang distinguishers for 16 rounds of TWINE in[4] that may take several hours or several days.

Running the above command also generatesoutput.tex file that contains the shape of the distinguisher in the LaTeX format.To compile theoutput.tex file, you can use the following command:

latexmk -pdf output.tex

The shape of the distinguisher will be stored in theoutput.pdf file, similar to the following:

TWINE

Example 2: WARP

To discover a 22-round distinguisher for WARP, navigate to thewarp directory, and run the following command:

python3 attack.py -RU 6 -RM 10 -RL 6

The subsequent field represents part of the terminal output of the above command:

Academic license - for non-commercial use only - expires 2024-06-10Read LP format model from file warp_6_10_6.lpReading time = 0.00 seconds: 2530 rows, 1248 columns, 6176 nonzerosSet parameter Seed to value 80693Gurobi Optimizer version 10.0.1 build v10.0.1rc0 (linux64)CPU model: 11th Gen Intel(R) Core(TM) i7-1165G7 @ 2.80GHz, instruction set [SSE2|AVX|AVX2|AVX512]Thread count: 4 physical cores, 8 logical processors, using up to 8 threadsOptimize a model with 2530 rows, 1248 columns and 6176 nonzerosModel fingerprint: 0xe53bd95dVariable types: 0 continuous, 1248 integer (1248 binary)Coefficient statistics:  Matrix range     [1e+00, 1e+00]  Objective range  [2e+00, 4e+00]  Bounds range     [1e+00, 1e+00]  RHS range        [1e+00, 1e+00]Found heuristic solution: objective 1088.0000000Presolve removed 1121 rows and 648 columnsPresolve time: 0.02sPresolved: 1409 rows, 600 columns, 3728 nonzerosVariable types: 0 continuous, 600 integer (600 binary)Found heuristic solution: objective 800.0000000Root relaxation: objective 7.916085e+00, 619 iterations, 0.01 seconds (0.01 work units)    Nodes    |    Current Node    |     Objective Bounds      |     Work Expl Unexpl |  Obj  Depth IntInf | Incumbent    BestBd   Gap | It/Node Time     0     0    7.91609    0  307  800.00000    7.91609  99.0%     -    0sH    0     0                     186.0000000    7.91609  95.7%     -    0s     0     0   14.90067    0  393  186.00000   14.90067  92.0%     -    0s     0     0   15.18697    0  382  186.00000   15.18697  91.8%     -    0s...Optimal solution found (tolerance 1.00e-04)Best objective 1.080000000000e+02, best bound 1.080000000000e+02, gap 0.0000%Number of active S-boxes: 108.0Upper Truncated Trail:0001001111000000110000110111010000000100000000110011110000010000000000000000110011000001000000000000000000000001000000001100000000000000001100000000000000000000000100000000000000000000000000000000000000000010000000000000000000000000001000000000000100000000100100000000000000000000100000000000001000010010001000000000000110000000101001000000010100100010101110110000000010010000101110010100001011011011101111100010011110101111101001011101111111111010111111111111101111111110101111111111111111111111111111111111111111111111111111111111111111111111++++++++++++++++++++++++++++++++################################Lower Truncated Trail:1111111111111111111111111111111111111111111111111111111111111111101111111110111111111011111111110011110011111110111010111111001110111100000011111111001111100000000010000011101100110011100000111100000000110000000000001110001010000011000000000011000000000000000000001000000000000000000000110000000000000000000000000011000000000000000000001000000000000000000000000000000100000000000000000000000000100000000000010000000000010100000000000000000010000000010000000001101000000000000001001001001001000000000010010100000100100101000100100110010010110101################################################################Middle Part:0*0*0*0*0*0*0*1*0*0*0*0*0*0*0*0*0*0*0*0*0*1*0*0*0*0*0*0*0*0*0*0*0*0*0*0*0*0*0*0*0*0*0*0*1*0*0*0*0*0*0*0*0*0*0*0*0*0*0*0*0*0*0*0*0*0*0*0*0*0*0*0*0*0*0*0*0*0*0*0*0*0*0*0*0*0*0*0*0*0*0*0*0*0*0*0*0*0*0*0*0*0*0*0*0*0*0*0*0*0*0*0*0*0*0*1*0*0*0*0*0*0*0*0*0*0*0*0*0*0*0*0*0*0*0*0*0*0*0*0*0*0*0*1*0*0*0*0*0*0*0*0*0*0*0*0*0*1*0*0*Number of common active S-boxes: 6Read LP format model from file warp_nr_6.lpReading time = 0.02 seconds: 7597 rows, 1568 columns, 32108 nonzerosThe probability of the best differential characteristic: 2^-(24.0)Differential trail:Time used: 0.07Read LP format model from file warp_nr_6.lpReading time = 0.02 seconds: 7649 rows, 1568 columns, 32160 nonzerosSet parameter TimeLimit to value 1200Set parameter PoolSearchMode to value 2Set parameter PoolSolutions to value 1...#######################################################Summary of the results:A differential trail for EU:Roundsx                                 pr     ------------------------------------------------000040024290000002100002104210400  -10                               100000200000000420042420000020000  -6                                200000000000024002400000400000000  -4                                300000000000000020000000042000000  -2                                400000000002400000000000000000000  -2                                500020000000000000000000000000000  -0                                600000000000000200000000000000000  none                              Weight: -24.00-------------------------------------------------------Sandwich 10 rounds in the middle with 6 active S-boxes-------------------------------------------------------A linear trail for EL:Roundsx                                 correlation----------------------------------------------------00000000000000000b000000000000000  -0                                1000000000000000b0000000000000000  -2                                20000000000b000000000000700000000  -2                                3000b0600000000000000000070000000  -4                                40c000000000760b00000000000000700  -6                                5700600c0060000000000700b06000006  -10                               60060050c000c006007600c00b06c0c07  none                              Weight: -24.00#######################################################differential effect of the upper trail: 2^(-24.00)squared correlation of the lower trail: 2^(-24.00)#######################################################Total correlation = p*r*q^2 = 2^(-24.00) x r x 2^(-24.00)2^(-57.00) <= Total correlation <= 2^(-51.00)To compute the accurate value of total probability, r should be evaluated experimentally or using the DLCT frameworkNumber of attacked rounds: 22Configuration: RU=6, RM=10, RL=6, RMU=0, RML=0, WU=4, WM=2, WL=4Elapsed time: 39.08 seconds

Running this command takes 39.08 seconds on a standard laptop (11th Gen Intel(R) Core(TM) i7-1165G7 @ 2.80GHz with 16GB RAM).It is worth comparing with the running time of finding boomerang distinguishers for 22 rounds of WARP in[4] that may take several hours or several days.

Running the above command also generatesoutput.tex file that contains the shape of the distinguisher in the LaTeX format.You can compile theoutput.tex file using the following command:latexmk -pdf output.tex.The shape of the distinguisher will be saved in theoutput.pdf file that is something like the following.

WARP

Example 3: AES

To find a 5-round distinguisher for AES, navigate into theaes directory, and run the following command:

python3 attack.py -RU 1 -RM 3 -RL 1

Running this command takes about 2 minutes on a standard laptop (11th Gen Intel(R) Core(TM) i7-1165G7 @ 2.80GHz with 16GB RAM). The following shape (generated bylatexmk -pdf ./output.tex) shows the discovered distinguisher by the tool.

AES

Example 4: Ascon

To find a 5-round distinguisher for Ascon, navigate into theascon directory, and run the following command:

python3 attack.py -RU 1 -RM 3 -RL 1

The following field represents the terminal output of the above command:

Searching a distinguisher for 5 rounds of Ascon ...Time used to find a distinguisher: 44.00 secondsSolver status: OPTIMAL_SOLUTIONAttack summary:Setting: RU: 1, RM: 3, RL: 1, RMU: 0, RML: 0##################################################input diff.: input_diff.x[0] = 0x0080000000000000;input_diff.x[1] = 0x0000000000000000;input_diff.x[2] = 0x0000000000000000;input_diff.x[3] = 0x0080000000000000;input_diff.x[4] = 0x0080000000000000;##################################################input diff. middle: input_diff.x[0] = 0x0000000000000000;input_diff.x[1] = 0x0000000000000000;input_diff.x[2] = 0x00c2000000000000;input_diff.x[3] = 0x0000000000000000;input_diff.x[4] = 0x0000000000000000;##################################################output mask middle: output_mask.x[0] = 0x0000000000000000;output_mask.x[1] = 0x0000000000000000;output_mask.x[2] = 0x0000000000000002;output_mask.x[3] = 0x0000000000000000;output_mask.x[4] = 0x0000000000000000;##################################################output mask: output_mask.x[0] = 0x24496da496ddb493;output_mask.x[1] = 0x65d37110f752d23e;output_mask.x[2] = 0x0000000000000000;output_mask.x[3] = 0x0000000000000000;output_mask.x[4] = 0x614be631e6e25c7f;##################################################PU:  2CM:  0Q^2: 2Number of effective S-boxes in the middle:       6Number of effective bit-positions in the middle: 0##################################################Upper trail:Round 0:x[0] = 0000000010000000000000000000000000000000000000000000000000000000x[1] = 0000000000000000000000000000000000000000000000000000000000000000x[2] = 0000000000000000000000000000000000000000000000000000000000000000x[3] = 0000000010000000000000000000000000000000000000000000000000000000x[4] = 0000000010000000000000000000000000000000000000000000000000000000--------------------------------------------------y[0] = 0000000000000000000000000000000000000000000000000000000000000000y[1] = 0000000000000000000000000000000000000000000000000000000000000000y[2] = 0000000010000000000000000000000000000000000000000000000000000000y[3] = 0000000000000000000000000000000000000000000000000000000000000000y[4] = 0000000000000000000000000000000000000000000000000000000000000000##################################################Round 1:x[0] = 0000000000000000000000000000000000000000000000000000000000000000x[1] = 0000000000000000000000000000000000000000000000000000000000000000x[2] = 0000000011000010000000000000000000000000000000000000000000000000x[3] = 0000000000000000000000000000000000000000000000000000000000000000x[4] = 0000000000000000000000000000000000000000000000000000000000000000--------------------------------------------------y[0] = 00000000**0000*0000000000000000000000000000000000000000000000000y[1] = 00000000**0000*0000000000000000000000000000000000000000000000000y[2] = 0000000011000010000000000000000000000000000000000000000000000000y[3] = 0000000011000010000000000000000000000000000000000000000000000000y[4] = 0000000000000000000000000000000000000000000000000000000000000000##################################################Round 2:x[0] = 00000000**0000*000000000000**0000*00**0000*000000000000000000000x[1] = 00000**0**0*00*00000000000000000000000000000000**0000*0000000000x[2] = 0000000010100000000010000000000000000000000000000000000000000000x[3] = 0000000011000010001100001110000100000000000000000000000000000000x[4] = 0000000000000000000000000000000000000000000000000000000000000000--------------------------------------------------y[0] = 00000**0****00*00011*000111**0010*00**0000*0000**0000*0000000000y[1] = 00000**0****00*000***000*****00*0*00**0000*0000**0000*0000000000y[2] = 00000**0**1*00*000**1000***0000*000000000000000**0000*0000000000y[3] = 00000**0**1*00*000**1000*****00*0*00**0000*0000**0000*0000000000y[4] = 00000**0**0*00*000110000111**0010*00**0000*0000**0000*0000000000##################################################Round 3:x[0] = ****0**0*****0*00*11*000**1****10**0****00*111***010**1**0010*00x[1] = ****0********0***************0**0**0**0*00*0**0****00*000***000*x[2] = 00000********0**1****100****00***0000*000000000***000**0000*0000x[3] = **000**0**1*00***0**0*********1*0******00********0*0***00***000*x[4] = 0111***0*********0**0*00**0**0*01*****10*0***0*****0****0001*000--------------------------------------------------y[0] = ***************************************************0**********0*y[1] = ***************************************************0**********0*y[2] = ***************************************************0****0****00*y[3] = ***************************************************0**********0*y[4] = ***************************************************0**********0*##################################################Round 4:x[0] = ****************************************************************x[1] = ****************************************************************x[2] = **************************************************************0*x[3] = ****************************************************************x[4] = ****************************************************************--------------------------------------------------##################################################Lower trail:Round 0:x[0] = ***************************************************************1x[1] = ****************************************************************x[2] = ********00****0****0********************************************x[3] = *******************************1********************************x[4] = ****************************************************************--------------------------------------------------y[0] = 1**11000000*000****0**1******0*1******0*10*****00*0**1****10***0y[1] = **0*****00*1**0****0*******000000000000**0*0******1**1******1**1y[2] = **000000000*0000**000***000000000*0000***00****001****1**0******y[3] = **0*****00****0*0*00****000***00*********************0***00****0y[4] = 110***00****0***111***1010000000*0000***10***************111***0##################################################Round 1:x[0] = 110000000000000*0100**11000000000000000*0000***00*0**0***0010**0x[1] = **0000000000000*0*00****000000000000000*0000***00*1**0***00*1**0x[2] = **000000000000000*0000**000000000000000*0000***0001**000*00*1**0x[3] = **0000000000000*0*00****000000000000000*0000***00****0***00****0x[4] = 110000000000000*0100**11000000000000000*0000***00****0***001***0--------------------------------------------------y[0] = 0000000000000000000000000000000000000000000000000000000000000000y[1] = 1100000000000000010000110000000000000000000000000000000010010110y[2] = 0000000000000000000000000000000000000000000000000010000000001010y[3] = 000000000000000000000000000000000000000*0000***0000**000*0000**0y[4] = 000000000000000*0000**000000000000000000000000000*0000***0000**0##################################################Round 2:x[0] = 0000000000000000000000000000000000000000000000000000000000000000x[1] = 0000000000000000000000000000000000000000000000000000000010000110x[2] = 0000000000000000000000000000000000000000000000000000000010000110x[3] = 00000000000000000000000000000000000000000000000000000000*0000**0x[4] = 00000000000000000000000000000000000000000000000000000000*0000**0--------------------------------------------------y[0] = 0000000000000000000000000000000000000000000000000000000000000000y[1] = 0000000000000000000000000000000000000000000000000000000000000000y[2] = 0000000000000000000000000000000000000000000000000000000010000110y[3] = 0000000000000000000000000000000000000000000000000000000000000000y[4] = 0000000000000000000000000000000000000000000000000000000000000000##################################################Round 3:x[0] = 0000000000000000000000000000000000000000000000000000000000000000x[1] = 0000000000000000000000000000000000000000000000000000000000000000x[2] = 0000000000000000000000000000000000000000000000000000000000000010x[3] = 0000000000000000000000000000000000000000000000000000000000000000x[4] = 0000000000000000000000000000000000000000000000000000000000000000--------------------------------------------------y[0] = 0000000000000000000000000000000000000000000000000000000000000010y[1] = 0000000000000000000000000000000000000000000000000000000000000010y[2] = 0000000000000000000000000000000000000000000000000000000000000000y[3] = 0000000000000000000000000000000000000000000000000000000000000000y[4] = 0000000000000000000000000000000000000000000000000000000000000010##################################################Round 4:x[0] = 0010010001001001011011011010010010010110110111011011010010010011x[1] = 0110010111010011011100010001000011110111010100101101001000111110x[2] = 0000000000000000000000000000000000000000000000000000000000000000x[3] = 0000000000000000000000000000000000000000000000000000000000000000x[4] = 0110000101001011111001100011000111100110111000100101110001111111--------------------------------------------------##################################################-Log2(P)              ~= 02-Log2(r)              ~= 00-Log2(Q^2)            ~= 02

Running this command takes 44 seconds on a standard laptop (11th Gen Intel(R) Core(TM) i7-1165G7 @ 2.80GHz with 16GB RAM).Running the above command also generatesoutput.tex file that contains the shape of the distinguisher in the LaTeX format. The following shape (generated bylatexmk -pdf ./output.tex) shows the discovered distinguisher by the tool.

Ascon

Analythical Estimations

Our generalized DLCT framework provides an analytical estimation for the correlation of the distinguishers (see Section 3 of our paper). Our generalized DLCT framework is a projection of the generalized BCT framework into the differential-linear setting. The generalized BCT framework has been shown to be an efficient tool for estimating the probability of boomerang distinguishers. Therefore, our generalized DLCT framework is also an efficient tool for estimating the correlation of the differential-linear distinguishers.We believe the generalized DLCT framework is even more efficient than the generalized BCT framework since we have proven in our paper that some of the generalized DLCT tables reduce to DDT and LAT tables, albeit with variable signs, whereas this is not the case for the generalized BCT tables.We note that, thanks to the link we provided between the the differential-linear and the boomerang distinguishers, one can simply adapt the tool in[1].

Here, we offer several examples for analytically estimating the correlation of distinguishers. These examples vary in difficulty, ranging from basic to medium and complex formulations. This diversity showcases that our generalized DLCT framework extends beyond basic scenarios.Additionally, our paper contains several other examples for AES, WARP, LBlock, and LBlock-s.For further analytical estimations, please refer to Sections 4.2 and 4.3 of our paper.

Example 1: 8 Rounds of TWINE (Basic)

The following figure visualizes a 13-round distinguisher for TWINE composed of 3 + 8 + 2 rounds.

twine_13r_v0

We have implemented our analytical estimation for the correlation of the 8-round middle part of our TWINE distinguishers in Python.To run this implementation, navigate into thetwine/formulation directory, and run the following command:

python3 twine-13r.py --version 0

Or equivalently, you can run the following command:

sage twine-13r.py --version 0

This command essentially uses our generalized DLCT tables to create the super DLCT table for 8 rounds of TWINE.

Example 2: 3 Rounds of AES (Medium)

The following figure visualizes the 3-round middle part of our AES distinguishers.

AES

We have implemented our analytical estimation for the correlation of the 3-round middle part of our AES distinguishers in Python.To run this implementation, navigate into theaes/formulation directory, and run the following command:

python3 aes3r.py

Using our analytical formula, this command essentially geneartes the super DLCT table for 3 rounds of AES. It also generates an SVG image that visualizes the super DLCT table as shown below.

AES

Example 3: 9 Rounds of TWINE (Medium)

The following figure visualizes a 13-round distinguisher for TWINE composed of 2 + 9 + 2 rounds.

twine_13r_v1

We have implemented our analytical estimation for the correlation of the 9-round middle part of our TWINE distinguishers in Python.To run this implementation, navigate into thetwine/formulation directory, and run the following command:

python3 twine-13r.py --version 1

Or equivalently, you can run the following command:

sage twine-13r.py --version 1

This command essentially uses our generalized DLCT tables to create the super DLCT table for 9 rounds of TWINE.

Example 4: 10 Rounds of TWINE (Complex)

The following figure visualizes a 13-round distinguisher for TWINE composed of 1 + 10 + 2 rounds.

twine_13r_v2

As can be seen, this examples involves 8 commonly active S-boxes in the middle.We have implemented our analytical estimation for the correlation of the 10-round middle part of our TWINE distinguishers in Python.To run this implementation, navigate into thetwine/formulation directory, and run the following command:

python3 twine-13r.py --version 2

Or equivalently, you can run the following command:

sage twine-13r.py --version 2

This command essentially uses our generalized DLCT tables to create the super DLCT table for 10 rounds of TWINE.

Experimental Verification

For each application in our paper, we have provided relatively efficientC/C++ code to verify or compute the correlation of the distinguishers. The required code is located in theverifications subfolder within each application's folder.Below, we demonstrate the usage for TWINE and WARP, but the same applies to other applications.

Example 1: AES

For AES we use theAES-NI instructions to achieve a high performance.Assume that we want to verify the correlation of the 3 middle rounds of our AES distinguisher. To do so, navigate into theaes/verifications directory and open thedifflin.c file, and set lines 148-155 as follows.

    int DEG1 = 0;    int DEG2 = 25;    uint64_t N1 = 1ULL<<DEG1;    uint64_t N2 = 1ULL << DEG2;    int NUMBER_OF_EXPERIMENTS = 10;   // Number of independent experiments    int NUMBER_OF_ROUNDS = 3;   // Number of rounds    char DP_STR[] = "0000000000000000000000b400000000";    char LC_STR[] = "0000000032ab66980000000000000000";

We first generate the master key randomly and fix it.Then we perform$2^{25}$ differential-linear queries with$2^{25}$ random plaintexts (under the same key) and compute the correlation of the masked output difference.We repeat the above process for 10 random master keys and compute the average correlation. We have provided a Makefile to compile the code. To compile the code, run the following command:

make

To run the code, execute the following command:

./difflin 0

The output will resemble something like the following:

[+] PRNG initialized to 0xFE09EBBFAES works correctly!average speed over 4194304 times of encryption: 6.96 (Gigabytes/Second)Difference = -173942Execution time: 7.27Correlation = 2^(-7.5918)####################################Difference = -167780Execution time: 7.29Correlation = 2^(-7.6438)####################################Difference = -158666Execution time: 8.76Correlation = 2^(-7.7244)####################################Difference = -171366Execution time: 9.16Correlation = 2^(-7.6133)####################################Difference = -157082Execution time: 9.11Correlation = 2^(-7.7388)####################################Difference = -165694Execution time: 9.20Correlation = 2^(-7.6618)####################################Difference = -168732Execution time: 9.05Correlation = 2^(-7.6356)####################################Difference = -161012Execution time: 9.42Correlation = 2^(-7.7032)####################################Difference = -158592Execution time: 10.11Correlation = 2^(-7.7250)####################################Difference = -159302Execution time: 8.98Correlation = 2^(-7.7186)####################################Average correlation = 2^(-7.6748)####################################

As observed, the output closely aligns with the analytical estimation.

Example 2: TWINE

Suppose we aim to verify the correlation of our 9-round distinguisher for TWINE.To accomplish this, navigate to thetwine/verifications directory and open thedifflin.h file, and set lines 57-63 as follows.

const int DEG1 = 0;              // Number of bunches per thread: N2 = 2^(DEG1)const int DEG2 = 25;             // Number of queries per bunch:  N3 = 2^(DEG2)int NUMBER_OF_EXPERIMENTS = 3;   // Number of independent experimentsint NUMBER_OF_ROUNDS = 9;        // Number of roundschar DP_STR[] ="0000000000000004";char LC_STR[] ="0005000000000000";

Next, compile the code using the following command:

make

To run the code, execute the following command:

./difflin 0

The output will resemble something like the following:

[+] PRNG initialized to 0x9BA17536Check decryption: true#Rounds: 9 rounds#Total Queries = (#Parallel threads) * (#Bunches per thread) * (#Queries per bunch) = 1 * 1 * 33554432 = 2^(25.000000)#Queries per thread = (#Bunches per thread) * (#Queries per bunch) = 1 * 33554432 = 2^(25.000000)PID: 0   Bunch Number: 0/1time on clock: 22.8919time on wall: 22.8931sum = 598876.0000002^(-5.808102)#####################################Rounds: 9 rounds#Total Queries = (#Parallel threads) * (#Bunches per thread) * (#Queries per bunch) = 1 * 1 * 33554432 = 2^(25.000000)#Queries per thread = (#Bunches per thread) * (#Queries per bunch) = 1 * 33554432 = 2^(25.000000)PID: 0   Bunch Number: 0/1time on clock: 20.8765time on wall: 20.8771sum = 597638.0000002^(-5.811088)#####################################Rounds: 9 rounds#Total Queries = (#Parallel threads) * (#Bunches per thread) * (#Queries per bunch) = 1 * 1 * 33554432 = 2^(25.000000)#Queries per thread = (#Bunches per thread) * (#Queries per bunch) = 1 * 33554432 = 2^(25.000000)PID: 0   Bunch Number: 0/1time on clock: 19.7801time on wall: 19.7805sum = 585822.0000002^(-5.839897)#####################################Rounds: 9 rounds#Total Queries = (#Parallel threads) * (#Bunches per thread) * (#Queries per bunch) = 1 * 1 * 33554432 = 2^(25.000000)#Queries per thread = (#Bunches per thread) * (#Queries per bunch) = 1 * 33554432 = 2^(25.000000)PID: 0   Bunch Number: 0/1time on clock: 20.6513time on wall: 20.6519sum = 587792.0000002^(-5.835054)#####################################Rounds: 9 rounds#Total Queries = (#Parallel threads) * (#Bunches per thread) * (#Queries per bunch) = 1 * 1 * 33554432 = 2^(25.000000)#Queries per thread = (#Bunches per thread) * (#Queries per bunch) = 1 * 33554432 = 2^(25.000000)PID: 0   Bunch Number: 0/1time on clock: 21.9701time on wall: 21.9711sum = 582166.0000002^(-5.848929)#####################################Rounds: 9 rounds#Total Queries = (#Parallel threads) * (#Bunches per thread) * (#Queries per bunch) = 1 * 1 * 33554432 = 2^(25.000000)#Queries per thread = (#Bunches per thread) * (#Queries per bunch) = 1 * 33554432 = 2^(25.000000)PID: 0   Bunch Number: 0/1time on clock: 22.7198time on wall: 22.7210sum = 589950.0000002^(-5.829767)#####################################Rounds: 9 rounds#Total Queries = (#Parallel threads) * (#Bunches per thread) * (#Queries per bunch) = 1 * 1 * 33554432 = 2^(25.000000)#Queries per thread = (#Bunches per thread) * (#Queries per bunch) = 1 * 33554432 = 2^(25.000000)PID: 0   Bunch Number: 0/1time on clock: 25.3275time on wall: 25.3359sum = 607440.0000002^(-5.787618)#####################################Rounds: 9 rounds#Total Queries = (#Parallel threads) * (#Bunches per thread) * (#Queries per bunch) = 1 * 1 * 33554432 = 2^(25.000000)#Queries per thread = (#Bunches per thread) * (#Queries per bunch) = 1 * 33554432 = 2^(25.000000)PID: 0   Bunch Number: 0/1time on clock: 23.3862time on wall: 23.3887sum = 591836.0000002^(-5.825162)#####################################Rounds: 9 rounds#Total Queries = (#Parallel threads) * (#Bunches per thread) * (#Queries per bunch) = 1 * 1 * 33554432 = 2^(25.000000)#Queries per thread = (#Bunches per thread) * (#Queries per bunch) = 1 * 33554432 = 2^(25.000000)PID: 0   Bunch Number: 0/1time on clock: 19.5636time on wall: 19.5643sum = 593720.0000002^(-5.820577)#####################################Rounds: 9 rounds#Total Queries = (#Parallel threads) * (#Bunches per thread) * (#Queries per bunch) = 1 * 1 * 33554432 = 2^(25.000000)#Queries per thread = (#Bunches per thread) * (#Queries per bunch) = 1 * 33554432 = 2^(25.000000)PID: 0   Bunch Number: 0/1time on clock: 21.1922time on wall: 21.1931sum = 600836.0000002^(-5.803388)####################################Average probability = 2^(-5.8208)

As observed, the output closely aligns with our analytical estimation in the paper.

Example 3: Ascon

Assume that we want to verify our 5-round distinguisher for Ascon.To do so, navigate into theascon/verifications directory and open thedifflin.c file, and set lines 102-115 as follows.

    //#######################################################################    int nrounds = 5;    input_diff.x[0] = 0x0000000000000080;    input_diff.x[1] = 0x0000000000000000;    input_diff.x[2] = 0x0000000000000000;    input_diff.x[3] = 0x0000000000000080;    input_diff.x[4] = 0x0000000000000080;    output_mask.x[0] = 0x6da496ddb4932449;    output_mask.x[1] = 0x7110f752d23e65d3;    output_mask.x[2] = 0x0000000000000000;    output_mask.x[3] = 0x0000000000000000;    output_mask.x[4] = 0xe631e6e25c7f614b;    int deg = 22; // num_of_experiments = 2^deg    //#######################################################################

Next, compile the code using the following command:

make

Then, execute the following command:

./difflin 0

The output averages to 2^(-4.33), closely matching our analytical estimation in the paper.

Example 4: WARP

Suppose we aim to verify our analytical estimation for the correlation of the 11-round middle part in our distinguishers for 16 to 22 rounds of WARP.According to our analytical estimation in page 22, the correlation of the 11-round middle part should be$2^{-3}$.To confirm this estimation, navigate into thewarp/verifications directory and open thedifflin.h file, and set lines 41-47 as follows.

//############################## User must change only the following lines ##############################const int DEG1 = 0;const int DEG2 = 20;const int NUMBER_OF_EXPERIMENTS = 10;   // Number of independent experimentsconst int NUMBER_OF_ROUNDS = 11;       // Number of roundschar DP_STR[] ="00000000000000a00000000000000000";char DC_STR[] ="00000000000000020000000000000000";//#######################################################################################################

Then, compile the code using the following command:

make

Next, execute the following command:

./difflin 0

The output will resembes something like the following:

[+] PRNG initialized to 0xA9B3DB27Check decryption: true#Rounds: 11 rounds#Total Queries = (#Threads)*(#Bunces)*(#Queries) = 1 * 1 * 1048576 = 2^(20.00)#Queries per thread = (#Bunches)*(#Queries) = 1 * 1048576 = 2^(20.00)PID: 0   Bunch Number: 0/1time on clock: 1.0399time on wall: 1.0400Absolute correlation: 131380Correlation         : 2^(-3.00)##################################################################################Rounds: 11 rounds#Total Queries = (#Threads)*(#Bunces)*(#Queries) = 1 * 1 * 1048576 = 2^(20.00)#Queries per thread = (#Bunches)*(#Queries) = 1 * 1048576 = 2^(20.00)PID: 0   Bunch Number: 0/1time on clock: 1.0441time on wall: 1.0451Absolute correlation: 130926Correlation         : 2^(-3.00)##################################################################################Rounds: 11 rounds#Total Queries = (#Threads)*(#Bunces)*(#Queries) = 1 * 1 * 1048576 = 2^(20.00)#Queries per thread = (#Bunches)*(#Queries) = 1 * 1048576 = 2^(20.00)PID: 0   Bunch Number: 0/1time on clock: 1.0212time on wall: 1.0212Absolute correlation: 130298Correlation         : 2^(-3.01)##################################################################################Rounds: 11 rounds#Total Queries = (#Threads)*(#Bunces)*(#Queries) = 1 * 1 * 1048576 = 2^(20.00)#Queries per thread = (#Bunches)*(#Queries) = 1 * 1048576 = 2^(20.00)PID: 0   Bunch Number: 0/1time on clock: 1.0211time on wall: 1.0211Absolute correlation: 131640Correlation         : 2^(-2.99)##################################################################################Rounds: 11 rounds#Total Queries = (#Threads)*(#Bunces)*(#Queries) = 1 * 1 * 1048576 = 2^(20.00)#Queries per thread = (#Bunches)*(#Queries) = 1 * 1048576 = 2^(20.00)PID: 0   Bunch Number: 0/1time on clock: 1.0179time on wall: 1.0179Absolute correlation: 131970Correlation         : 2^(-2.99)##################################################################################Rounds: 11 rounds#Total Queries = (#Threads)*(#Bunces)*(#Queries) = 1 * 1 * 1048576 = 2^(20.00)#Queries per thread = (#Bunches)*(#Queries) = 1 * 1048576 = 2^(20.00)PID: 0   Bunch Number: 0/1time on clock: 1.0124time on wall: 1.0125Absolute correlation: 132668Correlation         : 2^(-2.98)##################################################################################Rounds: 11 rounds#Total Queries = (#Threads)*(#Bunces)*(#Queries) = 1 * 1 * 1048576 = 2^(20.00)#Queries per thread = (#Bunches)*(#Queries) = 1 * 1048576 = 2^(20.00)PID: 0   Bunch Number: 0/1time on clock: 1.0115time on wall: 1.0116Absolute correlation: 129716Correlation         : 2^(-3.02)##################################################################################Rounds: 11 rounds#Total Queries = (#Threads)*(#Bunces)*(#Queries) = 1 * 1 * 1048576 = 2^(20.00)#Queries per thread = (#Bunches)*(#Queries) = 1 * 1048576 = 2^(20.00)PID: 0   Bunch Number: 0/1time on clock: 1.0095time on wall: 1.0095Absolute correlation: 131068Correlation         : 2^(-3.00)##################################################################################Rounds: 11 rounds#Total Queries = (#Threads)*(#Bunces)*(#Queries) = 1 * 1 * 1048576 = 2^(20.00)#Queries per thread = (#Bunches)*(#Queries) = 1 * 1048576 = 2^(20.00)PID: 0   Bunch Number: 0/1time on clock: 1.0145time on wall: 1.0145Absolute correlation: 130288Correlation         : 2^(-3.01)##################################################################################Rounds: 11 rounds#Total Queries = (#Threads)*(#Bunces)*(#Queries) = 1 * 1 * 1048576 = 2^(20.00)#Queries per thread = (#Bunches)*(#Queries) = 1 * 1048576 = 2^(20.00)PID: 0   Bunch Number: 0/1time on clock: 1.0102time on wall: 1.0102Absolute correlation: 131246Correlation         : 2^(-3.00)#################################################################################Average correlation = 2^(-3.00)

As seen, the output closely matches our analytical estimation in the paper.

Encoding S-boxes and Other Building Block Functions

To analyze the differential, linear, and differential-linear behavior of the S-boxes, we employ theS-box Analyzer, an open-source SageMath tool available athttps://github.com/hadipourh/sboxanalyzer.

Verifying Proposition 2

We have added a function to the Sbox Analyzer to verify Proposition 2 for a given S-box.To use this function, you need SageMath along with the S-box Analyzer.For example assume that we want to verify Proposition 2 for the S-box of Ascon.

sage:fromsboxanalyzerimport*sage:fromsage.crypto.sboxesimportAsconassbsage:sa=SboxAnalyzer(sb)sage:check=sa.check_hadipour_theorem();checkTheHadipouretal.'stheoremissatisfied.True

References

  1. Catching the Fastest Boomerangs - Application to SKINNY
  2. Improved Rectangle Attacks on SKINNY and CRAFT
  3. Throwing Boomerangs into Feistel Structures: Application to CLEFIA, WARP, LBlock, LBlock-s and TWINE
  4. Automatic Search of Rectangle Attacks on Feistel Ciphers: Application to WARP

Citation

If you use our tool in your work, please acknowledge it by citing our paper:

@article{difflin_hadipouretal_crypto_2024,  author       = {Hosein Hadipour and                  Patrick Derbez and                  Maria Eichlseder and},  title        = {Revisiting Differential-Linear Attacks via a Boomerang Perspective with Application to {AES}, {Ascon}, {CLEFIA}, {SKINNY}, {PRESENT}, {KNOT}, {TWINE}, {WARP}, {LBlock}, {Simeck}, and {SERPENT}},  editor       = {Reyzin, Leonid and                   Stebila, Douglas},  booktitle    = {{CRYPTO} 2024},  series       = {LNCS},  pages        = {38--72},  publisher    = {Springer Nature Switzerland},  year         = {2024},  doi          = {10.1007/978-3-031-68385-5_2},  eprint       = {2024/255},  usera        = {CRYPTO},  userb        = {2024},}

LicenseMIT License

This project is licensed under the MIT License - see theLICENSE file for details.

[8]ページ先頭
©2009-2025 Movatter.jp