1
$\begingroup$

(Hand moved from stackoverflow.com,due to suggestion)

Since breaking password hashes has become a new passtime for scriptkiddies, I thought of the problem and came up with a novel(?) idea.

  1. store the pass as offset+number instead of hash
  2. the number is a product of two large primes
  3. the password is converted into a number , offset is added and that prime is used to divide the number. If it divides AND the divisor is the larger of the two primes the password is correct.

by definition , each hash is unique and each password can be hashed in many different ways depending on the offset. Breaking one hash means you have to factor the number(which is hard), then find a word which corresponds to a number that is largerprime-offset (which is trivial).

To generate use function f() to turn password into a password-number (not important) , generate two random primes larger than 2^4096 or however much is enough. Take the larger prime and calculate prime-passwordnumber=offset. Multiply the primes to get "number". store number and offset.

To check. use function f() to turn password into a password-number, add offset to find prime. divide number with prime to get the other prime. Check that the first prime was the bigger of the two. If so, password was correct.

f() might be for example utf-8 encoding of the password understood as a large binary integer.

Improve this question
$\endgroup$
10
  • $\begingroup$ The limitation is always the entropy of the password. There is no way around that. $\endgroup$
    – CodesInChaos
    Jun 7, 2012 at 21:31
  • $\begingroup$ yes, I know that. $\endgroup$
    – Markus Mikkolainen
    Jun 8, 2012 at 7:23
  • $\begingroup$ Your "hash" is about 12288 bit long. That's 1.5 kByte per password. Also, you do not need to factor the number. Assuming that the passwords were uniformly distributed (and if your function f preserves that distribution) then -- if I'm not mistaken -- you can show that finding a valid password is equivalent to factoring. However, passwords are not uniformly distributed, so there is really nothing much one can say about the security. $\endgroup$
    – Maeher
    Jun 8, 2012 at 10:45
  • $\begingroup$ yeah i know it is big since it is not really a hash in the actual sense. and you do need to factor to break it. you dont need to factor to brute force it. $\endgroup$
    – Markus Mikkolainen
    Jun 8, 2012 at 10:58
  • $\begingroup$ There is no need to brute-force, you can use a dictionary attack, because passwords are not uniformly distributed. $\endgroup$
    – Maeher
    Jun 8, 2012 at 11:38

2 Answers 2

Reset to default
3
$\begingroup$

I don't see anything horribly wrong with your proposal. On the other hand, the obvious question would be "what advantage would this approach have over, say, PBKDF2 with a good salt"?

  • In your proposal, it is infeasible to recover the password from the hash (short of brute-force); that's also true of PBKDF2.

  • In your proposal, the hash is randomized (and so the same password doesn't always result in the same hash); that's also true of PBKDF2.

In addition, in your proposal, generating a hash is moderately expensive (it isn't cheap to find large random primes); with PBKDF2, it's no more expensive than validating a password. I can't see any reason why you'd want to make generating a hash an expensive operation.

Given that this proposal doesn't appear to have an advantage over well-accepted techniques, I can't recommend it.

Improve this answer
$\endgroup$
1
  • $\begingroup$ well the biggest difference is that you can actually feed in a very large password (pretty much any size) without having collisions. Also if needed you can make the cracking more difficult by only storing for example n-32 bits for the offset and multiply the work required to crack/check by 4 billion. $\endgroup$
    – Markus Mikkolainen
    Jun 8, 2012 at 7:22
2
$\begingroup$

Your scheme doesn't offer any advantage over good password hashing schemes¹. The best way to attack those hashes is guessing a password and going through the verification sequence, just like the legitimate server does. The same kind of attack is possible against your scheme.

¹ using many iterations and a salt

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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