This must be done in Perform It mode or Fitness mode, but can be done on any difficulty. It can also be done at varying difficulties. It is highly recommended to five star all of the songs on the same difficulty first before trying a higher difficulty, otherwise you may lose track of which songs you've five starred. For example, if you get five stars on easy, then attempt the song on hard and get four stars, you now have no way to go back and confirm that you got five stars on easy, and you may end up losing track. Although if you're going for all of the crew challenge achievements, you'll inevitably get this achievement from getting five stars on every song on Hard in the crew challenges. Dance Central and DLC songs are not required.