wPRF-Collision-Attack

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.

Usage

Run the following command line in your terminal:

python attack_wprf.py -L 28 -n 100

Arguments

-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.

Output

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.

Example

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.

Licence

The Collision Attack is licensed under the MIT License.

• MIT license (LICENSE or http://opensource.org/licenses/MIT)