1
$\begingroup$

Do any methods exist whereby a "hash" can be embedded in the "document" it hashes?

What I mean is this. Say I have a given plaintext T. I wonder if there is a method to craft (i.e. not discover as a fluke) a "document" D being some combination (e.g. a concatenation) of T and a hashvalue h, where h is H(D), H being some hash function.

Perhaps a simpler way of phrasing this is: Is there any way to make a document contain its own hash, under the constraint that the document must, apart from its own hash, contain a given plaintext?

Is this possible in theory? In practice?

This question is somewhat different from this one, in that I am assuming a given plaintext T, whereas that question asks if any T can be crafted (or found).

Improve this question
$\endgroup$
4
  • $\begingroup$ I considered that. It's similar but I don't think it's quite the same. That post seems to ask if it's possible to craft the document D given the hash value h, without caring about what the rest of D will look like. My question assumes that I have a given plaintext T, and am looking for a hash h to add. $\endgroup$ – Peter M. Dec 29 '16 at 2:53
  • $\begingroup$ "Some hash function" is meaningless. Which properties do you assume the hash function to have? $\endgroup$ – fkraiem Dec 29 '16 at 3:11
  • $\begingroup$ The usual, I suppose? A large range and apparent randomness. (I'm not familiar with the correct technical terms for these properties, but you probably know what I mean.) $\endgroup$ – Peter M. Dec 29 '16 at 3:53
  • $\begingroup$ You're asking for something harder, and even the easier problem is unfeasible. $\endgroup$ – Gilles 'SO- stop being evil' Dec 29 '16 at 22:37
4
$\begingroup$

It actually depends on what you consider a hash function.

If we take a CRC (Cyclic Redundancy Check) as our hash function, then it is quite feasible; a CRC has a property that every output bit is a linear (affine if the initial state is nonzero, but the difference is unimportant) function of the input bits; hence we can generate a set of linear equations over the various bits of X in the expression $CRC( Message || X || MoreMessage ) = X$, and attempt to solve that (and find the solutions, if any).

I would further note that CRC does meet the criteria you gave; it can potentially have a large range (just make the CRC state large enough), and at first glance, if you just look at inputs and outputs, it does appear random.

Of course, a CRC is not a secure hash function; however you didn't specify a secure hash function.

Improve this answer
$\endgroup$
1
$\begingroup$

As I noted in my earlier answer, for any standard secure hash function, it is unlikely that you could ever find any string that contains its own hash value. If you cannot do that at all, you certainly have no hope of doing it with extra constraints, like having the string begin with some preselected prefix $T$.

You could do that if the hash function you chose was broken enough to allow chosen-prefix first preimage attacks; indeed, that would even allow you to choose the hash value you want. Basically, just pick any $T$ and $h$ you want, and apply the preimage attack to generate a message the prefix $T \,\|\, h$ and the hash value $h$. But, of course, any hash function that broken would be completely useless as a cryptographic hash anyway.

In any case, I'm not sure what cryptographic purpose such a construction would serve. Hash functions don't have keys, so if you could construct a message containing its own hash, anybody else (with access to comparable computing power) could do it just as well. So such a scheme, even if possible, would be useless for authentication or data integrity.

If what you want to do is prove that you created a particular document, and that it hasn't been tampered with, what you actually want is a message authentication code or a digital signature. Both of those can be constructed using hash functions (among other things), but they're not the same thing.

Improve this answer
$\endgroup$
5
  • $\begingroup$ I'm have a basic understanding of digital signatures, and the public-private key stuff behind in. But I'm not interested in proving authorship, only in proving that a document hasn't been tampered with. Can the document itself ever contain proof of this? It seems you answer is no, at least not using a hash. $\endgroup$ – Peter M. Dec 30 '16 at 16:07
  • $\begingroup$ What do you mean by "not tampered with"? That's not a rhetorical question; if there's nothing to prove that you specifically wrote the document, what's to stop anyone else from creating their own version of the document and tagging it as authentic? $\endgroup$ – Ilmari Karonen Dec 30 '16 at 18:58
  • $\begingroup$ My idea was that if my text is T and I can construct a document <T,h> such that H(<T,h>)=h, then I have made it very difficult for anyone to create another, slightly different document <T',h> that also hashes to h and pass it off as the original. $\endgroup$ – Peter M. Dec 30 '16 at 23:14
  • $\begingroup$ Hm, I think I'm starting to see where my idea falls apart. Even if what I want to do were possible, who is to stop someone else from taking my text, modifying it slightly, and issuing a document <T',h'> that hashes to h'. Then there would be 2 docs "out there" with nothing to prove which is "truly" the original and which is the modification. Right? $\endgroup$ – Peter M. Dec 30 '16 at 23:23
  • $\begingroup$ Yes, exactly. The way digital signatures solve the problem is that they carry information about who (i.e. which private key) created them, which anyone who knows the corresponding public key can verify. (Of course, that in itself won't stop someone else from creating a new public/private key pair and claiming that this public key also belongs to "Peter M." That's a whole different problem altogether.) $\endgroup$ – Ilmari Karonen Dec 31 '16 at 3:56

Not the answer you're looking for? Browse other questions tagged or ask your own question.