Mechanisms for measuring data-path quality and identifying locations where packets were dropped are crucial for informing routing decisions. If such mechanisms are to be reliable, they must be designed to prevent ASes from `gaming' measurements to their advantage (e.g. by hiding packet loss events). This paper is a rigorous cryptographic study of secure fault detection, an end-to-end technique that allows a sender to detect whether or not her traffic arrived unaltered at a receiver, even when some of the nodes on the the data path maliciously attempt to bias measurements. We explore mechanisms for accurately detecting packet loss events on a data path in the presence of both benign loss (congestion, link failure) and active adversaries (ASes motivated by malice or greed). We do not advocate a specific network architecture. Instead, we use rigorous techniques from theoretical cryptography to present new protocols and negative results that can guide the placement of measurement and security mechanisms in future networks.

Our major contributions are: (1) Negative results that prove that any detection mechanism requires secret keys, cryptography and storage at every participating node, and (2) Pepper Probing and Salt Probing: two efficient protocols for accurate end-to-end detection of packet loss on a path, even in the presence of adversaries. In Pepper Probing, Alice and Bob sample packets in a coordinated manner with a cryptographic hash function. To reduce the key-management overhead, Salt Probing uses a timing strategy to extend Pepper Probing to the public-key setting without compromising the efficiency of the protocol.