0
$\begingroup$

Suppose you have a file of 240 lines. Any lines, any content. You then calculate the hash of that file, let's say MD5, and the result is something in the following structure:

f8dbe310c1f61066d766071b07503ce8

Now, you take this hexadecimal digest, and add it to the file as line 241.

Rehashing the file (with additional hash line) will result with a new hash value obiously.

My questoin is whether it is even theoretically possible for a hash value to contain itself, meaning, can there be a file, with some content that its hashed value is identical to a string already presented in the file (e.g. line 241 in this example)

$\endgroup$
4
  • $\begingroup$ Can the program be $2^{128}$ lines long? $\endgroup$
    – Yonatan N
    May 20, 2020 at 8:44
  • $\begingroup$ assuming it can... $\endgroup$ May 20, 2020 at 11:08
  • 1
    $\begingroup$ For the question about the last line, it surely depends on the hash function. For example, suppose each line is a single bit (0 or 1). If the hash function is the xor of the bits, then the answer is yes -- take 240 lines with total parity 0. But the answer is no if the hash function is defined by $$f(x_1, x_2, \ldots, x_n) = \neg (x_n \oplus f(x_1, x_2, \ldots, x_{n-1}))$$ with $f() = 0$. (Here $\oplus$ is xor.) BTW I think Yonatan's point was that if the file already contains every possible hash output (one per line), then no matter what the hash outputs it will be in the file already. $\endgroup$
    – Neal Young
    May 20, 2020 at 18:53
  • $\begingroup$ Than kyou @NealYoung! may you change this comment to an answer so I can mark it properly ? $\endgroup$ May 20, 2020 at 20:28

1 Answer 1

4
$\begingroup$

For the first question, about the last line, it surely depends on the hash function. For example, suppose each line is a single bit (0 or 1). If the hash function is the xor of the bits, then the answer is yes -- take 240 lines with total parity 0. But the answer is no if the hash function is defined by $$f(x_1, x_2, \ldots, c_n) = \neg (x_n \oplus f(x_1, \ldots, x_{n-1})),$$ with $f()=0$, where $\oplus$ is xor.

For the second question (about any line), I think @Yonatan's point in his comment was that if the hash function has finitely many possible outputs (as e.g. MD5 does), then, for a file that already contains every possible hash output (one per line), no matter what the hash outputs it will be in the file already.

$\endgroup$

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