5 ms·

I dont understand. If you can use mixed-cased, letters and symbols you have 26 * 2 + 20 = 72 possible characters. 72^8 >> 1e9 It would still take more than 8

by mwytock 15y ago

I dont understand. If you can use mixed-cased, letters and symbols you have 26 * 2 + 20 = 72 possible characters. 72^8 >> 1e9 It would still take more than 8 days to brute force at 1 billion/sec. And using a longer password (16 chars?) would make this a very long time. Or is there other trick that makes this fast? Or, is it simply that people don't choose random, long passwords?

tptacek 15y ago
Secure password hashes don't protect users, and particularly not users who use one-time effectively-random passwords. Secure password hashes protect application developers from the disclosure of hundreds or thousands of user passwords from their database. It allows them to attest to their userbase "your password is cryptographically stored in a manner that makes them hard to break even by dedicated hardware; you should consider changing your password if it's weak and shared", instead of, "expect to see your password on Pastebin any day now".
- kragen 15y ago
  To clarify, I assume you mean that using secure password hashes instead of insecure ones does not help users who use one-time effectively-random passwords, because those users are already safe? That is true. However, it seems to me that the combination of an effectively-random password and password hashing does protect users, because their password is not effectively crackable in a situation like this. Additionally, there's a tradeoff between how secure your password hashing is and how much randomness users need to put into their password: every additional factor of 1000 in the iterations of the hash saves you a random character or two.
  - sunchild 15y ago
    I wish everyone could use complex, unique, strong passwords all the time, but some use cases just don't support it. For example, I have to type my Apple ID into my iPhone/iPad what seems like every 5 minutes in iOS. Without access to 1password or a similar tool, I just can't use a strong password. Even if I did, I couldn't change it as often as I'd like to. FWIW, I wish I could.
    - sliverstorm 15y ago
      security vs. convenience
      - sunchild 15y ago
        My point was that the choice is sometimes not left in the user's direct control. If I thought I could choose an absurdly strong password (e.g., to overcome the shortcomings of the developer's choice of SHA1), I would always do that – except if I'm going to need to enter that password from memory a bunch of times per day.
meroliph 15y ago
> Or, is it simply that people don't choose random, long passwords? That's always part of the problem.
getsat 15y ago
You're looking at more like 5+ billion/sec today. There was a listing of modern consumer video cards + their hashing capabilities posted on another HN story recently, but I can't find it.
- ahi 15y ago
  https://en.bitcoin.it/wiki/Mining_hardware_comparison https://en.bitcoin.it/wiki/Mining_hardware_comparison Not sure if this is what you were looking for or the particular hash bitcoin uses, but a $110 Radeon 5830 can get you around 250Mhash/s
  - angusgr 15y ago
    "Hashes" aren't interchangeable, they're an abstract concept. In this case, the thread is talking about the SHA-1 hash algorithm. AFAIK Bitcoin uses SHA-2 w/256-bit digests. So, actually, in this case the two happen to be related but different - SHA-1 being considered potentially flawed but not (yet) the stronger SHA-2. Also, the Bitcoin block headers that are hashed are (I think) 80 bytes (640 bits) long, salted passwords probably a bit shorter. Wikipedia says SHA-256 runs about 2/3 the raw throughput of SHA-1. You can the comparative rate yourself on any nix computer: $ openssl speed sha1 sha256 -snip- Doing sha1 for 3s on 16 size blocks: 7760096 sha1's in 2.99s Doing sha1 for 3s on 64 size blocks: 5502820 sha1's in 3.00s -snip= Doing sha256 for 3s on 16 size blocks: 5460366 sha256's in 3.00 Doing sha256 for 3s on 64 size blocks: 3169031 sha256's in 3.00s -snip- * So... about 2/3 faster. I don't know enough about crypto implementation, but I'd guess this ratio would scale roughly to the much faster GPU implementations as well.
    - woadwarrior01 15y ago
      Yes, I have 2 6950s, which together average to about 660MH/s on hashkill mining bitcoin, but when I tried MD5, IIRC they averaged to about 3200MH/s. I'd assume SHA1 to be slightly slower, but not much.
- spindritf 15y ago
  > You're looking at more like 5+ billion/sec today. Sounds about right http://blog.zorinaq.com/?e=43 http://blog.zorinaq.com/?e=43 And a few times more if it's md5.
Hawramani 15y ago
If my understanding is correct that's not the issue here. Hashes are meant to be one-way functions, the developer can easily check if a user's password matches the hash, but it should be practically impossible to deduce the password from the hash. What the user chose as their password should be irrelevant if using a good hash. [Edit: I stand corrected on the effect of password length.]
- rchowe 15y ago
  But there are rainbow tables, or tables of all of the MD5s/SHA1s/<insert favorite hash algorithm> for arbitrary strings. So the time's already sunk in. 8 days for one password is a very short amount of time comparatively (tiny for a botnet). If you use bcrypt, which you can force a certain complexity on, you can get that amount of time up much higher.
  - tptacek 15y ago
    Rainbow tables don't work even against amateurish salted hash schemes.
- Xk 15y ago
  SHA-1 is a reasonably good hashing algorithm, but for the sake of argument, I'll talk about an imaginary SHA-4 which is perfect in every respect. It will be a 4096 bit hash function which has no faster-than-bruteforce collisions or preimage attacks or second preimage attacks. Let's also assume that this perfect SHA-4 function is freakishly fast, say, a million times faster than SHA-1. Now, even though my imaginary SHA-4 function is perfect in every way, it would be strictly worse to use this for password hashing than SHA-1. Why? Because cryptographic attacks aren't the problem here. The problem is that the entropy of a user's password is very VERY small. So small, in fact, that attacks on passwords aren't done through cryptographic weaknesses, they are done by simply hashing everything someone might pick as a password and asking "did I get it right?". An attacker will repeat this process for a little while, and eventually they'll get the answer "YES, this user chose to make abc123 as their password!".
  - 15y ago

by mwytock 15y ago

tptacek 15y ago

Secure password hashes don't protect users, and particularly not users who use one-time effectively-random passwords. Secure password hashes protect application developers from the disclosure of hundreds or thousands of user passwords from their database. It allows them to attest to their userbase "your password is cryptographically stored in a manner that makes them hard to break even by dedicated hardware; you should consider changing your password if it's weak and shared", instead of, "expect to see your password on Pastebin any day now".

kragen 15y ago
To clarify, I assume you mean that using secure password hashes instead of insecure ones does not help users who use one-time effectively-random passwords, because those users are already safe? That is true. However, it seems to me that the combination of an effectively-random password and password hashing does protect users, because their password is not effectively crackable in a situation like this. Additionally, there's a tradeoff between how secure your password hashing is and how much randomness users need to put into their password: every additional factor of 1000 in the iterations of the hash saves you a random character or two.
- sunchild 15y ago
  I wish everyone could use complex, unique, strong passwords all the time, but some use cases just don't support it. For example, I have to type my Apple ID into my iPhone/iPad what seems like every 5 minutes in iOS. Without access to 1password or a similar tool, I just can't use a strong password. Even if I did, I couldn't change it as often as I'd like to. FWIW, I wish I could.
  - sliverstorm 15y ago
    security vs. convenience
    - sunchild 15y ago
      My point was that the choice is sometimes not left in the user's direct control. If I thought I could choose an absurdly strong password (e.g., to overcome the shortcomings of the developer's choice of SHA1), I would always do that – except if I'm going to need to enter that password from memory a bunch of times per day.

meroliph 15y ago

> Or, is it simply that people don't choose random, long passwords? That's always part of the problem.

getsat 15y ago

You're looking at more like 5+ billion/sec today. There was a listing of modern consumer video cards + their hashing capabilities posted on another HN story recently, but I can't find it.

ahi 15y ago
https://en.bitcoin.it/wiki/Mining_hardware_comparison https://en.bitcoin.it/wiki/Mining_hardware_comparison Not sure if this is what you were looking for or the particular hash bitcoin uses, but a $110 Radeon 5830 can get you around 250Mhash/s
- angusgr 15y ago
  "Hashes" aren't interchangeable, they're an abstract concept. In this case, the thread is talking about the SHA-1 hash algorithm. AFAIK Bitcoin uses SHA-2 w/256-bit digests. So, actually, in this case the two happen to be related but different - SHA-1 being considered potentially flawed but not (yet) the stronger SHA-2. Also, the Bitcoin block headers that are hashed are (I think) 80 bytes (640 bits) long, salted passwords probably a bit shorter. Wikipedia says SHA-256 runs about 2/3 the raw throughput of SHA-1. You can the comparative rate yourself on any nix computer: $ openssl speed sha1 sha256 -snip- Doing sha1 for 3s on 16 size blocks: 7760096 sha1's in 2.99s Doing sha1 for 3s on 64 size blocks: 5502820 sha1's in 3.00s -snip= Doing sha256 for 3s on 16 size blocks: 5460366 sha256's in 3.00 Doing sha256 for 3s on 64 size blocks: 3169031 sha256's in 3.00s -snip- * So... about 2/3 faster. I don't know enough about crypto implementation, but I'd guess this ratio would scale roughly to the much faster GPU implementations as well.
  - woadwarrior01 15y ago
    Yes, I have 2 6950s, which together average to about 660MH/s on hashkill mining bitcoin, but when I tried MD5, IIRC they averaged to about 3200MH/s. I'd assume SHA1 to be slightly slower, but not much.
spindritf 15y ago
> You're looking at more like 5+ billion/sec today. Sounds about right http://blog.zorinaq.com/?e=43 http://blog.zorinaq.com/?e=43 And a few times more if it's md5.

Hawramani 15y ago

If my understanding is correct that's not the issue here. Hashes are meant to be one-way functions, the developer can easily check if a user's password matches the hash, but it should be practically impossible to deduce the password from the hash. What the user chose as their password should be irrelevant if using a good hash. [Edit: I stand corrected on the effect of password length.]

rchowe 15y ago
But there are rainbow tables, or tables of all of the MD5s/SHA1s/<insert favorite hash algorithm> for arbitrary strings. So the time's already sunk in. 8 days for one password is a very short amount of time comparatively (tiny for a botnet). If you use bcrypt, which you can force a certain complexity on, you can get that amount of time up much higher.
- tptacek 15y ago
  Rainbow tables don't work even against amateurish salted hash schemes.
Xk 15y ago
SHA-1 is a reasonably good hashing algorithm, but for the sake of argument, I'll talk about an imaginary SHA-4 which is perfect in every respect. It will be a 4096 bit hash function which has no faster-than-bruteforce collisions or preimage attacks or second preimage attacks. Let's also assume that this perfect SHA-4 function is freakishly fast, say, a million times faster than SHA-1. Now, even though my imaginary SHA-4 function is perfect in every way, it would be strictly worse to use this for password hashing than SHA-1. Why? Because cryptographic attacks aren't the problem here. The problem is that the entropy of a user's password is very VERY small. So small, in fact, that attacks on passwords aren't done through cryptographic weaknesses, they are done by simply hashing everything someone might pick as a password and asking "did I get it right?". An attacker will repeat this process for a little while, and eventually they'll get the answer "YES, this user chose to make abc123 as their password!".
- 15y ago