Do hash collisions persist if a file is modified?

Question

Suppose I use a relatively insecure hash algorithm to digitally sign a contract. Suppose also that creating a fraudulent contract with the same hash, a collision, is practical. As I understand, in order to take advantage of a hash collision, the black hat is required to introduce some contrived information into the data first to counter the hash affects of their anticipated alterations.

For example, the original contract and hash are:

I will pay you $1.00 -> 12345

and a fraudulent colliding contract:

I will pay you $1,000,000.00 (contrived info) -> 12345

Can I protect myself by including some of my own text before signing?

For example:

I will pay you $1.00 have a nice day -> 67890

Can the attacker simply add the same text to their contrived file and get the same new hash?

I will pay you $1,000,000.00 (contrived info) have a nice day -> 67890

or will the additional text alter the hash such that the files no longer collide?

I will pay you $1,000,000.00 (contrived info) have a nice day -> 37294

I.e. Will my added information counteract the contrived information of the attacker?

In reality, as with SHA1 or MD5 where a practical method for finding collisions has been found, using this algorithm is faster than more secure ones. Could it make sense to use a very fast insecure algorithm coupled with both parties, a third party, or a random automated system, adding some novel, benign information prior to the hash? Does this add sufficient complexity?

I.e. In the case of SHA1 and git, could an attacker add some obscure contrived information in advance (that gets committed and signed or whatever) and then introduce the malicious code later when the timing was right? Or would subsequent commits thwart this plan? I.e. Are code repos with lots of contributors and commits coming from all over somewhat more secure than repos with little change?

Answer 1

TL;DR: when using SHA-1 or similarly weak hash, include unpredictable data at the beginning of the message.

---

Simplifying, there are three kinds of attacks to fear on practical (iterated) hashes that result in a collision, that is where the attacker ends with two different messages (of the same length) having the same hash. From easiest to hardest:

1. Collision attacks: the attacker can choose per operational constraints one meaningful prefix and one meaningful suffix. Messages are of the form
   I will pay you $1,000,000.00 (Qn47y2NXu49ssmexutgno5!QsmtxG) have a nice day
I will pay you $1,000,000.00 (eCW3Y!=jLJK;q&vM+;gdPZma7JAP4) have a nice day
   An example of such attack against SHA-1 is shattered.

2. Chosen-prefixes¹ collision attacks: the attacker can choose per operational constraints two meaningful prefixes (of equal length) and one meaningful suffix. Messages are of the form
   I will pay you $1.00 (G&RyUbpwgnn6dYbkLLnkx2WqMu5RVZ!QsmxyG) have a nice day
I will pay you $1,000,000.00 (KE2nFdwUizu;uo!BKgSB$c&ULEQ!R) have a nice day
   An example of such attack against SHA-1 is this recent paper.

3. Second-preimage attacks. The attacker can choose per operational constraints one of the two messages in full, the prefix of the other message, and have the two messages share a suffix. Messages are of the form
   I will pay you $1.00 on presentation of this signed message, have a nice day
I will pay you $1,000,000.00 (48CMWaAb5gt9RopNsgw!W2&o9x54e) have a nice day
   There is no example of such attack against SHA-1, nor even against MD5.

Note: the arbitrary portion typically has a minimum length of a few blocks (32 or 64 bytes for common hashes).

Note: depending on how the messages are interpreted, collision attacks (1) can still result in two messages with appearance entirely under the adversary's control. In particular, it may be possible to have a prefix that selects between two arbitrarily different appearances both encoded in the suffix, with the one displayed according to one bit in the arbitrary portion. The prefix of the shattered attack was chosen to allows that for PDF documents. This trick can be played with images, executable code..

Attacks 1 and 2 can be useful to an adversary only when sh/e can chose part of the signed message, e.g. for messages like
I will pay you $1.00 per invoice PkictdyAxvaokEeTtEkVYEG24UYtK4GLiTqCWHtw, have a nice day

Can I protect myself by including some of my own text before signing?

Yes, but not quite per the method illustrated in the question. You can protect against collision attacks and chosen-prefixes collision attacks (1 and 2) by including some unpredictable data at the beginning (in the first block) of the signed message. E.g.
My Ref BzCP3dFT. I will pay you $1.00 per invoice PkictdyAxvaokEeTtEkVYEG24UYtK4GLiTqCWHtw

This technique is used by savvy certification authorities when generating digital certificates with unpredictable Certificate Serial Number. This guards against chosen-prefixes collision attacks where the prefixes include a predictable CSN and two different domain names (one the attacker's target and the other under control of the attacker), and some of the arbitrary data belongs to public keys.

Can the attacker simply add the same text to their contrived file and get the same new hash?

Yes, the attacker can easily add or alter a suffix of two colliding messages. That's why the unpredictable data must be at start.

Will my added information counteract the contrived information of the attacker?

Only if the addition is early enough in the message (e.g. first block), and if the adversary can not perform attack 3 (second-preimage). Critically, the unpredictable data must be at the start of the hashed message. It is pointless to add unpredictable data in the appearance of a PDF document or other structured message.

Could an attacker add some obscure contrived information in advance (that gets committed and signed or whatever) and then introduce the malicious code later when the timing was right?

Yes, but only if the attacker (able to perform attack 1 or 2) can predict what's before the portion s/he has under control. This is avoidable when preparing a zip file, then hashed (and e.g. signed or referenced by hash): the zip creation process can add a random header, making attacks 1 and 2 infeasible. This is not avoidable when an adversary can post a whole file and the integrity of that file is insured per the hash of that file (attack 1 is enough for many file formats including most executables).

---

¹ Often written just chosen-prefix (collision).

Answer 2

If the attacker gets to add their contrived data after seeing your contrived data it makes no difference and the added contrived data will do you know good.

If the attacker however needs to prepare in advance, for instance the attack is computationally intensive and he must submit the forged document shortly after receiving the valid document, then adding unpredictable information may make the attack impractical.

If the hash follows a MD (e.g MD5/SHA1/SHA2) construction it is important to add the unpredictable(random) information at the begining, as adding a common suffix to such hash functions will preserve collisions.

If an attacker has a collision for message m. Forged(m), he is unlikely to be able to easily find a collision for modified message (random || m) just because he already has Forged(m). But if he has a generic ability to find collision and has the necessary time/resources he will be able to just create Forged(random || m).