I'm no lawyer, but I suspect it is legal. When I lived in a townhouse - I wasn't even renting - and the association wouldn't let us do anything in the yard. When you rent a house, they can tell you that you can't put anything on the walls, etc.
Now, can and SHOULD is different. That is really really stupid. what possible reason would they have for saying no?
