Ah okay, I'll respond to the edit:
It depends on exactly what you mean by "directly reverse". If you mean "using some analytic method to find the exact input", then no, hashes can't be reversed. This is because of the pigeon hole principle, causing that "information loss" that you alluded to. However, that's not necessarily what you need.
One could take "reverse" to have a looser definition: to produce an input (any one input), that hashes to the same value as the true input. This is the more useful definition, and for this definition of "reverse", it is not true to say that
If the input space is larger than the output space, information loss occurs and the hash is not reversible.
Take a basic message authentication code, for example. You have a message you want to send and a shared secret key that authenticates you to an awaiting party. You want to authenticate the message, so you send your friend the message, plus hash(msg, yourSharedSecretKey). For me to forge the message, I have to intercept and change the message, but also update the hash so that your friend's verification works out. For me to succeed at this, I don't need to reverse what the exactly value yourSharedSecretKey is. I only need to figure out a key value, any key value, which hashes the same way as yourSharedSecretKey; whether or not the key I guess is exactly yourSharedSecretKey is irrelevant. For this attack to be successful (for for the hash function to be determined to be shit), I only need a way of easily figuring out values that collide with yourSharedSecretKey. This property is not guaranteed simply because "hashes lose information", and it's one of the defining characteristics of cryptographic hashes, that this process is made exceptionally difficult.
Here's a cute little example. I use Ints for messages, keys and signatures to simplify things, but I'm sure you can imagine how this could be generalized to any bit stream.
// A really shitty hash function
func hash(input: Int, sharedSecret: Int) -> Int { return (sharedSecret + input) % 3 }
enum SignitureError: Error {
case invalidSigniture(expectedSigniture: Int, attachedSigniture: Int)
}
struct SignedMessage {
var message: Int
var signiture: Int
init(message: Int, sharedSecret: Int) {
self.message = message
self.signiture = hash(input: message, sharedSecret: sharedSecret)
}
func verify(expectedSharedSecret: Int) throws {
let expectedSigniture = hash(input: self.message, sharedSecret: expectedSharedSecret)
if self.signiture != expectedSigniture {
throw SignitureError.invalidSigniture(expectedSigniture: expectedSigniture, attachedSigniture: self.signiture)
}
}
}
let avisSharedSecret = 6562346
func sendMessageToAvisFriend(message: SignedMessage) {
// Avi'd friend receives the message and verifies it:
do {
try message.verify(expectedSharedSecret: avisSharedSecret)
print("Avi's friend receives a valid message: \(message.message) with signiture \(message.signiture)")
} catch SignitureError.invalidSigniture(let expectedSigniture, let attachedSigniture) {
print("""
Avi's friend received an invalid message!
message: \(message.message)
attached signiture: \(attachedSigniture)
expected signiture: \(expectedSigniture)
""")
} catch { fatalError("Unexpected error") }
}
func happyCase() {
// Good guy Avi sends a real message:
let realMessage = SignedMessage(message: 123, sharedSecret: avisSharedSecret)
sendMessageToAvisFriend(message: realMessage)
}
func happyCaseForgedMessageDetected() {
// Good guy Avi tries to send a real message:
let realMessage = SignedMessage(message: 123, sharedSecret: avisSharedSecret)
// Evil guy Alex intercepts the message, changes it, but doesn't change the signiture:
var forgedMessage = realMessage
forgedMessage.message = 100
// Avi's friend receives the message, verifies it, and discovers that the signiture isn't
// what he expected. The message has been tampered with!
sendMessageToAvisFriend(message: forgedMessage)
}
func sadCaseMessageForged() {
// Good guy Avi tries to send a real message:
let realMessage = SignedMessage(message: 123, sharedSecret: avisSharedSecret)
// Evil guy Alex intercepts the message, changes it
// Alex is smart this time. He inspected the hash function, and was able to analytically
// deduce that if the key is one of {2, 5, 8, 11, ...}, he produces a compatible signiture as the real shared secret.
//
// In general, a key that works with one message to produce a valid signiture doesn't mean it will necessarily work
// to produce a valid signiture for every message, but that's okay, it just needs to work for this message.
// For another message, a different key would be figured out, just the same.
let guessedSharedSecret = 2
let fakeMessageBody = 100
var forgedMessage = SignedMessage(message: fakeMessageBody, sharedSecret: guessedSharedSecret)
// Avi's friend thinks the message is legit! :(
// The hash has been "reversed" successfully, even though the hash function caused a loss of information.
sendMessageToAvisFriend(message: forgedMessage)
}
happyCase()
happyCaseForgedMessageDetected()
sadCaseMessageForged()
Even though I couldn't reverse engineer the hash function to know that Avi's sharedSecret was precisely 6562346, there are a set of values I could use that would work instead, because they all hash to produce the same signature 0. (2, 5, 8, 11 ...)
If hash(input:sharedSecret:) was a cryptographic hash function, it would have been designed so that it's extremely difficult to reverse the hash to find any value that hashes equivalently to 6562346. Only then would forging the message be impossible. That's the useful definition of "irreversible".