3 ms·
Right :-) Brute force is 'hard' - dictionary is not. Calculating 'v' is a bit harder than SHA1 - there is a lot of research on performance of modular exponent
by zaroth 14y ago
Right :-) Brute force is 'hard' - dictionary is not.
Calculating 'v' is a bit harder than SHA1 - there is a lot of research on performance of modular exponentiation since it is the foundation of crypto, but most of the current benchmarks are at 1024 or 2048 bit N.
Given that we have a mere 256-bit N, it looks like between 10k - 100k operations / sec is achievable with a modest budget. I should go benchmark this on Google Compute or EC2 GPU, but I need to sleep at some point.
Intel released a benchmark here: http://download.intel.com/design/intarch/PAPERS/324952.pdf http://download.intel.com/design/intarch/PAPERS/324952.pdf claiming they can do 1024-bit ME in 2m cycles, and 512-bit ME in 250k cycles on an i7-2600. Assuming that means you can do 256-bit ME in 32k cycles, that's 100k / sec at 3.4GHz.
So an attacker takes a dictionary with 100k passwords in it (or just the top 10k, that works almost as well...) and tests them for each { username, salt, v }.
If you can do 100k tests per second, you can test 100k passwords for 100k users (10B tests total) in a little over a day. You won't successfully crack every password, but a well formed dictionary with top 100k passwords will crack a majority of them.
So don't tell me it's too slow to dictionary attack, ok?! :-)