In the CTF's implementation, the 2nd piece of the password would only be checked if the first one was correct. You could figure out how many different requests were made by correlating TCP sequence numbers. If only 1 request was made, the first piece was incorrect. If 2 requests were made, the 1st piece was correct, but not the second, etc...
The attack was akin to a timing attack (but definitely not a timing attack).
Haha, this is the first thing I thought of when reading this article.
In reality, it would probably be difficult to execute on a live production server via the TCP port method. The artificial delay they added in to prevent timing attacks might cause a heavy load on the server, so if they leave that out that would be another possible attack vector.
I enjoyed a lot stripe 2.0 and I have watched Dan Bone on coursera. In the article, they just split the password in two. 128bit/2 -> 64bits. This remains two much for brute force like TCP port method or timing attack.
If LinkedIn, the article's whipping boy for bad password storage, had somebody with the brains and capability to purchase and integrate this multi-machine password storage system, LinkedIn would have had somebody with the capability of implementing a secure password hashing system like pbkdf or bcrypt or scrypt and wouldn't need to buy a mega priced security solution from RSA.
LinkedIn is written almost entirely in Java, so Devise would not have worked out that well. Using something like jBCrypt would have been almost as easy, though -- if they'd thought of it from the beginning.
The failure here is just that whoever wrote the auth code didn't know that it was a problem, or thought (incorrectly) that using something like bcrypt would be significantly more effort.
That's really the sad part... technically it's a superior solution to bcrypt/scrypt but the reason why LinkedIn got pwned was because they MD5'd their passwords instead of bcrypt/scrypt.
If I remember correctly they were also not using a salt. They stated that "members whose passwords have not been compromised benefit from the enhanced security we just recently put in place, which includes hashing and salting of our current password databases."[1]
The problem is that when you make this mistake early, it's not easy to fix, since you don't have the passwords yourself. Though I guess they could have rainbow-table'd their own password database and migrated everything over to a better scheme, rather than waiting for users to successfully log in.
I'm surprised common auth systems don't handle this more elegantly. It's possible to maintain a history of crypt methods and store that with the password data. The system can then keep track of which user records were created with older algorithms, and automatically update them when the user logs in, but not requiring an across-the-board password update. The process is completely transparent to the user.
I believe there are some systems that don't store the crypt methods with the password data, but instead just run through each password method to try to find one that works, then transparently upgrade to the newest.
Possibly. I'm no expert, but it seems like if you were using an incorrect password, you would be running through every old system every time, regardless of if the person had upgraded. The only time you would short-circuit any of the methods would be if you used the right password.
I actually think the originally described system is more vulnerable to a timing attack, since you could determine which crypto system a user's password is using based on the timing.
You could definitely use a timing attack to isolate accounts still using the weak crypto, but the mitigation against that is the same as any time attack mitigation strategy: you configure your auth solution with a return time floor.
I don't see this scenario presenting any more risk from a timing attack vector than a bare implementation using weak crypto, and it offers a balance between having no option to upgrade your crypto algorithm, and an option that involves some trade off.
That's the standard, but all those unused accounts still have vulnerable passwords, which is sub-optimal. (This might not matter for discussion forums or something like that, but consider something like your state's online tax site; something people only view once a year, but something that's very important to keep secure.)
It's not really that difficult. Let's say you've got a column called 'insecure_pass' that is storing a simple md5 hash of users' passwords.
Four simple steps:
1) You add a new password column to your DB (secure_pass) and modify your account creation / password change code to store bcrypt(md5(password)) in that column in parallel with just md5(password) in the old insecure_pass column.
2) You run a job that migrates insecure_pass to secure_pass by calculating bcrypt(insecure_pass) and storing that in secure_pass.
3) You turn on "dark reads" for secure_pass on login and log if there are any cases where validation against secure_pass failed when validation against insecure_pass succeeded. If a log message shows up, you did something wrong.
4) You move over to "light reads" for secure_pass and stop updating/validating insecure_pass. Once that's deployed, you drop the insecure_pass column from your DB.
You might be surprised how little many companies actually care about security when the fallout is largely externalised (for example users having their gmail compromised because they used the same password for linkedin).
The real question from linkedin's point of view is how many profitable people stopped using the service because they stored the passwords in MD5?
Based on some of the systems I have seen over the years I will say that there is a very strong chance that some company you have bought something from at some point has a copy of your credit card number + CCV2 stored in plaintext in a mysql database somewhere.
No one bothers with rainbow tables anymore... Why bother with terabytes of storage when you can make billions of guesses per second, on extremely cheap commodity hardware?
That's simply not true. Rainbow tables are still the first choice of many people trying to crack passwords, with brute force or hybrid attacks as a follow up after the common passwords have been found.
It doesn't hurt that there are a lot of rainbow tables available to access for free on the Internet.
Well, I guess our experiences differ. Personally, I find it impractical to push many-terabyte files around, when, for a few bucks, I can effectively regenerate them in a matter of minutes.
Threshold cryptography might be an interesting approach when you need to keep credentials (vs. hashes of credentials), but I'd probably go with keeping my credentials encrypted under keys stored in a hardware security module (HSM) with rules on access (rate limit, etc.), first. Vastly cheaper (even though HSM prices are generally a form of rape), and simpler.
I like the little plug at the bottom for physical OTP devices, which completely neglects to mention that RSA is a leading player in this space. I wonder if the writer accidentally went the completely wrong direction with that sound bite.
In theory if you're going to the trouble of hashing your users' passwords, you'll salt them too. None of us would be in this thread if these types of theories were true.
Why in the world would there be a root password at all?
"No, Bob, if you lost the private key associated with your ssh credentials you can send me a gpg-signed email or wait until morning when you can verify your identity physically."
As I linked further down, this is probably based on Adi Shamir's (of RSA) threshold sharing scheme [1] [2]. Essentially, this approach splits any "secret" into n parts, requiring that k of them are necessary to reconstruct the original secret.
It relies on the fact that k points are necessary to reconstruct a k-1 order polynomial. So if you hand out n points, with n > k, then any k of these points can be used to reconstruct the polynomial, whose y-intercept is the "secret". The coefficients of the polynomial are random.
There are other [3] sharing schemes, and for the trivial k = n case, Shamir's scheme is probably overkill.
Yeah...this is nice, but really who's gonna implement it? Only folks with a lot of resources and need to protect something more serious than passwords on a social network.
Or organizations who are vulnerable to the RSA sales person attack. ;)
As others have hinted - once you have folks sophisticated enough to do tricks like using multiple operating systems, you'd hope they're going to catch the basics...
I'm confused by their logic. Customers are those who are unable to keep one set of servers appropriately secured and unable to mitigate compromises through the use of better techniques (eg bcrypt).
So the solution is to run a second set of servers. Why would those be any better or differently secured?
Maybe it can keep safe weak password from dictionary attack. If a user has "pass" as password, BCrypt do not protect him once the attacker has an hash of its password. Maybe their 2 servers methods prevent that (I'm really not sure)
What leads you to believe that bcrypt is susceptible to hashing or rainbow tables? It uses salts and extremely expensive key setup (ie different for each password even if the original plaintext is the same).
It is true that if the password is one of the most common such as "pass" or "password" then you'll be to tell if that is the case in a reasonable amount of time. However you could trivially do that testing without going to the lengths of breaking into and compromising systems.
All this RSA mechanism does is split the password verification into two halves each with knowledge of about half the information necessary to compromise. In theory compromising one system won't help you - you need to do both. But that doesn't help against the weakest passwords since they can just be tried against the system.
There are some good presentations on the bcrypt wikipedia page. Of note is that 1,000 password guesses per second per system is roughly what happens now, and that scrypt is better for some circumstances. By contrast legacy schemes have rates from 10 million to 2 billion per second - even something as modern as WPA has 100,000 guesses per second per system crackers.
But back to the original point - a company with weak administration and security practises isn't going to get any better by doing more of it.
This is from a crypto startup called Envault that was founded on the idea of splitting data in pieces - they keep a fraction of the ciphertext somewhere "in the cloud" and off the local storage of your device when not in use. This is advertised as being very very safe.
I never heard any crypto guy with credentials comment on their tech though which is usually a bad sign...
No doubt I'm missing something dumb, but would one get similar benefits from simply storing half of the password hash on one server, and half on the other? To authenticate the password, you would then just authenticate it against both servers which can tell you whether their half matches. What is the advantage of the technique described[1] in the article compared to this?
[1] That's putting it a bit kindly. 'that we were told exists' might be more fair.
49 comments
[ 3.6 ms ] story [ 107 ms ] threadhttps://github.com/stripe-ctf/stripe-ctf-2.0/tree/master/lev...
I thought that an adaptation of something like Shamir's Secret Share could work.
The attack was akin to a timing attack (but definitely not a timing attack).
In reality, it would probably be difficult to execute on a live production server via the TCP port method. The artificial delay they added in to prevent timing attacks might cause a heavy load on the server, so if they leave that out that would be another possible attack vector.
gem 'devise'
into a textfile.
The failure here is just that whoever wrote the auth code didn't know that it was a problem, or thought (incorrectly) that using something like bcrypt would be significantly more effort.
Security announcement: Devise v2.2.3, v2.1.3, v2.0.5 and v1.5.4 released
http://blog.plataformatec.com.br/2013/01/security-announceme...
So using a real database mitigated the entire issue. Secondly, this security issue doesn't allow you to retrieve every user's password in 8 hours.
[1] http://blog.linkedin.com/2012/06/06/linkedin-member-password...
I actually think the originally described system is more vulnerable to a timing attack, since you could determine which crypto system a user's password is using based on the timing.
I don't see this scenario presenting any more risk from a timing attack vector than a bare implementation using weak crypto, and it offers a balance between having no option to upgrade your crypto algorithm, and an option that involves some trade off.
Four simple steps:
1) You add a new password column to your DB (secure_pass) and modify your account creation / password change code to store bcrypt(md5(password)) in that column in parallel with just md5(password) in the old insecure_pass column.
2) You run a job that migrates insecure_pass to secure_pass by calculating bcrypt(insecure_pass) and storing that in secure_pass.
3) You turn on "dark reads" for secure_pass on login and log if there are any cases where validation against secure_pass failed when validation against insecure_pass succeeded. If a log message shows up, you did something wrong.
4) You move over to "light reads" for secure_pass and stop updating/validating insecure_pass. Once that's deployed, you drop the insecure_pass column from your DB.
The real question from linkedin's point of view is how many profitable people stopped using the service because they stored the passwords in MD5?
Based on some of the systems I have seen over the years I will say that there is a very strong chance that some company you have bought something from at some point has a copy of your credit card number + CCV2 stored in plaintext in a mysql database somewhere.
It doesn't hurt that there are a lot of rainbow tables available to access for free on the Internet.
by Adi Shamir, the "S" in RSA
"No, Bob, if you lost the private key associated with your ssh credentials you can send me a gpg-signed email or wait until morning when you can verify your identity physically."
It relies on the fact that k points are necessary to reconstruct a k-1 order polynomial. So if you hand out n points, with n > k, then any k of these points can be used to reconstruct the polynomial, whose y-intercept is the "secret". The coefficients of the polynomial are random.
There are other [3] sharing schemes, and for the trivial k = n case, Shamir's scheme is probably overkill.
[1] http://en.wikipedia.org/wiki/Shamir%27s_Secret_Sharing
[2, PDF] http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.80....
[3] http://en.wikipedia.org/wiki/Secret_sharing
UPDATE: Here are some links to RSA's "Distributed Credential Protection" offering [4] and the white paper [5] describing it.
[4] http://www.emc.com/security/rsa-distributed-credential-prote...
[5, PDF] http://www.emc.com/collateral/software/white-papers/h11013-r...
Or organizations who are vulnerable to the RSA sales person attack. ;)
As others have hinted - once you have folks sophisticated enough to do tricks like using multiple operating systems, you'd hope they're going to catch the basics...
You can change banks easier than you can migrate all your contacts to another social network.
So the solution is to run a second set of servers. Why would those be any better or differently secured?
or
sudo port install ssss
It is true that if the password is one of the most common such as "pass" or "password" then you'll be to tell if that is the case in a reasonable amount of time. However you could trivially do that testing without going to the lengths of breaking into and compromising systems.
All this RSA mechanism does is split the password verification into two halves each with knowledge of about half the information necessary to compromise. In theory compromising one system won't help you - you need to do both. But that doesn't help against the weakest passwords since they can just be tried against the system.
There are some good presentations on the bcrypt wikipedia page. Of note is that 1,000 password guesses per second per system is roughly what happens now, and that scrypt is better for some circumstances. By contrast legacy schemes have rates from 10 million to 2 billion per second - even something as modern as WPA has 100,000 guesses per second per system crackers.
But back to the original point - a company with weak administration and security practises isn't going to get any better by doing more of it.
This is from a crypto startup called Envault that was founded on the idea of splitting data in pieces - they keep a fraction of the ciphertext somewhere "in the cloud" and off the local storage of your device when not in use. This is advertised as being very very safe.
I never heard any crypto guy with credentials comment on their tech though which is usually a bad sign...
[1] That's putting it a bit kindly. 'that we were told exists' might be more fair.