In an ad hoc network, mobile computers (or nodes) cooperate to forward packets for each other, allowing nodes to communicate beyond their direct wireless transmission range. Many proposed routing protocols for ad hoc networks operate in an on-demand fashion, as on-demand routing protocols have been shown to often have lower overhead and faster reaction time than other types of routing based on periodic (proactive) mechanisms. Significant attention recently has been devoted to developing secure routing protocols for ad hoc networks, including a number of secure on-demand routing protocols, that defend against a variety of possible attacks on network routing. In this paper, we present the rushing attack, a new attack that results in denial-of-service when used against all previous on-demand ad hoc network routing protocols. For example, DSR, AODV, and secure protocols based on them, such as Ariadne, ARAN, and SAODV, are unable to discover routes longer than two hops when subject to this attack. This attack is also particularly damaging because it can be performed by a relatively weak attacker. We analyze why previous protocols fail under this attack. We then develop Rushing Attack Prevention (RAP), a generic defense against the rushing attack for on-demand protocols. RAP incurs no cost unless the underlying protocol fails to find a working route, and it provides provable security properties even against the strongest rushing attackers.