A MODEL OF COMPUTATIONAL COMPLEXITY AND EFFECTIVENESS OF PASSWORD-GUESSING ATTACKS USING OSINT AND LARGE LANGUAGE MODELS
TL;DR
This paper examines modern attack vectors against password systems in a context where attempt limits have rendered brute-force attacks ineffective, while open generative models and open-source intelligence tools have made targeted, user-specific password guessing more cost-effective.
Abstract
This paper examines modern attack vectors against password systems in a context where attempt limits have rendered brute-force attacks ineffective, while open generative models and open-source intelligence (OSINT) tools have made targeted, user-specific password guessing more cost-effective. It is shown that existing performance metrics (the proportion of compromised accounts, time to first hit, and theoretical polynomial complexity) cannot be reduced to a common scale. Consequently, methods of different natures cannot be quantitatively compared. A computational complexity model in which the cost of an attack is represented as the product of the hit position in the dictionary and the duration of a single hashing operation was proposed. The model is specified for five classes of attacks: brute-force, corpus-based, statistical (Markov chain-based), combinatorial (OSINT-based), and generative (large language model-based). An efficiency parameter is introduced as the ratio of the empirical probability of success to the computational complexity, supplemented by an estimate of the cost of a failed dictionary run. The parameter's structure separates the influence of the dictionary, which acts through the match position, from that of the storage algorithm, which acts as a common scaling factor. Experimental validation was performed on benchmark profile passwords using four dictionaries and the MD5, SHA-256, bcrypt, and Argon2id algorithms. A combinatorial OSINT dictionary, 57 times smaller than the RockYou million-sample dataset, compromised 66.7% of the passwords. The corpus and Markov dictionaries did not yield a single exact match. The generative dictionary had a lower success probability (3.3%) but found the password at the 232nd position. Its effectiveness was approximately 3.5 times that of the combinatorial dictionary, and this advantage is not apparent when comparing the compromise rates themselves. Switching to slower algorithms reduces the effectiveness of all attacks by approximately six orders of magnitude without changing their relative order. Based on the results, a layered system of protective measures is proposed, ranked by their measured impact on security.