0
$\begingroup$

How many attempts does it take to crack (match) a 32-bit password hash from a database of 4 million password hashes?

Correct me if I'm wrong, but to crack a 32-bit password hash would take roughly 2^31 attempts, while the math for matching a 32-bit hash from 4 million hashes should take (2^31)/4M ~ 537 attempts.

However in reality, the 4 million passwords in the database are not unique, as certain combinations are used as common passwords. Thus, what would be a more accurate calculation of the above question?

| improve this question | |
$\endgroup$
  • 1
    $\begingroup$ Could you explain, in pseudo-code, exactly what you mean by "attempts" in the context of "matching a 32-bit hash from 4 million hashes". Finding a value that is known to exist in a list of 4 million values, depends on whether the list is already sorted or not, and does not depend of what kind of values are in the list or how they were generated. $\endgroup$ – Henrick Hellström Feb 17 '15 at 15:30
  • $\begingroup$ Answer: too few. $\endgroup$ – Joshua Feb 17 '15 at 16:40
  • $\begingroup$ What exactly do you have in mind, when you ask about a 32-bit password hash? I have never come across any system using such a short password hash. $\endgroup$ – kasperd Feb 17 '15 at 22:50
  • $\begingroup$ @HenrickHellström, attempts mean an attacker crafts a 32-bit hash and try to authenticate that value against a hash password database. You may add in your assumption on sort. $\endgroup$ – George Feb 18 '15 at 3:26
  • $\begingroup$ Are you assuming a straight-up hash of the password or is there salting going on? $\endgroup$ – mikeazo Feb 18 '15 at 13:11
3
$\begingroup$

Correct me if I'm wrong, but to crack a 32-bit password hash would take roughly 2^31 attempts, while the math for matching a 32-bit hash from 4 million hashes should take (2^31)/4M ~ 537 attempts.

It would take on average $2^{32}$ attempts to crack a single 32-bit hash.

If you've got 4 million unique hashes to test against then then each hash you generate you've got a $4,000,000(\dfrac{1}{2^{32}}) \approx \dfrac{1}{1073}$ chance of finding a matching one. So you're going to need to try on average $1073$ times.

Unless you know the distribution of passwords and which ones are more common than others and you incorporate that into your guessing, this is as accurate as it's going to get.

| improve this answer | |
$\endgroup$
  • 1
    $\begingroup$ $2^{32}$ attempts would enumerate the entire hash output space. It would take $2^{31}$ attempts to have a 50% chance of cracking a single hash. $\endgroup$ – Stephen Touset Mar 21 '15 at 15:56
  • $\begingroup$ I said $2^{32}$ on average. The mean number of attempts. $\endgroup$ – user13741 Mar 21 '15 at 17:18
  • 2
    $\begingroup$ $2^{32}$ attempts will give you a 100% chance at having cracked all hashes. $2^{31}$ attempts will have a 50% chance of having cracked particular hash, which is the mean. $\endgroup$ – Stephen Touset Mar 21 '15 at 21:10
  • $\begingroup$ No, that is the median probability. $\endgroup$ – user13741 Mar 22 '15 at 0:28
  • 4
    $\begingroup$ user13741 is right for this one. The reason is simple: If you hash different inputs, you can get the same hash value on several occasions. Basically, you got a $1/2^{32}$ probability for a success on every try. This is a geometric distribution, with estimated value at $2^{32}$ (if looking for one hash value). Subtracting $1$ from the exponent is applicable, when you brute force a key for a symmetric encryption, where you directly try out every possibility. For hashes, $2^{32}$ does not give you that $100\%$ chance. $\endgroup$ – tylo Mar 23 '15 at 13:54
1
$\begingroup$

It is not $\simeq 537\textrm{ or }1073$

It's close, but it's not accurate. Each hash attempt has a $ \frac{1}{2^{32}} $ chance of matching a single key, the probability of not matching any of the $4\cdot 10^6$ keys is $ \left(1-\frac{1}{2^{32}}\right)^{4\cdot 10^6} $, and since the average of the geometric distribution is the inverse of the probability of success we have:

$$ \frac{1}{1-\left(1-\frac{1}{2^{32}}\right)^{4\cdot 10^6}}=1074.\small 241\scriptsize 901\tiny 485213438\dots $$

and if your good with a 50% chance of failure then the median of the geometric distribution gives us (just rearranged from the above formula):

$$ \frac{\log_{1-\frac{1}{2^{32}}}{1/2}}{4\cdot 10^6}=744.\small 261\scriptsize 117\tiny 8682496203\dots $$

These numbers are accurate and precise.

For those of you who demand more precision:

#include <gmp.h>
#include <mpfr.h>
#include <stdlib.h>

void handle_oom() {
  /* safe clean up */
  /* for those who *demand* reliability in the face of uncertainty */
  /* for those who deem unconditional and immediate program termination to be unthinkably reckless */
  /* for those of us who deem the corruption of personal data to be a programming SIN */
  /* for the rest of us ... */
  exit(EXIT_FAILURE);//there is always religious hypocrisy...
}
void*alloc_func_ptr(size_t alloc_size) {void*result=malloc(alloc_size);if(result==NULL)handle_oom();return result;}
void*realloc_func_ptr(void*ptr,size_t old_size,size_t new_size){void*result=realloc(ptr,new_size);if(result==NULL)handle_oom();return result;}
void free_func_ptr(void*ptr,size_t size){free(ptr);}

int main(void) {
  mpfr_t result;
  mpfr_t a;
  mp_set_memory_functions(alloc_func_ptr,realloc_func_ptr,free_func_ptr);
  mpfr_set_default_prec(69);
  mpfr_init_set_ui(result, 2, MPFR_RNDN);//2

  mpfr_pow_ui(result, result, 32, MPFR_RNDN);//2^32
  mpfr_ui_div(result, 1, result, MPFR_RNDN);//1/2^32
  mpfr_ui_sub(result, 1, result, MPFR_RNDN);//1-1/2^32
  mpfr_pow_ui(result, result, 4000000,MPFR_RNDN);//(1-1/2^32)^4000000
  mpfr_ui_sub(result,1,result,MPFR_RNDN);//1-(1-1/2^32)^4000000
  mpfr_ui_div(result,1,result,MPFR_RNDN);//1/(1-(1-1/2^32)^4000000)
  mpfr_printf("%.19RNg\n", result);


  mpfr_init(a);
  //mpfr_set_ld(a, 0.367708147258652352659885967356423464025283, MPFR_RNDN);
  mpfr_set_ld(a, 0.5, MPFR_RNDN);//1/2
  mpfr_log(a, a, MPFR_RNDN);//log(1/2)
  mpfr_set_ui_2exp(result,1,32,MPFR_RNDN);//2^32
  mpfr_ui_div(result,1,result,MPFR_RNDN);//1/2^32
  mpfr_ui_sub(result,1,result,MPFR_RNDN);//1-1/2^32
  mpfr_log(result,result,MPFR_RNDN);//log(1-1/2^32)
  mpfr_div(result,a,result,MPFR_RNDN);//log(1/2)/log(1-1/2^32)
  mpfr_div_ui(result,result,4000000,MPFR_RNDN);//log(1/2)/log(1-1/2^32)/4000000
  mpfr_printf("%.19RNg\n", result);

  mpfr_clear(result);//because you never know where your code will run
  mpfr_clear(a);//some simple embedded hardware OSs might not reclaim the memory on their own...
  //and we wouldn't want some dumb rocket to fall out of the sky now do we...
  //because that's what happens when you get lazy with code

  return EXIT_FAILURE;//because life sucks, and your all going to die
  //plus if your reading this you really are a failure
  //go do something useful!
}

and remember: if you forget to add the "$\tiny\dots$" at the end of at least one number, you'r a liar, a damned liar.

| improve this answer | |
$\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.