5 ms·

I work on an enterprise infosec tool that just demonstrated 48 trillion MD5s per second using AWS GPUs. Hashed passwords are cracked so easily it is a minor ob

I work on an enterprise infosec tool that just demonstrated 48 trillion MD5s per second using AWS GPUs. Hashed passwords are cracked so easily it is a minor obstacle at this point. It is a question of when not if a hash table is fully cracked.

dhritzkiv 7y ago
MD5 is one thing as a password can be retrieved from a hash table. But pulling out passwords from a hashed + salted value (e.g. via bcrypt) is many orders of magnitude more infeasible, no?
- bredren 7y ago
  I would be impressed if SO's user password table is in bcrypt.
  - dhritzkiv 7y ago
    What makes you say that? bcrypt's been the defacto best practice for user password "storage" for probably 10 years now. MD5's been known to be inadequate for much longer. Even if they had a legacy implementation in MD5, gradually migrating from storing MD5 hashes to storing bcrypt hashes is trivial to do.
    - bredren 7y ago
      From what I understand, many systems do not choose to implement strong hashing algos.
      - cyphar 7y ago
        Even PHP's hash_function uses scrypt. Yes, some people explicitly decide to hash everything with sha1 but nothing you or I do will ever be able to stop them.
  - gpvos 7y ago
    I would be disappointed if such a high-profile and technically savvy site would be using anything less.
- dagenix 7y ago
  Salting was originally important as a defense against rainbow tables - which are more or less obsolete with GPUs that can crank through trillions of hashes per second. The real reason that bcrypt is a better way to store a password isn't just because it uses a salt - it's because its designed to be slow and to use a bunch of memory which makes it much harder to brute force.
stephenr 7y ago
And how does it do on hashes that are not known to be useless, eg bcrypt or argon2?
- bredren 7y ago
  It is running on top of hashcat, and at the above-mentioned compute it was benchmarking 45 million bcrypts per second. At that point it is more about the attack plan than the compute. https://imgur.com/a/DXQMsM1 https://imgur.com/a/DXQMsM1 edit: here is the demo video: https://www.youtube.com/watch?v=KnD4f8N1_OE https://www.youtube.com/watch?v=KnD4f8N1_OE
  - lucb1e 7y ago
    "X bcrypts per second" is completely meaningless. What was the bcrypt setting? With the right setting, it would not be more than 1 bcrypt per century, or with the wrong setting, an almost equivalent rate to md5. It depends. More meaningful would be the speedup compared to a single CPU core, which is what the developers (should) benchmark against. They should make it as slow as possible, so if their system can do bcrypt with a cost of 15 in 0.1 seconds, they should set either that or cost 16. (Much more than 0.2s might be annoying to users or be a DOS vector.)
    - lazyjones 7y ago
      > With the right setting, it would not be more than 1 bcrypt per century You can't really call that a "right" setting when it takes at least as long to log in...
      - lucb1e 7y ago
        Right was meant as necessary to achieve that effect (sorry, English is not my native language). Obviously this is not a recommendation but just to point out that its configuration ranges from negligible to (on today's computers) forever.
        7y ago
cyphar 7y ago
Well, nobody should be using MD5 (nor should they have been using it 20 years ago with the introduction of bcrypt). In fact, nobody should be using any hash function that was designed for speed (such as the SHA family) because you don't want fast hashing of passwords. Modern cryptographic hash functions that are tailored for password hashing (such as scrypt or Argon2) are much harder to brute-force and have tunable knobs to allow you to increase the memory or CPU hardness. Obviously you cannot be safe forever but if you have a database dump of Argon2id-hashed passphrases with very strong parameters you aren't going to break it any time soon.
- bredren 7y ago
  There are plenty of publicly leaked hash tables running MD5 and the like. Just because modern hash functions exist does not mean they are in use. [1] Also you do not need the hash table of a hardened system to get useful passwords. You need a reused password from a weak one. [1] https://hashes.org/leaks.php https://hashes.org/leaks.php
  - pathseeker 7y ago
    >There are plenty of publicly leaked hash tables running MD5 and the like. Not related to stackoverflow though. >You need a reused password from a weak one. If the weak password is already public, what is gained by finding out that it's a weak password in a strong DB? You've just described a dictionary attack.
    - bredren 7y ago
      My mention of MD5 was just a benchmark reference. I can see from the downvotes the very idea that it is in regular use as triggering for some folks—-but md5 and other weak hashing algos are not just in obscure anime forums but in systems everywhere. “They don’t like to think it be like it is, but it do.” And it isn’t about md5 hash rate it’s about the ease of cracking in general due to low cost of compute. If the SO password hash has leaked even in bcrypt its going to be attacked and many strong passwords will be broken. If they are reused elsewhere, important email addresses will be attempted elsewhere. Don’t reuse passwords.
thaumasiotes 7y ago
> It is a question of when not if a hash table is fully cracked. ...? At 48 trillion hashes / second, you could get the entire hash space in as little as 224 quadrillion years. Of course, if you had any collisions, it would take longer. A lot longer. This suggests that strong passwords are still just as strong under md5 as under a more modern hash. No? Use of md5 is a problem because people use passwords that are easy to guess, not because you can enumerate the hash space. The one-way-ness is as secure as ever.
- AstralStorm 7y ago
  No, MD5 has about 18 bit collision strength. Combined with predictable salting practice, this is crackable with a calculator. Welcome to Merkle-Damgard construction allowing any prefix or suffix. Given random salt (random placed or mixed) or HMAC, you have to use the more complex preimage attack at 123 bits. This is crackable with a medium sized botnet or a supercomputer. 48 THash is an underestimate. Specialized hardware easily surpasses this, even FPGA does. SHA1 salted is a tougher customer with 60-64 bit collision resistance meaning you probably cannot crack it with your calculator. However, it is still prone to length extension meaning predictable salting has this much strength.
  - thaumasiotes 7y ago
    At 123 bits, you're five bits short of the 128 bits I calculated with. I don't think a medium sized botnet can rise to the level of doing 8 quadrillion years of work within your lifetime. What problem are you trying to solve? As I understand it, we're discussing enumerating the hash space, such that: 1. You are given a hashed value, such as 2b0f4e60b80da7ef1e84573d764f1bf4 . 2. The value is someone's hashed password. You need to find any string which hashes to this particular fixed value, but you don't know of any such string to start with. You can do this by brute force, but it will take you a long, long time. The problem is NOT: 1. You have a string which hashes to a particular value. 2. You want other strings which hash to the same value. And it also isn't: 1. You have a string which, with an unknown prefix, hashes to a particular known value. 2. You want to identify hashes which represent the same string with other prefixes applied. I don't see where salting is relevant to the question. It's a defense against the phenomenon that cracking one user's password automatically also cracks everyone else who uses the same password (since, without salting, they all have the same hash), but it isn't a defense against having your password cracked by a targeted attack (since, in a targeted attack, there are no other hashes to be collateral damage). Why did you bring it up? What attack are you thinking of?

dhritzkiv 7y ago

MD5 is one thing as a password can be retrieved from a hash table. But pulling out passwords from a hashed + salted value (e.g. via bcrypt) is many orders of magnitude more infeasible, no?

bredren 7y ago
I would be impressed if SO's user password table is in bcrypt.
- dhritzkiv 7y ago
  What makes you say that? bcrypt's been the defacto best practice for user password "storage" for probably 10 years now. MD5's been known to be inadequate for much longer. Even if they had a legacy implementation in MD5, gradually migrating from storing MD5 hashes to storing bcrypt hashes is trivial to do.
  - bredren 7y ago
    From what I understand, many systems do not choose to implement strong hashing algos.
    - cyphar 7y ago
      Even PHP's hash_function uses scrypt. Yes, some people explicitly decide to hash everything with sha1 but nothing you or I do will ever be able to stop them.
- gpvos 7y ago
  I would be disappointed if such a high-profile and technically savvy site would be using anything less.
dagenix 7y ago
Salting was originally important as a defense against rainbow tables - which are more or less obsolete with GPUs that can crank through trillions of hashes per second. The real reason that bcrypt is a better way to store a password isn't just because it uses a salt - it's because its designed to be slow and to use a bunch of memory which makes it much harder to brute force.

stephenr 7y ago

And how does it do on hashes that are not known to be useless, eg bcrypt or argon2?

bredren 7y ago
It is running on top of hashcat, and at the above-mentioned compute it was benchmarking 45 million bcrypts per second. At that point it is more about the attack plan than the compute. https://imgur.com/a/DXQMsM1 https://imgur.com/a/DXQMsM1 edit: here is the demo video: https://www.youtube.com/watch?v=KnD4f8N1_OE https://www.youtube.com/watch?v=KnD4f8N1_OE
- lucb1e 7y ago
  "X bcrypts per second" is completely meaningless. What was the bcrypt setting? With the right setting, it would not be more than 1 bcrypt per century, or with the wrong setting, an almost equivalent rate to md5. It depends. More meaningful would be the speedup compared to a single CPU core, which is what the developers (should) benchmark against. They should make it as slow as possible, so if their system can do bcrypt with a cost of 15 in 0.1 seconds, they should set either that or cost 16. (Much more than 0.2s might be annoying to users or be a DOS vector.)
  - lazyjones 7y ago
    > With the right setting, it would not be more than 1 bcrypt per century You can't really call that a "right" setting when it takes at least as long to log in...
    - lucb1e 7y ago
      Right was meant as necessary to achieve that effect (sorry, English is not my native language). Obviously this is not a recommendation but just to point out that its configuration ranges from negligible to (on today's computers) forever.
      - 7y ago

cyphar 7y ago

Well, nobody should be using MD5 (nor should they have been using it 20 years ago with the introduction of bcrypt). In fact, nobody should be using any hash function that was designed for speed (such as the SHA family) because you don't want fast hashing of passwords. Modern cryptographic hash functions that are tailored for password hashing (such as scrypt or Argon2) are much harder to brute-force and have tunable knobs to allow you to increase the memory or CPU hardness. Obviously you cannot be safe forever but if you have a database dump of Argon2id-hashed passphrases with very strong parameters you aren't going to break it any time soon.

bredren 7y ago
There are plenty of publicly leaked hash tables running MD5 and the like. Just because modern hash functions exist does not mean they are in use. [1] Also you do not need the hash table of a hardened system to get useful passwords. You need a reused password from a weak one. [1] https://hashes.org/leaks.php https://hashes.org/leaks.php
- pathseeker 7y ago
  >There are plenty of publicly leaked hash tables running MD5 and the like. Not related to stackoverflow though. >You need a reused password from a weak one. If the weak password is already public, what is gained by finding out that it's a weak password in a strong DB? You've just described a dictionary attack.
  - bredren 7y ago
    My mention of MD5 was just a benchmark reference. I can see from the downvotes the very idea that it is in regular use as triggering for some folks—-but md5 and other weak hashing algos are not just in obscure anime forums but in systems everywhere. “They don’t like to think it be like it is, but it do.” And it isn’t about md5 hash rate it’s about the ease of cracking in general due to low cost of compute. If the SO password hash has leaked even in bcrypt its going to be attacked and many strong passwords will be broken. If they are reused elsewhere, important email addresses will be attempted elsewhere. Don’t reuse passwords.

thaumasiotes 7y ago

> It is a question of when not if a hash table is fully cracked. ...? At 48 trillion hashes / second, you could get the entire hash space in as little as 224 quadrillion years. Of course, if you had any collisions, it would take longer. A lot longer. This suggests that strong passwords are still just as strong under md5 as under a more modern hash. No? Use of md5 is a problem because people use passwords that are easy to guess, not because you can enumerate the hash space. The one-way-ness is as secure as ever.

AstralStorm 7y ago
No, MD5 has about 18 bit collision strength. Combined with predictable salting practice, this is crackable with a calculator. Welcome to Merkle-Damgard construction allowing any prefix or suffix. Given random salt (random placed or mixed) or HMAC, you have to use the more complex preimage attack at 123 bits. This is crackable with a medium sized botnet or a supercomputer. 48 THash is an underestimate. Specialized hardware easily surpasses this, even FPGA does. SHA1 salted is a tougher customer with 60-64 bit collision resistance meaning you probably cannot crack it with your calculator. However, it is still prone to length extension meaning predictable salting has this much strength.
- thaumasiotes 7y ago
  At 123 bits, you're five bits short of the 128 bits I calculated with. I don't think a medium sized botnet can rise to the level of doing 8 quadrillion years of work within your lifetime. What problem are you trying to solve? As I understand it, we're discussing enumerating the hash space, such that: 1. You are given a hashed value, such as 2b0f4e60b80da7ef1e84573d764f1bf4 . 2. The value is someone's hashed password. You need to find any string which hashes to this particular fixed value, but you don't know of any such string to start with. You can do this by brute force, but it will take you a long, long time. The problem is NOT: 1. You have a string which hashes to a particular value. 2. You want other strings which hash to the same value. And it also isn't: 1. You have a string which, with an unknown prefix, hashes to a particular known value. 2. You want to identify hashes which represent the same string with other prefixes applied. I don't see where salting is relevant to the question. It's a defense against the phenomenon that cracking one user's password automatically also cracks everyone else who uses the same password (since, without salting, they all have the same hash), but it isn't a defense against having your password cracked by a targeted attack (since, in a targeted attack, there are no other hashes to be collateral damage). Why did you bring it up? What attack are you thinking of?