That's true, but the format of signed tags will need to change in one way or another. What we could do is to have a "shadow" tree which is built using a stronge

That's true, but the format of signed tags will need to change in one way or another. What we could do is to have a "shadow" tree which is built using a stronger hash algorithm (e.g. SHA256), and which is used for signing history. The shadow tree would be identical to the real tree except for the hashes and references to hashes.