An ad hoc or sensor network that is employed for security sensitive applications is expected to tolerate a certain quantity of maliciously behaving nodes. Algorithms must be designed in a way to withstand attacks such as manipulation and injection of messages. End-to-end security mechanisms, albeit desirable, are generally too costly with regard to the limited computational resources available in sensor networks. We propose and evaluate a robust, scalable scheme for interleaved message authentication, which approximates security guarantees of end-to-end schemes.