Is there a way to reverse a crypt() in c?

Question

Not sure if this is possible but I want to be able to start with a string, and then figure out what the input must be into the crypt in order to get this string out.

Or maybe it's impossible, which would be the whole purpose of the thing anyways?

Yes, there is a salt in the code where I am trying this.

Answer 1

By design intent, crypt() is a one-way hash. As everyone has said, that means that the intent is that it would be computationally infeasible to discover a plaintext string that produces the same hash.

A couple of factors have an effect on that design intent.

1. Computation is a lot cheaper than it was when crypt() was designed. Worse, the rate at which computation got cheaper was not anticipated, so it is a lot cheaper now than it was ever imagined it could be.

2. DES hasn't held up as well as it was thought it would. It was probably the best choice given the public state of knowledge at the time, however.

3. Even if computation isn't yet cheap enough to do your own cracking, the cloud that is the internet has already done a lot of the work for you. People have been computing and publishing Rainbow Tables which make it possible to shortcut a lot of the computation required to reverse a particular hash. (Jeff had a blog post on rainbow tables too.) Salt helps protect against rainbow tables (because you would need a table set for each possible value of the salt), but the size of the salt used in the classic implementation of crypt() is only 12 bits so that isn't as huge a block as might be hoped.

Worse yet, for certain high-valued hash functions (like the LM hash invented for old Microsoft Lan Manager passwords but used for short password in all versions of Windows before Vista) nearly complete dictionaries of hashes and their inverses exist.

Answer 2

If it's an old implementation of crypt(3), using DES, then you can almost (but not quite) brute-force it.

In that scheme, the input is truncated to 8 characters, and each character to 7 bits, which means there's a 56 bit space of distinct passwords to search.

For DES alone, you can search the whole space in about 18 days on $10K worth of FPGAs (http://en.wikipedia.org/wiki/Data_Encryption_Standard#Brute_force_attack), so the expected time is 9 days. But I'm assuming you don't have $10K to spend on the problem. Give it a few more years, and who knows whether DES crackers will run in plausible time on a PC's GPU.

Even then, crypt(3) traditionally involves 25 rounds of DES, with slight modifications to the algorithm based on the salt, so you'd expect it to be at least 25 times slower to brute-force.

Newer implementations of crypt(3) are way beyond brute force, since they're based on better hash algorithms than the DES-based one that old crypt(3) used.

Of course if the string isn't random (e.g. if it's a password chosen by some human), then you may be able to get a much better expected time than brute force.