Traffic hijacking over the Internet has become a frequent incident over the last two decades. From minor inconveniences for casual users to massive leaks of governmental data, these events cover an unprecedently large spectrum. Many hijackings are presumed to be caused by unfortunate routing mistakes, but a well-organized attacker could set up a long-term stealthy relay, accessing critical traffic metadata, despite suitable encryption schemes. While many studies focus on the mitigation of known attacks, we choose to design a complete detection method regardless of the attacker’s strategy. We propose a two-party cryptographic protocol for detecting traffic hijacking over the Internet. Our proposal relies on a distance-bounding mechanism that performs interactive authentication with a “Challenge–Response” exchange, and measures the round-trip time of packets to decide whether an attack is ongoing. Our construction is supported by worldwide experiments on communication time between multiple nodes, allowing us to both demonstrate its applicability and evaluate its performance. Over the course of this paper, we demonstrate our protocol to be efficient—itrequires only two cryptographic operations per execution inducing negligible workload for users and very few loss of throughput, scalable—no software updates are required for intermediate network nodes, routing protocol independent—this means that any future update of the route selection process will not induce changes on our scheme, and network friendly—the added volume of transiting data is only about 1.5%.