Classic scheme:

  1. Given password and hashing algorithm
  2. Generate salt
  3. Calculate hash=hashing(password, salt)
  4. Separately storing hash & salt

Checking password validity: comparing stored hash with calculated test_hash=hashing(test_password, salt). If hash=test_hash - password is ok, otherwise test failed.

Proposed scheme:

  1. Given password, cipher algorithm and predefined dictionary (e.g. set of digits {0,1,2,3,4,5,6,7,8,9})
  2. Generate salt
  3. Generate random test_phrase from our dictionary (e.g. only random digits, like test_phrase=32759823767865236451236647894678923897)
  4. Calculate hash=cipher(test_phrase) with key=keygen(password,salt)
  5. Storing hash and salt (no need to store test_phrase)

Checking password validity:

  • calculating test_phrase=decipher(hash) for a test_key=keygen(test_password,salt)
  • check if test_phrase consists only symbols/bytes of predefined dictionary (e.g. decrypted phrase are only digits, say if decrypted phrase is smth like: askjdfhasjkdfhasjkdhe-0123=jkasfhasjdfh - that means test failed, since some symbols are not digits)


What do you think about pros/cons for this proposed hashing scheme?

  • $\begingroup$ I'm pretty sure the classic scheme uses password,salt instead of password+salt. $\hspace{1.05 in}$ $\endgroup$ – user991 Jul 3 '15 at 8:14
  • $\begingroup$ Thanx guys, I've fixed $\endgroup$ – Barmaley Red Star Jul 3 '15 at 8:20

Essentially, instead of checking against a (salted) hash of a password, you suggest using the hash (since you can choose hashing = keygen) as a key to encrypt a kind of test value. The main question is whether this adds or reduces security.

  1. If you store the hash/key directly, the chance of a randomly chosen password hashing to the same value is $2^{-n}$, where $n$ is the length of the hash in bits.

  2. If you use the key to encrypt a string from the dictionary in your example (10 out of 256), the chance that a random key (from a password guess) decrypts the stored value to a valid $k$-bit string is $(10/256)^{k/8} = 25.6^{-k/8} \approx 1.5^{-k}$.

To have equivalent security you need to store a longer verification string. For example, to match the security of a 256-bit hash value, you'd need to encrypt a 439-bit value.

In addition, the whole process would allow an attacker to discard wrong guesses slightly faster than the verification process takes, since most encryption algorithms encrypt in blocks and if the first block is a mismatch, the whole thing must be.

That's without considering the inherent insecurity in using a complex scheme that relies on multiple primitives for its security.

You could get back to an equal length-to-security ratio by encrypting a known string (like a string of zeros) instead. The downside of complexity would remain, without a clear upside to compensate. It could be more resistant to a weak hash, but that might be difficult to prove.

  • $\begingroup$ Generous answer - I was looking for analysis something like yours - applause :) $\endgroup$ – Barmaley Red Star Jul 3 '15 at 8:48

Your proposal is not good. First, the checking procedure is wrong:

Checking password validity:

  • calculating test_hash=cipher(test_password+salt) for a given test_key=keygen(test_password+salt)
  • check if test_hash consisting only symbols/bytes of predefined dictionary (...)

I guess you meant:

  • calculating test_phrase=decipher(hash) with key test_key=keygen(test_password+salt)
  • check if test_phrase consists only of symbols/bytes of predefined dictionary (...)

Second, and most worryingly, the chances of an attacker to succeed are now greater. In the classic solution, the attacker could succeed either by guessing correctly the password or by finding a string such that hash(password+salt) = hash(string+salt). This is actually a pre-image attack, and should be extremely difficult if the hash function is cryptographically secure. In your proposal, however, the attacker could succeed either by guessing correctly the password or by finding a string such that decrypt(string+salt) consists only of predefined symbols. The probability would be approximately equal to sampling a random test-phrase that consists only of predefined symbols. Let $p$ be the ratio between the size of dictionary of predefined symbols and the size of the possible symbols, and $n$ the number of symbols in the test-phrase, then the probability is $p^n$. Assuming a dictionary of 10 symbols out of 256, and a cipher of 128 bits (16 bytes), then the probability is $(10/256)^{16} = 2.93 \cdot 10^{-23}$, which is not that low.

Third, the classic scheme only uses a hash function, but in your proposal you need an encryption scheme cipher and a key derivation function keygen (which BTW, are usually made of hash functions).

  • $\begingroup$ but succeeding of attacker to fit hash in dictionary doesn't mean revealing of password, huh? $\endgroup$ – Barmaley Red Star Jul 3 '15 at 8:26
  • $\begingroup$ @barmaley The security goal in this case is authentication of the user, not confidentiality of the password. $\endgroup$ – cygnusv Jul 3 '15 at 8:40

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.