| Title | Universal Randomized Guessing with Application to Asynchronous Decentralized Brute—Force Attacks |
| Publication Type | Conference Paper |
| Year of Publication | 2019 |
| Authors | Merhav, Neri, Cohen, Asaf |
| Conference Name | 2019 IEEE International Symposium on Information Theory (ISIT) |
| Date Published | jul |
| Keywords | asynchronous 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 |
| Abstract | Consider 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. |
| DOI | 10.1109/ISIT.2019.8849716 |
| Citation Key | merhav_universal_2019 |
Universal Randomized Guessing with Application to Asynchronous Decentralized Brute—Force Attacks