Digital signatures usually utilize one-way hash functions designed by other parties. It is thus possible that such hash functions are adverserially designed so as to enable forging signatures in otherwise secure schemes.
We initiate the study of signing with adversarial hashing by considering hash functions for which an adversary can fix arbitrarily the input-output values at polynomially many inputs.
On the negative side, we show that many known signature schemes are vulnerable against such partially adversarial hashing attacks. On the positive side, we show that a surprisingly simple modification makes any scheme invulnerable against such attacks. The computational requirements of our modification are so mild that it could be easily integrated into any signature scheme.