Given a hash, salt, charset and password length, how do you get the password without brute-forcing it?

Question

I got that question on an exercise and I'm not sure what to answer.

Without conventional brute-forcing and without a rainbow table, how could I find out the password?

An improved brute-force algorithm is acceptable, but how could I improve it?

Answer 1

Assuming a decent hash function, the only way to find the password in this situation is to guess it. This is true for any cryptographic hash function: it's the meaning of the preimage resistance property. This is true for any cryptographic hash; password hash functions have additional properties (salt and slowness) that make it more expensive to verify guesses.

Rainbow tables work by precomputing the hash of many passwords and storing them in a way that allows quickly finding the password from the hash if the password is in the precomputed set. In other words, you make a lot of guesses in advance.

“Conventional brute-forcing” is an ambiguous term. It may refer to trying passwords in a naive order (e.g. by increasing length). But you're free to make guesses in any order. For example, it makes sense to try 123456, password and iloveyou before quszoy and nyoktw. So make sure that you try guesses in an intelligent order.

You cannot find the password in any other way by computational means, but you may be able to find it by external means, such as:

• Snooping: wait until the user enters their password and watch over their shoulder, listen to their keystrokes, …
• Spyware: plant a keylogger (physical or software) on the user's computer and wait until they enter their password.
• Data leak: read the post-it note on their monitor, or crack the bank safe and open the envelope.
• Man-in-the-middle: listen to the communication between the user's computer and the password-protected server while they're typing their password.
• Phishing: pretend to be the server system administrator or other authority figure and get the user to type their password on your computer instead of the legitimate one.
• Social engineering: offer the user a lot of money or a bar of chocolate. If it fails, apply wrench cryptanalysis (or a rubber hose if you're a stickler for tradition).