Hacker News Reader

Comment by nickh9000 | Hacker News Reader

No, by all means share the MD5 hash of your passwords. After all it's a one way hash. /S

It's my understanding that even an MD5 hash of a not-terrible password is still virtually impossible to crack, is that wrong?

Here's an md5 sum of a not-that-great password I just made up. It's 14 characters long, but has plenty of guessable features. Is it crackable?

1cf016ea3cb1f2aa2ccb59c196d0e704

Yes, that is incorrect. A GPU accelerated tool like HashCat can crack that password with a fairly small hardware footprint. Here's an article involving a 25 machine cluster which would reverse your hash in about 12 minutes -- regardless of your password features. http://www.zdnet.com/article/25-gpus-devour-password-hashes-...

This isn't nation-state level cost. Individuals could afford this level of hardware. Many individuals have access to systems of this size, for example through botnets, schools, spare junk in the local IT department closet, etc.

It's very reversible.

Don't forget spinning up an AWS cluster for 12 mins would not cost too much.

Well, you would pay for the full hour regardless of how long the machines were up. GCP would give you too the minute pricing however. But your right, even a full hour is really cheap

Uhh, 14 characters long.

Call it even ~30^14 / 348 billion per second = 1,374,416,379 seconds. So, they can break passwords with some pattern to them, but not really brute force em.

That's only 43 years and it was only 25 GPUs. Bump that up to 12000 GPUs and you could do it in about a month.

It's also an unsalted hash, so you could brute force an unlimited number of passwords at the same time without additional resources. Someone with a budget of a few million dollars could break every password in the world in a month.

So in other words, definitely don't publicize unsalted MD5 hashes of your passwords.

We can't really store that many passwords. It's even just 30^14 = 500 exabytes per byte and MD5 is 16 bytes at a minimum so you need 8000+ exabytes = 8,000,000,000+ Terabytes.

Note: only "In the third quarter of 2016, approximately 144.6 million hard disk drives were shipped worldwide" aka something like all HDD ever produced might fit that much data.

PS: Plus that 30 was low balling for a full search space it's 26 (lower case letters) + 26 (upper case letters) + 10 (numbers) + some number of special characters. So, ~100^14 or ~20,907,515x as large aka 10^17 TB.

There's no need to store anything. You have a list of hashes you'd like to reverse. You compute the entire search space and compare each.

No storage, other than the hashes you're attempting to reverse -- which for a data dump from even a large site like Yahoo wouldn't be very large at all. Megabytes.

Not at the same hash rate. Sure you can do binary search, but 100^14 or even 30^14 such searches is not fast. So, it's about as fast if you want 2 passwords but not 2 billion passwords.

It wouldn't be a binary search, the values are already hashes, so you could do a hash table lookup very cheaply. MD5 isn't great by cryptological standards, but it is extremely robust by hash table standards.

While no extra resources might not have been strictly accurate, the lookup would be practically free compared to the time it takes to compute the hash.

In the example I gave the hashes don't fit on GPU's and for your hash table lookup you would need ~64GB of ram to do the hash table lookups. You can scale this across multiple machines but even the ideal case of 2 lookups to main memory * 100^14 is slow and thus expensive.

You don't have to store all of the possible passwords, just the hashes for all of the real passwords that you are trying to crack.

If you mean after generating a hash you can compare it to your list of hashes then that saves time for cracking every password, but it's slower than cracking one password. Assuming you wanted to crack every Facebook password this way, that's not going to fit into cache and a binary search into RAM is actually rather slow. Yea, you could have more computers doing just this, but it's much slower than computing the hash in the first place.

You wouldn't need to do a binary search. The values are already MD5 hashes. You could do a hash table lookup in just a few CPU cycles since computing the hash is free.

Good point, though at a minimum you need to touch main memory twice which is 200+ clock cycles. And in practice that O(1) has an much worse constant factor.

Keep in mind article is from 5 years ago.

Sure, but "25 machine cluster which would reverse your hash in about 12 minutes -- regardless of your password features." is clearly wrong as GPU's are not that much faster and the article is talking about 25 GPU's.

You're right, that should read "25 machine cluster which would reverse your hash in about 12 minutes -- assuming similar password features"

In reality while that would be really easy to crack (measured in minutes as others pointed out).

However, any possible password with a standard printable ASCII character set will typically be found in Rainbow tables up to 10 characters long making expensive cracking unnecessary. [not quite right see edit]

Rainbow tables are just giant tables where the key is the hash and the value is the string that generated it.

However, your example being 14 characters long is a bit long to be in most readily available rainbow tables.

This is why using salts and peppers are incredibly important regardless of what hash you use.

Edit: minor(ish) correction to the previous sentence. Full alphanumeric with punctuation and digits is available readily in smaller password lengths but the 10 character long datasets seem to be mostly only lower case characters and digits.

>However, any possible password with a standard printable ASCII character set will typically be found in Rainbow tables up to 10 characters long making expensive cracking unnecessary.

Umm what? Even assuming a limited set of ASCII i.e. Base64, on what magical medium do you suppose a 64^10 rainbow table is stored?

Any medium really. Rainbow tables are compressed (by throwing away most of the hashes). The amount you throw away determines how long it takes to crack.

For example, A rainbow table might use chain lengths of 10,000. This means that for every 10,000 hashes calculated, only 1 (really 2) are kept. Each chain ends up as a row in the table, which is then sorted. When cracking, the target hash is hashed and reversed up to 10,000 times looking through the table.

The more compression the less space needed, but longer look up. The original Windows XP rainbow table cracking CD published along with the Rainbow table paper was only ~500Mb, but was able to crack pretty much every windows password.

An md5 rainbow table for lower alphanumeric which covers passwords of length 9 is 63gb. Length 10 is 316gb. You can see where this is going. It's important to note the caveat upfront; lower case-only plus numbers. No upper case, no symbols.

http://project-rainbowcrack.com/table.htm

That is just a rainbow table, but there are many others. By modifying the chain length, you can make the table as arbitrarily small. The example commands on that site use a chain length of 3800, but it could be raised to 1 million.

> However, any possible password with a standard printable ASCII character set will typically be found in Rainbow tables up to 10 characters long making expensive cracking unnecessary.

Really? Storing every possible 10 character long printable ASCII password plus its MD5 hash would require approximately 1.5 zettabytes[1].

[1] 95^10 * (16+10)

Rainbow tables are formed by chains of passwords and their hashes. The rainbow table only includes the ends of the chains, so you can throw away the middle of the chain.

Rainbow tables are a tradeoff between storing every hash, and generating them during cracking. You get to pick how much space you want to spend to speed up cracking.

If you know the md5 hash, why not login with another password that generates the same hash value? Does it actually need to be the same passord?

Yes, that will also work, hence why rainbow tables don't need to contain more entries than the possible set of hashes.

That's called a collision

It will work but a common reason to crack passwords is because people use the same password on multiple sites. Getting the wrong value may work to log into that specific site but will not work where the user the real password elsewhere. (unless that other place is using the same hash algorithm)

hunter2hunter2

No. Just for reference. :)

That's pretty much correct, yeah. Due to exponentiation, length is almost everything in password security. Which means there's going to be a bunch of lengths at which brute force cracking is trivial, and then a very sharp rise in complexity, after which brute force cracking quickly becomes astronomical, and then absolutely impossible.

If you look at the current cracking benchmarks of GPUs (https://gist.github.com/epixoip/a83d38f412b4737e99bbef804a27...), there is an easily quantifiable difference between bcrypt and MD5: 21 bits. (https://www.wolframalpha.com/input/?i=log2(200*%5E9)-log2(10...)

That means under current GPU architecture, bcrypt is basically like "adding 3-4 characters (or 1.5 diceware words)" for free to your password. Can you basically just add 3-4 characters to your password? Sure, but not without user friction, and certainly you can't think that way as the developer of the system, because you're trying to give a small leg up to even the most vulnerable by salting and bcrypt/PBKDF2/Argon hashing.

What about theoretical limits? Well, there is another way to approach this: Landauer's principle (https://en.wikipedia.org/wiki/Landauer%27s_principle), which considers the theoretical minimum energy of a bit flip of information - so this even covers future computing technologies. Even if you used up all available mass-energy in the entire sun, it is only theoretically possible to perform 2^225.2 operations (https://security.stackexchange.com/questions/6141/amount-of-...). 225 bits of entropy is roughly a 35-character (printable ASCII) password.

(Note that you can't do this with MD5 - it has only a 128-bit hash space, before preimage attacks, the best of which lowers it to 123 bits).

So the lesson is: use slow hashes to give some protection to the vulnerable and people whose password complexity is "on the edge". Use a password manager so that the rest of your passwords can be comfortably > 128 bits in complexity, without reuse. And then forget about passwords because after that, every other part of the security system becomes more important.

A fantastic overview - clear and informed. Thanks very much for this.

I see a lot of people saying how easy it would be to crack this, but I don't see it cracked...

"Very easy to crack this! You just need a bajillion dollars, 5000 AWS instances and a couple minutes!"

Not surprised why no one tried yet.

I think it's a reasonable point. There's lots of armchair experts saying that md5 is broken, unusable, and anyone can reverse it, and here we are 14 hours later and nobody has proven it. Given that the claim was 12 minutes on a 25 machine cluster, that would imply 300 minutes of compute time which is 6 hours. This is hacker news, if it's not going to be done here, then no armchair enthusiasts are going to do it.

If someone can point me towards the tools and how to set it up, I'll leave my gtx1070 at it overnight and see.

https://hashcat.net/hashcat/

I haven't used it, but FAQs, Forums, wikis, and tutorials are all out there.

I will give it a try this weekend, thanks!

Even SHA512 and bcrypt, totally uncrackable! /S

Every time someone says or writes "bcrypt", the GPU prices go up $10.

Gotta keep those hashcat farms in business :-)

Reply on news.ycombinator.com