We construct a Lie bracket on the Gerstenhaber-Schack cohomology of a bialgebra B (= Hopf algebra without unit, counit and antipode). This gives an affirmative answer to an old question about the existence of such a bracket. We do in fact much more -- we show that this kind of a bracket exists on the cohomology of any type of (bi)algebras over an operad or a PROP. Our construction applies also to Quillen's cohomology of algebras over a field of characteristic zero.