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

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

TL;DR

Botnets don't need to coordinate to be efficient. This paper proves that uncoordinated, asynchronous attackers can perform brute-force attacks just as effectively as perfectly synchronized ones by using a specific randomized guessing strategy based on "tilted" probability distributions.

What Problem Does This Paper Address?

Brute-force attacks—trying every possible password until one works—account for a massive portion of network security threats. To defend against them, many systems implement rate-limiting or IP blocking. Attackers bypass this using botnets: thousands or millions of compromised computers, each making a small number of guesses to stay under the radar.

The traditional assumption is that for a botnet to be efficient, the bots must be synchronized (e.g., Bot A tries passwords 1-100, Bot B tries 101-200). Without synchronization, bots might repeat the same guesses, wasting computational effort. This paper investigates the "synchronization gap": how much does the lack of coordination actually hurt an attacker, and can they overcome it?

Methods

The authors use a mathematical framework called Guesswork, which measures the number of attempts required to find a secret. They model the lack of synchronization as a min-max problem: the attacker wants to find a guessing strategy that performs well even if the guesses from various bots arrive at the target server in the "worst possible order."

The core of their approach is moving away from deterministic lists (where every bot tries the same "top 100" passwords) to randomized strategies. Instead of following a fixed list, each bot draws guesses independently from a specific probability distribution.

The researchers leverage tools from information theory, specifically Rényi entropy and Large Deviation Theory, to find the optimal distribution for these randomized guesses.

Datasets

The paper evaluates its theoretical findings using a subset of the Adobe Leaked password dataset.

  • They extracted the $10^4$ most likely passwords from a pool of 10 million.
  • They used this data to calculate the "true" distribution of passwords ($P_X$) and then compared how different randomized guessing strategies performed against it.

Key Insights and Ideas

  • The "Tilted" Distribution: Surprisingly, the best way to guess a password isn't to guess according to its natural probability. If a password has a distribution $P_X$, the optimal guessing distribution is a "tilted" version: $P_X^{1/(1+\rho)}$. This tilt gives more weight to less-likely passwords than the original distribution does, which minimizes the "heavy tail" of the guesswork.
  • Asynchrony is "Free": The most significant finding is that, asymptotically (as password length increases), the performance of asynchronous guessers matches that of synchronized ones. Randomization acts as an implicit coordination mechanism.
  • Randomization is Key: Deterministic strategies fail in asynchronous settings because they lead to massive overlaps in guesses. By simply rolling the dice on each guess using the "tilted" distribution, bots naturally avoid each other's work enough to remain efficient.
  • Loss of Universality: In a synchronized attack, one list is optimal for all scenarios. In an asynchronous attack, the "optimal" distribution depends on what you are trying to minimize (e.g., the average number of guesses vs. the probability of success within a fixed time).

Key Results

  • Theorem 1: Proves that the exponential growth rate of the total number of guesses in an asynchronous attack is identical to the synchronized case, provided the bots use the optimal tilted distribution.
  • Adobe Dataset Performance: Using the "naive" distribution ($P_X$) resulted in a log-expected number of guesses of 9.2. Switching to the optimal "tilted" distribution reduced this to 8.8.
  • Success Probability: The paper shows that even with a fixed "budget" of guesses (a constraint on the number of attempts), asynchronous attackers can achieve the same success exponent as synchronized ones.

Limitations and Future Work

  • I.I.D. Assumption: The primary model assumes password characters are independent and identically distributed (i.i.d.). While they briefly discuss extensions to Markov Chains, real-world password structures are often more complex.
  • Knowledge of Distribution: The model assumes the attacker knows the underlying distribution of passwords ($P_X$). In reality, attackers estimate this from leaked databases, which may be biased.
  • Targeted vs. Multi-user: The paper focuses on a "targeted" attack (cracking one specific account). The authors suggest that future work should look at "multi-user" attacks, where a botnet tries to breach any $U$ accounts out of a total $V$, which introduces new trade-offs in round-robin guessing strategies.

Summary updated

Abstract

In September 2017, the McAfee 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) 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 the 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 the 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},
}

Loading related content...

Figure