Asymmetric cryptography is a cornerstone for security in modern IT infrastructures like virtual private networks (VPNs). Unfortunately, the security of currently deployed schemes is threatened by the ongoing research in quantum computing. And while quantum-resistant alternatives exist, known as post-quantum cryptography (PQC), analyses regarding their (implementation) security are not as mature, yet. Consequently, solely relying on PQC might be susceptible to “store now, decrypt later” attacks. Instead, many researchers suggest using “hybrid” key exchanges, e.g., combining classical asymmetric cryptography, PQC, and symmetric alternatives like quantum key distribution (QKD) and multipath key reinforcement (MKR). In this article, we formalize the idea of “opportunistic re-keying”, where a session key is continuously updated using input key material that might be known or even chosen by an attacker. Assuming that at least one input key material is not known to the attacker, we prove th e security of the construction in the random oracle model. I.e., when an ideal random function is used for combining the current internal state and new input to generate the next session key and state. Further, we suggest two concrete parameter sets for the construction, corresponding to the security categories 3 and 5 of the NIST standardization process for PQC.

Assuming a threat model of a global observer, statistical disclosure attacks have been proposed to efficiently de-anonymize communication relationships in text-based mix networks over time. It is commonly assumed that such attacks are also able to disclose call relationships in anonymous communication networks (ACNs) that support voice calls. One straightforward countermeasure is to expect users to permanently send and receive packets that mimic a Voice over IP (VoIP) call. However, this is not practical in real world scenarios, like on mobile devices. In this article, we adapt one specific statistical disclosure attack (Z-SDA-MD) to voice calls and quantitatively study less resource-intensive countermeasures. As base countermeasure, we evaluate a round-based communication model, corresponding to a timed mix. A simulation study of this scenario shows that the Z-SDA-MD is not well suited for a general disclosure of call relationships because of too many false positives. Nevertheless, the attack is able to correctly identify the most frequent relationships. Still, the accuracy in that regard may significantly be decreased by increasing the duration of one round, by decoupling actions (call setup and teardown) of caller and callee by a random number of rounds, and by occasional fake calls to a fixed set of “fake friends”. Overall, our study shows that anonymous voice calls may be implemented with an acceptable trade-off between anonymity, call setup time, and bandwidth overhead.

Onion routing is a promising approach to implement anonymous voice calls. Uniform-sized voice packets are routed via multiple relays and encrypted in layers to avoid a correlation of packet content in different parts in the network. By using pre-built circuits, onion encryption may use efficient symmetric ciphers. However, if packets are forwarded by relays as fast as possible—to minimize end-to-end latency—network flow watermarking may still de-anonymize users. A recently proposed countermeasure synchronizes the start time of many calls and batch processes voice packets with the same sequence number in relays. However, if only a single link with high latency is used, it will also negatively affect latency of all other calls. This article explores the limits of this approach by formulating a mixed integer linear program (MILP) that minimizes latency “bottlenecks” in path selection. Furthermore, we suggest a different scheduling strategy for voice packets, i.e. implementing independent de-jitter buffers for all flows. In this case, a MILP is used to minimize the average latency of selected paths. For comparison, we solve the MILPs using latency and bandwidth datasets obtained from the Tor network. Our results show that batch processing cannot reliably achieve acceptable end-to-end latency (below 400 ms) in such a scenario, where link latencies are too heterogeneous. In contrast, when using de-jitter buffers for packet scheduling, path selection benefits from low latency links without degrading anonymity. Consequently, acceptable end-to-end latency is possible for a large majority of calls.

Communication metadata may leak sensitive information even when content is encrypted, e.g. when contacting medical services. Unfortunately, protecting metadata is challenging. Existing approaches for anonymous communications either are vulnerable in a strong (but feasible) threat model or have practicability issues like intense usage of asymmetric cryptography. We propose Hydra, a mix network that is able to provide multiple anonymous services in a uniform way. In contrast to previous messaging systems with strong anonymity, we deliberately use padded onion-encrypted circuits. This allows to support connectionless applications like contact discovery with authenticated key exchange, messaging, and dialing (signalling for connection-oriented communications) with strong anonymity and relatively low latency. Our cryptography benchmarks show that Hydra is able to process messages an order of magnitude faster than state of the art messaging systems with strong anonymity. At the same time, bandwidth overhead is comparable to previous systems. We further develop an analytical model to predict the end-to-end latency of Hydra and validate it in a testbed.

To support position-dependent services, like matchmaking algorithms for online games or geographic backup routes, the estimation of peer locations became a key requisite for a range of applications, recently. However, exact localization may be impossible, e.g., due to nodes lacking Global Positioning System (GPS) access for reasons of cost, energy, or signal unavailability. Alternative approaches, e.g., by nearby WLAN BSSIDs or IP geolocation, rely on databases and normally contain large outliers, in particular when concerning underrepresented mapping locations. This led us to the study of a complementary idea: By embedding nodes on a sphere and periodically minimizing local positioning errors by delay-based multilateration, we efficiently estimate node positions by distributed means, given a fair amount of position hints. Based on simulations that rely on real-world PlanetLab latency data, we show that global-scope peer locations can be estimated with an accuracy of a few hundred kilometers, where the novel approach outperforms a previously proposed spring-mass-based method by about 50%.