# Self verifying hash algorithm

For quite some time I've been thinking about the idea to construct a hashing algorithm that contains its own checksum value, and thereby can verify itself. With hashing algorithms like SHA1 and MD5 this seems to be difficult although not impossible as explained here. The content that is hashed could never change, but I can think of a few situations where this is absolutely desirable. For example, certificates containing their own thumbprint calculated over all fields. I have tried to design the basics myself once, but that was more ambitious than I had foreseen.

The way I see it there are two approaches:

• Narrow down the possible hash values by analyzing the content. Then race for all possibilities to see if the content and the hash match. I have implemented this and although it did work it was everything but usable.
• Calculate a hash and adjust the content to match the hash value. For hashing algorithms like MD5 this is near to impossible and any new algorithm would possibly impaired by this.

I'm convinced it is both possible and usable someway, therefore it surprises me how few there is to find on the subject. Are there any case studies or related algorithms to this idea?

• I do not see any conceivable use for this. A certificate with its own fingerprint included in the signed part is absolutely useless -- the whole point of the fingerprint is to manually verify that a certificate is the one you expect, but if you trust the signer then the signature suffices for that. For a plain hashing algorithm, what do you mean by "verify itself?" You don't verify a hash; you might verify that a message hashes to a given value, but this cannot be done by including a checksum in the output. – cpast Mar 12 '15 at 13:19
• I think he may mean that the hash is also a proof/argument of knowledge of a preimage. Some clarification would be welcome. – Andrew Poelstra Mar 12 '15 at 13:23
• @cpast For a certificate this would be perfect. I'm not talking about the signature itself, but only the hash that indicates integrity. Ofcourse by verification I referred to the message output matching the hash. If you read the article I linked you'd see that its most certainly possible. – Yorick de Wid Mar 12 '15 at 13:44
• @YorickdeWid An unkeyed hash does not and cannot indicate integrity if it comes over the same channel as the thing it's claimed to protect. The signature is what gives integrity for a certificate. The answer you linked shows that there exist things which contain their own hash, but that wasn't what I was talking about -- something containing its own hash cannot show integrity of that something. – cpast Mar 12 '15 at 13:49
• @Yorick Then what are you talking about? An unkeyed hash included alongside the message it was computed over cannot protect against an attacker. Protecting against transmission error is out of scope on this site; that's not cryptography. So what do you intend to protect against? – cpast Mar 12 '15 at 14:08

Maybe you can create a hash function like that, but it will have a major security weakness, because in order to achieve your goal, you need some correlated manipulations in the input and output. And that can be exploited by an attacker for cryptanalysis.

• Assume you have a given input and know its according hash value.
• If you flip a single bit in the input, it should flip the hash value at every position with probability $0.5$, because otherwise you have a weakness for differential cryptanalysis. Formally, this can be seen as an linear correlation of some part of the algorithm.

That last part is what you actually need for your self containing hash function but at the same time that also gives the attacker an advantage for finding collisions or even preimages, calculate the internal algorithm of the hash backwards, etc.

The fact that something exists, does not mean there is a more efficient way than just testing all candidates.

• So basically this is a no-go since a function of a linear correlation can be easily predicted. I'm almost starting to think about one way hashing and verification (check match) using a different method, but that's more in the scope of asymmetric encryption. – Yorick de Wid Mar 13 '15 at 11:37

I think what you're missing here is that a cryptographic hash by itself is not actually sufficient to verify the integrity of a message. Consider this:

I want to send a message over the Internet (on an insecure connection, e.g. UDP), but have it be protected from tampering. I take the message and attach at the end a cryptographic hash of the message (e.g. SHA256(message)). When my friend receives the message, she verifies that the hash at the end matches SHA256(message).

Now, despite the fact that she has "verified" the message using a cryptographic hash, it turns out that this is not sufficient to prevent tampering. If an attacker is able to intercept and modify the message before it reaches my friend, they can remove the old hash, SHA256(message), and add a new hash, SHA256(tamperedMessage). When my friend receives the tampered message, she won't notice anything is wrong, because the message she receives still ends with a matching SHA256 hash.

Hashes do not (by themselves) provide integrity protection (in other words, prevent tampering). Hashes provide a convenient way of identifying the content of a message.

We can use hashes to build schemes that do provide integrity protection. Consider the earlier example. Let's say I again transmit a message to my friend over the Internet, this time without a hash. She receives the message, but knows that she can not yet trust that it has not been tampered with. If I meet up with her in person, I can provide her with the hash, say, diligently scrawled on a sheet of paper. If she checks this hash against the message she received over the Internet, she will know that it has not been tampered with. Why? Because (1) the hash uniquely identifies the original, legitimate message and (2) the hash was provided over a secure channel (i.e. in person).

This is why having a hash that "verifies itself" does not prevent tampering. You could attach to a hash, a hash of that hash, then attach to that hash, a hash of that hash, but your scheme would still not provide any integrity protection unless the hashes are provided over a secure channel. Hashes identify, and further identifying the identifier does not actually improve security.

Note (in anticipation of nitpicks): I used the term "uniquely identifies". Hashes aren't actually unique from a theoretical perspective, but they are in practice.

• Is the conclusion that hashes can always be manipulated if they contain their own value a purely practical one, or is this what theorie tells us? For a long time people thought public key cryptography was impossible too, until RSA proved otherwise. – Yorick de Wid Mar 13 '15 at 8:55
• @YorickdeWid Unless you need a secret key to compute the hash, anything you can do the attacker can do just as easily. If you can create one of your special hashes over arbitrary data (so turning any arbitrary thing into that data, plus a hash value, where the hash hashes to that value), then an attacker can do so as well. The only way to stop an attacker from tampering with data is to do something that the attacker can't do; neither of your approaches to this qualifies as "something the attacker can't do." – cpast Mar 13 '15 at 19:03