This repository contains Python code designed to simulate and test a key-recovery attack on the Standard One-to-One wPRF introduced by Alamati et al. The attack operates by iteratively refining a guessed key K through collision finding and exhaustive search. It also incorporates theoretical models to determine the optimal transition point between these phases, aiming to minimize overall complexity.
The program requires Python 3 and the numpy library.
Run the following command line in your terminal:
python attack_wprf.py -L 28 -n 100
-L (required): security parameter λ (e.g. 28, 34).
-n (optional, default = 100): number of experiments.
One experiment has expected complexity on the order of 2^{L/2}*log_2(L). The program then conducts n independent experiments, measuring the complexities of the collision finding and exhaustive search phases, as well as the overall efficiency of the attack.
To reproduce the results in the paper (Table 2), run with -L 28 -n 1000 or -L 34 -n 1000.
For each batch of experiments, the script reports averages across all runs. The numbers reported correpspond to the columns of Table 2 in the paper describing the attack:
- Collision Complexity (C_col)
- Exhaustive Search Complexity (C_exs)
- Number of Collisions required to recover the key
- Total Complexity (C_tot = C_col + C_exs)
- Percentage of runs where the theoretical Hamming-distance bound C was sufficient to recover the key. This corresponds to the column labelled Accuracy of C in the paper.
Final Results:
Average Collision Complexity: 92539.71 (log2 ≈ 16.50)
Average Exhaustive Search Complexity: 194.02 (log2 ≈ 7.60)
Average Number of Collisions: 4.42
Average Total Complexity: 92733.73 (log2 ≈ 16.50)
Percentage of Max_dist Sufficient Cases: 74.00%
The code is written to be adaptable for various experimental setups. You can modify the security parameter and the number of experiments. Intermediate results and detailed outputs are printed during execution to allow you to monitor the progress of the attack.
The Collision Attack is licensed under the MIT License.
- MIT license (LICENSE or http://opensource.org/licenses/MIT)