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