Is it possible to reverse a sha1?

Question

Hi

Is it possible to reverse a sha1?

I'm thinking about using a sha1 to create a simple lightweight system to authenticate a small embedded system that communicates over a unencrypted connection.

Let's say that I create a sha1 like this with input from a "secret key" and spice it with a timestamp so that the sha will change all the time.

sha1("My Secret Key"+"a timestamp")

Then I include this sha1 in the communication and the server, that can do the same calculation. And hopefully nobody would be able to figure out the "secret key".

But is this really true?

If you know that this is how I did it, you would know that I did put a timestamp in there and you would see the sha1. Can you then use those two and figure out the "secret key"?

secret_key = bruteforce_sha1(sha1, timestamp)

Thanks Johan

---

Note1: I guess you could brute force in some way, but how much work would that actually be?

Note2: I don't plan to encrypt any data, I just would like to know who sent it.

Answer 1

No, you cannot reverse SHA-1, that is exactly why it is called a Secure Hash Algorithm.

What you should definitely be doing though, is include the message that is being transmitted into the hash calculation. Otherwise a man-in-the-middle could intercept the message, and use the signature (which only contains the sender's key and the timestamp) to attach it to a fake message (where it would still be valid).

And you should probably be using SHA-256 for new systems now.

sha("My Secret Key"+"a timestamp" + the whole message to be signed)

You also need to additionally transmit the timestamp in the clear, because otherwise you have no way to verify the digest (other than trying a lot of plausible timestamps).

If a brute force attack is feasible depends on the length of your secret key.

The security of your whole system would rely on this shared secret (because both sender and receiver need to know, but no one else). An attacker would try to go after the key (either but brute-force guessing or by trying to get it from your device) rather than trying to break SHA-1.

Answer 2

SHA-1 is a hash function that was designed to make it impractically difficult to reverse the operation. Such hash functions are often called one-way functions or cryptographic hash functions for this reason.

However SHA-1 has some recently discovered weaknesses that allow finding an input faster than by doing a brute force search of all inputs. You should consider using something stronger like SHA-256 for new applications.

Jon Callas on SHA-1:

It's time to walk, but not run, to the fire exits. You don't see smoke, but the fire alarms have gone off.

Answer 3

In mathematical terms, only bijective functions have an inverse function. But hash functions are not injective as there are multiple input values that result in the same output value (collision).

So, no, hash functions can not be reversed. But you can look for such collisions.

---

Edit

As you want to authenticate the communication between your systems, I would suggest to use HMAC. This construct to calculate message authenticate codes can use different hash functions. You can use SHA-1, SHA-256 or whatever hash function you want.

And to authenticate the response to a specific request, I would send a nonce along with the request that needs to be used as salt to authenticate the response.

Answer 4

The question is actually how to authenticate over an insecure session.

The standard why to do this is to use a message digest, e.g. HMAC.

You send the message plaintext as well as an accompanying hash of that message where your secret has been mixed in.

So instead of your:

sha1("My Secret Key"+"a timestamp")

You have:

msg,hmac("My Secret Key",sha(msg+msg_sequence_id))

The message sequence id is a simple counter to keep track by both parties to the number of messages they have exchanged in this 'session' - this prevents an attacker from simply replaying previous-seen messages.

This the industry standard and secure way of authenticating messages, whether they are encrypted or not.

---

(this is why you can't brute the hash:)

A hash is a one-way function, meaning that many inputs all produce the same output.

As you know the secret, and you can make a sensible guess as to the range of the timestamp, then you could iterate over all those timestamps, compute the hash and compare it.

Of course two or more timestamps within the range you examine might 'collide' i.e. although the timestamps are different, they generate the same hash.

So there is, fundamentally, no way to reverse the hash with any certainty.

Answer 5

Note that the best attacks against MD5 and SHA-1 have been about finding any two arbitrary messages m1 and m2 where h(m1) = h(m2) or finding m2 such that h(m1) = h(m2) and m1 != m2. Finding m1, given h(m1) is still computationally infeasible.

Also, you are using a MAC (message authentication code), so an attacker can't forget a message without knowing secret with one caveat - the general MAC construction that you used is susceptible to length extension attack - an attacker can in some circumstances forge a message m2|m3, h(secret, m2|m3) given m2, h(secret, m2). This is not an issue with just timestamp but it is an issue when you compute MAC over messages of arbitrary length. You could append the secret to timestamp instead of pre-pending but in general you are better off using HMAC with SHA1 digest (HMAC is just construction and can use MD5 or SHA as digest algorithms).

Finally, you are signing just the timestamp and the not the full request. An active attacker can easily attack the system especially if you have no replay protection (although even with replay protection, this flaw exists). For example, I can capture timestamp, HMAC(timestamp with secret) from one message and then use it in my own message and the server will accept it.

Best to send message, HMAC(message) with sufficiently long secret. The server can be assured of the integrity of the message and authenticity of the client.

You can depending on your threat scenario either add replay protection or note that it is not necessary since a message when replayed in entirety does not cause any problems.