3 ms·
I haven't studied SRP, but a quick look at it and it seems that one also needs to perform the v = g^x. While still vulnerable to brute forcing due to lack of en
by mindslight 14y ago
I haven't studied SRP, but a quick look at it and it seems that one also needs to perform the v = g^x. While still vulnerable to brute forcing due to lack of entropy in a password, this is more expensive than bare SHA1. The opine.me post you linked elsewhere completely glosses this over.
edit: okay, just to give you some very rough numbers from 'openssl speed' on my machine. 16 byte SHA1 is about 1M/sec. Projected dsa256 (based on dsa512 and its ratio to dsa1024) signatures (most of which is an exponentiation) is about 3k/sec. It's certainly not a purpose-built tunable KDF, but it's orders of magnitude harder than SHA1.
- zaroth 14y agoSee below, the algorithm is clearly specified in the RFC, and it's no better than plain SHA1 in terms of preventing dictionary attacks once the database is stolen.
- tedunangst 14y agoWhatever logic you are using to prove that performing g^x is the same as computing plain sha1 would also prove that bcrypt and pbkdf2 are no better than sha1.
- zaroth 14y agov = 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?! :-)
- zaroth 14y agoFixed the blog to give more credence to the ME op. Thanks for the great discussion mindslight & tedunangst. I'm not trying to be sensationalist, but I think it's bullshit that Blizzard is saying SRP makes it "computationally very difficult and expensive" to extract the passwords from the stolen verified database. Blizzard should come out and say, "the majority of our users' passwords have been stolen. If you have an extremely random password, you may be one of the few that were not cracked, but don't bet on it." Just to keep the friendly banter going though, even Anandtech was getting better performance back in 2006 with his exponentiation: http://www.anandtech.com/show/2022/5 http://www.anandtech.com/show/2022/5 On EC2 c1.xlarge running AMI ami-ef5ff086 ($0.66 / hour): ./openssl speed rsa -multi 8 rsa 512 bits 54663.2 sign/s rsa 1024 bits 10709.9 sign/s ./openssl speed dsa -multi 8 dsa 512 bits 56011.1 sign/s dsa 1024 bits 20449.8 sign/s So $100 would buy you... about 100 billion guesses?