A Cryptographic Study of Secure Internet Measurement

Abstract:

Mechanisms for measuring data-path quality and identifying locations where packets were dropped are crucial for informing routing decisions and enforcing network accountability. 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 or by blaming packet loss on innocent ASes). In this paper, we explore mechanisms for accurately detecting and localizing 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 or localization mechanism requires secret keys, cryptography and storage at every participating node. (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. (3) A new protocol for accurately localizing packet loss to specific links along a path, even in the presence of adversaries.

This technical report contains proofs, definitions, and other results in support of our short paper, "Measuring Path Quality in the Presence of Adversaries: The Role of Cryptography in Network Accountability".