Why Botnets Work: Distributed Brute-Force Attacks Need No Synchronization

Salman Salamatian, Wasim Huleihel, Ahmad Beirami, Asaf Cohen, Muriel Médard

Abstract

In September 2017, McAfee Labs reported that brute force attacks represent 20% of total network attacks, making them as prevalent as browser-based vulnerabilities. Understanding the fundamental limits of these attacks is crucial for risk assessment and the design of secure protocols. While single-IP attacks can be mitigated by rate-limiting, distributed attacks via botnets are more challenging. This paper analyzes distributed attacks using a simplified model to understand the impact of asynchronization on computational effort. Using "Guesswork" as a metric, we model uncoordinated attacks as a min-max optimization problem. We demonstrate that for sequences of growing length, asynchronous guessers can achieve optimal performance—matching synchronized guessers—by using randomized guesses drawn from a specific "tilted" probability distribution.

Introduction

Brute-force attacks—the systematic attempt to guess a password or secret—remain a primary threat to network security. To defend against these, systems often implement IP-based blocking or rate-limiting. Attackers circumvent these defenses using botnets: vast networks of compromised devices that each contribute a small number of guesses to avoid detection.

The Synchronization Problem

A common assumption in cybersecurity is that for a botnet to be efficient, its nodes must be synchronized. In a synchronized attack, bots coordinate to ensure they do not repeat the same guesses. Without this coordination, the "synchronization gap" suggests that bots will overlap in their work, wasting computational resources.

Comparison between synchronized (left) and asynchronous (right) botnet guessing strategies.

This research investigates whether this gap is a fundamental limitation or if uncoordinated attackers can overcome it through strategic randomization.

Methodology: Guesswork and Randomization

The study utilizes the mathematical framework of Guesswork, which measures the number of attempts required to find a secret. To address the lack of coordination, the authors formulate a min-max problem: finding a guessing strategy that remains effective even if the server receives guesses in the worst possible order for the attacker.

The core innovation is the move from deterministic lists to randomized strategies. Instead of every bot following the same top-password list, each bot independently draws guesses from a probability distribution. Using information theory and Rényi entropy, the researchers identified an optimal "tilted" distribution: $P_X^{1/(1+\rho)}$. This distribution assigns more weight to less-likely passwords than the natural distribution ($P_X$) does, which minimizes the "heavy tail" of the guesswork process.

Key Results and Insights

  • Asynchrony is "Free": The most significant finding is that, asymptotically, the performance of asynchronous guessers matches that of synchronized ones. Randomization acts as an implicit coordination mechanism, allowing bots to naturally avoid excessive overlap without direct communication.
  • The Tilted Advantage: Testing against the Adobe Leaked password dataset (using the $10^4$ most likely passwords), the researchers found that the optimal tilted distribution reduced the log-expected number of guesses from 9.2 (using the naive distribution) to 8.8.
  • Success Probability: Even with a fixed budget of guesses, asynchronous attackers can achieve the same success exponent as synchronized ones, provided they use the correct randomized strategy.

Limitations and Future Directions

While the model provides a powerful theoretical foundation, it currently relies on the assumption that password characters are independent and identically distributed (i.e.i.d.). Real-world passwords often follow more complex structures. Additionally, the model assumes attackers have accurate knowledge of the underlying password distribution, which is typically estimated from leaked databases. Future work will explore multi-user attacks, where botnets attempt to breach any subset of accounts within a larger pool, introducing new trade-offs in guessing strategies.

Conclusion

This research proves that botnets do not require complex synchronization to be highly efficient. By employing randomized guessing from a tilted distribution, distributed attackers can perform brute-force attacks just as effectively as perfectly coordinated networks. This highlights the ongoing need for robust, non-IP-based defense mechanisms in modern security architectures.

Summary updated

Abstract

In September 2017, McAffee Labs quarterly report estimated that brute force attacks represent 20\% of total network attacks, making them the most prevalent type of attack ex-aequo with browser based vulnerabilities. These attacks have sometimes catastrophic consequences, and understanding their fundamental limits may play an important role in the risk assessment of password-secured systems, and in the design of better security protocols. While some solutions exist to prevent online brute-force attacks that arise from one single IP address, attacks performed by botnets are more challenging. In this paper, we analyze these distributed attacks by using a simplified model. Our aim is to understand the impact of distribution and asynchronization on the overall computational effort necessary to breach a system. Our result is based on Guesswork, a measure of the number of queries (guesses) required of an adversary before a correct sequence, such as a password, is found in an optimal attack. Guesswork is a direct surrogate for time and computational effort of guessing a sequence from a set of sequences with associated likelihoods. We model the lack of synchronization by a worst-case optimization in which the queries made by multiple adversarial agents are received in the worst possible order for the adversary, resulting in a min-max formulation. We show that, even without synchronization, and for sequences of growing length, the asymptotic optimal performance is achievable by using randomized guesses drawn from an appropriate distribution. Therefore, randomization is key for distributed asynchronous attacks. In other words, asynchronous guessers can asymptotically perform brute-force attacks as efficiently as synchronized guessers.
BibTeX
@article{salamatian2019why,
  author = {Salman Salamatian and Wasim Huleihel and Ahmad Beirami and Asaf Cohen and Muriel Médard},
  title = {{Why Botnets Work: Distributed Brute-Force Attacks Need No Synchronization}},
  journal = {IEEE Trans. Inf. Forensics Secur.},
  year = {2019},
  url = {https://openreview.net/forum?id=PsKEoIGFqN},
}
Figure