Visible to the public Universal Randomized Guessing with Application to Asynchronous Decentralized Brute—Force Attacks

TitleUniversal Randomized Guessing with Application to Asynchronous Decentralized Brute—Force Attacks
Publication TypeConference Paper
Year of Publication2019
AuthorsMerhav, Neri, Cohen, Asaf
Conference Name2019 IEEE International Symposium on Information Theory (ISIT)
Date Publishedjul
Keywordsasynchronous decentralized brute - force attacks, Botnet, brute force attacks, brute-force attack, computer network security, Decoding, Entropy, guesswork moment, human factors, invasive software, memoryless systems, password, policy-based governance, pubcrawl, query processing, Random variables, source coding, Tools, universal decentralized guessing strategies, universal distribution, universal randomized guessing, Vectors
AbstractConsider the problem of guessing a random vector X by submitting queries (guesses) of the form "Is X equal to x?" until an affirmative answer is obtained. A key figure of merit is the number of queries required until the right vector is guessed, termed the guesswork. The goal is to devise a guessing strategy which minimizes a certain guesswork moment. We study a universal, decentralized scenario where the guesser does not know the distribution of X, and is not allowed to prepare a list of words to be guessed in advance, or to remember its past guesses. Such a scenario is useful, for example, if bots within a Botnet carry out a brute-force attack to guess a password or decrypt a message, yet cannot coordinate the guesses or even know how many bots actually participate in the attack. We devise universal decentralized guessing strategies, first, for memoryless sources, and then generalize them to finite-state sources. For both, we derive the guessing exponent and prove its asymptotic optimality by deriving a matching converse. The strategies are based on randomized guessing using a universal distribution. We also extend the results to guessing with side information (SI). Finally, we design simple algorithms for sampling from the universal distributions.
Citation Keymerhav_universal_2019