0
$\begingroup$

I have a 30000 user passwords and usernames stored in a table on a database in which the passwords are stored as hash where ,I need to guess the passwords for all users and I have the hash function which its output is 32 bit in length.

My questions is: How much time do I need to guess that if I use collision attack?

I am confused which is better pre-image attack or collision attack ? if the input to the hash function is 80 bits.

if collision is better, is this mean to look at 32 bits?

$\endgroup$
  • 5
    $\begingroup$ Collisions are irrelevant for attacking password hashes. You already have the hashes, so what you need is to find the pre-images for those hashes. $\endgroup$ – Xander Apr 15 '16 at 19:20
  • $\begingroup$ I have a table for hashs,if the order of collision o(2^n/2) which is better than pre-image i.e. is it better to break the algorithm it self if the output bits are less than the input ?? $\endgroup$ – Robin Apr 15 '16 at 20:31
  • $\begingroup$ I think the input for hash 80 bits, if to use pre-image to guess password that I know what its length and role to creat $\endgroup$ – Robin Apr 15 '16 at 20:34
  • $\begingroup$ Is this about a real-world system? If so, which one? I'd like to avoid it like the plague. $\endgroup$ – a CVn Apr 16 '16 at 13:14
  • $\begingroup$ @Xander Collisions aren't irrelevant for 32-bit hash. If you can find an input that produces the same output value, you get access to the system, even if it's not the original password used. $\endgroup$ – Stephen Touset Jun 15 '16 at 18:35
2
$\begingroup$

Generating collisions for a 32-bit hash is trivial; thanks to birthday paradox, the expected effort is only about 217 hash evaluations.

If you don't believe me, try running this Perl code:

use strict;
use warnings;
use Digest::SHA 'sha256';

my $message = "a";
my %preimages;
while (1) {
    my $hash = unpack("H8", sha256($message));
    print "$hash: $message, $preimages{$hash}\n" if $preimages{$hash};
    $preimages{$hash} = $message++;
}

After a second or so, it should start spewing out collisions for SHA256 truncated to 32 bits, like this:

63212655: hgwj, ever
14202469: ioaw, ehks
5e6655a3: isvc, gfub
62bd0444: jcgu, ifoz
dbdda724: jyen, ifph
3fbea896: keer, bmeq
2932fabe: mcdt, akcg
ee6816e2: mlgl, dmyo
82952ecc: nmbm, apqi
...

Finding preimages for a given hash is a bit harder, taking 232 hash evaluations on average, but still easily doable on a modern computer. Even my 10 year old laptop, running an inefficient Perl script like the one above, should be able to do it in a few hours; with a faster computer and a more efficient script, it should be doable in minutes if not seconds.

Also, the 232 hash evaluations is for finding a preimage for a single hash. If you have 30,000 hashes, you can trivially attack them all at the same time, reducing the expected time needed to find the first preimage by a factor of 30,000.

The expected time needed to find preimages for all the 30,000 hashes is, of course, more than that needed to find a single preimage, but only by a factor of about log(30,000) ≈ 10. So if your computer can find a preimage to a single hash in an hour, then testing all 30,000 hashes in parallel should give you the first preimage in about 0.1 seconds, and all of them in about 10 hours.

For example, I left a modified version of the script above (searching for preimages for preselected hashes instead of collisions) running in the background, and found the preimage hbwxaod for the 32-bit hash 0123abcd in a few minutes of parallel searching on multiple cores. (I also cheated a bit and picked a dozen similar looking target hashes instead of just one to speed up the search. This one was the first preimage I found.)

$\endgroup$
2
$\begingroup$

You'd still need to iterate over all the possible passwords to do this, using a brute force or dictionary attack (i.e. a pre-image attack with regards to the hash). That is, unless the hash algorithm used isn't one way; i.e. you can retrieve more information about the passwords. A 32 bit hash is not common, so this could be possible.

Fortunately most passwords do not have a very high entropy, especially if they are limited to 80 bits (information taken from the comments). However, I don't think they are just limited to 80 bits (which would take too much time to crack). Usually passwords aren't made up of control characters and such; you'd need to know how the 80 bits are encoded - i.e. which character encoding was employed. Probably you can at least bring it back to 70 bits by always keeping the highest bit to 0 (keeping just to ASCII, in other words).

One advantage of 32 bit hashes is that it isn't likely that a strong password hash was used. That means that testing the passwords could be pretty fast. A disadvantage would be that there may be multiple passwords that match a specific hash.

That's useful information to an attacker, who's just interested in gaining access instead of the actual password. If you need to know the exact password though you might have some trouble for some passwords. That said, 32 bit could be just enough to have relatively few of those.


From the information you've given this may just be feasible. It depends on too many other parameters such as the strength of the hash function and the restrictions on the password to calculate the time precisely. Given a strong hash function it's however still directly (and probably linearly) related to amount of possible passwords.

$\endgroup$
  • $\begingroup$ Even if we posit only 5 bits/character of entropy in the passwords (roughly equivalent to random single-case alphabetic passwords), 32 bits output hash seems to only allow for 6-7 character passwords before you start seeing collisions. Wouldn't that be the set you need to hash to have a high likelihood of finding a collision, if the hash (aside from outputting only 32 bits) at least has a uniform output distribution? Approaching that even as a brute force attack on a modern PC should be trivial. $\endgroup$ – a CVn Apr 16 '16 at 12:31
  • $\begingroup$ @MichaelKjörling If your goal is to find the exact password - instead of just one that matches the hash - then then collisions are only in the way of finding a correct one. If the passwords were randomly generated then you may never find a password with 100% certainty. Also see the first comment or Xander below the question. If you just need a password that hashes to the 32 bit value, yeah, trivial. $\endgroup$ – Maarten Bodewes Apr 16 '16 at 12:53
  • $\begingroup$ True, Maarten. I took the question to be about "finding a password that matches the hash", but I see how it could equally well be interpreted as "finding the password the user selected". However, with a 32-bit hash, I think it stands to reason that the latter is not possible to do with any reasonable degree of certainty, at least if the passwords were reasonably well chosen; there are just going to be too many candidate passwords that match the hash output. $\endgroup$ – a CVn Apr 16 '16 at 13:13
  • $\begingroup$ Yeah, that is my concern as well. You'd get a match pretty quickly, but this is not like finding a collision in, say, SHA-256. Of course most passwords are not random bit strings, and you could try the entire set against another service as well - if that service would allow it. $\endgroup$ – Maarten Bodewes Apr 16 '16 at 13:14
0
$\begingroup$

With a cryptographic hash function, reversing hashes amounts to trying potential inputs until you find an input that matches the hash. If you do find an input that hashes to the target, it is presumed to be the same input that was originally used (e.g. the user's password). In that case, the entropy and length of the input is useful to know since it can guide your search.

Regardless of its other strengths, 32 bits is too short an output for a hash to be strong. In this case, you can expect to find an input that hashes to a given output after a feasible number of attempts. Furthermore, there's no reason to expect that you will be finding the user's password. What you will find is a string that will be pass the same (weak) verification that the user's password passes. In this case it's not necessary to know much about the user's original password - if it's long you'll find a short counterpart.

$\endgroup$

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.