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

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.

Answer 2

That function being one-way is the backbone of every password scheme in the world. If anybody here were to answer "yes, and here's how..", the government would be forced to immediately delete their comment, go burn their house down, and wisk them away to an undisclosed location.

In short, no.

Answer 3

No it's not possible take a look at this site (assuming you are using the GNU C library) http://www.gnu.org/s/libc/manual/html_node/crypt.html

The way that the crypt is salted will pretty much guarantee that what you're trying to do isn't going to work.

Answer 4

No, that's the idea behind one way hash functions, but you can use google to help you in some cases.

To answer to a comment to this answer (google won't help if there's a salt) I say: yes and no. The salt increases the solutions' space, making the creation of a full dictionary less easy (because for each word you have to compute and store one crypted version for each possible two-letter salt). If you assume the internet to be a giant database, and google its index, what google does is to search if there's somewhere the occurrence of the encrypted string around in the web. The presence of salt reduces the chance you will find it, but if you are lucky enough that the occurrence is present, and it is also together with the cleartext, then you have the password.

See also this article on slashdot.

Concluding: the salt will reduce the chance of finding that specific encrypted string around on the web, true, but google is indifferent to any amount of salt, and can still help somehow if you happen to be lucky (as it was for the case I gave).

Answer 5

Nope .. it's a one-way function.

Answer 6

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.