Hacker News Reader

Comment by zaroth | Hacker News Reader

SRP is great at many things, but terrible at securing the server-side password database from brute force attacks.

A quick look at http://srp.stanford.edu/design.html and http://srp.stanford.edu/demo/demo.html and you can see that SRP uses simple SHA1 plus a Salt to store the hashed passwords.

With the hashes and salts stolen, please assume your password has been brute forced by the attacker (1 billion hashes per second with SHA1 is not expensive). This is LinkedIn all over again.

If Blizzard customized their SRP algorithm to use a more expensive hash than SHA1, they should come out and say it.

Otherwise, we should assume their statement that using SRP "means that each password would have to be deciphered individually" is nothing more than a salted SHA1. Combined with their reduced entropy password policy, all stored passwords are likely brute forced already.

View on HN

It seems like you either didn't actually read the RFC or read but didn't understand, then made a fuss out of your ignorance.

SRP uses SHA1, but not just that. Here is the relevant part of the RFC [1]:

The host stores user passwords as triplets of the form

        { <username>, <password verifier>, <salt> }

   Password entries are generated as follows:

        <salt> = random()
        x = SHA(<salt> | SHA(<username> | ":" | <raw password>))
        <password verifier> = v = g^x % N*

[1] http://www.ietf.org/rfc/rfc2945.txt

cryptbe - I quoted the exact same text from the RFC in a post below. Sheesh...
From this it should be obvious to you that what SRP is doing is no better than SHA1 for protecting against dictionary attacks.
'g' and 'N' are well known numbers (also posted below). Username, and salt are known.
It's the perfect setup for high speed dictionary attacks. Please edit or delete your post. You can read my more lengthy post on this here: http://www.opine.me/blizzards-battle-net-hack/

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.

Fixed 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
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?

See 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.

Whatever 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.

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.

Your point is taken, but saying "you cannot retrieve X from v" in a thread about doing exactly that is kind of funny. :)

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 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?! :-)

SRP is supposed to make use of multiple types of entropy to ensure the passwords are far more complicated that salted SHA1.
While I agree it's possible that the attackers also got this information but I don't think we can jump to conclusions about the overall security of the passwords until more information is known.

Please read the RFC, it's right here: http://www.ietf.org/rfc/rfc2945.txt
Password entries are generated as follows:
<salt> = random() x = SHA(<salt> | SHA(<username> | ":" | <raw password>)) <password verifier> = v = g^x % N G = 47 N = 112624315653284427036559548610503669920632123929604336254260115573677366691719
What was stolen was no better than LinkedIn hashes -- for the purposes of dictionary attacking the database

Define slow tedunangst - Big O notation please.
Maybe you can look here: http://en.wikipedia.org/wiki/Modular_exponentiation.
Ok, I'll save you the trouble -- the modular exponentiation is O(log exponent). That's log as in... FAST.

What's the Big-O of PBKDF2 ?
Constants matter.
(Also, computational complexity of crypto algorithms is usually specified in terms of nbits, not numeric magnitude)
(Although this argument has given me an idea for everyone that thinks using the same password on different sites is reasonable - a browser extension that runs a client-side KDF :P)

slow == 172.959 times slower than sha1("password")

Actually, I forgot one minor thing. LinkedIn hashes were unsalted. Even assuming SRP is no better than sha1, cracking all of the battle.net passwords is going to be $number_of_users times harder than LinkedIn.

g^x is slow, therefore better than linkedin hashes for the purpose of dictionary attacking the database.

They use SHA1, although they make a couple of tweaks. I've implemented the bnet login stuff (https://github.com/Strilanc/Tinker/blob/master/Bnet/ClientCr...).

Well that's it then. 'g' and 'N' are published in your code, and they are using SHA1 as the hash.
GAME OVER. These passwords are cracked. Please see full explanation here: https://news.ycombinator.com/item?id=4364826

Reply on news.ycombinator.com