6 ms·

They said they Hashed and Salted password so it's unlikely the hackers will get "actual" passwords by brute-force However what I've seen happen after this atta

They said they Hashed and Salted password so it's unlikely the hackers will get "actual" passwords by brute-force However what I've seen happen after this attacks is usually they attacker use the e-mail addresses to do phishing attacks and just get passwords that way. They already know their e-mail and that they are living-social customers. Expect a phishing e-mail that looks like coming from living social.

thirsteh 13y ago
Hashed and salted means almost nothing. It could be one invocation of SHA-256 (or SHA512, or SHA-3) with a salt, which is fairly meaningless unless the key/password contains a large amount of entropy (almost no passwords do.) It's much more important to know what algorithm they were actually using, e.g. scrypt, bcrypt or PBKDF2, and what the settings/work factors/iteration counts for them are/were. If a company is reluctant to disclose that, they're likely using something that's highly vulnerable to parallelization/efficient brute force cracking, regardless of what kind or size of salt was used.
- StavrosK 13y ago
  I like how everybody is optimistic. It could have been MD5!
  - integraton 13y ago
    Since, AFAIK, it's built on Rails, that's unlikely. However, it's possible that it's SHA-1 since popular Rails auth solutions used that by default at the time the company was founded (2007), assuming that's what they started with and never switched from.
    - ukd1 13y ago
      I'd be very surprised if Rails didn't support upgrading the hash over time - anyone know if it does with has_secure_password?
      - integraton 13y ago
        Prior to 3.1, Rails didn't have built-in support for password hashing or user auth beyond http auth, so it was handled by libraries (like devise or authlogic), generated code (such as with restful-auth, which was popular in 2007), or custom code. I don't think it's very common for legacy codebases to be migrated to has_secure_password, but it's not impossible. There is not built in migration for has_secure_password, AFAIK. LivingSocial is a big enough company I wouldn't be surprised if their authentication code was all or mostly custom.
gdeglin 13y ago
It's actually very possible for hackers to still decode many of the passwords. An attacker could simply put together a dictionary of 10,000 common passwords then hash them against each user's salt value and see they they get a match for that user's password Hash. Assuming Hashes are stores as SHA-256, with a GPU hashing setup they'll be able to scan through 50 million users in very little time at all.
- gruseom 13y ago
  I have a dumb question about this. It was a smart question when someone asked me it the other day, but it's a dumb question now because I feel like I should know the answer and I don't. Why can't you get away with using some trivial but obscure modification of one of the standard fast hashing algorithms? It will be just as vulnerable as the standard algorithm, of course, once you know what it is. But now the attacker has to figure out which algorithm you modified and how you modified it. How do they do that? I get that this is a bad idea that won't work, blah blah security by obscurity and so on. But when I was asked why it doesn't work, I was unable to give a very satisfying answer.
  - ukd1 13y ago
    It would work, but a) you might break the algorithm in ways that make collisions b) if your code is stolen in a breach, it's useless. Most people should use bcrypt with enough rounds to make it difficult to brute force. scrypt is also an option, though newer (good / bad: http://security.stackexchange.com/questions/26245/is-bcrypt-better-than-scrypt http://security.stackexchange.com/questions/26245/is-bcrypt-...).
  - rajivm 13y ago
    Well if they don't have your source code, why modify the algorithm, you can just use sha1(password + user_salt + site_secret) -- that site_secret just made the sha1 unique to your site. Of course, if they have your source code, then it doesn't matter: they would have your 'site_secret' or your modified algorithm. Better would be not storing your site_secret in a accessible way (not on disk). Edit: See udk1 below -- he's right, sha1 is an outdated algorithm for this purpose. Poor example choice on my part.
fudged71 13y ago
Would encrypting the email addresses be feasible? They do seem to have a lot of value to hackers, but I'm not sure what the technical limitations would be for a user-base this large or with their functionality.
- whichdan 13y ago
  Encrypting would be pointless. Hashing would be possible, but then you break things like email notifications and password resets.
  - umsm 13y ago
    Upon a password reset submit, check if the hash(email_submit) exists, if so, email the password reset instructions to the email_submit address :)
    - rozap 13y ago
      Still, notifications would be toast. Thought most email notifications are annoying, they can be useful (or crucial).
      - umsm 13y ago
        If you don't need email notifications, then it's not a problem. One nice feature from gmail/yahoo/outlook/etc.: temporary email addresses that forward to your email. This would solve the problem. Or, maybe alternative notification methods are preferred? If they wanted, a user can input an email address with a plus (if they're using gmail) and then receive notifications only on that. If the user wanted, then they could block all incoming messages that match that generated email.
  - unclebucknasty 13y ago
    Why is encrypting pointless if you generate the equivalent of a private key in code? Of course, if the attacker also gets the code, then you're toast, but getting the code is not guaranteed. So, seems like you'd have some additional protection with encryption.
dcu 13y ago
it's well known that many users pick passwords like "password", "123456", "qwerty", etc... so I don't think cracking many of those passwords will be a problem
mdasen 13y ago
That's good. However, if a good proportion of people use one of the 1,000 most common passwords, then they can hack those accounts in the time it takes to compute 50M * 1,000 hashes. With CUDA, it seems that you can do hundreds of millions per second. At 100,000,000 per second, you could compute that in 500 seconds (under 10 minutes). http://www.golubev.com/hashgpu.htm http://www.golubev.com/hashgpu.htm - this claims into the billions per second. When were talking 5B tries per second, that means trying the most common 100,000 passwords against each of the 50M accounts in under 20 minutes. The most common 1,000,000 passwords against all 50M accounts in under 3 hours; the most common 10M passwords against all 50M accounts in a little over a day. Hashing is good, salting is better, but unless there was a work factor involved like PBKDF2, bcrypt, or scrypt, it seems like it's protection against people who don't know what they're doing more than against people who know what they're doing. I'm not the type to say that we need to protect against people who have the money to make ASICs (app-specific integrated circuits likely used by governments), but I do think protection against nVidia chips is warranted. Now, it's genuinely possible that by "hashed and salted", they mean they used bcrypt or PBKDF2 (and simply aren't giving details in the email). But, if it's a salted SHA1, I think phishing would be harder than cracking a substantial proportion of them.
- EvanKelly 13y ago
  Maybe I'm misunderstanding (entirely possible!) and I think your point still stands, but isn't it 50M * 1,000 hashes * # of possible salts? EDIT: Just realized that the salts have to be stored somewhere and the attacker probably grabbed those as well. I think that answers my question.
  - mpyne 13y ago
    No, because the salt is stored with the password. Salts are used to defend against reversing a password hash into a password, but they don't appreciably impede bruteforcing passwords into hashes.
    - nwh 13y ago
      It does mean that for a large dictionary attack things will go a lot slower. Rather than one computing one hash and comparing it to 50M hashes, the same word must be hashed with 50M different salts and then compared with their respective hashes.
wglb 13y ago
Why would the attacker, if they got the passwords, not bother to look to the column just to the right and take the salts as well? Given that, the attacker can try hundreds of billions of password combinations per second.
- chill1 13y ago
  The point of unique salts is that even if all the user's passwords are the same, the end resulting hashes that are stored in the database, are different. So, let's say you wanted to hash your set of 50,000 different, commonly used passwords. You'd have to hash that list of 50k passwords for EACH individual user. So instead of 50,000 hashes... you have 50,000 x the total number of users.
  - wglb 13y ago
    I am not following your logic here. What I am saying that if the attacker gets a row from the database that has the user's id, the password will be in a column labeled 'password'. Next column is likely to be the salt generated for that user's password, and let's say that this column name is 'salt'. With the salt and password for each user, you can run a dictionary across each combination at a furious rate.
- StavrosK 13y ago
  The attacker does, of course, have the salts as well, since they're part of the hash. I don't see how they can try hundreds of billions of password combinations per second, though.
  - bcoates 13y ago
    http://securityledger.com/new-25-gpu-monster-devours-passwords-in-seconds/ http://securityledger.com/new-25-gpu-monster-devours-passwor... 25 late 2012 vintage GPUs gets you 180 billion MD5 tries per second. With a fairly modest budget you can rent a whole lot more GPU power than that. A little Googling gets me several companies offering password hash cracking as a service.
marshray 13y ago
We can expect 50% of the password hashes to be cracked in the first few minutes, 10% will never be cracked, and the 40% in between will survive with a roughly exponential decay.
malandrew 13y ago
I wouldn't be surprised if we eventually see a breach for a company where the attackers, after securing the DB of emails, goes on to email everyone informing them of the breach before the company does so and asking them to reset their passwords. This would give the attackers the old email of the person (which has likely been reused on other services) AND a new password that they also may already be using on some services or plan on using on other services in the future.

thirsteh 13y ago

Hashed and salted means almost nothing. It could be one invocation of SHA-256 (or SHA512, or SHA-3) with a salt, which is fairly meaningless unless the key/password contains a large amount of entropy (almost no passwords do.) It's much more important to know what algorithm they were actually using, e.g. scrypt, bcrypt or PBKDF2, and what the settings/work factors/iteration counts for them are/were. If a company is reluctant to disclose that, they're likely using something that's highly vulnerable to parallelization/efficient brute force cracking, regardless of what kind or size of salt was used.

StavrosK 13y ago
I like how everybody is optimistic. It could have been MD5!
- integraton 13y ago
  Since, AFAIK, it's built on Rails, that's unlikely. However, it's possible that it's SHA-1 since popular Rails auth solutions used that by default at the time the company was founded (2007), assuming that's what they started with and never switched from.
  - ukd1 13y ago
    I'd be very surprised if Rails didn't support upgrading the hash over time - anyone know if it does with has_secure_password?
    - integraton 13y ago
      Prior to 3.1, Rails didn't have built-in support for password hashing or user auth beyond http auth, so it was handled by libraries (like devise or authlogic), generated code (such as with restful-auth, which was popular in 2007), or custom code. I don't think it's very common for legacy codebases to be migrated to has_secure_password, but it's not impossible. There is not built in migration for has_secure_password, AFAIK. LivingSocial is a big enough company I wouldn't be surprised if their authentication code was all or mostly custom.

gdeglin 13y ago

It's actually very possible for hackers to still decode many of the passwords. An attacker could simply put together a dictionary of 10,000 common passwords then hash them against each user's salt value and see they they get a match for that user's password Hash. Assuming Hashes are stores as SHA-256, with a GPU hashing setup they'll be able to scan through 50 million users in very little time at all.

gruseom 13y ago
I have a dumb question about this. It was a smart question when someone asked me it the other day, but it's a dumb question now because I feel like I should know the answer and I don't. Why can't you get away with using some trivial but obscure modification of one of the standard fast hashing algorithms? It will be just as vulnerable as the standard algorithm, of course, once you know what it is. But now the attacker has to figure out which algorithm you modified and how you modified it. How do they do that? I get that this is a bad idea that won't work, blah blah security by obscurity and so on. But when I was asked why it doesn't work, I was unable to give a very satisfying answer.
- ukd1 13y ago
  It would work, but a) you might break the algorithm in ways that make collisions b) if your code is stolen in a breach, it's useless. Most people should use bcrypt with enough rounds to make it difficult to brute force. scrypt is also an option, though newer (good / bad: http://security.stackexchange.com/questions/26245/is-bcrypt-better-than-scrypt http://security.stackexchange.com/questions/26245/is-bcrypt-...).
- rajivm 13y ago
  Well if they don't have your source code, why modify the algorithm, you can just use sha1(password + user_salt + site_secret) -- that site_secret just made the sha1 unique to your site. Of course, if they have your source code, then it doesn't matter: they would have your 'site_secret' or your modified algorithm. Better would be not storing your site_secret in a accessible way (not on disk). Edit: See udk1 below -- he's right, sha1 is an outdated algorithm for this purpose. Poor example choice on my part.

fudged71 13y ago

Would encrypting the email addresses be feasible? They do seem to have a lot of value to hackers, but I'm not sure what the technical limitations would be for a user-base this large or with their functionality.

whichdan 13y ago
Encrypting would be pointless. Hashing would be possible, but then you break things like email notifications and password resets.
- umsm 13y ago
  Upon a password reset submit, check if the hash(email_submit) exists, if so, email the password reset instructions to the email_submit address :)
  - rozap 13y ago
    Still, notifications would be toast. Thought most email notifications are annoying, they can be useful (or crucial).
    - umsm 13y ago
      If you don't need email notifications, then it's not a problem. One nice feature from gmail/yahoo/outlook/etc.: temporary email addresses that forward to your email. This would solve the problem. Or, maybe alternative notification methods are preferred? If they wanted, a user can input an email address with a plus (if they're using gmail) and then receive notifications only on that. If the user wanted, then they could block all incoming messages that match that generated email.
- unclebucknasty 13y ago
  Why is encrypting pointless if you generate the equivalent of a private key in code? Of course, if the attacker also gets the code, then you're toast, but getting the code is not guaranteed. So, seems like you'd have some additional protection with encryption.

dcu 13y ago

it's well known that many users pick passwords like "password", "123456", "qwerty", etc... so I don't think cracking many of those passwords will be a problem

mdasen 13y ago

That's good. However, if a good proportion of people use one of the 1,000 most common passwords, then they can hack those accounts in the time it takes to compute 50M * 1,000 hashes. With CUDA, it seems that you can do hundreds of millions per second. At 100,000,000 per second, you could compute that in 500 seconds (under 10 minutes). http://www.golubev.com/hashgpu.htm http://www.golubev.com/hashgpu.htm - this claims into the billions per second. When were talking 5B tries per second, that means trying the most common 100,000 passwords against each of the 50M accounts in under 20 minutes. The most common 1,000,000 passwords against all 50M accounts in under 3 hours; the most common 10M passwords against all 50M accounts in a little over a day. Hashing is good, salting is better, but unless there was a work factor involved like PBKDF2, bcrypt, or scrypt, it seems like it's protection against people who don't know what they're doing more than against people who know what they're doing. I'm not the type to say that we need to protect against people who have the money to make ASICs (app-specific integrated circuits likely used by governments), but I do think protection against nVidia chips is warranted. Now, it's genuinely possible that by "hashed and salted", they mean they used bcrypt or PBKDF2 (and simply aren't giving details in the email). But, if it's a salted SHA1, I think phishing would be harder than cracking a substantial proportion of them.

EvanKelly 13y ago
Maybe I'm misunderstanding (entirely possible!) and I think your point still stands, but isn't it 50M * 1,000 hashes * # of possible salts? EDIT: Just realized that the salts have to be stored somewhere and the attacker probably grabbed those as well. I think that answers my question.
- mpyne 13y ago
  No, because the salt is stored with the password. Salts are used to defend against reversing a password hash into a password, but they don't appreciably impede bruteforcing passwords into hashes.
  - nwh 13y ago
    It does mean that for a large dictionary attack things will go a lot slower. Rather than one computing one hash and comparing it to 50M hashes, the same word must be hashed with 50M different salts and then compared with their respective hashes.

wglb 13y ago

Why would the attacker, if they got the passwords, not bother to look to the column just to the right and take the salts as well? Given that, the attacker can try hundreds of billions of password combinations per second.

chill1 13y ago
The point of unique salts is that even if all the user's passwords are the same, the end resulting hashes that are stored in the database, are different. So, let's say you wanted to hash your set of 50,000 different, commonly used passwords. You'd have to hash that list of 50k passwords for EACH individual user. So instead of 50,000 hashes... you have 50,000 x the total number of users.
- wglb 13y ago
  I am not following your logic here. What I am saying that if the attacker gets a row from the database that has the user's id, the password will be in a column labeled 'password'. Next column is likely to be the salt generated for that user's password, and let's say that this column name is 'salt'. With the salt and password for each user, you can run a dictionary across each combination at a furious rate.
StavrosK 13y ago
The attacker does, of course, have the salts as well, since they're part of the hash. I don't see how they can try hundreds of billions of password combinations per second, though.
- bcoates 13y ago
  http://securityledger.com/new-25-gpu-monster-devours-passwords-in-seconds/ http://securityledger.com/new-25-gpu-monster-devours-passwor... 25 late 2012 vintage GPUs gets you 180 billion MD5 tries per second. With a fairly modest budget you can rent a whole lot more GPU power than that. A little Googling gets me several companies offering password hash cracking as a service.

marshray 13y ago

We can expect 50% of the password hashes to be cracked in the first few minutes, 10% will never be cracked, and the 40% in between will survive with a roughly exponential decay.

malandrew 13y ago

I wouldn't be surprised if we eventually see a breach for a company where the attackers, after securing the DB of emails, goes on to email everyone informing them of the breach before the company does so and asking them to reset their passwords. This would give the attackers the old email of the person (which has likely been reused on other services) AND a new password that they also may already be using on some services or plan on using on other services in the future.