Question: are covers of songs legal?
Answer: There actually are simple... Cover recordings are quite legal, assuming that royalties are paid and that the song's integrity isn't violated. For a faithful and properly credited cover, you don't even need prior permission.