  Many IoT use cases involve constrained battery-powered devices offering
services in a RESTful manner to their communication partners. Such services may
involve, e.g., costly computations or actuator/sensor usage, which may have
significant influence on the power consumption of the service Providers. Remote
attackers may excessively use those services in order to exhaust the Providers'
batteries, which is a form of a Denial of Service (DoS) attack. Previous work
proposed solutions based on lightweight symmetric authentication. These
solutions scale poorly due to requiring pre-shared keys and do not provide
protection against compromised service Requesters. In contrast, we consider
more powerful attackers even capable of compromising legit Requesters. We
propose a method that combines attacker detection and throttling, conducted by
a third trusted Backend, with a lightweight authentication protocol. For
attacker detection and throttling, we propose a novel approach using rate
limitation algorithms. In addition, we propose and formally verify two
authentication protocols suitable for different, widely used IoT network
topologies. Our protocols ensure service availability for benign Requesters
even if Providers are under a battery exhaustion attack. The protocols do
neither require pre-shared keys between Requesters and Providers, nor the usage
of asymmetric cryptography and public key infrastructures on the Provider. This
makes our protocols suitable for a variety of IoT deployments involving
constrained devices and constrained networks. We demonstrate the feasibility of
our method through a simulation and a proof of concept implementation.
