Avoid recipient-compatibility SHA1

[Neal H. Walfield]

Hi Stefan,

A chosen-prefix collision attack works as follows: an attacker chooses
two message prefixes, and then uses near collisions blocks (in the
SHA-1 is a Shambles paper they needed about 10 such 512-bit blocks) to
align the internal state of the two hashes.  Since SHA-1 is a
streaming function, the attacker can also append a common suffix.
That is, we want:

  Hash(prefix #1 || near collision blocks #1 || suffix)
  = Hash(prefix #2 || near collision blocks #2 || suffix)

And the attacker can choose prefix #1, prefix #2, and suffix, but
cannot control near collision blocks #1 or near collision blocks #2.

One way to exploit this is to create a pair of colliding documents
(e.g., something benign and a will), and then convince Alice to sign
the benign one.  If successful, the signature can be transferred to
the other document, and it appears that Alice has sign it too!

This attack requires the attacker to hide the near collision blocks in
the documents.  This is often straighforward: most formats have
provisions for comments, or metadata, which the user does not see.

The difficulty is to get Alice to sign the first document: if she
modifies it (e.g., adds any context), then the hash will be different.
But, if Alice is a signing service, then this may be possible even if
Alice modifies the document as long as the modifications are
predictable.

On Wed, 18 Nov 2020 14:30:12 +0100,
Stefan Claas via Gnupg-users wrote:
> Mallory has managed to listen to the clear text communications from
> Alice and Bob's online devices. Alice and Bob always use GnuPG
> to digitally sign their messages.
> 
> Mallory is *not* in possession of the private keys from Alice and Bob.
> Mallory has created a document which causes a collision and was
> signed with his own key.

This is currently not possible.  What you describe is a preimage
attack, not a collision attack.  A preimage attack is when you can
create a document with the same hash as an existing document.  Right
now, it is possible to find two documents that collide, but you can
only partially control the content of each of them (i.e., you need to
add the near collision blocks to both to actually create the
collision).

:) Neal