[security] Is it possible to decrypt SHA1

Is it possible to decrypt(retain the actual string) the password which is saved in db using SHA1 algorithm.

Example:If password is "password" and it is stored in db as "sha1$4fb4c$2bc693f8a86e2d87f757c382a32e3d50fc945b24",is any chance to retain the same "password"(string) from "sha1$4fb4c$2bc693f8a86e2d87f757c382a32e3d50fc945b24"

SHA1 is a one way hash. So you can not really revert it.

That's why applications use it to store the hash of the password and not the password itself.

Like every hash function SHA-1 maps a large input set (the keys) to a smaller target set (the hash values). Thus collisions can occur. This means that two values of the input set map to the same hash value.

Obviously the collision probability increases when the target set is getting smaller. But vice versa this also means that the collision probability decreases when the target set is getting larger and SHA-1's target set is 160 bit.

Jeff Preshing, wrote a very good blog about Hash Collision Probabilities that can help you to decide which hash algorithm to use. Thanks Jeff.

In his blog he shows a table that tells us the probability of collisions for a given input set.

As you can see the probability of a 32-bit hash is 1 in 2 if you have 77163 input values.

A simple java program will show us what his table shows:

public class Main {

    public static void main(String[] args) {
        char[] inputValue = new char[10];

        Map<Integer, String> hashValues = new HashMap<Integer, String>();

        int collisionCount = 0;

        for (int i = 0; i < 77163; i++) {
            String asString = nextValue(inputValue);
            int hashCode = asString.hashCode();
            String collisionString = hashValues.put(hashCode, asString);
            if (collisionString != null) {
                collisionCount++;
                System.out.println("Collision: " + asString + " <-> " + collisionString);
            }
        }

        System.out.println("Collision count: " + collisionCount);
    }

    private static String nextValue(char[] inputValue) {
        nextValue(inputValue, 0);

        int endIndex = 0;
        for (int i = 0; i < inputValue.length; i++) {
            if (inputValue[i] == 0) {
                endIndex = i;
                break;
            }
        }

        return new String(inputValue, 0, endIndex);
    }

    private static void nextValue(char[] inputValue, int index) {
        boolean increaseNextIndex = inputValue[index] == 'z';

        if (inputValue[index] == 0 || increaseNextIndex) {
            inputValue[index] = 'A';
        } else {
            inputValue[index] += 1;
        }

        if (increaseNextIndex) {
            nextValue(inputValue, index + 1);
        }

    }

}

My output end with:

Collision: RvV <-> SWV
Collision: SvV <-> TWV
Collision: TvV <-> UWV
Collision: UvV <-> VWV
Collision: VvV <-> WWV
Collision: WvV <-> XWV
Collision count: 35135

It produced 35135 collsions and that's the nearly the half of 77163. And if I ran the program with 30084 input values the collision count is 13606. This is not exactly 1 in 10, but it is only a probability and the example program is not perfect, because it only uses the ascii chars between A and z.

Let's take the last reported collision and check

System.out.println("VvV".hashCode());
System.out.println("WWV".hashCode());

My output is

86390
86390

Conclusion:

If you have a SHA-1 value and you want to get the input value back you can try a brute force attack. This means that you have to generate all possible input values, hash them and compare them with the SHA-1 you have. But that will consume a lot of time and computing power. Some people created so called rainbow tables for some input sets. But these do only exist for some small input sets.

And remember that many input values map to a single target hash value. So even if you would know all mappings (which is impossible, because the input set is unbounded) you still can't say which input value it was.

Since SHA-1 maps several byte sequences to one, you can't "decrypt" a hash, but in theory you can find collisions: strings that have the same hash.

It seems that breaking a single hash would cost about 2.7 million dollars worth of computer time currently, so your efforts are probably better spent somewhere else.

SHA1 is a cryptographic hash function, so the intention of the design was to avoid what you are trying to do.

However, breaking a SHA1 hash is technically possible. You can do so by just trying to guess what was hashed. This brute-force approach is of course not efficient, but that's pretty much the only way.

So to answer your question: yes, it is possible, but you need significant computing power. Some researchers estimate that it costs $70k - $120k.

As far as we can tell today, there is also no other way but to guess the hashed input. This is because operations such as mod eliminate information from your input. Suppose you calculate mod 5 and you get 0. What was the input? Was it 0, 5 or 500? You see, you can't really 'go back' in this case.