mantin wep implementation in c++

Question

I have implemented the Mantin model of WEP attack published in 2005 in c++. To check wether the implementation is correct i am generating 2^48 IVs and their corresponding 257th keystream byte from RC4 PRG. The complexity of the algorithm is o(n). Basically the structure of the code is as follows:

for(loop through n times){
    for(loop through 3 times){}
    for(loop through 256 times){ some code}
    for(loop through 257 times){some code}
}

so while putting n = 2^48 it is taking a very long time. Is is normal or I am missing something? I am using intel i3 processor.

Answer 1

Yes, it will take a while.

Consider what it takes to just count from 0 to 2^48-1. That's roughly 281 trillion operations. My computer (using an Intel Core i5-2500K) took about 9 seconds to run a single-threaded loop that counts from 0 to 2^32-1; based on that, counting to 2^48-1 would take roughly 164 CPU core-hours, or about a week on a single CPU core. That doesn't count the time that it would take to do anything useful with that counter.

Fortunately, the problem is easily parallelizable. Split the search space into chunks and run each chunk on a different CPU core, then merge the results when done.