If companies such as Facebook store our passwords as hashes, when they are leaked how can this be a threat to the users? I thought of it because nowadays we do not have computational power to break those hashes, so how can a criminal use those hashes against the users?
4
-
2$\begingroup$ you put too much faith in computer security: krebsonsecurity.com/2019/03/… $\endgroup$– Richie FrameCommented Jun 11, 2019 at 0:22
-
4$\begingroup$ I'm voting to close this question as off-topic because it belongs to Security.SE due to its focus on the consequences of “leaks” and “breaches”. All in all, it is not cryptography as defined in the help center. $\endgroup$– e-sushiCommented Jun 11, 2019 at 13:56
-
$\begingroup$ There is a cryptographic question here about online vs. offline attacks which are frequently quantified in cryptography and often directly relevant to cryptography engineering. $\endgroup$– Squeamish OssifrageCommented Sep 19, 2019 at 20:31
-
$\begingroup$ I was thinking of reopening this and then migrating it, but it is "too old" for that - whatever that means. Oh well. $\endgroup$– Maarten Bodewes ♦Commented Sep 21, 2019 at 22:08
Add a comment
|
5 Answers
$\begingroup$
$\endgroup$
2
Not every company hashes passwords properly and not everyone chooses secure passwords. If you hash them poorly (i.e. if you do not use a password hash with salt, and simply use SHA-256), then you can use a dictionary attack where you hash a list of common passwords and compare them to the leaked hashes and try to find any matches. This way, you can "invert" the hash and find the password for a lot of users.
-
2$\begingroup$ That's not what a rainbow table is. But let's suppose the company had a serious security team, like Facebook does (setting aside, for the moment, how hopelessly corrupt their management is), and let's suppose they salt the password hashes and use argon2di like they should, and let's suppose they even use OPAQUE so that not even the argon2di password hash is stored on the server, per se. What then? There's still a relevant answer here—there's still a reason for the adversary to benefit from a leak of the authentication database. $\endgroup$ Commented Jun 10, 2019 at 14:35
-
$\begingroup$ @SqueamishOssifrage I removed the rainbow table mention. I'm interested in the "relevant answer" you're mentioning, because I don't know what it is... $\endgroup$– ConradoCommented Jun 10, 2019 at 16:36
$\begingroup$
$\endgroup$
Users have a habit of choosing passwords badly so that they can be guessed much more easily than cryptographic keys, requiring (say) only a trillion ($10^{12} \approx 2^{40}$) guesses on average instead of a duodecillion ($10^{39} \approx 2^{128}$, or thousand sextillion in the long scale) guesses on average. Users also have a habit of reusing passwords from site to site, like using the same password for Facebook and Gmail.
Suppose I'm trying to break into your Gmail. There's only a limited rate at which I can test guesses for your password. Even if I can narrow your likely passwords down to a trillion possibilities, I can't try more than a few passwords every second at Gmail—even if I had a colossal botnet around the world to avoid IP-based rate limits, and even if I did it in bulk to many targets to avoid account-based rate limits, I'd still be limited by network bandwidth.
But if Facebook's password database gets breached—even if they do everything right like using salts to thwart rainbow tables, using argon2id to raise the computational cost of testing a guess, using OPAQUE to thwart adversaries on the network—then I can try guesses without using the network. No more rate limits to work around. No more network bandwidth to worry about. No more botnet to manage. I can try guesses offline using my supercomputer cluster tucked away in my evil lair built into the simmering underbelly of a volcano powering my machinations with geothermal heat while sipping at my martini and cackling evilly.
And once I have confirmed a guess for your Facebook password I can try it at Gmail.
There are some mistakes that Facebook could do to make it worse:
Facebook could fail to salt their password hashes uniquely per user.
Then I can search for one of many passwords given their hashes even faster using multi-target attacks like rainbow tables[1] in parallel[2]; if the cost to find one password given its hash is $C$, the cost to find the first of $t$ passwords given their hashes is $C/t$, and the time to find them can be as little as $C/tp$, as long as my volcano supercomputer lair is parallelized $p \geq t^2$ ways.
Facebook could fail to use a costly password hash like argon2id, and instead use MD5.
Then the offline computational cost to test a single guess is as cheap as computing MD5, which costs a few hundred cycles on a typical CPU and negligible memory, in contrast to argon2id which can be scaled to cost billions of cycles and gigabytes of RAM and multiple CPUs in parallel according to the legitimate user's available resources. This lowers the cost $C$ to find one password and the cost $C/t$ to find the first of $t$ passwords.
In practice, Facebook probably doesn't offload the password hash to the user's computer, so they probably won't use argon2id with billions of cycles of CPU time and gigabytes of RAM and multiple CPUs in parallel, but they will probably use something more expensive to compute than MD5.
Facebook could use a hash that fails to have preimage resistance.
This one is a stretch because essentially no major hash function with advertised preimage resistance has ever been broken[3] (archived). But if Facebook—for some inexplicable reason—used 2-pass Snefru to hash passwords, then in principle there may be a shortcut to finding a password given its hash more cheaply than just trying passwords until one works[4].
Facebook could just accidentally log their passwords in cleartext.
Well, this one actually happened[5], but Facebook swears that the logs were visible only inside Facebook and that nobody breached Facebook and that nobody inside Facebook would ever dream of abusing insider information like that[6] (archived 2019-06-19), and disclosed it on a night of big news of a long-awaited drama in United States national politics[7].
answered Jun 10, 2019 at 23:46
$\begingroup$
$\endgroup$
I thought of it because nowadays we do not have computational power to break those hashes, so how can a criminal use those hashes against the users?
Breaking a hash algorithm requires a pre-image, second pre-image, or collision attack that is cheaper than brute force. (For full or partial outputs.) More generally, a broken algorithm is any algorithm for which there is an attack that requires less work compared to the standard set by the algorithm's security claims.
Cracking a password hash is the process of searching for the password(s) that produce the same output as one of the values from a leaked password database. This is either a guess-and-check process (trying different candidate passwords as input until we find a match) or, if salts are not used properly, a lookup against a precomputed table.
We may say an algorithm has $n$-bit security when we mean that all known attacks require at least as much work as $2^n$ brute-force evaluations of the function. Anything with at least 128-bit security will require more computing resources than anyone has access to.
Cracking weak passwords is feasible regardless of the security level of a hash function. You don't need the same amount of resources as a brute force attack against the hash function would. The computing power actually needed depends on how predictable a password is; it is inversely proportional to the probability of correctly guessing a person's password.
Password crackers can test as many candidate passwords per second as their budget permits. Unless a person uses an inhumanly strong password, password cracking will always require less effort than an attack on the cryptographic hash function itself will.
answered Jun 10, 2019 at 22:58
$\begingroup$
$\endgroup$
The "irreversibility" of hash functions (more technically known as their preimage resistance) means that if you have:
- An output value produced by a specified known hash function;
- No practical method for guessing likely inputs that produced that hash output;
...then the only way you could possibly recover what the input may have been is to somehow "run the hash function backwards" (so to speak) from the known output. And the goal of a hash function is to ensure there's no practical way to do that.
But if we have a situation where #2 is not true—where we have some other way of guessing the input, and it's a practical one with a good chance of success in reasonable time—then the attacker doesn't have to work backwards from the output; they can just hash lots of likely guesses and see if they get lucky and one of them produces matching output.
The reason password cracking works is because #2 is not true for human-picked passwords. Nearly all people, in practice, pick passwords that aren't that hard for a computer to guess, because:
- GPUs can compute popular hash functions at speeds in the billions/second;
- Developers are really bad at protecting their users' passwords, and too often use hash functions that weren't designed to resist GPU-based cracking;
- Most people aren't good enough at picking passwords to overcome an attack that makes billions of guesses per second.
answered Jun 11, 2019 at 9:24
$\begingroup$
$\endgroup$
Note that while it may not pose a threat to the user currently, due to hash functions being computational infeasible to invert. This may not be the case in the future. For example if quantum computers are used and an attacker has your SHA256 hashes and you have not changed your password. It’s better that the attacker has the least amount of information as possible.
If you don’t need to expose it, it would be wise not to.