0
$\begingroup$

Is it possible to produce a file(zip) where the first $n$ bits match a given value in optimal time?

Let us say we have a folder $f_1$ with hash $h_1$. After I change some contents in folder and the new folder this becomes $f_2$ with a rather different hash $h_2$.

Can I change (the) hidden contents in $f_2$ say $f_2'$ to get a hash $h_2'$ with where the first $n$ bits are identical to hash $h_1$?

If we can make such file can someone explain how?

note: hash is for zip of folder

$\endgroup$
1
  • 2
    $\begingroup$ There is no standard way to hash a folder of files with MD5, making the question ill-defined. Can you simplify the question so that it refers to a single file (with perhaps distinct fragments), and state what's known to the attacker, and what's not? Also, please clarify if/that "first $n$ bits" refers to the 128-bit MD5 hash. $\endgroup$
    – fgrieu
    Apr 4, 2017 at 14:52

1 Answer 1

0
$\begingroup$

Yes, you can, but the amount of bits (that get translated into characters if you'd use, say hexadecimal encoding) that will be identical to the original hash are of course limited.


Say a hidden file in the folder contains a large counter $c$. The total hash $h_2^c$ will have a pseudo-random value. The first bit of the hash will be identical to the first bit of hash $h_1$ with a probability of $1 \over 2$. That the next bit also matches has a probability of $1 \over 4$, which is ${1 \over 2} \times {1 \over 2}$ or $2^{-2}$. If you try enough counter values you will quickly find a hash where the first few bytes are identical.

Of course the chances of finding a full MD5 hash of 128 bits this way are very close to zero. 48 bits or so may be doable (your counter $c$ should be at least 48 bits but preferably larger, say 64 bits).


If the contents of the first folder $f_1$ can have a pre-calculated value inserted then you may be able to attack MD-5 and create a fully identical hash as MD5 is rather broken. But from your description this doesn't seem to be the case.

Furthermore, if $h_1$ is set then you cannot take advantage of the birthday problem, which halves the security of the hash. It's much easier to find two hashes $h_x$ and $h_y$ that match for $n$ bits than finding a single $h_x$ that matches a preset $h_1$.

$\endgroup$
8
  • $\begingroup$ should i keep entering random bit strings into hidden file and what is the length of data to be inserted $\endgroup$ Apr 4, 2017 at 16:25
  • $\begingroup$ Just a 64 bit counter would suffice. Random bit strings as well, but as long as there aren't (many) dupes, it really doesn't matter. $\endgroup$
    – Maarten Bodewes
    Apr 4, 2017 at 16:25
  • $\begingroup$ why 64 bits are to be used,if i want 7 characters to match is it enough $\endgroup$ Apr 4, 2017 at 16:26
  • $\begingroup$ It kind of doesn't matter. 32 bits is too small 'cause you'd run out of bits. You can also encode the counter in as many bytes as required, as long as the input of the hash differs all the time. $\endgroup$
    – Maarten Bodewes
    Apr 4, 2017 at 16:29
  • $\begingroup$ Note that this is very much like bitcoin mining, where they increase the number of bits that need to be found by hashing when enough bitcoins are mined (matches are found). $\endgroup$
    – Maarten Bodewes
    Apr 4, 2017 at 16:35

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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