2 ms·
v = g^x % N Finding 'x' given g, v, and N is HARD. Calculating g^x is EASY. O(log X) This is crypto 101 man... This is why SRP is said to be verifier based
by zaroth 14y ago
v = g^x % N
Finding 'x' given g, v, and N is HARD.
Calculating g^x is EASY. O(log X)
This is crypto 101 man...
This is why SRP is said to be verifier based and not password or password-equivalent based, because you cannot retrieve X from v.
But this is ALSO why the CREATOR of SRP Thomas Wu specifically states in his presentations on SRP that it does not resist dictionary attacks when the verifier database is stolen.
- tedunangst 14y agoYour point is taken, but saying "you cannot retrieve X from v" in a thread about doing exactly that is kind of funny. :)
- zaroth 14y agoRight :-) 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?! :-)