Title: The count-min sketch is vulnerable to offline password-guessing attacks

Authors: Jaryn Shen; Qingkai Zeng

Addresses: State Key Laboratory for Novel Software Technology, Nanjing University, Nanjing 210023, China; Department of Computer Science and Technology, Nanjing University, Nanjing 210023, China ' State Key Laboratory for Novel Software Technology, Nanjing University, Nanjing 210023, China; Department of Computer Science and Technology, Nanjing University, Nanjing 210023, China

Abstract: The count-min sketch is used to prevent users from selecting popular passwords so as to increase password-guessing attackers' cost and difficulty. This approach was proposed by Schechter et al. (2010) at USENIX Conference on Hot Topics in Security in 2010. Schechter et al. (2010) originally intended the count-min sketch to resist password-guessing attacks. In this paper, however, for the first time, we point out that the count-min sketch is vulnerable to offline password-guessing attacks. Taking no account of the false positive rate, the offline password-guessing attack against the count-min sketch and the password file requires less computational cost than the benchmark attack against only the password file. Taking the false positive into account, in order to eliminate the threat to quicken password-guessing rate, the lower bound of the false positive rate must be greater than 33% in the naked count-min sketch and greater than 31% in the expensive count-min sketch, both of which are too high and unacceptable.

Keywords: password; guess; offline attacks; count-min sketch; password file; false positive; authentication.

DOI: 10.1504/IJICS.2022.122912

International Journal of Information and Computer Security, 2022 Vol.18 No.1/2, pp.27 - 39

Received: 02 Feb 2019
Accepted: 26 Aug 2019
Published online: 17 May 2022 *

Full-text access for editors Full-text access for subscribers Purchase this article Comment on this article