How to handle a dict variable with 2^50 elements?

Question

I have to find SHA256 hashes of 2^25 random strings. And then look for collision (using birthday paradox for the last, say, 50 bits of the hash only). I am storing the string:hash pair in a dict variable. Then sorting the variable with values (not keys) and then looking for collision using a O(n) loop. The problem is that since there are 2^25 strings and their 2^25 hashes, so the dict variable has 2^50 values in it. This is EXTREMELY resource intensive. So, how do I do this with limited RAM, say, around 1GB? What I have already tried: 1. Running this with a 6GB swap space. The program ran overnight and was still not done. This is essentially even slower than an O(n_square) search! The hashes are calculated with RAM usage of about 3.2 GB. But after that when it comes to the sort command, the RAM used starts shooting up again! I though the python sort uses In-Place-Quicksort :( 2. I have stored only the hashes and found a collision. But could not find the corresponding string since did…

Accepted Answer

I'd go for something like this:

Open 16 files (opened in binary mode should be fine; this will be easiest if all your strings have the same length). Generate your strings and hashes, and write them to a file depending on the first 4 bit of the hash. Then load and process each file separately. This will reduce memory usage by a factor of 16. (Of course you can use any number of files as long as you don't run out of file handles. Having to open and close each file on every access will become rather slow.)

If generating the strings and hashes is relatively inexpensive, you don't even need the files. Simply do 16 passes, and in each pass keep only thoses hashes the upper nibbles of which match the pass number.

How to handle a dict variable with 2^50 elements?

Solution

Problem