2

is there any defense against this kind of attack?

https://youtu.be/7U-RbOKanYs?t=974

I know someone who uses a password encryption hashing that generates the same length of keys as in this video and it makes me worried that those keys are equally vulnerable? (I don't know what kind of encryption hashing is used, nor do I want to know)

*Does it help to increase the length of the encrypted hashed keys?*

As I understand the attack:

The attacker have somehow got a hold of the encrypted hashed keys, and also downloaded a big database of already cracked passwords & also downloaded some (or made own) rules for switching letters (a "mutator").

Then the attacker takes a solved password, mutates the password in all kinds of ways, then encrypts hashes the mutated passwords & simply compare the newly encrypted hashed keys with the encrypted hashed keys in the database, and if the encrypted hashed gibberish is the same then the attacker knows that the newly encrypted hashed key is the same as that entry in the database.

(PS. what's the name of this type of attack?)

5

First things first: passwords are not (or at least, never should be) encrypted. They are hashed, a one-way transformation that takes an arbitrary input of arbitrary length and produces a constant-length (for any given hash algorithm), deterministic (the same input always produces the same output), and high-entropy (hard to distinguish from random) digest (also simply called a hash). For cryptographically-secure hash functions, there is no way to tell, given a digest, what input string produced it (and of course, there may be an infinite number of possible inputs that would produce it, since there are infinitely many possible inputs but "only" a limited number - such as 2^256, for 256-bit hash functions - possible outputs). In other words, you cannot reverse a hash function. Additionally, any changes to the input of a secure hash function, be they large or just a single bit-flip, generally produce a dramatic change in the digest.

Due to that, the standard attack on password hashing has long been to hash a large set of candidate passwords with the same algorithm, and check if any of the outputs match the digests in the dumped collection. Originally, this could be done with large, pre-computed lookup tables (called "rainbow tables") where a password, if it was present in the rainbow table, could be identified from its hash easily (simply search the table for the same digest). To protect against that, password hashing algorithms began to incorporate a "salt", which is a random string of bytes that are generated uniquely for each user, and are combined with the user's password when hashing. This makes rainbow tables useless unless the attacker already knows the salt of the user they want to crack, and even if they do they can only crack that specific user's password and have to generate an entirely new set of hashes for each other password. It also means to users who use the same password will have different digests, as their salts will be different.

However, even salted passwords can fall prey to a simple brute-force attack, because secure hash functions are generally optimized for performance (many of the places they are used, such as HTTPS traffic, require that they be computationally inexpensive). Chips that are optimized for performing the same operations on many distinct pieces of data in parallel - which is exactly what GPUs (graphics processing units) do - can brute-force an enormous number of hashes in a very short time (high-end GPUs can compute billions of hashes per second, for some of the common hash functions). Very, very few users are going to select a password so rare it's not one of the first few billion attempted, so such an approach can crack most passwords in a few seconds, for the cost of a few hundred dollars of graphics card. To defeat this, people started using slow hash functions for password hashing. The simplest way to make a slow hash is to take a fast hash, feed its output (and the salt) back into itself, and do that a few thousand more times; this is the basis of the PBKDF2 function, and it can slow down password brute-forcing attempts by a few orders of magnitude. Over time, more advanced password hashing algorithms have been developed, which resist not only GPUs but even customized chips (FPGAs or ASICs) designed to do nothing but brute-force passwords as fast as possible. No resistance is perfect, of course - the server still has to be able to hash your password when you log in, which puts a limit on how expensive the hash function can be made - but it can be literally millions of times slower to brute-force passwords protected by a proper password hashing algorithm (such as scrypt or argon2) than by a single-iteration fast hash (such as SHA-256). In other words, trying "the first few billion possible passwords" for each user goes from taking 1 second to taking a few weeks. Getting even a single password becomes expensive; breaking thousands of them becomes nigh-impossible.


Now, to answer your questions:

Is there any defense against this kind of attack? Aside from what I mentioned above - use salt, use a slow hash function, and make it as expensive as possible to brute-force passwords - there's no way to truly prevent brute-force attacks. However, you can make brute-force attacks take so long to succeed that they are de facto impossible, if you can get your users to use passwords that the brute-forcing tool won't try within a reasonable timeframe. Simple permutations and common substitutions, like "password" to "Pa$sW0Rd", are easy for programs to try and therefore add little security, even though they'll get past the foolish "complexity" requirements many sites have. Using long passwords, generated with an element of genuine randomness, works much better. For example, a passphrase generation algorithm such as Diceware (online generator) can produce passphrases that aren't too hard to remember but are extremely strong. With reasonable length choices and generous estimates of cracking speed and technological progress, Diceware-style passphrases should be safe for at least a few decades (and potentially for centuries) even against an attacker who is doing nothing but try to crack that one passphrase using constantly-improving cutting-edge technology.

Does it help to increase the length of the encrypted keys? Not really. Leaving aside that they aren't "encrypted" at all, the strength of a password hashing function has very little to do with the length of its digest. Obviously you should not use extremely short digests, because then you have a high risk of collisions (two unrelated passwords that hash to the same thing, and either one would be accepted for that user), but all secure hash algorithms have a digest of at least 128 bits, which is plenty to avoid that particular risk. Longer digests do technically make the comparison step of the brute-forcing attack take longer, but the difference is irrelevant next to the time it takes to compute a slow password hash in the first place.

  • Thank you for writing this long & well explained answer! To clarify, when I said encrypted I probably meant hashed. – Sebastian Norr Sep 22 '18 at 20:56
  • 1
    You should mention, the "much longer" you refer to, can mean "sometime after the death of our sun" or longer, with a good randomly generated password. – Ben Sep 24 '18 at 15:34
  • 1
    @Ben Moore's Law is also exponential, so some of those "death of our sun" timelines aren't actually accurate because they assume that technology remains stagnant (I once computed that in roughly 300 years, a nation-state will probably be able to brute-force AES-256 in a day). Of course, that's still far and away long enough, and the only effective limit on the entropy is the size of the hash digest. – CBHacking Sep 25 '18 at 8:50
  • Some of the "death of the sun" timelines are energy-based as well, rather than time based. As in, "for an X-word password, you would need to consume the entire energy output of 6 of our suns, assuming this unrealistically efficient computer technology that doesn't even exist yet or is only theoretically possible". – Ben Sep 25 '18 at 16:05

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.