Selective forgery of RSA signatures with fixed-pattern padding

We present a practical selective forgery attack against RSA signatures with fixed-pattern padding shorter than two thirds of the modulus length. Our result extends the practical existential forgery of such RSA signatures (Brier et al., 2001). For an n-bit modulus the heuristic asymptotic runtime of our forgery is comparable to the time required to factor a modulus of only 9/64 n bits. Thus, the security provided by short fixed-pattern padding is negligible compared to the security it is supposed to provide