RhoPollard

This code is a python algorithm using Pollard's Rho method to find collision in any hash function. Moreover it uses the Floyd's cycle-finding algorithm to optimize the search. A whole study had been conducted by myself in 2021 : See the paper (free and in french 🇫🇷)

Contributor(s) : @DevNathan (Nathan Stchepinsky)

Licence

This code source is published under MIT licence.

Usage

1 - Clone the project

Clone this project on your laptop by using this link or by executing the following command in your terminal :

git clone https://github.com/DevNathan/RhoPollard

2 - Generate collisions

Generate a collision on a hash function :

from rho_pollard import *
hash_method = hashFunc() # Must be func which takes one argument, the clear message and returns the corresponding hash.
len_randWord_max = 1000 # Maximum length (in char) of the random word generated by Pollard's Rho algorithm

rho_pollard = RhoPollard(hashFunc, len_randWord_max)

(clear1, clear2, nb_hash) = rho_pollard.generateCollision() # The called func returns the two clears message in collision and the number of hashes generated.

Optional init argument (ie while calling Rho_Pollard()) :

• Name : is_printing_hash
• Default value : False
• Comment : If the boolean is true, all hashs generated will be printed. Else, only the collisions and the number of generated hashs are printed.

3 - Example : MD5

Code

from rho_pollard import *
import hashlib


def hash_func(clear) :
    # MD5 hash
    return hashlib.md5(clear.encode()).hexdigest()[:8] # We only keep the 8 first char of the MD5 hash

pollard = Rho_pollard(hash_func, 10000, is_printing_hash = False)

(clear1, clear2, nb_hash) = pollard.generateCollision() # In this example I don't use the ouput of the func

Note : Here we use a special MD5 hash, by only keeping the 8 first char, for time reason. With a 32 char hash the collision research would take to much time for my machine.

Output

Random message generated = 4mmETMIDOjhgUq7vHcu2czcLAkaTxCtcuNluqTHxy3EKRn4XpjKr3JRKGlr8NBrNHEdGiFLMotpoSVxuoUOMN9V3qlk
[*] STEP 1 ...
673141  hashs generated
[*] STEP 1 finished with success.
[*] STEP 2 ...
428749  hashs generated



################## COLLISION FOUND ##################

Hash( c20dbe3b37 ) =  62aab29a02
Hash( c9c3d4c63b ) =  62aab29a02

####################################################

Computing time

*Executed on a Macbook Pro 2019 Intel Core i5 (1,4 GHz and 4 cores) *