Distributed Brute-Force Attacks: Synchronization is Expandable, but Coordination is Worthwhile!

: In September 2017, McAffee Labs quartely 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 risk assessment of password-secured systems. While simple solution exist to prevent online brute-force attacks that arise from a single IP address, it is harder to deal with attacks performed by botnets.

In this talk, we analyze these distributed attacks under an information theoretic framework. Our aim is to understand the impact of distribution and asynchronization on the overall computational effort necessary to breach a system. As a surrogate for this computational effort we use the Guesswork, a measure for the number of password queries (guesses) before the correct one is found. We first model the lack of synchronization by a worst-case optimization in which the queries are received in the worst possible order, 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. We then study the impact of coordination between the Bots when independent sources of side- information are available to them (e.g., passwords for other services). Contrary to the case where no side -information is available, we show that coordination reduces the guesswork exponentially. In other words, pooling of the side-information, and joint-optimization of the next guess in a centralized manner, results in much better performance compared to the decentralized approach in which the side-information are never shared among the agents.

Joint work with Salman Salamatian, Wasim Huleihel, Ahmad Beirami and Muriel Me ́dard.