Does an Aura that becomes attached to an illegal permanent fall off immediately?

State-based actions are checked continuously by the game, and one of them (CR 704.5n) specifically handles Auras: if an Aura is attached to something it could not legally enchant — due to protection, shroud, hexproof, type mismatch, or any other reason — it is put into its owner's graveyard the next time state-based actions are checked.

This check happens before any player receives priority, so the Aura never 'sits' on an illegal permanent for any meaningful game moment. The moment state-based actions fire (such as after a spell or ability resolves that caused the illegal attachment situation), the Aura goes to the graveyard with no player able to respond in between (CR 704.3).

Note that this is different from targeting: when an Aura spell is cast, its target is checked on resolution (CR 608.2b). The 704.5n rule applies to Auras that are already on the battlefield and whose enchant condition is later broken — for example, if a permanent gains protection from the Aura's color after the Aura is attached.

Concrete example: You have Pacifism (enchant creature) attached to an opponent's Grizzly Bears. Your opponent then activates an ability that gives their Bears protection from white until end of turn. As soon as state-based actions are checked, Pacifism is put into your graveyard, because the Bears' protection makes the Aura's attachment illegal (CR 704.5n, 702.16e).

The Aura's controller does not get a chance to move it or use it — it simply goes to the graveyard as a state-based action, not as a spell or ability that can be responded to (CR 704.3).